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 (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. Bloomovy filtry, hešování vektorů a řetězců, lemma o kompozici.
Slajdy (s drobnou opravou), záznam.
Zdroje k Bloomovu filtru: [L 6.4], též [SSBD 2.7]
Zdroje k hešovacím funkcím: [L 6.1], též [T2], [E]
2. 12. Sufixová pole a stromy: opakování trie (písmenkového stromu) a komprimované trie. Sufixový strom a jeho základní aplikace (vyhledávání jehly a nejdelší opakující se podslovo). Sufixové pole, vyhledávání jehly binárním vyhledáváním, LCP pole a použití na nejdelší opakující se podslovo (další aplikace jako cvičení). Výpočet sufixového pole, tedy řazení sufixů, zdvojováním. Výpočet LCP pole ze sufixového pole: jen začátek (lemma o posunu o znak), pokračování příště.
Slajdy (záznam bohužel není z důvodu špatného nastavení, příště snad zase bude :-)
Zdroje k sufixovým stromům a polím: [P 13.5-13.7] a [L 8] (trochu stručnější a bez sufixových stromů)
9. 12. Sufixová pole: dokončení výpočtu LCP pole ze sufixového. Stručně lineární algoritmus Skew pro sufixové pole (Skew se nezkouší). Bonusové téma (zkouší se jen na jedničku): FM-index pomocí Burrowsovy-Wheelerovy transformace a ranku na bitovým vektorem.
Slajdy a záznam.
Zdroje ke kontrukci sufixového a LCP pole: [P 13.6] a [L 8]
Pracovní poznámky k FM indexu (dejte mi prosím vědět, kdybyste viděli chyby), původní článek je [FM] (přednesen jen základní algoritmus ze sekce 3.1)
16. 12. Informace ke zkouškám (viz slajd č. 2). Geometrické DS a zpracování vícedimenzionálních intervalových dotazů (výpis nebo počítání bodů): 1D případ přes vyvážené BVS, k-d stromy (statických 2D případ, příklad času alespoň sqrt(n) na RangeQuery ve 2D; dynamizace jen velmi stručně), Range trees: statický případ (2D i vícedimenzionální), dynamický případ (jen 2D pro Insert přes líně vyvažované BVS). Vynecháno zrychlení range query pomocí zlomkového kaskádování (bude na cvičení). Krátká zmínka o Quadtree.
Slajdy a záznam.
Zdroje ke geometrickým DS: [L 7], též [G 5] nebo [H].
23. 12. volno, příprava na Vánoce.
30. 12. volno, příprava na Silvestr.
6. 1. Paralelní DS: PRAM model (varianta CREW). Zámky a problémy s nimi (hlavně deadlock a jak se mu vyhnout), použití na top-down verzi (a,b)-stromů (korektnost stručně přes serializovatelnost). Bezzámkové DS pomocí atomických operací (CAS, LL/SC) a zásobník pomocí CAS. Problém ABA a jeho řešení. Problémy s dealokací paměti pro uzly a jejich možná řešení (stručně). Na konci velmi stručně zlomkové kaskádování pro zrychlení range query pro Range trees ve 2D (více detailů ve skriptech).
Slajdy a záznam.
Zdroje k paralelním DS: [L 9], též [H kap. 48]. Můžete se též naučit z předloňské přednášky Martina Mareše

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