{{TOC float}}
''Tento popis byl původně vytvořen podle [http://ktiml.mff.cuni.cz/teaching/files/materials/dsii2.pdf Koubkových skript], [[TIN066 Skripta Vidner-Kotal|skript Vidner-Kotal]] a [http://www.google.com/books?hl=cs&lr=&id=-X39_rA3VSQC&oi=fnd&pg=PA326#v=onepage&q&f=false popisu K. Mehlhorna]. -- [[User:Tuetschek|Tuetschek]] 22:00, 20 Aug 2010 (CEST)''
==Úvod==
Mnoho datových struktur podporuje velice efektivní operaci '''MEMBER''', ale nemá operace '''INSERT''' a '''DELETE'''. Úkolem ''dynamizace'' je právě tyto operace do jakékoliv obecné struktury co nejefektivněji doplnit.
===Zobecněný vyhledávací problém===
''Zobecněný vyhledávací problém'' je libovolná funkce <math>f:U_1\times 2^{U_2} \to U_3\,\;</math> -- dostává prvek a nějakou množinu a vrací (libovolnou hodnotu).
Struktura <math>\mathcal{S}\,\;</math> je ''statická struktura řešící vyhledávací problém'' (neboli ''S-struktura'') <math>f\,\;</math>, je-li dán algoritmus, který pro <math>A\subseteq U_2\,\;</math> zkonstruuje datovou strukturu <math>\mathcal{S}(A)\,\;</math> a algoritmus, který pro <math>x\in U_1\,\;</math> a <math>\mathcal{S}(A)\,\;</math> spočte <math>f(x,A)\,\;</math>.
Struktura je ''[[#Semidynamizace|semidynamická]]'', pokud navíc existuje algoritmus, který pro <math>x\in U_2\,\;</math> a <math>\mathcal{S}(A)\,\;</math> zkonstruuje S-strukturu <math>\mathcal{S}(A\cup\{x\})\,\;</math>.
Struktura je ''[[#Dynamizace|dynamická]]'', pokud navíc existuje algoritmus, který pro <math>x\in A\,\;</math> a <math>\mathcal{S}(A)\,\;</math> zkonstruuje S-strukturu <math>\mathcal{S}(A\backslash\{x\})\,\;</math>.
Ve všech následujících operacích budeme uvažovat jen ''rozložitelný'' vyhledávací problém:
* Vyhledávací problém je ''rozložitelný'', pokud existuje binární operace <math>\odot\,\;</math> na univerzu <math>U_3\,\;</math> taková, že pro disjunktní <math>A,B\subseteq U_2\,\;</math> a <math>x\in U_1\,\;</math> platí <math>f(x,A)\odot f(x,B) = f(x,A\cup B)\,\;</math>.
To platí pro situaci, která nás nejvíc zajímá -- pokud funkce <math>f\,\;</math> provádí operaci '''MEMBER''' nad nějakou datovou strukturou. Jiné problémy (patří <math>x\,\;</math> do konvexního obalu množiny?) ale rozložitelné nejsou.
Navíc budeme předpokládat, že funkce <math>\odot\,\;</math> lze spočítat v konstantním čase. Označme
* <math>Q_{\mathcal{S}}(n)\,\;</math> čas na vyčíslení <math>f(x,A)\,\;</math>, pokud <math>|A|=n\,\;</math>
* <math>S_{\mathcal{S}}(n)\,\;</math> paměťový prostor potřebný k reprezentaci <math>n\,\;</math>-prvkové množiny
* <math>P_{\mathcal{S}}(n)\,\;</math> čas na vytvoření struktury <math>\mathcal{S}(A)\,\;</math> pro <math>|A|=n\,\;</math>
Pro asymptotické odhady budeme předpokládat, že funkce <math>Q_{\mathcal{S}}(n)\,\;</math>, <math>\frac{S_{\mathcal{S}}(n)}{n}\,\;</math> a <math>\frac{P_{\mathcal{S}}(n)}{n}\,\;</math> jsou neklesající.
==Semidynamizace==
Vytvoříme semidynamickou strukturu, jejíž čas operace '''INSERT''' bude velmi rychlý a navíc se nám moc nepokazí doba pro provedení operace '''MEMBER'''. Základní idea je podobná jako v binomiálních haldách -- roztrháme reprezentovanou množinu <math>A\,\;</math> na sadu ''disjunktních'' podmnožin <math>A_i</math> o velikosti <math>2^i\,\;</math> (takové množiny jsou neprázdné pro <math>i\,\;</math> odpovídající jedničkám v binárním zápisu čísla <math>|A|\,\;</math>.
Formálně budeme mít spojový seznam S-struktur odpovídajících množinám <math>A_i\,\;</math>.{{Odkaz na poznámku|1}} Taková struktura zjevně vyžaduje jen <math>O(S_{\mathcal{S}}(n))\,\;</math> paměti (celkem reprezentujeme pořád stejně prvků).
===Operace MEMBER===
Operace '''MEMBER''' potom projde všechny neprázdné množiny <math>A_i\,\;</math> a zavolá '''MEMBER''' na nich. Výsledek spojí za pomoci funkce <math>\odot\,\;</math>.
To celkem dává složitost '''MEMBER'''u <math>O(Q_{\matcal{S}}(n)\log(n)\,\;</math>, protože hledáme v max. <math>\log_2\,\;</math> dílčích množinách.
===Operace INSERT===
{{TODO|}}
==Dynamizace==
{{TODO|}}
----
{{Poznámka|1|Doc. Koubek tu ve skriptech uvádí ještě dynamickou dat. strukturu <math>T\,\;</math> a spojové seznamy <math>s(A_i)\,\;</math> obsahující prvky z <math>A_i\,\;</math>, podle mě tu ale ještě nejsou potřeba -- [[User:Tuetschek|Tuetschek]] 22:00, 20 Aug 2010 (CEST)}}
{{Statnice I3}}
