2022/2023
Теория вычислений
Статус:
Дисциплина общефакультетского пула
Когда читается:
3, 4 модуль
Охват аудитории:
для своего кампуса
Преподаватели:
Захаров Павел Александрович
Язык:
русский
Кредиты:
2
Контактные часы:
40
Программа дисциплины
Аннотация
Факультатив представляет собой введение в центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода - придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.Курс затронет другие подходы к оценке сложности той или иной задачи, например деревья решений. Одной из мини-кульминаций станет гипотеза Аандераа—Карпа—Розенберга о проверке наличия у графа некоего монотонного свойства путём серии запросов о наличии того или иного ребра.