Теория вычислений
Информация о преподавателях
Первая часть курса, относящаяся к формальным языкам, будет прочитана А.А. Рубцовым, научным сотрудником лаборатории теоретической информатики. Остальные части курса будут прочитаны кем-то из сотрудников лаборатории теоретической информатики (https://cs.hse.ru/big-data/tcs-lab/) и их коллег из списка ниже:
- Н. К. Верещагин, заведующий лабораторией
- М.Н. Вялый, ведущий научный сотрудник
- В.А. Гурвич, ведущий научный сотрудник
- В.В. Подольский, старший научный сотрудник
- А.Х. Шень, партнёр лаборатории
- С. Л. Кузнецов, сотрудник департамента анализа данных и искусственного интеллекта
С вопросами по курсу можно обращаться к Владимиру Владимировичу Подольскому vpodolskii@hse.ru и к Александру Александровичу Рубцову arubtsov@hse.ru.
Факультатив «Теория вычислений» является введением в классические темы теоретической информатики. Изложение во многом следует книге Майкла Сипсера «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
При вычислении промежуточных оценок, дробные части округляются вверх.
План занятий
Каждую неделю будет проходить лекция и семинар по её материалу. Изложение соответствует книге M. Sipser «Introduction to the Theory of Computation». Мы приведём примерный план курса — реальный план может отличаться в зависимости от начальной подготовки слушателей, их интересов и пожеланий, однако мы не выйдем за пределы книги Сипсера.
Лекции 1-2: регулярные языки
Лекции 3-4: контекстно свободны
Лекции 4-7: классы P и NP; NP-полные задачи
Лекции 8-12: классы L, NL, PSPACE, полиномиальная иерархия
Расписание:
29.01 - ауд. 509
время - с 13.40 до 16.30
с 05.02 по 19.03 - ауд. 400 - 3 модуль
с 02.04 по 21.05 – ауд. 402 – 4 модуль
31 мая с 16.40 до 19.30 - ауд. 219
7 июня с 16.40 до 19.30 - ауд. 505