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

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

Лекции

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Монадическая логика 2-го порядка S1S и ее взаимосвязь с конечными автоматами над бесконечными словами.
38. Темпоральная логика PLTL: синтаксис и семантика. Применение PLTL для спецификации вычислений и взаимосвязь с автоматами над бесконечными словами.
39. Задача проверки выполнимости формул PLTL и ее сведение к задаче проверки пустоты конечных автоматов над бесконечными словами.
40. Алгоритм двойного поиска в глубину проверки пустоты конечных автоматов над бесконечными словами. Система верификации SPIN: ее устройство и применение.

Литература

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 баллов - удовлетворительно.