Бакалавриат
2022/2023
Теория вычислений
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
английский
Кредиты:
5
Контактные часы:
60
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
Learning Objectives
- Know the parameterized complexity classes FPT, W[i], XP. Apply kernelization technique to obtain FPT-algorithms
- Know famous streaming algorithms, such as SpaceSaving, CountMinSketch to find the most frequent element
- Oracle computation and understand the diagonalization barrier in solving the P vs NP problem
- Prove that PSPACE = NPSPACE and that the TQBF problem is PSPACE complete
- Know the proof of the Cook-Levin theorem: 3SAT is NP-complete
