ТЕОРИЯ
ВЫЧИСЛЕНИЙ
Лектор:
профессор В.Н. Касьянов
2012/2013
учебный
год
1.
Введение
Цепочки, языки, графы и деревья. Порождающие грамматики и
распознаватели, классификация Хомского. Теорема о свойствах КЗ-грамматик.
Приведение КС-грамматики к виду без е-правил.
2.
Регулярные множества и автоматы
Регулярные множества и выражения, конечные автоматы, теорема о детерминизации. Регулярные грамматики, теорема о свойствах
регулярных множеств. Теорема о разрастании для регулярных множеств, пример не
регулярного множества. Теорема о накачке, нерегулярность языка Leq. Теорема о свойстве
отношения эквивалентности цепочек относительно автомата. Теорема Майхилла–Нероуда.
3.
КС-языки и автоматы с магазинной памятью
Деревья вывода и эквивалентные преобразования КС-грамматик, алгоритмы проверки пустоты КС-языка, удаления недостижимых и бесполезных символов. Однозначность КС-грамматик и языков, приведение КС-грамматики к нормальной форме Хомского. Теорема о разрастании для КС-языков, пример языка, не являющегося КС-языком. Теорема о замкнутости класса КС-языков относительно подстановки. Свойства замкнутости и незамкнутости класса КС-языков относительно объединения, конкатенации, итерации, позитивной итерации, пересечения и дополнения. МП-автоматы, представление языков {0n1n: n ≥0} и {wwR: wÎ{0,1}+}. Теорема о свойстве верхнего символа. Связь МП-автоматов с КС-языками. Детерминированные КС-языки и их свойства.
4. Машины
Тьюринга и проблемы разрешимости
Машины Тьюринга (ТМ) и их связь с порождающими грамматиками.
Линейно-ограниченные автоматы и их связь с КЗ-языками.
Алгоритмически неразрешимые проблемы, метод сведения, неразрешимость проблем самоприменимости, пустой ленты и проблемы Поста.
Неразрешимость проблем распознавания свойств пересечения двух КС-языков и
дополнения КС-языка, эквивалентности и включения для двух КС-грамматик,
неоднозначности КС-грамматик.
5. Классы
P и NP
Сложность алгоритмов и задач. Недетерминированные ТМ,
теоремы о емкостной и временной сложностях их детерминированного моделирования.
Классы P и NP, полиномиальная сводимость, NP-полные
и NP-трудные языки и задачи,
полиномиальное преобразование оптимизационных задач к задачам распознавания
свойств. Теорема Кука. NP-полнота
задач о 3-выполнимости, о клике, о вершинном покрытии, о суммах подмножеств, о трехмерном
сочетании и о точном покрытии 3-множествами. Методы доказательства NP-полноты. Структура класса NP, список задач из NPC и кандидаты в NPI.
Класс co-NP.
6.
Иерархии языков и задач
Многоленточные ТМ и их моделирование. Класс P-SPACE, примеры языка, полного для P-SPACE, и задачи, требующей экспоненциальной памяти. Иерархия по емкостной сложности для детерминированных TM. Понятие моделирования, теорема об ускорении. Существование сколь угодно сложных задач, теорема Цейтина. Техника следов и нижняя оценка сложности распознавания симметрии. Альтернирующие машины Тьюринга (ATM) и их свойства. Полиномиальная иерархия, ее связь с ATM. Модели вычислений PTM, RTM и CTM, класс #P, примеры #P-полных задач. Гамма-сводимость и гамма-полнота. RАМ с равномерным и логарифмическим критерием, ее связь с TM. Параллельные RAM, их классификация и свойства. Эффективные и оптимальные алгоритмы. Тезисы инвариантности и параллельного выполнения.
7. Сети
Петри
Сети Петри, графы разметок, теорема о дополнительных фишках.
Моделирование сетями Петри, представление блок-схем, задачи о взаимном
исключении, о производителе/потребителе, об обедающих философах, о
читателях/писателях. Основные свойства сетей Петри, проблемы R-включения и R-эквивалентности. Покрывающее дерево, алгоритм проверки
ограниченности сети. Полное покрывающее дерево и разрешимость проблемы
ограниченности места в сети. Алгоритмы проверки t-тупиковости, безопасности,
потенциальной живости, получения местом фишки, неограниченности срабатываний
перехода. Проблемы достижимости и живости, сведении проблемы достижимости к
проблеме живости. Сведение проблемы живости к проблеме достижимости. Языки
сетей Петри, разрешимость проблемы принадлежности.
Литература
1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. - М.: Мир ,1978. - т. 1, 2.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. ‑ М.: Мир, 1979.
3. Гэри М.Р., Джонсон Д.С. Вычислительные машины и тpудноpешаемые задачи. – М.: Миp, 1982.
4. Карпов Ю. Теория автоматов. Учебник для вузов. – СПб.: Издательский дом “Питер”, 2002.
5. Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. ‑ Новосибирск: НГУ, 1995.
6. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка,
визуализация и применение. ‑ СПб: БХВ, 2003.
7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. ‑ М.: МЦНМО, 2001.
8. Котов В.Е. Сети Петри. ‑ М.: Наука, 1984.
9. Хопкрофт Дж., Мотвани Р., Ульман Дж. Ведение в теорию автоматов, языков и вычислений. 2-е издание. — М.: Вильямс, 2002.