Текущая версия на 00:52, 9 мая 2020

Факультатив Теория вычислений (2-й курс ПМИ) 2020 год

Лекции и семинары проходят по пятницам, лекция в 13:40, семинар в 15:10. Аудитория: R602.

Новости

Изменился номер аудитории, теперь лекции и семинары в ауд. R602.

Изменилось расписание. Теперь лекция начинается в 13:40, а семинар в 15:10, ауд. R206.

Лекция 7 февраля не состоялась из-за опоздания лектора (на 3 часа) по ошибке.

Лекция и семинар 31 января отменяются, поскольку аудитория будет занята Олимпиадой Высшая проба.

Лекторы и семинаристы

Н. К. Верещагин, А.С. Милованов, М.Н. Вялый, В.В. Подольский, А.А. Рубцов

С вопросами по курсу можно обращаться к Владимиру Владимировичу Подольскому vpodolskii@hse.ru и к Александру Александровичу Рубцову arubtsov@hse.ru.

Краткое описание

NP и теорема Кука-Левина. Вероятностные алгоритмы и классы BPP, RP, ZPP.

Fine-grained сложность.

Теория формальных языков

Отчётность по курсу и критерии оценки

Домашнее задание и экзамен.

Домашнее задание состоит из задач (обычных и дополнительных), постепенно добавляемых в список. Рядом с каждой задачей (или её пунктом) указано количество баллов, которые можно получить за правильное решение, а также дата сдачи ("дедлайн"). Решения, сданные после дедлайна, получают не более половины баллов.

Пусть Sреш — сумма баллов, набранных за решение обычных задач, Sреш_доп — сумма баллов, набранных за решение дополнительных задач, а S — максимально возможная сумма баллов, которые можно набрать за обычные задачи. Тогда оценка за домашнее задание вычисляется по формуле: Одз = min{(Sреш + Sреш_доп)/S * 10, 10}.

Экзамен (устный) оценивается по десятибалльной системе. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.

Итоговая оценка вычисляется по формуле: Оитог = Одз*0,3 + Оэкз*0,7

Те, кто не смог прийти на экзамен по болезни, могут сдать его отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.

Правила округления

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется (арифметически) в момент выставления итоговой оценки.

Экзамен

Домашние задания

Задачи по первой части курса (исходный код). Рядом с каждой задачей (или её пунктом) указано количество баллов, которые можно получить за правильное решение, а также дата сдачи ("дедлайн"). Решения, сданные после дедлайна, получают не более половины баллов.

В задаче 4 изменено условие. Добавлен дополнительный пункт. Срок сдачи продлён до 15 мая

Таблица с оценками

Прочитанные лекции

Лекция 1 (24 января).

Машины Тьюринга. Время и память. Класс P. Полиномиальная m-сводимость (сводимость Карпа).

Лекция 2 (14 февраля).

Сводимость Кука. Классы NP (определение с недетерминированными машинами и как проекций предикатов из P) и FNP и сводимость каждой задачи из FNP к некоторой задаче из NP.

Существование NP полных задач.

Лекция 3 (28 февраля).

Доказательство NP полноты задачи о замощении квадрата. Связь между машинами Тьюринга и схемами из функциональных элементов. Класс P/poly (определение со схемами из функциональных элементов). Теорема о NP полноте задачи о выполнимости схем.

Лекция 4 (6 марта).

NP полнота задачи 3-КНФ. Вероятностные полиномиальные алгоритмы для проверки простоты и для проверки алгебраических тождеств.

Лекция 5 (13 марта).

Доказательство леммы Шварца - Зиппеля. Классы BPP, RP. Амплификация и включение BPP в P/poly.

Планируемые лекции

Лекция 6 ().

Алгоритмы для k-SAT быстрее полного перебора. Формулировка ETH и SETH. Нижние оценки для задачи о клике и задаче k-SUM, основанные на ETH. Формулировка нижней оценки для задачи Orthogonal Vectors, основанной на SETH.

Лекция 7 ()

Нижняя оценка для Orthogonal Vectors. Лемма о спарсификации.

Лекция 8 ().

Нижняя оценка для задач о диаметре графа и наибольшей общей подпоследовательности. Задача 3-SUM и основанная на ней нижняя оценка для задачи о перетаскивании шкафа.

Лекция 9 ().

Регулярные языки. Эквивалентность определений через регулярные выражения, детерминированные и недетерминированные конечные автоматы. Лемма о накачке. Материал курса по регулярным языкам хорошо освящён в книжке Сипсера, а также здесь.

Лекция 10 (3 апреля).

Регулярные языки. Алгоритм минимизации автоматов и теорема Майхилла-Нероуда.

Лекция 11 (10 апреля).

Контекстно-свободные языки. Формальные грамматики и магазинные автоматы. Алгоритм построения МП-автомата по грамматике.

Лекция 12 (17 апреля).

Контекстно-свободные языки. Алгоритм построения КС-грамматики по МП-автомату. Нормальная форма Хомского. Алгоритм Кока–Янгера–Касами. Лемма о накачке для КС-языков.

Лекция 13 (24 апреля).

Игры достижимости, игры чётности. Существование позиционных выигрышных стратегий. Решение игр чётности лежит в пересечении классов NP и coNP. Конспект лекции

Лекция 14 (8 мая).

Сводимость игр четности к играм достижимости. Автоматы на деревьях. Универсальные деревья квазиполиномиального размера. Алгоритм решения игр четности за квазиполиномиальное время. Конспект лекций 13-14

Лекция 15 (15 мая).

Коммуникационная сложность, протокол для задачи о кликах и независимых множествах. Определение детерминированных протоколов, комбинаторные прямоугольники, метод трудных множеств, метод размера прямоугольника, метод ранга. Нижние оценки для EQ, GT, IP, DISJ.

Лекция 16 (22 мая).

Потоковые алгоритмы. Нахождение элемента, встречающегося более половины раз. Трудность нахождения самого часто встречающегося элемента. Односторонняя вероятностная коммуникационная сложность функции DISJ.

Семинары

Семинар 1 (24 января).

Классы P, NP и coNP. Листок 1.

Семинар 2 (7 февраля).

Классы P, NP и coNP (продолжение). Ещё раз листок 1.

Семинар 3 (14 февраля).

Сводимость по Куку и сводимость по Карпу Листок 2.

Семинар 4 (21 февраля).

NP-трудность и NP-полнота Листок 3.

Семинар 5 (28 февраля).

NP-трудность и NP-полнота (продолжение) Ещё раз листок 3.

Семинар 6 (6 марта).

Задачи оптимизации (без листочка) и вероятностные алгоритмы Листок 4 (первая задача).

Семинар 7 (13 марта).

Вероятностные алгоритмы Ещё раз листок 4.

Семинар 8 (20 марта).

Схемы из функциональных элементов Листок 5.

Семинар 9 (3 апреля).

Коммуникационная сложность Листок про коммуникационную сложность.

Занятие 17 апреля.

Теоремы об иерархии Листок к семинару (с.1-2)

Занятие 8 мая.

Теоремы об иерархии (окончание). Игры и альтернирующие вычисления. Листок к семинару (с.2-4)

Прошлогодние семинары

Здесь временно лежат листочки прошлогодних семинаров.

Листок 5 марта.

Листок 12 марта

Листок 19 марта

Листок 9 и 19 апреля

Листок 26 и 30 апреля

Листок 31 мая Решили 1-ую и 8-ую задачу.

Листок 4 июня

Рекомендуемая литература