Сложность вычислений
Название спецкурса на английском языке
Computational complexity
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Теорема Фишера–Рабина об экспоненциальной нижней оценки времени разрешения элементарной теории поля действительных чисел.
Класс NP. NP полные и NP трудные задачи. Теорема Кука — Левина об NP-полноте проблемы выполнимости.
Вероятностные полиномиальные алгоритмы. Класс BPP. Уменьшение вероятности ошибки и вложение класса BPP в класс P/poly.
Класс NP. NP полные и NP трудные задачи. Теорема Кука — Левина об NP-полноте проблемы выполнимости.
Вероятностные полиномиальные алгоритмы. Класс BPP. Уменьшение вероятности ошибки и вложение класса BPP в класс P/poly.
Список источников
M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999.
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999.
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
День недели
вторник
Время
18:30-20:05
Аудитория
424
Аудитория первого занятия
424