Grafové algoritmy II

V letním semestru 2015/2016 přednáším Grafové algoritmy II [NDMI088].

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 Pá 10:40 v S3, začneme první týden semestru.

datum co se přednášelo [zdroje]
26. 2. Verifikace minimality kostry: redukce hloubky pomocí Borůvkových stromů, Komlósův algoritmus. [S 3.3]
4. 3. Kargerův-Kleinův-Tarjanův randomizovaný algoritmus na minimální kostru [S 3.5]. Úvod do výpočetních modelů: RAM (na mnoho způsobů) vs. Pointer Machine [S 2.1].
11. 3. Vektorové výpočty na RAMu [S 2.3, 2.4]. Verifikace minimality kostry v lineárním čase [S 3.4].
18. 3. Pokračování RAMové magie: logaritmus v konstantním čase. Q-haldy: výpočet ranku pomocí trie, kompaktní kódování trie. [S 2.5, FW]
25. 3. Pomni, abys den sváteční světil…
1. 4. Přednáška se nekoná.
8. 4. Ani dnes se přednáška nekoná.
15. 4. Q-haldy: operace, dekodér toliko načrtnut [S 2.5, FW]. Aplikace: výpočet celočíselné minimální kostry v lineárním čase [S 3.2]. 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].
6. 5. Soft haldy: definice, průběh operací, základní invarianty [H].
13. 5. Soft haldy: analýza časové složitosti (tahák) [H]. Zpět k minimálním kostrám: lemma o robustních kontrakcích [S4.2].
20. 5. Minimální kostry: robustní kontrakce, clusterovací algoritmus [S4.2], rozhodovací stromy [S4.3].
27. 5. Zbytek odhadů k rozhodovacím stromům [S4.3]. Finále: Optimální algoritmus na minimální kostry [S4.4].

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šce byste měli znát odpřednesenou látku a rozumět jí. Též se očekává schopnost přednesené algoritmy jednoduše upravovat.

U zkoušky můžete používat své poznámky.

Literatura

Stránku spravuje Martin Mareš