2023/2024
Вычислительная сложность
Статус:
Маго-лего
Когда читается:
1 модуль
Онлайн-часы:
52
Охват аудитории:
для своего кампуса
Язык:
английский
Кредиты:
3
Контактные часы:
10
Course Syllabus
Abstract
This course teaches the basics of computational complexity theory, approximation, and probabilistic algorithms for solving intractable problems including those from data analysis. You will learn:
- definitions of the complexity classes P, NP, and PSPACE,
- techniques to prove that a problem is NP-complete, and
- approaches to solving such problems including exponential algorithms other than exhaustive search, approximation algorithms, and efficient algorithms for special cases.