Sylabus
Haldy
• regulární halda
• binomiální halda
• Fibonacciho halda
Stromy
• (a,b)-stromy a jejich varianty
• strategie Move-to-Front pro seznamy, Splay stromy
• přehled ostatních řešení: AVL stromy, červeno-černé stromy, BB-α stromy
Techniky pro paměťovou hierarchii
• I/O model, cache-oblivious analýza, strategie LRU pro on-line stránkování
• příklady: transpozice a násobení matic, van Emde-Boasovo rozložení vyhledávacích stromů
• cache-aware techniky
Hašování
• řešení kolizí, analýza pro uniformně rozdělená data
• výběr hešovací funkce: univerzální hešování a dobré hešovací funkce
• kukačkové hešování
Vícerozměrné datové struktury
• KD stromy
• range trees (intervalové stromy)
Upozornění: Předmět se bude vyučovat od 2018/19 v českém jazyce pouze v zimním semestru a v anglickém jazyce pouze v letním semestru.
Anotace
Základní přednáška o konstrukci efektivních datových struktur. Vyhledávací stromy, haldy, hešování.
Analýza nejhoršího, amortizovaného a očekávaného chování datových struktur. Samoupravující se datové struktury.
Chování a analýza datových struktur na systémech s paměťovou hierarchií. Přednáška volně navazuje na Algoritmy a datové struktury I a II a Programování I a II bakalářského studia.