Seminář z grafových algoritmů
... má v LS 2005/2006 podobu přednášky a koná se v pondělky od 15:40 v S6. Zápočet je za zpracování zápisu v TeXu.
Obsah
| datum | téma | zapisovali |
| 6. 3. | Toky v sítích: formulace, základní věty a algoritmy. Převod bipartitního párování a k-souvislosti na toky. | Radovan Šesták |
| 13. 3. | Důkladná analýza Dinicova algoritmu a různých jeho variant. Scalovací algoritmus pro celočíselné kapacity. | Bernard Lidický |
| 20. 3. | Bipartitní párování a k-souvislost pomocí toků i bez nich. Perfektní párování v regulárním bipartitním grafu pomocí degree splittingu. Globální hranová k-souvislost (Nagamochi-Ibaraki) rekurzivně. | Jiří Peinlich & Michal Kůrka |
| 27. 3. | Gomory-Hu Trees: Datová struktura pro efektivní popis všech minimálních řezů v grafu. Základní vlastnosti a algoritmus pro efektivní konstrukci. | Milan Straka |
| 3. 4. | Minimální kostry: základní věty o struktuře MST. Červeno-modrý algoritmus a jeho dualita. Důkazy korektnosti všech klasických algoritmů zdarma. | Martin Kruliš & Petr Sušil |
| 10. 4. | Minimální kostry v rovinných grafech a minor-closed třídách grafů (Borůvkův algoritmus s kontrakcemi a filtrováním). Chytrá a chytřejší implementace Jarníkova algoritmu pomocí Fibonacciho hald. | Petr Škoda & Tomáš Gavenčiak |
| 24. 4. | Výpočetní modely. Počítání na RAMu (triky s bitovými operacemi a násobením; jak udělat z normálního procesoru vektorový). Van Emde-Boasovy stromy. | Zdeněk Vilušínský |
| 15. 5. | Bitově paralelní B-stromy. Q-Heaps a minimální kostra pro celočíselné váhy hran v lineárním čase. Union-Find problem a jeho varianta s předem známou posloupností Unionů. Fredericksonova clusterizace a micro/macro-tree dekompozice. | Aleš Šnupárek & Cyril Strejc |
| 22. 5. | Paběrky z minula (bitový select, jednodušší μ/M-tree dekompozice). Suffixové stromy, jejich vlastnosti a dva lineární algoritmy pro jejich konstrukci (rekurzivní a inkrementální). Převod řetězcových problémů na grafové. | Tomáš Mikula & Honza Král |
Ze zápisů vznikla skriptíčka o grafových algoritmech.
Literatura
- Erik Demaine: Advanced Data Structures (lecture notes)
- Jiří Demel: Grafy (základní algoritmy, Kleeneho algebry)
- Luděk Kučera: Kombinatorické algoritmy (základní algoritmy)
- Alexander Schrijver: Combinatorial Optimization
Jak psát zápisky
V zápiscích z každé přednášky by mělo být shrnuto vše důležité z každé přednášky: definice, základní věty, alespoň kostry důkazů. Zběsilé výpočty je možno vynechávat. Zápis je dobré tu a tam doprovodit obrázkem.
Úprava: nejlépe v plain TeXu, doporučuji použít makra
za účelem psaní zápisků stvořená. Inspiraci najdete v komentářích v sgr.tex
a hlavně ve zdrojácích již vystavených zápisků. Pokud máte jakékoliv problémy se sazbou,
ozvěte se, rád pomohu.