Факультатив теория вычислений 2016/2017 — различия между версиями
Rubtsov (обсуждение | вклад) |
Rubtsov (обсуждение | вклад) (→Дневник курса) |
||
(не показано 9 промежуточных версии 2 участников) | |||
Строка 2: | Строка 2: | ||
Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40. | Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40. | ||
+ | |||
+ | Срок сдачи первого домашнего задания — первая неделя ноября. | ||
+ | |||
+ | Доступен [https://dl.dropboxusercontent.com/u/31418200/hse/2016/edited.pdf листок] от 7-го ноября. | ||
+ | |||
+ | Результаты домашнего задания по формальным языкам в [https://dl.dropboxusercontent.com/u/31418200/hse/2016/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9.xls таблице]. См. лист «Задание 1». | ||
+ | |||
+ | == Объявления == | ||
+ | |||
+ | '''13 декабря (вторник, обычное время)''' для желающих будет еще раз заново рассказан AM[2] протокол для задачи неизоморфизма графов. | ||
+ | |||
+ | '''О домашнем задании 2 (вычислительная сложность):''' требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу) | ||
+ | из [https://www.dropbox.com/s/dibc6o5wgry3dqm/edited.pdf?dl=0 этого списка]. Те, кто не успевают подготовить домашнее задание к сроку (утро 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. | ||
== Дневник курса == | == Дневник курса == | ||
Строка 13: | Строка 65: | ||
|| 20.09 || Лекция 1 || Глава 1 Сипсера | || 20.09 || Лекция 1 || Глава 1 Сипсера | ||
|- | |- | ||
− | || 23.09 || Семинар 1 || [ | + | || 23.09 || Семинар 1 || [http://rubtsov.su/public/fl/2016/hse_ct/cw01_ct.pdf Листок семинаров (1-2)] |
|- | |- | ||
− | || 27.09 || Семинар 2 || [ | + | || 27.09 || Семинар 2 || [http://rubtsov.su/public/fl/2016/hse_ct/hw01_ct.pdf Домашнее задание 1 (1/2)] |
|- style="text-align:center;" | |- style="text-align:center;" | ||
|colspan=3 style="padding: 0.5ex 0; "| '''Контекстно-свободные языки''' | |colspan=3 style="padding: 0.5ex 0; "| '''Контекстно-свободные языки''' | ||
Строка 21: | Строка 73: | ||
|| 30.09 || Лекция 2 || Глава 2 Сипсера | || 30.09 || Лекция 2 || Глава 2 Сипсера | ||
|- | |- | ||
+ | || 04.10 || Лекция 3 || Глава 2 Сипсера | ||
+ | |- | ||
+ | || 07.10 || Семинар 3 || [http://rubtsov.su/public/fl/2016/hse_ct/cw02_ct.pdf Листок семинаров (3-4)] | ||
+ | |- | ||
+ | || 11.10 || Лекция 4 || Глава 2 Сипсера | ||
+ | |- | ||
+ | || 14.10 || Семинар 4 || [http://rubtsov.su/public/fl/2016/hse_ct/hw01_2_ct.pdf Домашнее задание 1 (2/2)] | ||
|} | |} |
Текущая версия на 14:53, 9 ноября 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) |