Информация по курсу

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

Программа курса

Лекторы