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
Stránku spravuje Martin Mareš