Название спецкурса на русском языке
Введение в теорию сложности
Перевод названия курса на английский язык
Introduction to complexity theory
Целевая аудитория
3 курс
4 курс
5 курс
6 курс
Магистранты
Аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Полгода (осень)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2021/22
Аудитория
[Неприменимо]
Аннотация
Курс посвящен теоретическим основам компьютерных наук. Будут рассмотрены основные сложностные классы, такие как P, NP, coNP, PSPACE, BPP, P/poly, будут разобраны понятия сводимости и полноты, будут показаны примеры полных задач для части из перечисленных классов. Ближе к концу курса будут рассмотрены дополнительные темы из теории сложности вычислений, такие как коммуникационная сложность и ее приложения к потоковым алгоритмам.
Дополнительная информация
Записаться на курс, посмотреть видеозаписи, контакты:
http://www.mathnet.ru/conf1988