Алгоритмы для NP-трудных задач
Курс Хит![](https://www.lektorium.tv/sites/lektorium.tv/files/courses/1283292820_22758_1273955208_12849_c19_l8_p2.flv_000124133.jpg)
В курсе рассмотрены красивые идеи построения алгоритмов для NP–трудных задач — от классических до недавних результатов. Предварительный список тем: точные алгоритмы (расщепление, локальный поиск, умный перебор, сведение к простой задаче), fixed parameter tractable алгоритмы (kernelization, color coding, алгоритмы, основанные на матричном умножении и формуле включений–исключений), приближённые алгоритмы (алгоритмы, основанные на линейном и полуопределённом программировании).
Лекции курса
13