Параметризованные алгоритмы весна 2018 — различия между версиями
Материал из SEWiki
Bliznets (обсуждение | вклад) (→Лекции) |
Bliznets (обсуждение | вклад) (→Практика) |
||
| Строка 23: | Строка 23: | ||
*[[Медиа:FPT-class-5.pdf|30 march, "Randomized methods."]] | *[[Медиа:FPT-class-5.pdf|30 march, "Randomized methods."]] | ||
*[[Медиа:FPT-home-5.pdf|30 march, "Randomized methods(HW)."]] | *[[Медиа:FPT-home-5.pdf|30 march, "Randomized methods(HW)."]] | ||
| + | *[[Медиа:FPT-class-6.pdf|06 april, "Derandomization."]] | ||
| + | *[[Медиа:FPT-home-6.pdf|06 april, "Randomized methods and derandomization(HW)."]] | ||
Версия 21:16, 10 апреля 2018
Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)
Лекции
- 16 february. Bounded search trees.
- FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.
- 2 march. Kernelization.
- Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.
- 16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.
- 23 march. Vertex Cover above Matching. Iterative Compression.
- Odd Cycle transversal . Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal .
- 30 march. Randomized methods.
Практика
Надо оформить 5 самых сложных задач из Вами решенных.
- 2 march, "Kernelization."
- 2 march, "Kernelization(HW)."
- 16 march, "Kernelization II(HW)."
- 23 march, "Iterative Compression."
- 23 march, "Iterative Compression(HW)."
- 30 march, "Randomized methods."
- 30 march, "Randomized methods(HW)."
- 06 april, "Derandomization."
- 06 april, "Randomized methods and derandomization(HW)."
