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

Stránku spravuje Martin Mareš