Адрес e-mail:

Сложность вычислений (весна 2012)

Лекторы — Д. В. Мусатов, к.ф.-м.н. А. Е. Ромащенко.

Следующие студенты освобождаются от следующих задач:

От первой задачи:

095 Зиятдинов Тимур, Ирхин Илья, Ключников Никита, Павленко Виталий,
Чумбалов Данияр
096 Чернецкий Аркадий
097 Андреева Екатерина, Булатов Виктор, Романов Алексей, Савельев
Константин, Саитов Рустем, Яныкин Кирилл
017 Бахтеев Олег

От второй задачи:

095 Ирхин Илья, Ключников Никита, Павленко Виталий, Попов Максим,
Пушняков Филипп, Чумбалов Данияр
097 Булатов Виктор, Савельев Константин
017 Кищенко Ярослав

От третьей задачи:

095 Ирхин Илья, Ключников Никита, Павленко Виталий, Попов Максим,
Пушняков Филипп, Чумбалов Данияр
097 Булатов Виктор, Красных Александр, Куратов Юрий, Курносов Артём,
Савельев Константин

Получают право на сдачу дополнительного вопроса:

095 Ирхин Илья, Павленко Виталий

Программа курса
Программа экзамена

Задачи для самостоятельного решения

Модели вычислений
Классы P, NP и coNP
NP-полные задачи
Диагонализация
Пространственная сложность
Полиномиальная иерархия
Схемная сложность
Вероятностная сложность

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li soc-yt
Яндекс.Метрика