Факультатив теория вычислений 2016/2017
Общая информация
Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40.
Срок сдачи первого домашнего задания — первая неделя ноября.
Доступен листок от 7-го ноября.
Результаты домашнего задания по формальным языкам в таблице. См. лист «Задание 1».
Объявления
13 декабря (вторник, обычное время) для желающих будет еще раз заново рассказан AM[2] протокол для задачи неизоморфизма графов.
О домашнем задании 2 (вычислительная сложность): требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу) из этого списка. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны связаться с кем-нибудь из преподавателей курса и договориться о продлении срока сдачи.
Экзамен по курсу состоится 16 декабря, 16:40. Экзамен устный.
Программа экзамена
I. Регулярные языки
- Регулярные выражения
- Конечные автоматы
- Эквивалентность определений регулярных языков через конечные автоматы и регулярные выражения
- Лемма о накачке
- Теорема Майхилла-Нероуда. Минимальный ДКА.
- Замкнутость класса регулярных языков относительно теоретико-множественных операций
II. Контекстно-свободные языки
- КС-грамматики
- Лемма о накачке (для КС языков)
- Нормальная форма Хомского
- Автоматы с магазинной памятью
- Эквивалентность языков, задаваемых КС-грамматиками и МП-автоматами
- Свойства замкнутости класса КС-языков относительно теоретико-множественных операций и относительно пересечения с регулярными языками
III. Вычислительная сложность.
- Классы P, NP, coNP.
- Полиномиальная сводимость.
- NP- и coNP-полные задачи.
- Класс BPP. Устойчивость определения относительно уменьшения вероятности ошибки.
- Вероятностное сведение задачи о полном паросочетании в двудольном графе к вычислению определителя.
- Схемная сложность булевых функций и класс P/poly.
- Вложение BPP в P/poly.
- Полиномиальная иерархия. Вложение BPP во второй уровень иерархии.
- Универсальный перебор по Левину
- Решение полиномиальной игры лежит в PSPACE. Обратное: для всякого свойства из PSPACE есть полиномиальная игра с параметром, в которой есть выигрыш тогда и только тогда, когда параметр обладает указанным свойством. 3.11 Задача TQBF и её полнота в PSPACE.
- PSPACE-полные задачи: игра на графе без повторений позиций, игра в слова.
- Теорема Сэвича
- Определение класса AM: вместо второго игрока случайные биты. Вероятность выигрыша при оптимальной стратегии.
- Замкнутость класса AM относительно сводимости.
- AM лежит в PSPACE.
- TQBF лежит в AM.
Дневник курса
| дата | занятие | материалы |
|---|---|---|
| Регулярные языки и конечные автоматы | ||
| 20.09 | Лекция 1 | Глава 1 Сипсера |
| 23.09 | Семинар 1 | Листок семинаров (1-2) |
| 27.09 | Семинар 2 | Домашнее задание 1 (1/2) |
| Контекстно-свободные языки | ||
| 30.09 | Лекция 2 | Глава 2 Сипсера |
| 04.10 | Лекция 3 | Глава 2 Сипсера |
| 07.10 | Семинар 3 | Листок семинаров (3-4) |
| 11.10 | Лекция 4 | Глава 2 Сипсера |
| 14.10 | Семинар 4 | Домашнее задание 1 (2/2) |
