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). Slajdy jsou pouze doplněk a neslouží jako náhrada skript.
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. Cache-oblivious transpozice ([L 5.3]). Online správa cache pomocí algoritmu LRU (Least Recently Used) a jeho kompetitivní analýza (Sleator-Tarjanova věta – trochu silnější odhad, než je v [L 5.4], ale stačí, když se naučíte to ze skript; viz též [ST2]). Krátký úvod do hešování.
Slajdy, záznam se bohužel z nějakého důvodu neuložil do počítače :-(
11. 11. Hešování jako házení míčků do košů (uniformně náhodně a nezávisle). Střední hodnota počtu kolizí a počtu míčků v jednom koši (tedy velikost řetězce). Velikost nejplnějšího koše (bez důkazu). Souvislost s narozeninovým paradoxem (v uvažovaném modelu mají všichni lidé narozeniny uniformní a nezávisle náhodný den v roce). Hešovací funkce univerzální a k-nezávislé a jak je zkonstruovat: multiply-shift (bez důkazu univerzality), lineární kongruence (s důkazem 2-nezávislosti přes lemma o modulení) a polynomiální (zobecnění důkazů pro lineární kongruenci).
Slajdy, záznam je :-)
Zdroje k hešovacím funkcím: [L 6.1], též [T2], [E]
18. 11. Tabelace (tabulkové hešování, analýza ponechána na cvičení). Řešení kolizí: kukačkové hešování (bez analýzy) a otevřená adresace, konkrétně lineární přidávání (se zjednodušenou analýzou).
Slajdy, záznam bude (bohužel na začátku bez zvuku).
Zdroje ke kukačkovému hešování: [L 6.2] (bohužel jen velmi stručné), [PR] (původní článek), [MU 17.4] (obsahuje analýzu)
Zdroje k lineárnímu přídávání: [L 6.3], [T] (též [E], ale tam se analyzuje "binary probing")
25. 11. Plán: Bloomovy filtry, hešování vektorů a řetězců. Možná též DS pro řetězce.
Slajdy (objeví se před přednáškou)

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