Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2 značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS
NI-PAM | Efektivni předzpracování a parametrizované algoritmy | Rozsah kontaktní výuky: | 2P+1C | ||
---|---|---|---|---|---|
Vyučující: | Suchý O. | Způsob zakončení: | Z,ZK | ||
Zodpovědná katedra: | 18101 | ECTS Kredity: | 4 | Semestr: | L |
Anotace:
Existuje řada optimalizačních problémů, pro které nejsou známy polynomiální algoritmy (např. NP-úplné problémy). Přesto je v praxi nutné takové problémy přesně řešit. Ukážeme si, že mnoho problémů lze řešit značně efektivněji, než prostým zkoušením všech řešení. Často lze nalézt společnou vlastnost (parametr) vstupů z praxe - např. všechna řešení jsou malá. Parametrizované algoritmy toho využívají tak, že jejich časová složitost je exponenciální pouze v tomto (malém) parametru, kdežto polynomiální vzhledem k délce vstupu (která může být obrovská).
Parametrizované algoritmy také představují způsob jak formalizovat pojem efektivního polynomiálního předzpracování vstupu pro těžké problémy, což v klasické výpočetní složitosti není možné. Takové polynomiální předzpracování je pak vhodným prvním krokem, ať už následně řešení hledáme libovolným způsobem.
Ukážeme si řadu metod jak parametrizované algoritmy navrhovat a zmíníme také jak ukázat, že pro jistý problém (a parametr) takový algoritmus neexistuje. Neopomineme také souvislosti s dalšími přístupy k těžkým problémům jako jsou mírně exponenciální algoritmy nebo aproximační schémata.
Osnovy přednášek:
1. | Úvod. Omezené prohledávací stromy. Základní definice. | |
2. | Kernelizace jako formalizace pojmu ``efektivní předzpracování.'' Ukázky jednoduchých kernelizací. | |
3. | Prokládání kernelizace s omezenými prohledávacími stromy. Složitější prohledávací stromy. | |
4. | Kernelizace založené na globálních pravidlech. | |
5. | Neexistence polynomiálních kernelů pro některé problémy. | |
6. | Dynamické programovaní, využití principu inkluze a exkluze. Barevné kódování. | |
7. | Iterativní komprese. | |
8. | Stromová šířka a základní vlastnosti. | |
9. | Dynamické programování na grafech omezené stromové šířky. Courcellova věta. | |
10. | Approximační schémata Bakerové typu. | |
11. | Minory, jejich využití ke konstrukci parametrizovaných algoritmů. | |
12. | Parametrizované algoritmy pro rovinné grafy (Bidimensionalita). | |
13. | Třídy parametrizované složitosti, parametrizované redukce, vazby na hypotézu ETH. |
Osnovy cvičení:
Cvičení sestává z řešení zadaných úloh na probíraná témata studenty.
Literatura:
M. | Cygan, F.V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, Ma. Pilipczuk, Mi. Pilipczuk, S. Saurabh: Parameterized Algorithms, Springer, 2015. |
Požadavky:
Pro pochopení je nutná znalost pouze základních pojmů z teorie grafů a úplných základů složitosti (např. BI-AG1, BI-AG2, pro NP-úplnost BI-AAG). Mohou ji tedy navštěvovat i studenti třetího ročníku bakalářského studia.
|
Předmět je zahrnut do těchto studijních plánů:
|
Stránka vytvořena 29. 4. 2024, semestry: Z/2023-4, Z/2019-20, L/2021-2, L/2020-1, L/2022-3, Z/2021-2, L/2019-20, Z/2022-3, Z/2020-1, L/2023-4, Z/2024-5, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: J. Novák, I. Halaška |