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

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

Лекции

  1. (4 сентября) Машины Тьюринга и неразрешимые задачи. Теорема Райса. Детерминированные конечные автоматы (DFA).
  2. (11 сентября) Формальные языки и действия над ними. Регулярные выражения. Недетерминированные конечные автоматы (NFA). Преобразование NFA к DFA (преобразование подмножеств). Нерегулярность языка {anbn | n>=0}.
  3. (18 сентября) Формальные языки и действия над ними. Преобразование регулярных выражений в ε-NFA, преобразование ε-NFA в NFA, преобразование NFA в регулярные выражения. Лемма о накачке для регулярных языков. DFA для пересечения, дополнения и поэлементного квадратного корня.
  4. (25 сентября) Язык, удовлетворяющий лемме о накачке. Минимизация DFA. Двухсторонние конечные автоматы (2DFA).
  5. (2 октября) Пример 2DFA. Преобразование 2DFA к DFA. Введение в формальные грамматики.
  6. (9 октября) Преобразование 2DFA к NFA. Четыре определения формальных грамматик: деревья разбора, логический вывод, перезапись строк, языковые уравнения
  7. (16 октября) Грамматика для дополнения языка {ww | w ∈ {a,b}*}. Действия над грамматиками: пересечение с регулярным языком, множество всех префиксов. Лемма о накачке для грамматик, несуществование грамматики для языка {anbncn}. Невозможность полного описания синтаксиса языка программирования грамматикой. Лемма Огдена, несуществование грамматики для {albmcn | l,m,n попарно различны}. Грамматики над односимвольным алфавитом.
  8. (23 октября) Невыразимые действия над грамматиками: пересечение, деление. Нормальный вид Хомского. Синтаксический анализ за время O(n3): алгоритм Кокка–Касами–Янгера. Истории вычислений машины Тьюринга, неразрешимые задачи для грамматик.
  9. (30 октября) Синтаксический анализ через умножение матриц (алгоритм Валианта). Синтаксический анализ, использующий памяти O(log2n).
  10. (6 ноября) Логика FO(LFP), её равносильность полиномиальному времени (P).
  11. (13 ноября) Сложность вычислений по времени и по памяти, линейное ускорение и сокращение памяти, сокращение числа лент.
  12. (20 ноября) Иерархии по времени и по памяти, простые включения между классами сложности, теорема Савича, теорема Иммермана–Селепчени.

Задачи для самостоятельного решения («листочки»)

  1. Задачи по регулярным языкам, которые необходимо сдать до пятницы, 13 октября.
  2. Задачи по формальным грамматикам, которые необходимо сдать до пятницы, 17 ноября.
«Листочки» можно сдавать А. С. Охотину или С. А. Пузыниной. Если студент начал сдавать задачу из листочка одному из преподавателей, но сдать её с первой попытки не получилось, то далее эту задачу следует сдавать тому же преподавателю. Разные задачи при желании можно сдавать разными преподавателям.
E-mail: