Záznam přednášky - Parametrizované algoritmy
| Akce: | Krutá Smršť Přednášek 2022 (záznamy z akce) |
|---|---|
| Přednášející: | Martin Koreček |
| Motto: | Co přesně je tak těžké na daném NP-těžkém problému? |
| Anotace: | Pro žádný NP-těžký problém není znám algoritmus, který by jej řešil v čase lepším než exponenciálním. Často ale umíme najít algoritmus, jehož složitost je exponenciální jen v nějakém parametru problému. Například jednoduchým algoritmem zjistíme, zda má n-vrcholový graf vrcholové pokrytí velikosti ≤ k v čase 2k · nc. Hledáním parametrizovaných algoritmů se tak fakticky snažíme najít jádro těžkého problému, které jej činí těžkým. Přednáška poskytne krátký úvod do těchto metod a do toho, co nám o některých problémech prozradily. |
| Externí odkazy: | YouTube |
| Ke stažení: | Video (MP4/H.264) a Audio (Ogg/Opus) Doplnění k částečnému vrcholovému pokrytí (PDF) |