Datové struktury II

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

Přednášky se konají ve středu od 14:00 v S9.

Z přednášek vznikají videozáznamy, též jsou zde k dispozici poznámky, které jsem si sepsal při přípravě přednášky (o srozumitelnosti nic neslibuji).

datum co jsme dělali zdroje video
24. 2. Výpočetní model Word-RAM. Různé způsoby statické reprezentace slovníků. Perfektní hešování FKS (Fredman, Komlós, Szemerédi 1984): dvojstupňová konstrukce z univerzálního hešování. Zmínka o třídění reálnych čísel. 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. [P01] [FKS] [HMP] [S2.1] 02-24
2. 3. Dokončení statických slovníků: randomizovaná konstrukce řádkových permutací, použití ke konstrukci perfektního hešování, derandomizace pomocí podmíněných středních hodnot. [P01] [HMP] 03-02 [část]
9. 3. Uspořádané celočíselné struktury: van Emde-Boasovy stromy pomocí rekurzivního dělení na přihrádky. Trik s implicitní inicializací paměti. vEB interpretovaný jako binární intervalový strom: jednodušší, ale pomalejší aktualizace. Zrychlení aktualizací pomocí indirekce. [P02] [G] [E11] 03-09
16. 3. Snižujeme prostorové nároky vEB: x-fast a y-fast stromy. Bitové triky: simulace vektorového počítače na RAMu. Fusion trees: Fusion nodes, komprese trie pomocí sketchů, vyhodnocování ranku ze sketchů. [P02] [E11,12] [S2.4] [FW] 03-16
23. 3. Technické detaily Fusion trees – další bitové triky: pozice nejvyšší jedničky, místo sketchů pseudosketche. Ú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ů. [P02] [E12] [S2.4] [FW] [P03] 03-23
30. 3. Statické struktury založené na heavy-light dekompozici. Dynamická dekompozice: Sleatorovy-Tarjanovy Link-Cut stromy a jejich reprezentace pomocí propojených Splay stromů. [P03] [STa] [STb] 03-30
6. 4. Přednáška se nekoná, zato 13. 4. servírujeme dvojnásobnou porci. — —
13. 4. Poznámka o aplikaci Link-Cut stromů: zrychlení Dinicova algoritmu na maximální tok. 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 pomocí inverzní Ackermannovy funkce. [P04] [SE] [TL] 04-13
20. 4. Úvod ke geometrickým datovým strukturám v Rd. Vícerozměrné intervalové stromy (statická verze), zrychlení dotazu na O(logd-1 n + k) pomocí fractional cascadingu, zrychlení na O(logd-2 n + k) přidáním geometrických triků. Obecný princip fractional cascadingu. [P05] [E3] [E4] [CGa] [CGb] 04-20
27. 4. Dynamizace datových struktur: Úplná a částečná přestavba struktury, BB-α stromy, 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ů. [P06] [M7] [AT] 04-27
4. 5. Přednaška se nekoná, jeť rektorský sportovní den.
11. 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. [P06] [P07] [DS] [MS] [MP] 05-11
18. 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] 05-18
25. 5. 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). [P09] [CB] 05-25

Zkoušky

Předtermín se koná 25. května po poslední přednášce. Přihlašujte se prosím v SISu.

Další termíny jsou vypsány během zkouškového, opět prosím o přihlašování v SISu. Pokud vám žádný termín nevyhovuje, ozvěte se, vyzkouším vás jindy.

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

Stránku spravuje Martin Mareš