Санкт-Петербург, 199178, Россия, 14-я линия Васильевского острова дом 29 Б
(812) 363-68-71, (812) 363-68-72
ru

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

2018 – 2019, VIII семестр

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

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


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