INFO5152 Параметризовані та точні алгоритми École normale supérieure de Lyon

Код курсу INFO5152

параметризовані

Під назвою Параметризовані та точні алгоритми

І семестр

Кафедра Кафедра інформатики

Розташування сайту Monod

Ми представляємо алгоритмічні інструменти для оптимального вирішення проблем, що важкі для NP, швидше, ніж підхід грубої сили. Ми представляємо параметризовані алгоритми та складність. Основна увага приділяється методам і тому, як вони використовують вхідну структуру для обслуговування як параметризованих, так і помірно експоненціальних/субекспоненціальних алгоритмів. Ми також виділяємо теоретичні припущення щодо складності та те, як вони часто дозволяють доповнити відомі алгоритми, по суті узгоджуючи умовні нижні межі.

Знайомство з основними поняттями про алгоритми, графіки та теорію складності

Оцінка
Презентація статті

Параметризовані алгоритми Cygan et al.
Точні алгоритми Фоміна та Кратча
Кернелізація Фоміна та співавт.