Модели вычислений — различия между версиями

Курс для студентов бакалавриата кафедры МК, читается в весеннем семестре:

• 4-й курс — 3 часа лекций и 1 час семинаров в неделю (всего 16 пар), отчётность — экзамен.

Лектор: Савицкий Игорь Владимирович.

Аннотация

Курс посвящён изучению ряда вычислительных моделей (как классических, так и более специальных), используемых в теории алгоритмов. Исследуются распознаваемые данными моделями языки и анализируется сложность задач анализа этих моделей.

В первой части курса изучаются конечные автоматы-распознаватели и регулярные языки. Вторая часть курса посвящена машинам Тьюринга, рекурсивно перечислимым языкам и неразрешимым задачам. В третьей части рассматриваются формальные грамматики, контекстно-свободные языки и магазинные автоматы. В четвёртой части изучаются конечные автоматы-преобразователи, автоматы для распознавания языков из бесконечных слов, а также задание языков с помощью формул логики второго порядка специального вида.

Материалы по курсу

Программа и основные материалы

Программа курса и порядок проведения экзамена

Презентации к лекциям см. ниже

Литература

1. Захаров В.А. Презентации к лекциям (см. ниже)
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978. 612 с.

Дополнительная литература

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

Записи лекций

Видеозаписи лекций и семинаров 2025 года (И.В. Савицкий).

Видеозаписи и презентации лекций 2022 года (В.А. Захаров).

Презентации к лекциям (В.А. Захаров)

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

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

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

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

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

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

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

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

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

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

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

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

Задачи к семинарам (В.А. Захаров)

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

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

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

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