Vybrané kapitoly z datových struktur
V zimním semestru 2022/2023 přednáším 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á ve středu od 15:40 v 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 |
|---|---|
| 5. 10. | Opakování: výpočetní model Word-RAM a jeho varianty (Céčkové instrukce vs. AC0), vEB stromy, statické slovníky FKS. Vektorové výpočty pomocí aritmetiky. Fusion trees: high-level pohled. |
| 12. 10. | Fusion nodes: základní myšlenka, sketche a pseudosketche. Dynamizace pomocí exponenciálních stromů. |
| 19. 10. | Dokončení exponenciálních stromů. Q-haldy: předvýpočet funkcí, aplikace na minimální kostry, stav struktury, výpočet ranku, udržování setřiděné množiny. |
| 26. 10. | Q-haldy: udržování guidů, Insert a Delete, dekodér. |
| 2. 11. | AF-haldy a atomické haldy. Úvod k redukci univerza. |
| 9. 11. | Místo přednášky se koná cvičení (v Hostivaři) – je Děkanský sportovní den. |
| 16. 11. | Redukce univerza na polynomiální: samoopravné kódy z (2,2)-nezávislých systémů funkcí, hledání malé množiny rozlišujících bitů. |
| 23. 11. | Poslední krok redukce univerza: pseudo-sketche a Ramanovo perfektní hešování založené na rodině funkcí multiply-shift. |
| 30. 11. | Problém označeného předka (Marked ancestor): datová struktura založená na vEB stromech a mikro/makro dekompozici. Dolní odhad: model cell-probe, formulace odhadu pro paritní verzi problému, náčrtek důkazu. |
| 7. 12. | Dolní odhad na Marked ancestor: notace a lemma o pokrytích. |
| 14. 12. | Dolní odhad na Marked ancestor: ekvivalence updatů, rozklad množiny registrů a jeho vlastnosti. |
| 21. 12. | Dolní odhad na Marked ancestor: zbytek důkazu. Důsledky pro složitost dalších struktur (2D obdélníkové dotazy, prioritní vyhledávací stromy, Union-Find). |
| 4. 1. | Trable s asymptotikou ve více proměnných. |
Zdroje
- Vektorové výpočty na RAMu:
- Mareš: The Saga of Minimum Spanning Trees (kapitoly 2.1, 2.3, 2.4)
- Fusion trees:
- Poznámky z Datových struktur 2
- Eric Demaine: lecture notes z MIT
- Fredman, Willard: Blasting through the information theoretic barrier with Fusion Tres
- Exponenciální stromy:
- Poznámky z Datových struktur 2 (část P05)
- Andersson, Thorup: Dynamic ordered sets with exponential search trees
- Q-haldy, AF-haldy, atomické haldy:
- Fredman, Willard: Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths
- Mareš: The Saga of Minimum Spanning Trees (kapitola 2.5)
- Videozáznamy z VKDS 2020
- Redukce univerza:
- Hagerup, Miltersen, Pagh: Deterministic Dictionaries
- Raman: Improved data structures for predecessor queries in integer sets (kapitola 7)
- Marked ancestor:
- Alstrup, Husfeldt, Rauhe: Marked ancestor problems
- Demaine: Lecture 16, Lecture 17 z Advanced Data Structures 2005 na MIT
- Asymptotika:
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.