Факультатив теория вычислений 2016/2017 — различия между версиями

Текущая версия на 14:53, 9 ноября 2017

Общая информация

Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40.

Срок сдачи первого домашнего задания — первая неделя ноября.

Доступен листок от 7-го ноября.

Результаты домашнего задания по формальным языкам в таблице. См. лист «Задание 1».

Объявления

13 декабря (вторник, обычное время) для желающих будет еще раз заново рассказан AM[2] протокол для задачи неизоморфизма графов.

О домашнем задании 2 (вычислительная сложность): требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу) из этого списка. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны связаться с кем-нибудь из преподавателей курса и договориться о продлении срока сдачи.

Экзамен по курсу состоится 16 декабря, 16:40. Экзамен устный.

Программа экзамена

I. Регулярные языки

1. Регулярные выражения
2. Конечные автоматы
3. Эквивалентность определений регулярных языков через конечные автоматы и регулярные выражения
4. Лемма о накачке
5. Теорема Майхилла-Нероуда. Минимальный ДКА.
6. Замкнутость класса регулярных языков относительно теоретико-множественных операций

II. Контекстно-свободные языки

1. КС-грамматики
2. Лемма о накачке (для КС языков)
3. Нормальная форма Хомского
4. Автоматы с магазинной памятью
5. Эквивалентность языков, задаваемых КС-грамматиками и МП-автоматами
6. Свойства замкнутости класса КС-языков относительно теоретико-множественных операций и относительно пересечения с регулярными языками

III. Вычислительная сложность.

1. Классы P, NP, coNP.
2. Полиномиальная сводимость.
3. NP- и coNP-полные задачи.
4. Класс BPP. Устойчивость определения относительно уменьшения вероятности ошибки.
5. Вероятностное сведение задачи о полном паросочетании в двудольном графе к вычислению определителя.
6. Схемная сложность булевых функций и класс P/poly.
7. Вложение BPP в P/poly.
8. Полиномиальная иерархия. Вложение BPP во второй уровень иерархии.
9. Универсальный перебор по Левину
10. Решение полиномиальной игры лежит в PSPACE. Обратное: для всякого свойства из PSPACE есть полиномиальная игра с параметром, в которой есть выигрыш тогда и только тогда, когда параметр обладает указанным свойством. 3.11 Задача TQBF и её полнота в PSPACE.
11. PSPACE-полные задачи: игра на графе без повторений позиций, игра в слова.
12. Теорема Сэвича
13. Определение класса AM: вместо второго игрока случайные биты. Вероятность выигрыша при оптимальной стратегии.
14. Замкнутость класса AM относительно сводимости.
15. AM лежит в PSPACE.
16. TQBF лежит в AM.

Дневник курса