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

Обязательный курс для студентов 418 группы на 8 семестре обучения.

Лекционная нагрузка — 24 ч., семинары — 8 ч.

Курс читает профессор В. А. Захаров.

ПЛАН ЗАНЯТИЙ В ПЕРИОД 16.03 - 20.03

1. Слушатели курса прочитывают слайды лекции 7 и решают задачи, приложенные к этой лекции, в любое удобное для них время 17.03 -- 19.03
2. 20.03 с 10.30 до 12.00 преподаватель готов ответить на вопросы по материалам курса по skype (login: vladimir_zakharov_msu) и по WhatsApp (916 220 44 24)
3. C 12.00 до 20.00 слушатели присылают по электронной почте преподавателю решения задач 3 и 4.3 из списка задач, приложенных к лекции.

Лекции

Лекция 1. Формальные языки. Операции над языками.Разнообразие моделей вычислений. Конечные автоматы Рабина-Скотта. Автоматные языки. Упрощение конечных автоматов. Детерминированные конечные автоматы. Минимизация детерминированных конечных автоматов.

Лекция 2. Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками. Теорема о разрастании для автоматных языков. Примеры неавтоматных языков.

Лекция 3. Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами. Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик. Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.

Лекция 4. Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки. Моделирование односторонних и многоленточных машин Тьюринга одноленточными машинами Тьюринга. Арифметические функции, вычислимые по Тьюрингу. Характеристические теоремы для рекурсивных и рекурсивно-перечислимых языки. Массовые алгоритмические проблемы и их связь с рекурсивными языками. Замкнутость классов рекурсивных и рекурсивно перечислимых языков относительно теоретико-множественных операций.

Лекция 5. Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем. Примеры алгоритмически неразрешимых проблем программирования. Функциональные (семантические) свойства программ. Теорема Райса.

Лекция 6. Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста. Многоголовочные конечные автоматы. Алгоритмическая неразрешимость проблемы останова для многоголовочных конечных автоматов. Ассоциативные исчисления. Алгоритмическая неразрешимость проблемы достижимости для полусистем Туэ. Примеры алгоритмически неразрешимых проблем математики: проблема разрешимости диофантовых уравнений, проблема мозаики. Машины Минского. Универсальность модели вычислений машин Минского.

Лекция 7. Формальные грамматики. Классификация формальных грамматик. Иерархия Хомского формальных языков. Неограниченные грамматики и рекурсивно перечислимые языки. Праволинейные грамматики. Совпадение класса автоматных языков и класса праволинейных языков. Контекстно-свободные грамматики. Устранение недостижимых и ε-правил. Нормальная форма Хомского контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.

Задачи по теме Лекции 7.

Лекция 8. Деревья синтаксического разбора. Теорема о разрастании для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными. Автоматы с магазинной памятью и их свойства. Взаимосвязь контекстно-свободных языков и автоматов с магазинной памятью. Детерминированные магазинные автоматы.

Лекция 9. Свойства замкнутости контекстно-свободных языков. Алгоритмические проблемы для КС-языков. Неразрешимость проблемы эквивалентности для контекстно-свободных грамматик. Алгоритм Кока-Касами-Янгера синтаксического анализа контекстно-свободных языков. Детерминированные КС-языки и синтаксические анализаторы. LL(k)-грамматики. Контекстно-зависимые грамматики.

Лекция 10. Конечные автоматы-преобразователи. Рациональные отношения и их свойства. Описание рациональных отношений регулярными выражениями. Свойства замкнутости класса рациональных отношений. Неразрешимость проблемы эквивалентности для недетерминированных автоматов-преобразователей. Разрешимость проблемы эквивалентности для детерминированных автоматов-преобразователей.

