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. Plán: Splay stromy: vážená analýza, statická optimalita, static finger bound, working set bound, hypotéza o dynamické optimalitě. [D2.3] [STb]

Materiály

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

Základní zdroje:

Další literatura:

Stránku spravuje Martin Mareš