Efektivní předzpracování a parametrizované algoritmy (MI-PAM)

Základní informace

Přednášejícím je Ondřej Suchý.

Místo konání

Výuka probíhá v místnosti TH:A-1442, vždy ve středu od 12:45, každý sudý týden následuje od 14:30 cvičení.

Hodnocení

Během semestru budou zadávány domácí úkoly, celkem nejméně za 70 bodů. Na zápočet je potřeba získat 20 bodů. Termín pro odevzdání úkolů je typicky do cvičení, které následuje za aspoň 13 dní. Na cvičení buď předvede řešení úkolu někdo ze studentů, nebo přednášející, nebo úkol doplníme nápovědou, která může změnit jeho bodovou hodnotu, nebo jej odložíme na další cvičení. Za zdařilé předvedení příkladu student získá další 1 bod. Předpokládám, že úkoly budete odevzdávat vypracované na papíře, případně předvedete, jinou formu prosím konzultujte předem.

Předmět bude zakončen zkouškou. Každý student dostane 2 otázky, jednu tématickou a jednu definici (viz seznam otázek z minulého roku). K tématu by měl být student schopen něco říct, u definice znát její obrysy, nikoliv nutně přesné znění. Po písemné přípravě pak proběhne ústní zkouška, která rozhodne o známce.

Průběžné výsledky:

Probraná témata

Literatura

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.

Přednáška je určena spíše studentům vyšších ročníků, případně i doktorandům, ale pro pochopení je nutná znalost pouze základních pojmů z teorie grafů a základů složitosti (např. BI-GRA). Mohou ji tedy navštěvovat i studenti třetího ročníku bakalářského studia.

Předběžný sylabus


update 21.4.2017