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