Vybrané kapitoly z datových struktur
V zimním semestru 2020/2021 přednášíme společně s Matejem Lieskovským a Ondrou Mičkou přednášku o pokročilých datových strukturách [NTIN110]. Jejím 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.
Navazujeme na naši loňskou přednášku Pokročilé datové struktury.
Přednášky se budou konat online, odkaz na Zoom vám přišel e-mailem.
| datum | téma | zdroje | záznam |
|---|---|---|---|
| 8. 10. | Stručné (succinct) datové struktury: reprezentace binárních stromů, rank a select na řetězcích bitů, operace se závorkami. | Demaine: Lecture 17 | video |
| 15. 10. | Celočíselné datové struktury: Word-RAM a jeho varianty (Céčkové instrukce vs. AC0). Vektorové výpočty pomocí aritmetiky. Opakovaní fusion trees a fusion nodes, problémy s počítáním sketchů. Q-haldy: předvýpočet funkcí, aplikace na minimální kostry (Fredmanův-Willardův algoritmus). | Poznámky z Datových struktur 2
Mareš: The Saga of Minimum Spanning Trees (kapitoly 2.1, 2.3, 2.4) | video tabule |
| 22. 10. | Q-haldy: stav struktury, implementace operací, velmi-pseudo-sketche a dekodér. | Fredman, Willard: Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths
Mareš: The Saga of Minimum Spanning Trees (kapitola 2.5) | video tabule |
| 29. 10. | Q-haldy: zbylé části dekodéru. Skip listy. | Pugh: Skip Lists: A Probabilistic Alternative to Balanced Trees | video tabule |
| 5. 11. | Randomizované vyhledávací stromy: BST vzniklé inserty z náhodné posloupnosti; randomized binary search tree; treap. | Aragon: Treaps
Martínez & Roura: Randomized Binary Search Trees | video tabule |
| 12. 11. | Úvod do fractional cascadingu: prohledávání K setříděných polí délky L v čase O(K + log L). Cache-oblivious lookahead array. | Bender et al.: Cache-Oblivious Streaming B-Trees | video tabule |
| 19. 11. | Fractional cascading: katalogové grafy, mosty a díry, část budovacího algoritmu. | Chazelle, Guibas: Fractional cascading: I. a data structuring technique | video tabule |
| 26. 11. | Fractional cascading: zbytek budovacího algoritmu, amortizovaná analýza, zrychlená verze, náhrada binárního vyhledávání. Aplikace: DS pro průsečíky lomené čáry s přímkami. | Chazelle, Guibas: Fractional cascading: II. applications | video tabule |
| 3. 12. | Paralelní datové struktury. Zámky: seznamy, práce s (a,2a)-stromy shora dolů, různé problémy se zámky. Atomické operace, linearizovatelnost. Konstrukce zásobníku pomocí CAS. Problém ABA a jeho různá řešení. Správa paměti: free-listy, reference countery, SMR (hazard pointery). | Maged: Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes | video tabule |
| 10. 12. | Paralelní datové struktury. Praktické aspekty: paměťový model a bariéry. Herlihyho hierarchie atomických operací pomocí konsensu. Univerzální konstrukce z CAS. | Herlihy: Wait-Free Synchronization | video tabule |
| 17. 12. | Dokončení univerzální wait-free struktury. Lock-free Splay stromy: zadání domácího úkolu :) | video tabule | |
| 7. 1. | 3D range trees pomocí zlomkového kaskádování. Lock-free vyhledávací stromy. | Chazelle, Guibas: Fractional cascading: II. applications
Ellen et al.: Non-blocking Binary Search Trees | video tabule |