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 odvolání 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. Podívejte se na videopřednášku (viz odkaz vpravo): 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. Podívejte se na videopřednášku (viz odkaz vpravo): 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

Materiály

Přednášky z let 2016 (včetně videozáznamů) a 2018.

Literatura:

Stránku spravuje Martin Mareš