Название спецкурса на русском языке
Теория сложности вычислений
Перевод названия курса на английский язык
Theory of computation complexity
Авторы курса
доцент Боков Г.В.
Целевая аудитория
2 курс
3 курс
4 курс
5 курс
6 курс
Подразделение
[Кафедра МаТИС]
Семестр
Полгода (осень)
Тип курса
Спецкурс по выбору студента
Учебный год
2020/21
Аудитория
[Неприменимо]
Аннотация
В курсе рассматриваются различные модели вычислений – машины Тьюринга, схемы из функциональных элементов, интерактивные доказательства, алгебраические и логические системы – и изучается их сложность. Рассматриваются многие современные представления в теории сложности: новые вероятностные определения классов сложности и их применение для алгоритмов аппроксимации, алгоритм Шора для факторизации целых чисел на квантовом компьютере, красивые конструкции псевдослучайных объектов и многое другое.
Целью курса является ознакомление студентов с основными понятиями и методами теории сложности вычислений, предполагающее овладение недавними достижениями в теории сложности, полученными за последние десятилетия, в контексте классических результатов.
Дополнительная информация

четверг 16:45, дистанционно, Zoom 724 8806 4772, п 7FjyWA