Grafové algoritmy II

V letním semestru 2013/2014 přednáším Grafové algoritmy II.

Chci navázat na svou základní přednášku o grafových algoritmech a ukázat různé pokročilejší partie, jako například práci s celočíselně ohodnocenými grafy a různé grafové datové struktury.

Umluveno na Út 15:40 v S4, začneme druhý týden semestru.

datum co se přednášelo [zdroje]
25. 2. Úvod do výpočetních modelů: RAM (na mnoho způsobů) vs. Pointer Machine [S 2.1]. Fredericksonova clusterizace: definice, vlastnosti, konstrukce v lineárním čase [G 9]. (Clusterizace je v tištěné verzi skriptíček popsána velmi minimalisticky, do online verze jsem doplnil detaily.)
4. 3. Dekrementální udržování lesa (Delete-Find) pomocí clusterizace [G 9]. Van Emde-Boasovy stromy [G 7]. Kouzelnický trik na využití neinicializované paměti [?].
11. 3. Vylepšujeme vEB stromy: stromová interpretace, zrychlení pomocí mikrostromů, x-fast a y-fast stromy [E 11]. Vektorové výpočty na RAMu [S 2.4].
18. 3. Pokračování vektorových výpočtů. (a,b)-stromy pro malé universum s vektorovým kódováním klíčů ve vrcholech. Fusion tree a počítání přibližných sketchů [E 12].
25. 3. Q-haldy (dekodér pouze načrtnut) [S 2.5, FW]. Aplikace: výpočet celočíselné minimální kostry v lineárním čase [S 3.2]. Zmínka o atomických haldách, AF-haldách a Dijkstrovi (bez důkazu) [FW].
1. 4. Verifikace minimality kostry: redukce hloubky pomocí Borůvkových stromů, Komlósův algoritmus. [S 3.3]
8. 4. Počítáme porovnání v Komlósově algoritmu [S 3.3]. Kargerův-Kleinův-Tarjanův randomizovaný algoritmus na minimální kostru [S 3.5].
15. 4. Hrátky s přihrádkovým tříděním: klestění multihran, isomorfismus stromů, unifikace posloupností a multimnožin. [S 2.2].
22. 4. Zoo Ackermannových funkcí a jejich inverzí [S A.3]. Offline algoritmus pro stromové předchůdce na Pointer Machine [B]: dekompozice, Union-Find se speciálními prvky, ale co s mikrostromy? Topologické výpočty a kanonické kódy grafů [S 2.2].
29. 4. Dokončení algoritmu z minula. Využití téhož přístupu pro verifikaci minimální kostry: úprava Union-Find na Link-Eval, generování rozhodovacích stromů Komlósovým algoritmem [B]. Zmínka o dynamické reprezentaci lesů a jejím použití v Dinicově algoritmu [ST1].
6. 5. Sleatorovy-Tarjanovy (Link-Cut) stromy [ST1]: princip rozkladu stromů na cesty, reprezentace cest binárními stromy. Opakování Splay stromů.
13. 5. Rozbor složitosti Splay stromů a jejich použití v Link-Cut stromech [ST2].
20. 5. Goldbergův algoritmus na maximální tok pomocí převádění přebytků a Tarjanovo zrychlení pomocí Link-Cut stromů [GT]. Navazující algoritmy, na které už nezbyl čas: Goldberg-Rao [GR], Orlin [O].

Zkoušky

Termíny jsou vypsány v SISu, přihlašujte se prosím tam; pokud by se vám to více hodilo jindy, ozvěte se mi.

Ke zkoušte byste měli mít základní přehled o odpřednesené látce (algoritmy, tvrzení vět, hrubé principy důkazů) a detailní přehled o jednom z následujících okruhů:

Detailní část zkoušky lze nahradit implementací algoritmu nebo sepsáním kapitoly skript.

Literatura

Stránku spravuje Martin Mareš