Datové struktury II

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

Přednáška se koná v úterý od 10:40 v S10.

Kvůli karanténním opatřením je fyzická výuka do konce semestru zrušena, takže přednáška probíhá dálkově. Každý týden se tu objeví videozáznam přednášky (někdy z minulých let, někdy nová) a další studijní materiály.

Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares+ds@kam.mff.cuni.cz a domluvíme se.

datum co jsme dělali zdroje video
3. 3. Výpočetní model Word-RAM. Různé způsoby statické reprezentace slovníků. Perfektní hešování FKS v univerzálních systémů funkcí. Deterministické statické slovníky: 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, použití ke konstrukci perfektního hešování. [P01] [FKS] [HMP] [S2.1]
10. 3. Dokončení statických slovníků: randomizovaná konstrukce řádkových permutací, 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. [P01] [HMP] [P02] [G]
17. 3. Podívejte se na videopřednášku (viz odkaz vpravo): Pokračování van Emde-Boasových stromů. 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] 2016-03-09
24. 3. Videopřednáška: 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] 2016-03-16
31. 3. Videopřednáška: 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] 2016-03-23
7. 4. Videopřednáška: 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] 2016-03-30
14. 4. Videopřednáška: 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ů. Konzultace po Zoomu od 11:00. [P05] [M7] [AT] 2016-04-27
21. 4. Videopřednáška: 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. [P05] [P06] [DS] [MS] [MP] 2016-05-11
28. 4. Přednáška po Zoomu od 10:40: 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. [P04] [SE] tabule 2020-04-28
5. 5. Přednáška po Zoomu od 10:40: Union-Find: Amortizovaná analýza komprese cest – O(log n) pro samotnou kompresi, O(α(n)) pro kombinaci s Unionem dle ranku. [P04] [SE] [TL] tabule 2020-05-05
12. 5. Videopřednáška: Ú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] 2016-05-18
19. 5. Videopřednáška: 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] 2016-05-25
26. 5. Konzultace po Zoomu od 10:40.

Zkoušky

Zkoušet budeme dálkově po Zoomu, během léta a v září bude pravděpodobné možné domluvit se i na prezenční zkoušce. Žádné termíny nejsou vypsány, až budete chtít vyzkoušet, ozvěte se mi prosím e-mailem.

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řednášky z let 2016 (včetně videozáznamů) a 2018.

Literatura:

Stránku spravuje Martin Mareš