Лекция 11. Реагирующие системы вычислений. Автоматы Бюхи. ω-регулярные языки. Свойства замкнутости класса ω-регулярных языков. Алгоритмические проблемы для автоматов Бюхи. Другие виды ω-автоматов: автоматы Рабина, автоматы Маллера. Взаимосвязь детерминированных и недетерминированных ω-автоматов. Применение ω-автоматов для верификации реагирующих систем.

Лекция 12. Логический способ описания языков. Монадическая предикатов логика второго порядка S1S. Взаимосвязь логики S1S и ω-автоматов. Другие логики предикатов второго порядка.

Семинарские занятия

Семинар 1. Построение конечных автоматов для заданных языков. Преобразование недетерминированных автоматов к детерминированным. Минимизация детерминированных автоматов. Распознавание автоматности языков, полученных при помощи теоретико-множественных и алгебраических операций над автоматными языками. Доказательство неавтоматности языков. Построение регулярных выражений для автоматных языков. Построение автоматов, соответствующих регулярным выражениям.

Семинар 2. Доказательство нерекурсивности и рекурсивной перечислимости языков. Использование метода сводимости для доказательства алгоритмической неразрешимости массовых проблем.

Семинар 3. Построение контекстно-свободных грамматик и магазинных автоматов. Приведение контекстно-свободных грамматик к нормальной форме Хомского. Применение алгоритма Кока-Касами-Янгера для проверки принадлежности заданного слова заданному контекстно-свободному языку. Применение теорем о разрастании для классификации языков.

Семинар 4. Построение конечных автоматов-преобразователей, распознающих заданные рациональные отношения. Построение автоматов Бюхи и формул логики S1S, задающих регулярные omega-языки.

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

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

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

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

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

Контекстно-свободные языки и автоматы с магазинной памятью

22. Формальные грамматики. Классификация формальных грамматик. Иерархия Хомского формальных языков.
23. Праволинейные грамматики. Совпадение класса автоматных языков и класса праволинейных языков.
24. Неограниченные грамматики и рекурсивно перечислимые языки.
25. Контекстно-свободные грамматики. Устранение недостижимых и ε-правил. Нормальная форма Хомского контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
26. Деревья синтаксического разбора. Теорема о разрастании для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными.
27. Автоматы с магазинной памятью и их свойства. Взаимосвязь контекстно-свободных языков и автоматов с магазинной памятью.
28. Теоремы о замкнутости и незамкнутости класса контекстно-свободных языков относительно операций над формальными языками. Алгоритм проверки пустоты для контекстно-свободных грамматик.
29. Алгоритмическая неразрешимость проблем эквивалентности и тотальности для контекстно-свободных грамматик.
30. Задача синтаксического анализа. Алгоритм Кока-Касами-Янгера проверки принадлежности слова контекстно-свободному языку. Детерминированные автоматы с магазинной памятью и LL(1) грамматики.
31. Контекстно-зависимые грамматики. Взаимосвязь контекстно-зависимых грамматик и машин Тьюринга с линейно-ограниченной памятью.

Автоматы над бесконечными словами и темпоральные логики

32. Конечные автоматы-преобразователи (трансдьюсеры) и рациональные отношения. Детерминированные трансдьюсеры.
33. Свойства замкнутости класса рациональных отношений.
34. Алгоритм проверки эквивалентности детерминированных трансдьюсеров.
35. Алгоритмическая неразрешимость проблемы эквивалентности недетерминированных трансдьюсеров.
36. Конечные автоматы над бесконечными словами (автоматы Бюхи, Рабина, Мюллера) и их свойства.
37. ω-регулярные языки. Алгоритм проверки пустоты для ω-автоматов.
38. Замкнутость класса ω-регулярных языков относительно теоретико-множественных операций.
39. Монадическая логика 2-го порядка S1S
40. Взаимосвязь логики S1S с ω-регулярными языками.

Литература

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 с.

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

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

В каждом блоке для решения предлагаются следующие задания.

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

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

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

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

28-36 баллов - отлично,

20-27 баллов - хорошо,

13-19 баллов - удовлетворительно.