Бакалавриат
2026/2027
Параметризованные алгоритмы и сложность
Статус:
Курс по выбору (Прикладная математика и информатика)
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 1, 2 модуль
Охват аудитории:
для своего кампуса
Язык:
английский
Кредиты:
5
Контактные часы:
56
Course Syllabus
Abstract
This course is intended either (A) for student theoretical computer science or (B) student
software engineering with both an interest in theory and implementing large scale industrial
optimization problems.
For certain problems, like various circuit optimizations or resource allocations are both
algorithmically difficult (NP-complete) and still great savings happen when solved just slightly
better. In this case, approximations algorithms might not be optimal and companies might
want to pay for exponential searches. We study how to optimize such searches by
– finding parameters in the given data with reasonably small values
– programming techniques that speed up searches for small values of a parameter.
A classical example is the vertex cover problem: it could be solved reasonably efficiently
on arbitrarily large graph, provided the minimal vertex cover is small. Thus, the parameter
is the “natural parameter” or the size of the object that we search for. In fact, you might
have learned that it can be solved in time 2k ոO(1) on graphs with n nodes, provided there
exists a vertex cover of size at most k. Moreover, this is practical if k ≤ 50, even if n is in
the millions. With more advanced techniques, one can improve this to 1.25k kO(1) + nO(1) and
practical algorithms exist that always find vertex covers of size k ≤ 200, provided they exist.
This even includes adversarial examples generated with crypto.
In the 1st part of the course, we study these algorithmic techniques theoretically. In the
last 4 lectures, this course differentiates.
– Students with a pure theory profile will learn on how to prove the absence of efficient search
for certain problems, called parameterized hardness.
– Students with an applied interest will learn to implement these techniques with and without
LLM’s.