Seminář z grafových algoritmů

V LS 2011/2012 má seminář formu přednášky. Přednáším o hlubších partiích teorie minimálních koster, vztazích mezi výpočetními modely a speciálních datových používaných pro ukládání celých čísel.

Seminář se koná ve čtvrtky od 15:40 v S8.

Program semináře

datum téma
23. 2. Opakování základních vět o minimálních kostrách. Různé varianty Borůvkova a Jarníkova algoritmu. Výpočetní modely RAM a PM, vztahy mezi nimi. [S1, S2.1]
1. 3. RAMové triky: vektorové operace, MSB a LSB v konstantním čase. Úvod do Q-hald. [S2.3–2.5]
8. 3. Q-haldy. [S2.5] (Navíc jsem ukazoval konstrukci dekodéru pro x[B] a opravu chyby, která se nakonec ukázala nebýt chybou.)
15. 3. Verifikace minimality kostry: redukce hloubky pomocí Borůvkových stromů, Komlósův algoritmus. [S3.3]
22. 3. Verifikace minimality kostry: počítáme porování. Kargerův-Kleinův-Tarjanův randomizovaný algoritmus na minimální kostru. [S3.3, S3.5]
29. 3. Seminář odpadá.
5. 4. Hrátky s přihrádkovým tříděním: klestění multihran, isomorfismus stromů, unifikace posloupností. Topologické výpočty na grafech a kanonické kódy. [S2.2]
12. 4. Seminář odpadá.
19. 4. Verifikace minimality koster na Pointer Machine. [B]
26. 4. Soft haldy: definice a základní invarianty. [H]
3. 5. Soft haldy: dokončení analýzy. [H]
10. 5. Zpět k minimálním kostrám: lemma o robustních kontrakcích a clusterovací algoritmus. [S4.2]
17. 5. Optimální algoritmus na minimální kostry. [S4.3–4.4]
24. 5. Jak násobit čísla v lineárním čase (v různých výpočetních modelech). [A4.3.3]

Odkazy

Stránku spravuje Martin Mareš