Sylabus
Statické slovníky:
• perfektní hešování FKS
• deterministické slovníky (Hagerup, Miltersen, Pagh)
• redukce universa
Celočíselné datové struktury:
• van Emde-Boasovy stromy
• x-fast a y-fast stromy
• Fusion trees
Grafové datové struktury:
• dekompozice stromů na lehké a těžké hrany
• aktualizace cest pomocí líného vyhodnocování
• Link-Cut stromy (Sleator, Tarjan)
• inkrementální komponenty souvislosti (Union-Find)
Obecné techniky transformace struktur:
• semidynamizace a dynamizace
• persistence
Cache-oblivious struktury:
• Ordered File Maintenance
• B-stromy
Úsporné datové struktury:
• řetězce nad nebinární abecedou
• úsporná reprezentace stromů
Výpočty v proudovém modelu:
• deterministické hledání častých prvků
• randomizované hledání častých prvků
• odhad počtu různých prvků
Anotace
Přednáška navazuje na přednášku NTIN066 Datové struktury I. Bude věnována pokročilejším technikám návrhu a analýzy datových struktur: deterministická reprezentace statických množin, datové struktury pro celočíselné universum, základní grafové datové struktury, dynamické cache-oblivious vyhledávací stromy, dynamizace a persistence, úsporné datové struktury, výpočty v proudovém modelu.