Теория вычислений

Преподаватели: 
Николай Верещагин 
Александр Козачинский
Алексей Милованов
Михаил Вялый
Владимир Подольский
Александр Рубцов
Антон Гнатенко

Расписание занятий:
По пятницам
Время: 12.10-15.00
24.01 - ауд. D107
31.01 - ауд. N507
c 07.02 по 21.02 ауд. D102
Время: 13.40 - 16.30 (меняется)
с 28.02 по 20.03 - 3 модуль ауд. R602
c 03.04 по 19.06 - 4 модуль ауд. R602

Факультатив «Теория вычислений» является введением в классические темы теоретической информатики. Изложение во многом следует книге Майкла Сипсера «Introduction to the Theory of Computation», одной из лучших в этой области. Сипсер является одним из ведущих специалистов в области теоретической информатики и деканом по науке MIT.
 
Курс начинается с теории автоматов и формальных языков — математики, которая с одной стороны описывает самые простые модели вычислений, а с другой стороны, широко применяемой на практике в алгоритмах по обработке текстов и компиляторах.

Центральной темой курса является NP-полнота. Слова «P» и «NP» можно было услышать в разговорах о задачах тысячелетия: за разделение этих двух классов обещают $1 000 000 (как и за доказательство их совпадения). Однако, не смотря на невозможность решения этого вопроса в обозримом будущем, изучение NP полноты полезно в том числе и для практики: многие алгоритмы шифрования используют свойства задач из класса NP; также при работе на практике полезно выяснить, что поставленная задача NP-полна, поэтому эффективного решения искать не стоит, а значит стоит уточнить эту задачу или искать приближённые решения.

Также будут изучены и другие базовые классы сложности вычислений, такие как L, NL, PSPACE и полиномиальная иерархия. Курс не имеет жёсткой программы — содержание может варьироваться в зависимости от подготовки слушателей и их интересов, однако не будет выходить за пределы книги Сипсера.

Курс рассчитан на студентов 2-4 курсов, но может быть также интересен студентам магистратуры и аспирантам, интересующимся теоретической информатикой и в частности теорией вычислений. Предполагается, что слушатели уже знакомы с машинами Тьюринга или вычислимыми функциями.

Критерии оценки знаний и формула оценивания

Для успешного прохождения курса слушатели должны освоить математический аппарат теоретической информатики. В процессе аттестации по курсу предстоит отвечать на вопросы по теории и решать задачи. Из аттестационных мероприятий запланированы сдача задач преподавателям (баллы за сданные задачи формируют накопленную оценку Онак) и итоговый экзамен (оценка Оэкз).

Оценки за каждое из аттестационных мероприятий выставляются по десятибалльной системе. Итоговая оценка вычисляется по формуле

Оитог = Онак*0,2 + Оэкз*0,8.
При вычислении промежуточных оценок, дробные части округляются вверх.

Расписание:
12:10 – 15:00
24.01 – ауд. D107
c 07.02 по 20.03 – 3 модуль
ауд. D102

c 03.04 по 19.06 – 4 модуль
ауд. D102