Модели вычислений

Лектор - профессор Захаров Владимир Анатольевич.

Программа курса

Конечные автоматы и регулярные выражения

1. Формальные языки. Операции над языками. Проблемы принадлежности слова языку, пустоты, тотальности, равенства, включения.
2. Недетерминированные конечные автоматы. Вычисления автоматов. Автоматные языки.
3. Детерминированные конечные автоматы. Эквивалентные состояния и эквивалентные автоматы. Алгоритм проверки эквивалентности детерминированных конечных автоматов.
4. Минимальные детерминированные конечные автоматы. Теорема о существовании и единственности минимального детерминированного конечного автомата. Алгоритм минимизации детерминированных конечных автоматов.
5. Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками.
6. Теорема о разрастании для автоматных языков. Примеры неавтоматных языков.
7. Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами.
8. Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик.
9. Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.

Машины Тьюринга и рекурсивно перечислимые языки

10. Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки.
11. Моделирование односторонних и многоленточных машин Тьюринга одноленточными машинами Тьюринга.
12. Арифметические функции, вычислимые по Тьюрингу. Характеристические теоремы для рекурсивных и рекурсивно-перечислимых языки.
13. Массовые алгоритмические проблемы и их связь с рекурсивными языками
14. Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга.
15. Сводимость алгоритмических проблем. Примеры алгоритмически неразрешимых проблем программирования.
16. Функциональные (семантические) свойства программ. Теорема Райса.
17. Замкнутость классов рекурсивных и рекурсивно перечислимых языков относительно теоретико-множественных операций.
18. Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста.
19. Многоголовочные конечные автоматы. Алгоритмическая неразрешимость проблемы останова для многоголовочных конечных автоматов.
20. Ассоциативные исчисления. Алгоритмическая неразрешимость проблемы достижимости для полусистем Туэ.
21. Примеры алгоритмически неразрешимых проблем математики: проблема разрешимости диофантовых уравнений, проблема мозаики. Машины Минского. Универсальность модели вычислений машин Минского.

Формальные грамматики и языки

17. Формальные грамматики: основные понятия. Классификация Хомского формальных грамматик (иерархия Хомского).
18. Праволинейные грамматики и языки. Совпадением класса праволинейных языков и класса автоматных языков. Разрешимость проблем принадлежности и эквивалентности для класса праволинейных языков.
19. Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся автоматными.
20. Контекстно-свободные грамматики и языки. Примеры контекстно-свободных языков. Замкнутость класса контекстно-свободных языков относительно операции объединения. Разрешимость проблемы принадлежности для контекстно-свободных языков.
21. Нормальная форма Хомского для контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
22. Теорема о разрастании (лемма о накачке) для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными.
23. Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью.
24. Алгоритм Кока-Янгера-Касами синтаксического анализа контекстно-свободных языков.
25. Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения.
26. Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков.
27. Грамматики типа 0 и рекурсивно-перечислимые языки.

Алгоритмически неразрешимые математические задачи

28. Проблема соответствий Поста. Теорема об алгоритмической неразрешимости проблемы соответствий Поста.
29. Алгоритмическая неразрешимость проблемы непустоты пересечения, проблемы тотальности и проблемы эквивалентности для контекстно-свободных грамматик.
30. Примеры алгоритмически неразрешимых проблем арифметики, алгебры, комбинаторики.

Литература

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. - М.: Мир, 1978. - 612 с.
2. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: Вильямс, 2001. - 768 с.
3. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. - М.: МЦНМО, 1999. - 176 с.
4. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир, 1983.
5. Льюис Ф., Розенкранц Д, Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.. - 656 с.
6. Матрос Д.Ш., Поднебесова Г.Б. Теория алгоритмов. - М.: Бином, 2008. - 200 с.
7. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. Серия "Основы информатики и математики" - М: Бином, 2006. - 247 с.
8. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.
9. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. - М.: Вильямс, 2002. - 528 с.

Правила проведения экзамена

Экзамен проводится в форме письменной контрольной работы. Время, отведенное на решение задач, составляет 120 мин. Письменная контрольная работа состоит из 10 заданий.

Задания 1-4 - это задачи требующие применения стандартных алгоритмов и методов решения. Правильное решение каждой такой задачи оценивается 2 баллами.

В заданиях 5-8 требуется сформулировать определения основных понятий, введенных в лекционном курсе. Правильное решение каждой такой задачи оценивается 1 баллом.

В задании 9 требуется сформулировать и доказать одну из теорем, рассмотренных в лекционном курсе. Правильное решение каждой такой задачи оценивается 2 баллами.

В задании 10 требуется решить теоретическую задачу, опираясь на сведения, представленные в лекционном курсе. Правильное решение каждой такой задачи оценивается 3 баллами.

Оценка контрольной работы проводится по следующим критериям:

14-17 баллов - отлично,

10-15 баллов - отлично,

7-9 баллов - удовлетворительно.