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

Преподаватель: Захаров Павел Александрович

Модуль: 3-4

Кредиты: 3

Аннотация:

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

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

Курс будет состоять из лекций и задач для самостоятельного решения (обычных и бонусных), которые можно будет сдавать преподавателям в любое удобное для обоих время. Оценка формируется из оценки за задачи (0,7 от итога) и оценки за экзамен (0,3 от итога), который планируется провести в виде мини-конференции с разбором классических (и не очень) результатов по тематике (и не совсем) курса. За подробностями можно обращаться к страничке на вики, которая актуализируется ближе к началу весеннего семестра. 

Требования:

Успешное завершение базового курса Дискретная матрематика 1 на ПМИ или его аналог. В целом, глубокой математической подготовки не требуется, все специальные знания будут рассказаны в процессе.

Для кого: для студентов 1-2 курсов бакалавриата ФКН, бакалаврита Факультета математики. Все интересующиеся приветствуются

Расписание: понедельник 16:20 с 31 января очно