Datové struktury I

V zimním semestru 2019/2020 přednáším Datové struktury I [NTIN066]. Přednášky se konají v pondělí od 10:40 v S9. 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.

Pokud se vám datové struktury líbí, přijďte také na cvičení z Analýzy datových struktur.

datum co jsme dělali zdroje
7. 10. Co je to datová struktura – rozhraní/implementace, statičnost/dynamičnost, výpočetní model. Příklady rozhraní: fronta, množina, uspořádaná množina, slovník. Různé způsoby amortizované analýzy: agregace, účtování, penízky, potenciál. Příklady amortizace: nafukovací pole (se zvětšováním a zmenšováním), binární počítadlo. [L01] [P9.1–9.3]
14. 10. Líně vyvažovaná varianta BB[α] stromů. Splay stromy: Operace Splay a její amortizovaná analýza. Implementace operací Find, Insert a Delete pomocí Splay. [L02] [P9.4–9.5] [ST]
21. 10. Splay stromy: důkaz věty o amortizované ceně Splaye. Zmínka o dalších vlastnostech: sekvenční průchod, statická optimalita. (a,b)-stromy: definice, logaritmická hloubka, Find, Insert a Delete, volba parametrů. [L02] [P9.5] [ST] [L03] [P8.3]
28. 10. Přednáška se nekoná: Slavíme státní narozeniny.
Za domácí úkol se naučte věty o amortizovaném chování (a,2a-1) a (a,2a)-stromů z Lecture Notes. 		[L03]
4. 11. Haldy: rozhraní hald, d-regulární haldy, použití v Dijkstrově algoritmu. Halda binomiální, líná binomiální a Fibonacciho. [L04] [P4.2, 6.2, 18]
11. 11. Cache-oblivious algoritmy: Příklady rychlosti přístupu do paměti, zjednodušený popis hardwarové keše, množinová asociativita a aliasing. Teoretické modely: I/O, cache-aware, cache-oblivious. Scanování pole. Třídění: Mergesort, vícecestný Mergesort, zmínka o Funnelsortu a dolním odhadu. Transpozice matice: dlaždice a cache-aware algoritmus. [L05] [CO]
18. 11. Cache-oblivious algoritmy: Transpozice matice. Model kontra realita – Sleatorova-Tarjanova věta o kompetitivitě LRU. Hešování: c-univerzální systémy funkcí, očekávaná délka řetězce. [L05] [CO] [ST2] [L06] [P11.3] [P11.5]
25. 11. Hešování: c-univerzální a k-nezávislé systémy funkcí a jejich konstrukce. Systémy lineárních funkcí: 1-univerzalita, 2-nezávislost. Obecné lemma o nezávislosti modulo m. Další systémy: k-nezávislý systém polynomů, multiply-shift. [L06] [P11.5] [T2]
2. 12. Tabelační hešování. Kukaččí hešování. Hešování s lineárním přidáváním a jeho analýza. [L06] [KS] [T] [T2]
9. 12. Bloomovy filtry: 1-pásmové, k-pásmové, počítací. Hešování vektorů a řetězců: skalární součiny, okénkové hešování z polynomů, obecné lemma o skládání systémů funkcí (bez důkazu). [L06] [T2]
16. 12. Vícerozměrné datové struktury: intervalové dotazy na binárních stromech, k-d stromy, intervalové stromy (range trees), jejich dynamizace částečnou rekonstrukcí a zrychlení pomocí kaskádování. [L07] [G] [M7.2.1]
6. 1. 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ů. Konstrukce LCP pole v lineárním čase (Kasaiův algoritmus). Konstrukce suffixového pole v čase O(n log n) zdvojováním. [L08]

Cvičení

Cvičení se konají každý týden, zapište se na jedno z nich v SISu. Primárně mají charakter konzultace, proto je na ně v rozvrhu vyhrazena dvouhodinovka, přestože oficiálně mají formát 0/1.

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

Předtermín se koná 17. prosince od 9:30 v S322. Přihlašujte se prosím e-mailem.

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š