Datové struktury II

V letním semestru 2017/2018 přednáším Datové struktury II [NTIN067].

Přednáška se koná v pondělky od 17:20 v S8.

datum co jsme dělali zdroje
26. 2. Výpočetní model Word-RAM. Různé způsoby statické reprezentace slovníků. Deterministické statické slovníky (Hagerup, Miltersen, Pagh 2000): redukce obecného univerza na polynomiální (toliko náčrt) a polynomiálního na kvadratické (n-ární trie), princip permutování bodů v matici. Randomizovaná konstrukce řádkových permutací, použití ke konstrukci perfektního hešování. [P01] [HMP] [S2.1]
5. 3. Dokončení statických slovníků: derandomizace pomocí podmíněných středních hodnot. Uspořádané celočíselné struktury: van Emde-Boasovy stromy pomocí rekurzivního dělení na přihrádky. Trik s implicitní inicializací paměti. [P01] [HMP] [P02] [G]
12. 3. Přednáška se nekoná. —
19. 3. vEB interpretovaný jako binární intervalový strom: jednodušší, ale pomalejší aktualizace. Zrychlení aktualizací pomocí indirekce. Snižujeme prostorové nároky vEB: x-fast a y-fast stromy. Bitové triky: simulace vektorového počítače na RAMu. [P02] [E11] [S2.4]
26. 3. Fusion trees: Fusion nodes, komprese trie pomocí sketchů, vyhodnocování ranku ze sketchů. Další bitové triky: pozice nejvyšší jedničky, místo sketchů pseudosketche. [P02] [E11,12] [S2.4] [FW]
2. 4. Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace. —
9. 4. Úvod do grafových datových struktur. Reprezentace statických cest pomocí intervalových stromů, update vah líným vyhodnocováním. Heavy-light dekompozice stromů. Dynamická dekompozice: Sleatorovy-Tarjanovy Link-Cut stromy a jejich reprezentace pomocí propojených Splay stromů. Na rozmyšlení: zrychlení Dinicova algoritmu na maximální tok. [P03] [STa] [STb]
16. 4. Intermezzo: Statická struktura pro intervalové vyhodnocování asociativní operace. Inkrementální udržování komponent souvislosti (Union-Find): stromová reprezentace, Union dle ranku, komprese cest. Analýza komprese cest: rozkladové lemma. [P04] [SE] [TL]
23. 4. Dokončení z minula: samotná komprese cest zaručí amortizovanou složitost O(log n), kombinace s unionem dle ranku O(α(n)). [P04] [SE]
30. 4. Dynamizace datových struktur: Úplná a částečná přestavba struktury, vzpomínka na BB-α stromy a z nich odvozené 2D intervalové stromy. Rozložitelné vyhledávací problémy a jejich dynamizace rozkladem na bloky: amortizovaná i worst-case semidynamizace, amortizovaná plná dynamizace. Náčrtek dynamických Fusion trees pomocí exponenciálních stromů. [P05] [M7] [AT]
7. 5. Persistence: efermérní, semipersistentní, plně persistentní a funkcionální datové struktury. Techniky: kopírování cest, tlusté vrcholy, jejich kombinace. Obecná transformace ukazatelových datových struktur na semipersistentní, náčrt rozšíření na plně persistentní. Udržování lineárního uspořádání (list order, list labelling, ordered file maintenance). Aplikace: lokalizace bodu v rovině, cache-oblivious B-stromy (ty pouze naznačeny, stejně jako detaily OFM). [P05] [P06] [DS] [MS] [MP]
14. 5. Přednáška čistě virtuální: podívejte se na záznam. Proudové zpracování dat: Deterministické hledání majoritních a častých prvků (alespoň n/k výskytů; Misrův-Griesův algoritmus). Aproximace častých prvků (Count-Min). Pravděpodobnostní aproximace počtu různých prvků (Alon, Matias, Szegedy). [P07] [CB]
21. 5. Úsporné (succinct) datové struktury: Prefixový kód pro posloupnosti předem neznámé délky. Lemma o mixérech. Reprezentace řetězců nad obecnou abecedou. [P08] [DPT]

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 je třeba znát látku z přednášky (datové struktury a tvrzení o nich, viz podrobné požadavky ke zkoušce), rozumět jí a umět ji aplikovat.

Na zkoušku si smíte vzít tahák o velikosti jedné strany A4.

Materiály

Předloňská přednáška (včetně videozáznamů)

Literatura:

Stránku spravuje Martin Mareš