Магистратура
2024/2025
Теория вычислений
Статус:
Курс по выбору (Современные компьютерные науки)
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Прогр. обучения:
Современные компьютерные науки
Язык:
русский
Кредиты:
6
Контактные часы:
56
Программа дисциплины
Аннотация
Факультатив «Теория вычислений» является введением в классические темы теоретической информатики. Изложение во многом следует книге Майкла Сипсера «Introduction to the Theory of Computation», одной из лучших в этой области. Сипсер является одним из ведущих специалистов в области теоретической информатики и деканом по науке MIT.
Курс начинается с теории автоматов и формальных языков — математики, которая с одной стороны описывает самые простые модели вычислений, а с другой стороны, широко применяемой на практике в алгоритмах по обработке текстов и компиляторах. Курс рассчитан на студентов 2-4 курсов, но может быть также интересен студентам магистратуры и аспирантам, интересующимся теоретической информатикой и в частности теорией вычислений. Предполагается, что слушатели уже знакомы с машинами Тьюринга или вычислимыми функциями.