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

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

Аудитория
Неприменимо