Теоретическая информатика 3

Курс «теоретическая информатика-3», посвящённый теории автоматов, формальных грамматик и сложности вычислений, был прочитан А. Охотиным осенью 2016 года студентам 2-го курса СПбГУ, обучающимся по программе «математика».

Лекции

  1. (1 сентября) Введение в ТИ. Машины Тьюринга и неразрешимые задачи.
  2. (8 сентября) Регулярные языки регулярные выражения, DFA, NFA, их равносильность.
  3. (15 сентября) Регулярные языки (продолжение): лемма накачки, замкнутость относительно действий.
  4. (22 сентября) Регулярные языки: двухсторонние автоматы (2DFA), их перевод в односторонние (детерминированные и недетерминированные).
  5. (29 сентября) Регулярные языки: понятие о древоходных автоматах, минимизация односторонних DFA. Введение в формальные грамматики.
  6. (6 октября) Определения грамматик. Примеры. Замкнутость относительно действий. Лемма накачки, несуществование грамматики для {anbncn}.
  7. (13 октября) Невозможность полного описания синтаксиса языка программирования грамматикой. Лемма Огдена. Несуществование грамматики для {albmcn | l,m,n попарно различны}. Незамкнутость относительно пересечения и деления. Нормальный вид Хомского: удаление пустых правил, удаление единичных правил. Синтаксический анализ за время O(n3): алгоритм Кокка–Касами–Янгера.
  8. (20 октября) Синтаксический анализ через умножение матриц (алгоритм Валианта). Синтаксический анализ с использованием памяти O(log2n) .
  9. (27 октября) Неразрешимые свойства грамматик. Понятие о магазинных автоматах. (обновлено 29 ноября: написано про магазинные автоматы)
  10. (3 ноября) Логика FO(LFP). Логика FO(LFP) как обобщение формальных грамматик. Равносильность FO(LFP) и полиномиального времени (P).
  11. (10 ноября) Сложность вычислений по времени и по памяти. Теорема Савича. Теорема Иммермана-Селепчени.
  12. (17 ноября) Иерархии по времени и по памяти. Сводимость с логарифмической памятью. Понятие P-полной задачи. Задача о значении схемы (CVP), её P-полнота.
  13. (24 ноября) P-полнота задачи синтаксического анализа. Класс NP. Задача о выполнимости формулы в 3-КНФ (3-SAT), её NP-полнота. NP-полные задачи для графов: клика, независимое множество, вершинное покрытие раскраска в 3 цвета.
  14. (1 декабря) NP-полные задачи: гамильтонов путь в ориентированных и неориентированных графах, гамильтонов цикл, задача коммивояжёра, задача о покрытии множества. NP-полные задачи о множествах чисел: сумма подмножества, разбиение подмножества, задача о рюкзаке, построение расписания. .
  15. (8 декабря) NLOGSPACE-полные задачи: задача о пути в ориентированном графе, задача о пустоте NFA или DFA. PSPACE-полные задачи: задача о булевой формуле с кванторной приставкой (QBF) задача о пустоте пересечения нескольких DFA.
  16. (15 декабря) Чередующийся недетерминизм. Полиномиальная иерархия. Машины с оракулом.

Задачи для самостоятельного решения

  1. Задачи по регулярным языкам, которые необходимо сдать до 31 октября. Для этого надо отыскать А. Охотина и рассказать ему решения.
  2. Задачи по грамматикам и по теории сложности, которые очень желательно сдать до 27 декабря, поскольку позже может не найтись времени. Самый крайний срок --- день перед консультацией.
E-mail: