Datové struktury I

V zimním semestru 2023/2024 přednáším Datové struktury I [NTIN066]. Přednášky se konají ve středu od 9:00 v S3. Anglická verze předmětu se bude přednášet až v letním semestru.

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

Přečtěte si prosím pravidla hry.

datum co jsme dělali zdroje video
4. 10. Co je to datová struktura – rozhraní/implementace, statičnost/dynamičnost, výpočetní model. Příklady rozhraní: fronta, množina, slovník, uspořádaná množina, multimnožina. Různé způsoby amortizované analýzy: agregace, účtování, penízky. Příklady amortizace: nafukovací pole (se zvětšováním a zmenšováním), binární počítadlo. [L01] [P9.1-9.2] video
11. 10. Amortizovaná analýza pomocí potenciálů. Líně vyvažovaná varianta BB[α] stromů. Splay stromy: Operace Splay a definice potenciálu. [L01] [L02] [P9.3-9.5] [ST] video
18. 10. Splay stromy: Amortizovaná analýza, implementace operací Find, Insert a Delete pomocí Splay. Zmínka o dalších vlastnostech: sekvenční průchod, statická optimalita, dynamická optimalita, working set bound. [L02] [P9.5] [ST] video
25. 10. (a,b)-stromy: definice, logaritmická hloubka, Find, Insert a Delete, volba parametrů. Amortizovaná analýza (a,2a-1) a (a,2a)-stromů. Štěpení/slučování shora dolů. Ekvivalence (2,4)-stromů s červeno-černými stromy. [L03] [P8.3] video
1. 11. Úvodní příklad s rychlostí přístupu do paměti. Paměťová hierarchie: teoretické modely – I/O, cache-aware, cache-oblivious. Algoritmy s cachemi: sekvenční průchod polem, třídění – MergeSort a zmínka o FunnelSortu a dolních odhadech. Transpozice matice: cache-aware dlaždičkování, cache-oblivious rozděl & panuj. [L05] [CO] video
8. 11. Cache-oblivious algoritmy: analýza rekurzivní transpozice matice. Model kontra realita – Sleatorova-Tarjanova věta o kompetitivitě LRU. Hešování: přihrádky se seznamy (separované řetězce). Volba hešovacích funkcí: c-univerzální systémy funkcí, střední velikost přihrádky, časová složitost hešování s řetězci, k-nezávislost. [L05] [CO] [ST2] [L06] [P11.3] [P11.5] video
15. 11. Konstrukce systémů hešovacích funkcí: systémy lineárních funkcí (1-univerzalita a 2-nezávislost), obecná lemmata o modulení, k-nezávislý systém polynomů, multiply-shift, tabelace. Kukaččí hešování. [L06] [P11.5] [T2] video
22. 11. Hešování s lineárním přidáváním a jeho analýza. [L06] [T] [KS] video
29. 11. Hešování vektorů a řetězců: skalární součiny, polynomy, lemma o skládání systémů. Bloomovy filtry: 1-pásmové, k-pásmové, zmínka o počítacích. [L06] [T2] video
6. 12. Vícerozměrné datové struktury: intervalové dotazy na binárních stromech, k-d stromy, intervalové stromy (range trees, zatím 2D). [L07] [G] [M7.2.1] video
13. 12. Vícerozměrné datové struktury: range trees v libovolné dimenzi, jejich dynamizace částečnou rekonstrukcí a zrychlení pomocí kaskádování. Datové struktury pro řetězce: suffixové pole, rankové pole, LCP pole (nejdelší společné prefixy). Aplikace: hledání podřetězců, nejdelší opakující se podřetězec, nejdelší společný podřetězec dvou řetězců. [L07] [L08] video
20. 12. Řetězcové DS: Konstrukce LCP pole v lineárním čase (Kasaiův algoritmus). Konstrukce suffixového pole v čase O(n log n) zdvojováním, v čase O(n + Sort(n, Σ)) algoritmem Skew. Poznámka o suffixových stromech. [L08] video
3. 1. Paralelní DS: model PRAM/CRCW, zamykání a problémy s ním. Zamykání v binárních vyhledávacích stromech a (a,b)-stromech. Atomická primitiva. Bezzámkový zásobník Pro zábavu: The Deadlock Empire. [L09] video
10. 1. Bezzámkové DS: pokračování zásobníku, problém ABA, správa paměti. Zmínka o wait-free DS. Něco navíc (nezkouší se): Obecnější zlomkové kaskádování. [L09] video

Cvičení

Cvičení se konají každý týden, zapište se na jedno z nich v SISu.

Zadání domácích úkolů najdete v ReCodExu, řešení se odevzdávají tamtéž. Založte si prosím účet a přihlašte se do skupiny k vašemu cvičení. Další materiály k úkolům (zejména zdrojové kódy) najdete v gitovém repozitáři. Také si je můžete prohlédnout na webu.

Zkoušky

Termíny (včetně předtermínů) jsou vypsané v SISu, přihlašujte se prosím tam. Pokud vám žádný termín nevyhovuje, ozvěte se, vyzkouším vás jindy.

Podívejte se na podrobné požadavky ke zkoušce.

Ke zkoušce není potřeba zápočet.

Materiály

Stránku spravuje Martin Mareš