Seminář z grafových algoritmů
V LS 2008/2009 bude mít seminář převážně formu přednášky. Téma se bude točit zejména okolo minimálních koster, efektivního počítání v pointerových výpočetních modelech a okolo implicitních reprezentací grafů. Scházet se budeme v pátky od 12:20 v S1.
Co jsme dělali
| datum | téma |
|---|---|
| 6. 3. | Opakování základních vět o minimálních kostrách. Verifikace koster a hledání lehkých hran (Komlósův algoritmus). Trik s Borůvkovými stromy. |
| 13. 3. | Pokračování verifikace koster. Randomizovaný algoritmus na minimální kostru s průměrně lineární časovou složitostí (Karger-Klein-Tarjan). |
| 20. 3. | Seminář odpadá |
| 27. 3. | Martin Kupec: Persistentní datové struktury. |
| 3. 4. | Soft-haldy: definice, popis operací a příklad použití. |
| 10. 4. | Soft-haldy: rozbor. |
| 17. 4. | Martin Kupec: Persistentní datové struktury. |
| 24. 4. | Pointerové algoritmy: různé definice výpočetního modelu. Přihrádkové třídění založené na ukazatelích a jeho aplikace: unifikace posloupností, isomorfismus stromů. Union-Find problem v pointerovém provedení. |
| 1. 5. | Seminář odpadá |
| 8. 5. | Seminář odpadá |
| 15. 5. | Plán: Ackermannova funkce a její chování. Verifikace minimality kostry v lineárním čase. |
| 22. 5. | Plán: Optimální algoritmus na minimální kostru. |
Odkazy
- The Saga of Minimum Spanning Trees (zde najdete většinu věcí o kostrách)
- Minulý ročník semináře