Přednáška z Datových struktur I (NTIN066)

úterý od 9:00 v S5, ZS 25/26

„Ranní ptáče dál doskáče.“

Stránka přednášky Pavla Veselého z Datových struktur I, kde budeme probírat pokročilé techniky pro návrh a analýzu datových struktur a některé jejich praktické aspekty (např. chování ke keším procesoru). Představu o přednášce si můžete udělat z loňské přednášky Jirky Finka.

Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po přednášce. Také budu rád, když se během cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi emailem nebo před/po přednášce. Někdy mě můžete též najít v kanceláři S326 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře naproti učebně S3), ale je lepší se ozvat předem.

Pokud nemůžete přijít (nemoc, izolace, ...), pusťte si stream (pokusím se zprovoznit), podívejte se na záznam (podaří-li se ho pořídit) nebo si nastudujte příslušnou část skript (viz odkazy na sekce níže).

Cvičení povedou: Jirka Fink, Petr Chmel, Pavel Veselý. (Poznámka: o naplnění kapacity víme. Jelikož do S7 se už víc lidí nevejde, zapisujte se prosím do fronty na cvičení v S1.)

Podmínky zápočtu a pravidla. Zkouška bude ústní s písemnou přípravou z teorie z přednášky, bližší informace budou v prosinci.

Co jsme dělali / plán

U každého tématu jsou odkazy do skript. Na záznamech je hlavně tabule, slajdy najdete níže (objeví se vždy před přednáškou).
30. 9. Úvodní informace o předmětu. Amortizace: nafukovací pole (analýza agregací) a binární počítadlo (tři důkazy: agregací, penízkovou metodou a potenciálem). Zavedení amortizované složitosti pomocí potenciálů. Dynamické pole, tedy implementace zásobníku polem (nedokončeno, jen naznačen potenciál, zbytek na cvičení).
Slajdy a záznam (bohužel se ne vždy pořadilo správně natočit kameru, někdy je tedy tabule se zpožděním).
Hlavní zdroje: [P 9.1-9.3] a [L 1.1-1.3].
7. 10. Zaskočil Petr Chmel: Amortizace a stromové datové struktury pro uspořádané množiny: Líně vyvažované stromy (BB[alfa]) a samovyvažovací (Splay stromy), konkrétně operace Splay a analýza jeji amortizované ceny.
Slajdy (skončili jsme na slajdu 23) a záznam.
Hlavní zdroje: [P 9.4-9.5] a [L 1.4, 2.1], též [ST]
Další: Vizualizace splay stromů a tahák na splay stromy od Ondry Mičky.
14. 10. Dokončení Splay stromů: operace Find, Insert a Delete pomocí Splay a jejich amortizovaná složitost ([L 2.2], [P 9.5]), pokročilé vlastnosti (bez důkazů, [L 2.3]). (a,b)-stromy: definice, hloubka, operace Find, Insert a Delete a amortizovaná analýza počtu změn stromu.
Slajdy a záznam.
Hlavní zdroje pro (a,b)-stromy: [L 3], též [P 8.3] (ale bez amortizované analýzy)
21. 10. Dokončení (a,b)-stromů (top-down operace). Efektivní algoritmy pro paměťové hierarchie: teoretické modely (I/O model, cache-aware, cache-oblivious), (a,b)-stromy (cache-aware nastavení a,b), třídění MergeSortem a k-cestným MergeSortem (cache-aware), transpozice (zatím jen cache-aware).
Slajdy a záznam (zvuk bohužel obsahuje ozvěnu, mikrofon zřejmě zachytil reproduktory).
Hlavní zdroje k algoritmům pro paměťové hierarchie: [L 5.1-5.3], též [CO], kde je hlavně dobře popsaný model, ale není tam rozebrána transpozice
28. 10. Plán: státní svátek: slavíme Den vzniku samostatného československého státu. Můžete oslavit třeba s cache-oblivious datovými strukturami.
4. 11. Plán: cache-oblivious transpozice

Literatura, zdroje, odkazy, videa, ...

Zdroje k úkolům: Další videa: Další knihy v angličtině:

Podmínky zápočtu a pravidla

Zápočet bude za zisk alespoň 75 bodů z úkolů v recodexu. Zadáme alespoň sedm implementačních úkolů po 10 bodech a alespoň tři experimentální po 15 bodech, tedy půjde získat alespoň 115 bodů (a nějaké bonusové navíc). Na každý úkol budou alespoň dva týdny (ke konci semestru více).

Implementační úkoly:

Experimentální úkoly

Všeobecná pravidla