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

Преподаватель: Захаров Павел Александрович
Модуль: 3-4
Кредиты: 2
Формат проведения занятий: очно
Экзамен: в 4-м модуле

Аннотация:  

Факультатив представляет собой введение в центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода - придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.

Курс затронет другие подходы к оценке сложности той или иной задачи, например деревья решений. Одной из мини-кульминаций станет гипотеза Аандераа—Карпа—Розенберга о проверке наличия у графа некоего монотонного свойства путём серии запросов о наличии того или иного ребра.

Формула оценивания: Оценки за задачи (0,7 от итога) и оценки за экзамен (0,3 от итога).

Пререквизиты:  Базовые знания дискретной математики.

Для кого:  Студенты ПМИ пилотоных потоков 1-го курса и студенты ФКН.