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. Plán: Marked ancestor: dolní odhad.

Zdroje

Odkazy

Stránku spravuje Martin Mareš