Бакалавриат
2025/2026
Теория вычислений
Статус:
Курс обязательный (Прикладная математика и информатика)
Когда читается:
3-й курс, 1, 2 модуль
Охват аудитории:
для своего кампуса
Преподаватели:
Баувенс Бруно Фредерик Л.
Язык:
английский
Course Syllabus
Abstract
The aim of computational complexity is to classify computational problems by their difficulty. Here, difficulty, is measured by various resources needed to provide answers, such as computation time, space, randomness, circuits sizes. In particular, we train to distinguish polynomial time solvable problems and NP-hard problems. The latter are believed to require exponential time for worst case instances, and hence, in applications, one needs to restate the problem, use heuristics, or optimize exhaustive searches. The latter, is studied theoretically in the field of parameterized complexity