1626435674-2aa2204d71b92fca39a62b0a540076af (844294), страница 2
Текст из файла (страница 2)
Понятиеметаинтерпретатора иавтоинтерпретатора, критерийоптимальности Джонса. Другиепотенциальные применения СВ.4.2 Пример функции xn.3Интерпретационный подход креализации СВ. Понятиегенерирующего расширения, какобъектного кода для семантики,заданной СВ, Трансформационныйподход.4.3 Проблема задержанного управления 3при СВ, Поливариантные СВ,Пример интерпретатора конечныхавтоматов. Методы улучшенияспециализируемости программ.Построение транслятора конечныхавтоматов.4.4 Понятие анализа периода3связывания (BTA).
Сведение задачиBTA к ЗГА, Решение BTA методомнахождения неподвижной точки.Решение BTA методом решениясистемы неравенств. Понятиеполивариантного анализа периодасвязывания: преобразованиепрограммы в процессе анализа.316222172221822236 Экзамен1936 34 362363. Учебно-методические материалы дисциплиныа) основная литература:1.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.– М.: Издательский дом “Вильямс”, 2000.2. Бульонков М.А. Смешанные вычисления. Учебное пособие. – Новосибирск: Изд-воНГУ, 1995.3. Карпов Ю. Теория автоматов. Учебник для вузов. – СПб.: Издательский домПитер, 2002.4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ: Пер.
с англ. –М.: МЦНМО, 1999.5. Котов В.Е. Введение в теорию схем программ. – М.: Наука, 1978.6. Котов В.Е., Сабельфельд В.К. Теория схем программ. – М.: Наука, 1991.7. Лавров С. Программирование. Математические основы, средства, теория. –СПб.: БХВ-Петербург, 2001.8. Мотвани Р., Хопкрофт Дж., Ульман Дж. Введение в теорию автоматов, языков ивычислений: Пер.
с англ, 2-е издание. – М.: Издательский дом “Вильямс”, 2002.9. Сабельфельд В.К. Теория программирования. Учебное пособие. – Новосибирск:Изд-во НГУ, 1993.10. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity.Volume B: Formal Models and Semantics / Edited by J. van Leeuwen.
– Cambridge,MA: The MIT Press and – Amsterdam, New York, Oxford, Tokyo: Elsevier, 1996.б) дополнительная литература:1. Ахо А., Сети Р., Ульман Дж.Д. Компиляторы: принципы, технологии иинструменты: Пер. с англ. – М.: Издательский дом “Вильямс”, 2001.2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительныхалгоритмов: Пер. с англ. – М.: Мир, 1979.3. Барендрегт X. Ламбда-исчисление. Его синтаксис и семантика: Пер.
с англ. – М.:Мир, 1985.4. Биркгоф Г. Теория решеток: Пер. с англ. – М.: Наука, 1984.5. Грин Д., Кнут Д. Математические методы анализа алгоритмов: Пер. с англ. – М.:Мир, 1987.6. Ершов А.П. Введение в теоретическое программирование (беседы о методе). – М.:Наука, 1977.7. Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложностивычислений. Учебное пособие. – Новосибирск: Изд-во НГУ, 1995.8.
Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ. –М.: Мир, 1983.9. Кнут Д. Искусство программирования: Пер. с англ. – М., СПб, Киев: Вильямс,2000. – Т. 1-3.10. Трахтенброт Б.А. Сложность алгоритмов и вычислений. – Новосибирск: Изд-воНГУ, 1967.11. Hehnera E.C.R.
A Practical Theory of Programming. Second Edition. – Toronto:University of Toronto, 2004. – url: www.cs.utoronto.ca/~hehner/aPToP.4. Контроль изучения дисциплиныа) Вопросы для экзамена1. Машина Тьюринга. Конфигурация, протокол, временная и емкостная сложности.Моделирование машины Тьюринга на РАМ.2. РАМ. Конфигурация, протокол, временная и емкостная сложности. Равномерный илогарифмический весовые критерии.
Моделирование машины Тьюринга на РАМ.3. Моделирование вычислений. Моделирование РАМ на машине Тьюринга.4. Теорема об ускорении.5. Теорема о существовании сколь угодно сложных функций (диагональ Рабина).6. Теорема о нижней оценке количества умножений для вычисления Mx+y7. Конечные автоматы и регулярные выражения. Теорема об эквивалентностиконечно-автоматных и регулярных языков.8. Распознавание пустоты и эквивалентности конечных автоматов.9.
Задача поиска в информационном массиве. Деревья поиска, 2-3 деревья. Оценкисложности.10. Задача поиска в информационном массиве. АВЛ-деревья. Оценки сложности.11. Задача поиска в информационном массиве. Таблицы расстановки. Оценкисложности.12. Сортировка массивов. Классификация алгоритмов. Быстрая сортировка. Оценкасложности.13. Теоремы о сложности в среднем и в худшем сортировки, основанной насравнениях.14.
Задача анализа свойств графа методом разметки. Существование, единственность ибезопасность стационарной разметки.15. Задача анализа свойств графа методом разметки. Возможность построения точногорешения.16. Понятие стандартной схемы. Интерпретация, функциональная эквивалетность.17. Понятие стандартной схемы. Определение логико-термальной эквивалентности.18. Функциональные сети для представления множества утверждений.
Полурешетка.19. Система преобразований Sлт. Полнота и корректность.20. Рекурсивные схемы. Невозможность трансляции рекурсивных схем в стандартные.21. Рекурсивные схемы. Алгоритм трансляции стандартных схем в рекурсивныесхемы.22. Многоленточные и многоголовочные конечные автоматы. Проблемы пустоты иэквивалентности.23. Оптимальные деревья двоичного поиска24. Порядковые статистики25.
Древовидные структуры для задачи ОБЪЕДИНИТЬ-НАЙТИ.26. Определение смешанных вычислений. Проекции Футамуры.27. Интерпретативный, трансляционный и трансформационный подходы к смешаннымвычислениям28. Поливариантные смешанные вычисления.29. Анализ периода связывания как ЗГА. Поливариантный анализ периода связывания.б) Примеры задач, решаемых на занятиях.1. Написать РАМ-программу для извлечения целой части корня квадратного изнатурального числа без использования умножения и со сложностью O(√n).2. В первой ячейке на входной ленте одноадресной РАМ машины задана размерностьквадратной матрицы, а затем сама матрица по строкам.
Написать программу,которая выводит на выходную ленту нечётные элементы побочной диагоналиматрицы. Например, для входной последовательности23478результатом должно быть 4.3. По данной РАМ машине построить РАМ машину, которая не использует ячейки сномерами с 1 по 10.4. Являются ли классы машин Тьюринга с произвольным и бинарным алфавитамиэквивалентными.5. Промоделировать на РАМ машине машину Тьюринга.6. МоделированиенаРАМ-машинеарифметическогопереходаспомощьюлогического и наоборот.7. Построить регулярные выражения и конечные автоматы для следующих множеств:a. идентификаторы Фортрана;b.
идентификаторы С.8. Построить регулярное выражение и конечный автомат для множества цепочек изнулей и единиц, состоящих из четного числа нулей и четного числа единиц.9. Доказать или опровергнуть два следующих утверждения: а) конечные автоматымогут складывать произвольные двоичные числа; б) конечные автоматы могутумножать произвольные двоичные числа. Входом автомата является цепочка вкоторой нечетные символы представляют биты первого числа, четные - второго.Выход – двоичная цепочка, являющаяся результатом. На любом такте работыавтомата, в выход может быть записан либо один двоичный либо один пустойсимвол.10. Доказательство теоремы Клини о замкнутости класса регулярных языковотносительно операций объединения, пересечения, дополнения и конкатенации.11.
Является ли 2-скобочный язык Дика (язык всевозможных правильных скобочныхцепочек, где скобками являются {} и []) регулярным.12. Оценка времени поиска в худшем в сбалансированных по высоте деревьях.13. Пострить алгоритм потокового анализа, вычисляющего для всякой вершины графауправления программы множество всех вершин графа, достижимых из этойвершины.14. Стандартная схема задана в операторной форме:start(x)y:=x1: if p(x) then goto 2x:=f(x)goto 12: if q(y,x) then goto 4if q(y,x) then goto 3goto 53: y:=f(y)goto 24: if q(y,x) then goto 5goto 35: stop(x)Требуется построить для всех дуг инвариантные соотношения равенства термов.15.
Для заданных множеств равенств термов (необязательно транзитивно замкнутыхотносительно отношения равенства) построить замкнутое множество равенствтермов, которое содержит те, и только те, равества из исходных множеств, которыеимеются в обоих множествах. Множество A = { y=f(z)=g(z,a)=g(z,x), z=f(a), x=a }.Множество B = { f(x)=g(y,a)=f(y), x=y=f(z)=f(f(x)), z=a=f(x) }.16. Для заданного недетерминированного конечного автомата над алфавитом {a,b}построить эквивалентный детерминированный автомат:1a -> 11a -> 21b -> 12a -> 32b -> 33a -> 23a -> 33b -> 1Начальное состояние - 1, конечное - 2.17.
По заданному конечному автомату построить реглярное выражение, описывающеемножество цепочек, допускаемых этим автоматом:1a -> 21b -> 31c -> 12a -> a2b -> 12c -> 43a -> 43b -> 43c -> 44a -> 34b -> 44c -> 4Начальное состояние - 1, конечные - 3, 4.18. По заданному регулярному выражению над алфавитом {a,b,c} построить конечныйавтомат без эпсилон-переходов, допускающий множество цепочек, описываемыхданным регулярным выражением:((ab+aac)*)(bac+bcc+(bac+bcc)*)(cab+cba+abc).19. Расширим РАМ машину командами со стеком:a. PUSH - добавляет в стек значение сумматораb.
POP – выталкивает значение из стека, засылая его в сумматорc. EMPTY – засылает в сумматор 1, если стек пуст, 0 – иначе.Стек бесконечный, находится вне основной памяти. Доказать, что стековую РАМмашину можно моделировать на РАМ машине без стека..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
