Название спецкурса на русском языке
Введение в теорию сложности
Перевод названия курса на английский язык
Introduction to complexity theory
Авторы курса
Подольский Владимир Владимирович
Целевая аудитория
3 курс
4 курс
5 курс
6 курс
Магистранты
Аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Полугодовой, осень
Тип курса
Спецкурс по выбору кафедры
Аннотация
Курс посвящен теоретическим основам компьютерных наук. Будут рассмотрены основные сложностные классы, такие как P, NP, coNP, PSPACE, BPP, P/poly, будут разобраны понятия сводимости и полноты, будут показаны примеры полных задач для части из перечисленных классов. Ближе к концу курса будут рассмотрены дополнительные темы из теории сложности вычислений, такие как коммуникационная сложность и ее приложения к потоковым алгоритмам.
Как проходит
понедельник 10:00 – 11:25. МИАН, комн. 430 (ул. Губкина, 8) + Zoom. Первое занятие: 6 сентября
Учебный год
2021/22
Дополнительная информация

Записаться на курс, посмотреть видеозаписи, контакты:
http://www.mathnet.ru/conf1988