Vybrané kapitoly z datových struktur
V zimním semestru 2025/2026 přednášíme s Lukášem Ondráčkem o pokročilých datových strukturách [NTIN110]. Cílem je podívat se o něco dále, než kam dohlédneme v základním magisterském kursu Datové struktury 1+2. Předmět si můžete zapisovat opakovaně, každý rok děláme něco jiného.
Přednáška se koná v pondělky od 15:40 v pracovně S322.
Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares@kam.mff.cuni.cz a domluvíme se.
| datum | téma |
|---|---|
| 6. 10. | MM: Opakování základů hešování: c-univerzalita, (k,c)-nezávislost. Tabelační hešování: definice, 3-nezávislost, ale už ne 4-nezávislost, charakterizace nezávislých k-tic. |
| 13. 10. | MM: Odhad počtu nezávislých k-tic. Analýza (statického) kukaččího hešování s tabelací: překážky, dvojcykly, odhad pravděpodobnosti existence dlouhých nezávislých tahů a nezávislých dvojcyklů. |
| 20. 10. | Plán: MM: Kukačka: Trojzubce a lasa. Kuličky a přihrádky, trik s d hešovacími funkcemi, tie breaking, odhady zaplnění pro plnou náhodnost. Hešovací (hyper)grafy. |
Zdroje
- Skriptíčka k datovým strukturám, kapitola o hešování
- Tabelační hešování
- Aamand, Knudsen, Thorup: Power of d Choices with Simple Tabulation
Odkazy
- VKDS 2024: persistentní struktury, úsporné struktury
- VKDS 2023: cache-oblivious třídění + datové struktury, zlomkové kaskádování
- VKDS 2022: Q-haldy, Fusion trees, exponenciální stromy, redukce univerza na polynomiální, Marked ancestor a dolní odhad na něj
- VKDS 2021: streaming algoritmy, analýza kukaččího hešování
- VKDS 2020: celočíselné struktury, randomizované stromy, zlomkové kaskádování, lock/wait-free struktury
- PDS 2019: rankové vyvážené stromy, kompetitivní dynamické stromy, cache-oblivious struktury, p/q-fast trie