Datové struktury I

V zimním semestru 2019/2019 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 se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S322 na Malé Straně. Případně napište e-mail na adresu mares+ds@kam.mff.cuni.cz.

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. Plán: Cache-oblivious algoritmy: model, jednoduché příklady, transpozice matice.

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.

Materiály

Stránku spravuje Martin Mareš