Vybrané kapitoly z datových struktur
V zimním semestru 2024/2025 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 úterky od 15:40 v pracovně S322. Začínáme 8. 10.
Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares@kam.mff.cuni.cz a domluvíme se.
| datum | téma |
|---|---|
| 8. 10. | LO: Persistentní deque a c-steque. |
| 15. 10. | LO: Konfluentně persistentní trie. |
| 22. 10. | MM: Úvod do úsporných datových struktur. Reprezentace binárních stromů à la halda. Indexy pro Rank a Select v sublineárním prostoru. Reprezentace pěstovaných a binárních stromů pomocí závorek. |
| 29. 10. | MM: Match a Enclose na posloupnosti závorek. |
| 5. 11. | Přednáška se nekoná: děkanský sportovní den |
| 12. 11. | LO: Konfluentně persistentní trie: funkcionální worst-case link-cut stromy (Expose, Conceal a udržování prstů), nastavení vah pro biased trees. Rychlejší persistentní, ale nefunkcionální trie: persistentní hešovací tabulky, biased tabulky. |
| 19. 11. | MM: Ještě k závorkám: Rank a Select na uniformně řídkých množinách. Choice dictionaries a párovací struktura pro neinicializovanou paměť. |
| 26. 11. | LO: Persistence: částečně a plně persistentní pole (viz disertace Milana Straky), použití y-rychlých trií, redukce složitosti z O(log log počet_verzí) na O(log log n), konstrukce persistentní hešovací tabulky. Úvod do biased trees. |
| 3. 12. | LO: Biased trees. |
| 10. 12. | MM: Choice dictionaries: iterátory statické i dynamické, aplikace na BFS, 2-colored choice dictionary, úvod k c-colored. |
| 17. 12. | MM: Choice dictionaries: 2f-colored verze, komprese bloků, náznak řešení pro obecný počet barev. |
| 7. 1. | Plán: MM: Úsporné struktury: Prefixový kód pro posloupnosti předem neznámé délky. Lemma o mixérech. Reprezentace řetězců nad obecnou abecedou. |
Zdroje
- Persistentní struktury:
- Kaplan, Tarjan: Persistent Lists with Catenation via Recursive Slow-Down (deque, c-steque)
- Demaine, Langerman, Price: Confluently Persistent Tries for Efficient Version Control
- Straka: Functional Data Structures and Algorithms (disertační práce)
- Bent, Sleator, Tarjan: Biased Search Trees
- Sleator, Tarjan: A data structure for dynamic trees
- Úsporné struktury:
- Demaine: Advanced Data Structures, přednáška 17 (Rank a Select, reprezentace stromů)
- Geary et al.: A simple optimal representation for balanced parentheses (Match a Enclose)
- Dodis, Pătrașcu, Thorup: Changing base without losing space (řetězce nad obecnou abecedou)
- Choice dictionaries:
- Hagerup: Small Uncolored and Colored Choice Dictionaries (základní verze)
- Hagerup, Kammer: Succinct choice dictionaries (aplikace)
- Kammer, Sajenko: Simple 2f-Color Choice Dictionaries
Zkoušky
Na zkoušku se zapište v SISu nebo domluvte na jindy e-mailem.
Můžete si přinést tahák. Jedinou podmínkou je, že jste ho vytvořili sami.
Odkazy
- 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