Datové struktury II

V letním semestru 2025/2026 přednáším Datové struktury II [NTIN067].

Přednáška se koná v úterky od 15:40 v S8.

Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares+ds@kam.mff.cuni.cz a domluvíme se.

datum téma zdroje záznam
17. 2. Výpočetní model Word-RAM. Různé způsoby statické reprezentace slovníků. Perfektní hešování FKS v univerzálních systémů funkcí. Poznámka o třídění reálných čísel. Deterministické statické slovníky: redukce obecného univerza na polynomiální (toliko náčrt) a polynomiálního na kvadratické (n-ární trie), princip permutování bodů v matici, použití ke konstrukci perfektního hešování. [P01] [FKS] [HMP] [S2.1] video (špatný zvuk), starší nahrávka
24. 2. Dokončení statických slovníků: důkaz lemmatu, randomizovaná konstrukce řádkových permutací, derandomizace pomocí podmíněných středních hodnot. Uspořádané celočíselné struktury: van Emde-Boasovy stromy pomocí rekurzivního dělení na přihrádky. [P01] [HMP] [P02] [G] video
3. 3. Uspořádané celočíselné struktury: vEB stromy, jejich hešovaná verze a trik pro implicitní inicializaci paměti. vEB jako binární intervalový strom: jednodušší, ale s pomalejšími updaty; x-fast trie (ukládáme jen jedničky), y-fast trie (zrychlení indirekcí). Úvod do hald: připomenutí binárních a k-regulárních hald. [P02] [E11] [D4] [PLA18] [G] video
10. 3. Haldy: Binomiální, líné bioniální, Fibonacciho. [D4] [PLA18] video
17. 3. Splay stromy: vážená analýza, statická optimalita, static finger bound, working set bound, hypotéza o dynamické optimalitě. [D2.3] [STb] video
24. 3. Úvod do grafových datových struktur. Reprezentace statických cest pomocí intervalových stromů, update vah líným vyhodnocováním. Heavy-light dekompozice stromů. Dynamická dekompozice: Sleatorovy-Tarjanovy Link-Cut stromy. [P03] [STa] video
31. 3. Plán: Link-Cut stromy: reprezentace pomocí propojených Splay stromů. Použití v Dinicově algoritmu na maximální tok. Dynamizace datových struktur: Úplná a částečná přestavba struktury, vzpomínka na BB-α stromy a z nich odvozené 2D intervalové stromy. Rozložitelné vyhledávací problémy a jejich dynamizace rozkladem na bloky: amortizovaná i worst-case semidynamizace, amortizovaná plná dynamizace. Náčrtek dynamických Fusion trees pomocí exponenciálních stromů. [P03] [STa] [STb] [P05] [M7]

Materiály

Předchozí běhy přednášky

Základní zdroje:

Další literatura:

Stránku spravuje Martin Mareš