Grafové algoritmy II

V letním semestru 2017/2018 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.

Přednáška se bude konat ve čtvrtky od 9:00 v S4.

datum co se přednášelo [zdroje]
1. 3. Verifikace minimality kostry: redukce hloubky pomocí Borůvkových stromů, Komlósův algoritmus. [S 3.3]
8. 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].
15. 3. Hrátky s přihrádkovým tříděním: klestění multihran, isomorfismus stromů, unifikace posloupností. Kanonické kódování označkovaných grafů [S 2.2].
22. 3. Přednáška se nekoná.
29. 3. Topologické výpočty a kanonické kódy grafů [S 2.2]. 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, dávkové zpracování mikrostromů. 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.
5. 4. Dokončení verifikace minimální kostry [B]. Úvod do soft-hald: definice [H].
12. 4. Soft-haldy: průběh operací, invarianty, analýza časové složitosti (tahák) [H].
19. 4. Zpět k minimálním kostrám: lemma o robustních kontrakcích, clusterovací algoritmus [S4.2].
26. 4. Minimální kostry: rozhodovací stromy [S4.3], konečně optimální algoritmus [S4.4].
3. 5. Datová struktura pro dynamické udržování komponent souvislosti (Holm-de Lichtenberg-Thorup) [S5.2, S5.3].
10. 5. Dolní odhad na dynamickou souvislost [PD].
17. 5. Pokračování z minula.
24. 5. Gomoryho-Huovy stromy (vlastnosti, existence, efektivní konstrukce) [G4].

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. Ke zkoušce si můžete přinést tahák na jedné straně formátu A4.

Z následujících okruhů si vyberte jeden, který budete znát do detailů. O ostatních okruzích byste měli mít základní přehled: rozumět definicím, větám a algoritmům.

Literatura

Stránku spravuje Martin Mareš