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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

Лекции и семинары проходят вторникам в аудитории 400 в третьем модуле и 402 в четвертом модуле в 13:40 (лекция) и 15:10 (семинар).


Новости

1 марта 2019. Выложено первое домашнее занаие.

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


Экзамен

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


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

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

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

Лекция 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.

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

Семинары

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