Požadavky ke zkoušce z DS2
Statické slovníky
- Perfektní hešování FKS (Fredman, Komlós, Szemerédi)
- Deterministické statické slovníky (Hagerup, Miltersen, Pagh) pro polynomiální universum
- Randomizovaná verze
- Derandomizace pomocí podmíněných středních hodnot
Uspořádané celočíselné množiny
- Van Emde-Boasovy stromy
- Klasické vEB stromy
- Implicitní inicializace paměti
- vEB pomocí intervalových stromů
- Zrychlení použitím indirekce
- x-fast a y-fast stromy
- Fusion trees
- Fusion nodes a konstrukce stromu z nich
- Komprese trie pomocí sketchů a pseudo-sketchů
- Simulace vektorového počítače na RAMu
- Výpočet dvojkového logaritmu v konstantním čase
Grafové datové struktury
- Statická reprezentace stromů
- Reprezentace cest intervalovými stromy
- Heavy-light dekompozice stromů
- Dynamické stromy (Link-Cut trees, Sleator a Tarjan)
- Dynamický rozklad na cesty
- Reprezentace propojenýmy Splay-stromy
- Aplikace: Zrychlení Dinicova algoritmu na maximální tok
- Inkrementální komponenty souvislosti (Union-Find)
- Reprezentace zakořeněnými stromy
- Optimalizace: Union dle ranku a komprese cest
- Technika dvojitě rekurzivní analýzy struktur
- Příklad s asociativní operací a intervalovými dotazy
- Samotná komprese cest stojí O(log n)
- Kombinace komprese s ranky zlepšuje na O(α(n))
Vícerozměrné datové struktury
- Vícerozměrné intervalové stromy (statické)
- 2D strom s dotazem v O(log n)
- 3D strom s dotazem v O(log n)
Dynamizace datových struktur
- BB-α stromy založené na přebudovávání podstromů
- Dynamizace vícerozměrných intervalových stromů
- Obecná dynamizace
- Rozložitelné vyhledávací problémy
- Amortizovaná semi-dynamizace
- Worst-case semi-dynamizace
- Amortizovaná plná dynamizace
Persistentní datové struktury
- Klasifikace: efemérní, semipersistentní, plně persistentní, funkcionální DS
- Srůstající spojové seznamy
- Funkcionální vyhledávací stromy s kopírováním cest
- Obecný model ukazatelových datových struktur
- Semi-persistence pomocí tlustých vrcholů
- Semi-persistence kombinací tlustých vrcholů s kopírováním
- Plná persistence linearizací historie
- Udržování linéarního uspořádání
- List labelling
- Exponenciální rozsah v O(1) worst-case na operaci
- Polynomiální rozsah v O(log n) amortizovaně na operaci
- Lineární rozsah v O(log2 n) na operaci
- List order v O(1) amortizovaně na operaci
- List labelling
Úsporné (succinct) datové struktury
- Klasifikace paměťově efektivních struktur: implicitní, úsporné, kompaktní DS
- Prefixový kód pro posloupnosti předem neznámé délky s redundancí O(log n)
- Reprezentace řetězců nad obecnou abecedou s redundancí O(log n)
Proudové zpracování dat
- Deterministické hledání častých prvků (Misra a Gries)
- Pravděpodobnostní odhad častých prvků (count-min)
- Pravděpodobnostní odhad počtu různých prvků (algoritmus BJKST)