Параметризованные алгоритмы (2015)

Курс будет посвящен одному из направлений построения эффективных алгоритмов для NP-трудных задач, а именно построению FPT-алгоритмов (fixed paramater tractable). По сравнению с другими направлениями, такими как построение приближенных алгоритмов, эвристик и точных алгоритмов, построение FPT алгоритмов достаточно новое направление, но при этом уже завоевавшее достаточную популярность. В курсе будет дан обзор идей и методов, использующихся при построении и анализе FPT алгоритмов, а также связь FPT алгоритмов с эвристическими, приближенными и точными алгоритмами. Первые лекции будут посвящены следующим методам: дерево расщеплений, итеративное сжатие, кернелизация. В курсе также будет рассмотрены вопросы о доказательстве нижних оценок на вычислительную сложность некоторых задач в предположении гипотезы ETH.

Курс входит в магистерскую программу Академического университета и открыт для всех желающих.

Страница курса