Факультатив Теория вычислений

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

Лекции и семинары проходят вторникам в аудитории 400 в третьем модуле. В четвертом модуле в 13:40 (лекция) и 15:10 (семинар). 15:10 (лекция) в аудитории 402 и 16:40 (семинар); семинар пройдёт в аудитории 513 14 мая и в аудитории 317 21 мая.

Новости

18 июня 2019. Результаты экзамена выложены на страницу курса.

5 июня 2019. Экзамен планируется 11 июня с 16:40 до 19:30. Аудитория 511

3 июня 2019. Занятие на этой неделе пройдет 4 июня с 16:40 до 19:30, ауд. 219

23 мая 2019. Занятия по курсу перенесены на пятницу. 31.05 занятия будут в 219 ауд., 16:40-19:30. 07.06 - в 505 ауд., 16:40-19:30

1 марта 2019. Выложено первое домашнее задание. Cрок сдачи 19.3.2019 в 15:10 MSK.

28 марта 2019. Выложено второе домашнее задание. Cрок сдачи 19.4.2019 в 15:10 MSK.

11 апреля 2019. Выложены материалы по формальным языкам. Занятие на следующей неделе переносится на пятницу 19 апреля 16:40-19:30, ауд. 435.

3 мая 2019. Выложено второе домашнее задание по формальным языкам. Срок сдачи 21.5.2019. Занятия по курсу перенесены на вторники 15:10-18:00; лекции в ауд. 402, аудитории для семинаров уточняются.

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

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

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

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

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

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

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

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

4 домашних задания и экзамен.

Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара. Сдача домашних заданий после их срока невозможна.

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

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

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

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

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

Экзамен

Письменный состоится в июне.

Результаты экзамена и итоговые оценки.

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

Домашнее задание 1. Cрок сдачи 19.3.2019 в 15:10 MSK.

Домашнее задание 2. Срок сдачи 19.4.2019.

Домашнее задание 3 (часть 1). Срок сдачи 14.5.2019.

Домашнее задание 3 (часть 2). Срок сдачи 28.5.2019.

Оценки

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

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

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

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

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

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

Доказательство NP полноты задачи о замощении квадрата. Доказательство принадлежности NP задачи ЦЛП.

Лекция 4 (19 февраля).

Вероятностные полиномиальные алгоритмы для проверки простоты и для проверки алгебраических тождеств.

Лекция 5 (26 февраля).

Классы BPP, RP. Амплификация. Класс P/poly (два определения) и включение BPP в P/poly.

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

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

Лекция 7 (12 марта).

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

Лекция 8 (19 марта).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 16 (4 июня).

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

Задачи для семинаров

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

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

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

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

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

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

Листок 4 июня