\input ../sgr.tex
-\hyphenation{mikro-strom mikro-stro-mo-vé}
+\hyphenation{mikro-strom mikro-stro-mo-vé}
-\prednaska{9}{Dekompozice stromù}{}
+\prednaska{9}{Dekompozice stromů}{}
-V~této kapitole uká¾eme nìkolik datových struktur zalo¾ených
-na~my¹lence dekompozice problému na~dostateènì malé podproblémy,
-které u¾ umíme (obvykle vhodným kódováním èísly) øe¹it v~konstantním
-èase.
+V~této kapitole ukážeme několik datových struktur založených
+na~myšlence dekompozice problému na~dostatečně malé podproblémy,
+které už umíme (obvykle vhodným kódováním čísly) řešit v~konstantním
+čase.
\h{Union-Find Problem}
-\s{Problém:} Udr¾ování tøíd ekvivalence: na~poèátku máme $N$ jednoprvkových ekvivalenèních
-tøíd, provádíme operace \<Find> (zji¹tìní, zda dva prvky jsou ekvivalentní) a \<Union>
-(slouèení dvou tøíd do~jedné). Také na~to lze pohlí¾et jako na~inkrementální udr¾ování
-komponent souvislosti neorientovaného grafu: \<Union> je pøidání hrany, \<Find> test,
-zda dva vrcholy le¾í v~té¾e komponentì. To se hodí v~mnoha algoritmech, kupøíkladu
-v~Kruskalovì algoritmu pro hledání minimální kostry.
-
-\s{Triviální øe¹ení:} Prvky ka¾dé tøídy obarvíme unikátní barvou (identifikátorem
-tøídy). Operace \<Find> porovnává barvy, \<Union> prvky jedné ze~sjednocovaných
-tøíd pøebarvuje.
-
-Operace \<Find> tak pracuje v~konstantním èase, \<Union> mù¾e zabrat a¾ lineární èas. Mù¾eme si
-pomoci tím, ¾e v¾dy pøebarvíme {\I men¹í} ze~sluèovaných ekvivalenèních tøíd (budeme
-si pro ka¾dou tøídu pamatovat seznam jejích prvkù a velikost). Tehdy mù¾e být ka¾dý
-prvek pøebarven jen $\O(\log n)$-krát, jeliko¾ ka¾dým pøebarvením se alespoò zdvojnásobí
-velikost tøídy, ve~které prvek le¾í. Posloupnost operací \<Union>, kterou vznikla tøída
-velikosti~$k$, tak trvá $\O(k\log k)$, tak¾e mù¾eme bezpeènì prohlásit, ¾e amortizovaná
-slo¾itost operace \<Union> je $\O(\log n)$.
-
-\s{Chytøej¹í øe¹ení:} Ka¾dou tøídu budeme reprezentovat zakoøenìným stromem s~hranami
-orientovanými smìrem ke~koøeni (jinými slovy pro ka¾dý prvek si pamatujeme jeho otce
-nebo ¾e je to koøen). \<Find> nalezne koøeny stromù a porovná je, \<Union> pøipojí koøen
-jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì pravidla:
+\s{Problém:} Udržování tříd ekvivalence: na~počátku máme $N$ jednoprvkových ekvivalenčních
+tříd, provádíme operace \<Find> (zjištění, zda dva prvky jsou ekvivalentní) a \<Union>
+(sloučení dvou tříd do~jedné). Také na~to lze pohlížet jako na~inkrementální udržování
+komponent souvislosti neorientovaného grafu: \<Union> je přidání hrany, \<Find> test,
+zda dva vrcholy leží v~téže komponentě. To se hodí v~mnoha algoritmech, kupříkladu
+v~Kruskalově algoritmu pro hledání minimální kostry.
+
+\s{Triviální řešení:} Prvky každé třídy obarvíme unikátní barvou (identifikátorem
+třídy). Operace \<Find> porovnává barvy, \<Union> prvky jedné ze~sjednocovaných
+tříd přebarvuje.
+
+Operace \<Find> tak pracuje v~konstantnÃm Ä\8dase, \<Union> může zabrat až lineárnà Ä\8das. Můžeme si
+pomoci tím, že vždy přebarvíme {\I menší} ze~slučovaných ekvivalenčních tříd (budeme
+si pro každou třídu pamatovat seznam jejích prvků a velikost). Tehdy může být každý
+prvek přebarven jen $\O(\log n)$-krát, jelikož každým přebarvením se alespoň zdvojnásobí
+velikost třídy, ve~které prvek leží. Posloupnost operací \<Union>, kterou vznikla třída
+velikosti~$k$, tak trvá $\O(k\log k)$, takže můžeme bezpečně prohlásit, že amortizovaná
+složitost operace \<Union> je $\O(\log n)$.
+
+\s{Chytřejší řešení:} Každou třídu budeme reprezentovat zakořeněným stromem s~hranami
+orientovanými směrem ke~kořeni (jinými slovy pro každý prvek si pamatujeme jeho otce
+nebo že je to kořen). \<Find> nalezne kořeny stromů a porovná je, \<Union> připojí kořen
+jedné třídy pod kořen druhé. Aby stromy nedegenerovaly, přidáme dvě pravidla:
\itemize\ibull
-\:{\I Union dle ranku:} ka¾dý koøen $v$ si bude pamatuje svùj rank $r(v)$, co¾ je nìjaké
-pøirozené èíslo. Na~poèátku jsou v¹echny ranky nulové. Pokud spojujeme
-dva stromy s~koøeny $v$, $w$ a $r(v)<r(w)$, pøipojíme $v$ pod~$w$ a rank zachováme.
-Pokud $r(v)=r(w)$, pøipojíme libovolnì a nový koøen bude mít rank $r(v)+1$.%
-\foot{Stejnì by fungovalo pravidlo {\I Union dle velikosti,} které pøipojuje men¹í
-strom pod vìt¹í, ale ranky máme radìji, neb jsou skladnìj¹í a snáze se analyzují.}
-
-\:{\I Komprese cest:} pokud z~vrcholu vystoupíme do~koøene (napøíklad
-bìhem operace \<Find>), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li,
-rovnou pod koøen.
+\:{\I Union dle ranku:} každý kořen $v$ si bude pamatuje svůj rank $r(v)$, což je nějaké
+přirozené číslo. Na~počátku jsou všechny ranky nulové. Pokud spojujeme
+dva stromy s~kořeny $v$, $w$ a $r(v)<r(w)$, připojíme $v$ pod~$w$ a rank zachováme.
+Pokud $r(v)=r(w)$, připojíme libovolně a nový kořen bude mít rank $r(v)+1$.%
+\foot{Stejně by fungovalo pravidlo {\I Union dle velikosti,} které připojuje menší
+strom pod větší, ale ranky máme raději, neb jsou skladnější a snáze se analyzují.}
+
+\:{\I Komprese cest:} pokud z~vrcholu vystoupíme do~kořene (například
+během operace \<Find>), přepojíme všechny vrcholy na~cestě, po~které jsme prošli,
+rovnou pod kořen.
\endlist
-Pro úèely analýzy struktury budeme uva¾ovat také ranky ostatních vrcholù -- ka¾dý vrchol
-si ponese svùj rank z~doby, kdy byl naposledy koøenem. Struktura se ov¹em
-podle rankù vnitøních vrcholù nijak neøídí a nemusí si je ani pamatovat.
-Stromu s~koøenem ranku~$r$ budeme zkrácenì øíkat {\I strom ranku~$r$.}
+Pro účely analýzy struktury budeme uvažovat také ranky ostatních vrcholů -- každý vrchol
+si ponese svůj rank z~doby, kdy byl naposledy kořenem. Struktura se ovšem
+podle ranků vnitřních vrcholů nijak neřídí a nemusí si je ani pamatovat.
+Stromu s~kořenem ranku~$r$ budeme zkráceně říkat {\I strom ranku~$r$.}
-\s{Invariant~C:} Na ka¾dé cestì z~vrcholu do~koøene pøíslu¹ného stromu ranky
-ostøe rostou. Jinými slovy rank vrcholu, který není koøen, je men¹í, ne¾ je rank
+\s{Invariant~C:} Na každé cestě z~vrcholu do~kořene příslušného stromu ranky
+ostÅ\99e rostou. Jinými slovy rank vrcholu, který nenà koÅ\99en, je menÅ¡Ã, než je rank
jeho otce.
\proof
-Na poèátku (pro jednovrcholové stromy) tvrzení jistì platí.
-Nech» provedeme Union, který pøipojí vrchol~$v$ pod~$w$. Cesty do~koøene z~vrcholù,
-které le¾ely pod~$w$, zùstanou zachovány, pouze se vrcholu~$w$ pøípadnì
-zvý¹í rank. Cesty z~vrcholù pod~$v$ se roz¹íøí o~hranu~$vw$, na které rank
-v~ka¾dém pøípadì roste.
-Komprese cest nahrazuje otce vrcholu jeho vzdálenìj¹ím pøedkem, tak¾e se rank
-otce mù¾e jedinì zvý¹it.
+Na počátku (pro jednovrcholové stromy) tvrzení jistě platí.
+Nechť provedeme Union, který připojí vrchol~$v$ pod~$w$. Cesty do~kořene z~vrcholů,
+které ležely pod~$w$, zůstanou zachovány, pouze se vrcholu~$w$ případně
+zvýší rank. Cesty z~vrcholů pod~$v$ se rozšíří o~hranu~$vw$, na které rank
+v~každém případě roste.
+Komprese cest nahrazuje otce vrcholu jeho vzdálenÄ\9bjÅ¡Ãm pÅ\99edkem, takže se rank
+otce může jedině zvýšit.
\qed
-\s{Invariant~R:} Strom ranku~$r$ obsahuje alespoò $2^r$ vrcholù.
+\s{Invariant~R:} Strom ranku~$r$ obsahuje alespoň $2^r$ vrcholů.
\proof
-Indukcí podle èasu. Pro jednovrcholové stromy o~nulovém ranku tvrzení platí.
-Nech» pøipojíme vrchol~$v$ pod vrchol~$w$. Je-li $r(v)<r(w)$, rank stromu
-zùstane zachován a strom se je¹tì zvìt¹í. Je-li $r(v)=r(w)$, rank stromu
-se zvìt¹í o~1, ale z~indukce víme, ¾e oba spojované stromy mìly alespoò
-$2^{r(v)}$ vrcholù, tak¾e jejich spojením vznikne strom o~alespoò $2^{r(v)+1}$
-vrcholech. Komprese cest zasahuje pouze do~vnitøní struktury stromu, ranky
-ani velikosti stromù nemìní.
+Indukcí podle času. Pro jednovrcholové stromy o~nulovém ranku tvrzení platí.
+Nechť připojíme vrchol~$v$ pod vrchol~$w$. Je-li $r(v)<r(w)$, rank stromu
+zůstane zachován a strom se ještě zvětší. Je-li $r(v)=r(w)$, rank stromu
+se zvětší o~1, ale z~indukce víme, že oba spojované stromy měly alespoň
+$2^{r(v)}$ vrcholů, takže jejich spojením vznikne strom o~alespoň $2^{r(v)+1}$
+vrcholech. Komprese cest zasahuje pouze do~vnitřní struktury stromu, ranky
+ani velikosti stromů nemění.
\qed
-\s{Dùsledek:} Rank ka¾dého stromu je $\O(\log n)$, tak¾e rank ka¾dého vnitøního
-vrcholu takté¾. Díky invariantu~C strávíme výstupem z~ka¾dého vrcholu do~koøene
-také èas $\O(\log n)$, tak¾e logaritmická je i slo¾itost operací \<Union> a \<Find>.
+\s{Důsledek:} Rank každého stromu je $\O(\log n)$, takže rank každého vnitřního
+vrcholu taktéž. Díky invariantu~C strávíme výstupem z~každého vrcholu do~kořene
+také čas $\O(\log n)$, takže logaritmická je i složitost operací \<Union> a \<Find>.
-K~tomu nám ov¹em staèilo samotné pravidlo Union podle ranku, o~kompresi cest
-jsme zatím dokázali pouze to, ¾e slo¾itost v~nejhor¹ím pøípadì nezhor¹uje.%
-\foot{Mimochodem, Komprese cest samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila \cite{tarjan84setunion}.}
-Kombinace obou metod se ve~skuteènosti chová mnohem lépe:
+K~tomu nám ovšem stačilo samotné pravidlo Union podle ranku, o~kompresi cest
+jsme zatím dokázali pouze to, že složitost v~nejhorším případě nezhoršuje.%
+\foot{Mimochodem, Komprese cest samotná by také na~složitost $\O(\log n)$ amortizovaně stačila \cite{tarjan84setunion}.}
+Kombinace obou metod se ve~skutečnosti chová mnohem lépe:
-\s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion})
-Posloupnost $m$~operací \<Union> a \<Find> provedená na~prázdné struktuøe s~$n$ vrcholy
-trvá $\O(n + m\alpha(m,n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
-\foot{Je známo \cite{fredman:cellprobe}, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout,
-a~to ani v~modelu silnìj¹ím ne¾ RAM. Námi uvádìný algoritmus si témìø vystaèí
-s~Pointer Machine, jen porovnávání rankù z~tohoto modelu vyboèuje. Slo¾itost
-operací v~nejhor¹ím pøípadì je obecnì hor¹í, je znám dolní odhad $\Omega(\log n/\log\log n)$;
-více viz Alstrup \cite{alstrup:worstuf}.}
+\s{Věta:} (Tarjan, van Leeuwen \cite{tarjan84setunion})
+Posloupnost $m$~operací \<Union> a \<Find> provedená na~prázdné struktuře s~$n$ vrcholy
+trvá $\O(n + m\alpha(m,n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
+\foot{Je známo \cite{fredman:cellprobe}, že asymptoticky lepší složitosti nelze dosáhnout,
+a~to ani v~modelu silnějším než RAM. Námi uváděný algoritmus si téměř vystačí
+s~Pointer Machine, jen porovnávánà ranků z~tohoto modelu vyboÄ\8duje. Složitost
+operací v~nejhorším případě je obecně horší, je znám dolní odhad $\Omega(\log n/\log\log n)$;
+více viz Alstrup \cite{alstrup:worstuf}.}
-Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný. Místo toho podobnou
-metodou uká¾eme trochu slab¹í výsledek s~iterovaným logaritmem:
+Důkaz této věty neuvádíme, jelikož je technicky dosti náročný. Místo toho podobnou
+metodou ukážeme trochu slabší výsledek s~iterovaným logaritmem:
-\s{Vìta':} Ve~struktuøe s~$n$ prvky trvá provedení posloupnosti $m$~operací
+\s{Věta':} Ve~struktuře s~$n$ prvky trvá provedení posloupnosti $m$~operací
\<Union> a \<Find> $\O((n+m)\cdot\log^* n)$.
\def\up{\mathop{\uparrow}}
-\s{Definice:} {\I Vì¾ovou funkci} $2\up k$ definujeme následovnì: $2\up 0=1$,
+\s{Definice:} {\I Věžovou funkci} $2\up k$ definujeme následovně: $2\up 0=1$,
$2\up (k+1)=2^{2\up k}$.
-Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
-k~této funkci inverzní.
+Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
+k~této funkci inverzní.
-Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù:
-$k$-tá skupina bude tvoøena tìmi vrcholy, jejich¾ rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
-tedy rozdìleny do~$1+\log^*\log n$ skupin. Odhadnìme nyní shora poèet vrcholù v~$k$-té
-skupinì.
+Vrcholy ve~struktuře si nyní rozdělíme podle jejich ranků:
+$k$-tá skupina bude tvoÅ\99ena tÄ\9bmi vrcholy, jejichž rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
+tedy rozděleny do~$1+\log^*\log n$ skupin. Odhadněme nyní shora počet vrcholů v~$k$-té
+skupině.
-\s{Invariant~S:} V~$k$-té skupinì le¾í nejvý¹e $n/(2\up k)$ vrcholù.
+\s{Invariant~S:} V~$k$-té skupině leží nejvýše $n/(2\up k)$ vrcholů.
\proof
-Nejprve uká¾eme, ¾e vrcholù s~rankem~$r$ je nejvý¹e $n/2^r$. Kdybychom nekomprimovali
-cesty, snadno to plyne z~invariantù~C a~R: ka¾dému vrcholu ranku~$r$ pøiøadíme v¹ech
-jeho alespoò $2^r$ potomkù. Jeliko¾ ranky na cestách smìrem ke~koøeni rostou, ¾ádného
-potomka jsme nemohli pøiøadit více vrcholùm. Komprese cest ov¹em nemù¾e invariant
-poru¹it, proto¾e nemìní ranky ani rozhodnutí, jak probìhne který \<Union>.
+Nejprve ukážeme, že vrcholů s~rankem~$r$ je nejvýše $n/2^r$. Kdybychom nekomprimovali
+cesty, snadno to plyne z~invariantů~C a~R: každému vrcholu ranku~$r$ přiřadíme všech
+jeho alespoň $2^r$ potomků. Jelikož ranky na cestách směrem ke~kořeni rostou, žádného
+potomka jsme nemohli pÅ\99iÅ\99adit vÃce vrcholům. Komprese cest ovÅ¡em nemůže invariant
+porušit, protože nemění ranky ani rozhodnutí, jak proběhne který \<Union>.
-Teï u¾ staèí odhad $n/2^r$ seèíst pøes v¹echny ranky ve~skupinì:
+Teď už stačí odhad $n/2^r$ sečíst přes všechny ranky ve~skupině:
$$
{n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le
{n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} =
$$
\qed
-\>{\sl Dùkaz vìty:}
-Operace \<Union> a \<Find> potøebují nekonstantní èas pouze na~vystoupání
-po~cestì ze~zadaného vrcholu~$v$ do~koøene stromu. Èas strávený na~této cestì
-je pøímo úmìrný poètu hran cesty. Celá cesta je pøitom rozpojena a v¹echny
-vrcholy le¾ící na~ní jsou pøepojeny pøímo pod~koøen stromu.
-
-Hrany cesty, které spojují vrcholy z~rùzných skupin (takových je $\O(\log^* n)$),
-naúètujeme právì provádìné operaci. Celkem jimi tedy strávíme èas $\O(m\log^*n)$.
-Zbylé hrany budeme poèítat pøes celou dobu bìhu algoritmu a úètovat je vrcholùm.
-
-Uva¾me vrchol~$v$ v~$k$-té skupinì, jeho¾ rodiè le¾í také v~$k$-té skupinì.
-Jeliko¾ hrany na cestách do~koøene ostøe rostou, ka¾dým pøepojením vrcholu~$v$ rank jeho
-rodièe vzroste. Proto po nejvý¹e $2\up k$ pøepojeních se bude rodiè vrcholu~$v$ nacházet
-v~nìkteré z~vy¹¹ích skupin. Jeliko¾ rank vrcholu~$v$ se u¾ nikdy nezmìní, bude hrana z~$v$
-do~jeho otce ji¾ nav¾dy hranou mezi skupinami. Ka¾dému vrcholu v~$k$-té skupinì tedy naúètujeme
-nejvý¹e $2\up k$ pøepojení a jeliko¾, jak u¾ víme, jeho skupina obsahuje nejvý¹e $n/(2\up k)$ vrcholù,
-naúètujeme celé skupinì èas $\O(n)$ a v¹em skupinám dohromady $\O(n\log^* n)$.
+\>{\sl Důkaz věty:}
+Operace \<Union> a \<Find> potřebují nekonstantní čas pouze na~vystoupání
+po~cestě ze~zadaného vrcholu~$v$ do~kořene stromu. Čas strávený na~této cestě
+je přímo úměrný počtu hran cesty. Celá cesta je přitom rozpojena a všechny
+vrcholy ležící na~ní jsou přepojeny přímo pod~kořen stromu.
+
+Hrany cesty, které spojují vrcholy z~různých skupin (takových je $\O(\log^* n)$),
+naúčtujeme právě prováděné operaci. Celkem jimi tedy strávíme čas $\O(m\log^*n)$.
+Zbylé hrany budeme počítat přes celou dobu běhu algoritmu a účtovat je vrcholům.
+
+Uvažme vrchol~$v$ v~$k$-té skupině, jehož rodič leží také v~$k$-té skupině.
+Jelikož hrany na cestách do~kořene ostře rostou, každým přepojením vrcholu~$v$ rank jeho
+rodiče vzroste. Proto po nejvýše $2\up k$ přepojeních se bude rodič vrcholu~$v$ nacházet
+v~některé z~vyšších skupin. Jelikož rank vrcholu~$v$ se už nikdy nezmění, bude hrana z~$v$
+do~jeho otce již navždy hranou mezi skupinami. Každému vrcholu v~$k$-té skupině tedy naúčtujeme
+nejvýše $2\up k$ přepojení a jelikož, jak už víme, jeho skupina obsahuje nejvýše $n/(2\up k)$ vrcholů,
+naúčtujeme celé skupině čas $\O(n)$ a všem skupinám dohromady $\O(n\log^* n)$.
\qed
-\h{Union-Find s~pøedem známými Uniony}
+\h{Union-Find s~předem známými Uniony}
-Dále nás bude zajímat speciální varianta Union-Find problému, v~ní¾ dopøedu známe
-posloupnost Unionù, èili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
-Tøeba v~Thorupovì lineárním algoritmu \cite{thorup:usssp} na~nejkrat¹í cesty nebo
-ve~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních
-cest v~rovinných grafech.}
-Jiná interpretace tého¾ (jen pozpátku) je dekrementální udr¾ování komponent
-souvislosti lesa: na~poèátku je dán les, umíme smazat hranu a otestovat, zda jsou
-dva vrcholy v~tém¾e stromu.
+Dále nás bude zajímat speciální varianta Union-Find problému, v~níž dopředu známe
+posloupnost Unionů, čili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
+Třeba v~Thorupově lineárním algoritmu \cite{thorup:usssp} na~nejkratší cesty nebo
+ve~Weiheho taktéž lineárním algoritmu \cite{weihe:paths} na~hledání hranově disjunktních
+cest v~rovinných grafech.}
+Jiná interpretace téhož (jen pozpátku) je dekrementální udržování komponent
+souvislosti lesa: na~počátku je dán les, umíme smazat hranu a otestovat, zda jsou
+dva vrcholy v~témže stromu.
-Popí¹eme algoritmus,
-který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovanì
-konstantním èase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem \cite{alstrup97optimal,alstrup98marked}.
+Popíšeme algoritmus,
+který po~počátečním předzpracování v~čase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovaně
+konstantním čase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem \cite{alstrup97optimal,alstrup98marked}.
-\s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
+\s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakořeněný strom $T$ o~$n$ vrcholech
definujeme:
\itemize\ibull
-\:{\I Koøeny mikrostromù} budou nejvy¹¹í vrcholy v~$T$, pod~nimi¾ je nejvý¹e $\log n$ listù
-a které nejsou koøenem celého~$T$.
-\:{\I Mikrostromy} le¾í v~$T$ od~tìchto koøenù ní¾e.
-\:{\I Spojovací hrany} vedou z~koøenù mikrostromù do~jejich otcù.
-\:{\I Makrostrom} je tvoøen zbývajícími vrcholy a hranami stromu~$T$.
+\:{\I Kořeny mikrostromů} budou nejvyšší vrcholy v~$T$, pod~nimiž je nejvýše $\log n$ listů
+a které nejsou kořenem celého~$T$.
+\:{\I Mikrostromy} ležà v~$T$ od~tÄ\9bchto koÅ\99enů nÞe.
+\:{\I Spojovací hrany} vedou z~kořenů mikrostromů do~jejich otců.
+\:{\I Makrostrom} je tvořen zbývajícími vrcholy a hranami stromu~$T$.
\endlist
-\s{Pozorování:} Ka¾dý mikrostrom má nejvý¹e $\log n$ listù. Pod ka¾dým listem makrostromu le¾í
-alespoò jeden mikrostrom (mù¾e jich být i více, viz dekompozice hvìzdy na~obrázku), tak¾e
-listù makrostromu je nejvý¹e $n/\log n$.
+\s{Pozorování:} Každý mikrostrom má nejvýše $\log n$ listů. Pod každým listem makrostromu leží
+alespoÅ\88 jeden mikrostrom (může jich být i vÃce, viz dekompozice hvÄ\9bzdy na~obrázku), takže
+listů makrostromu je nejvýše $n/\log n$.
-Vnitøních vrcholù makro- i mikrostromù ale mù¾e být ne¹ikovnì mnoho, proto¾e se ve~stromech mohou
-vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu
-ji nahradíme hranou, která bude vlo¾ena právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty.
+VnitÅ\99nÃch vrcholů makro- i mikrostromů ale může být neÅ¡ikovnÄ\9b mnoho, protože se ve~stromech mohou
+vyskytovat dlouhé cesty. Pomůžeme si snadno: každou cestu si budeme pamatovat zvlášť a ve~stromu
+ji nahradíme hranou, která bude vložena právě tehdy, když budou přítomny všechny hrany cesty.
-\s{Pøíklad:} Následující obrázek ukazuje dekompozici nìkolika stromù za~pøedpokladu,
-¾e $\log n=4$. Vrcholy mikrostromù jsou èerné, makrostromu bílé. Spojovací hrany kreslíme teèkovanì,
-hrany komprimovaných cest tuènì.
+\s{Příklad:} Následující obrázek ukazuje dekompozici několika stromů za~předpokladu,
+že $\log n=4$. Vrcholy mikrostromů jsou černé, makrostromu bílé. Spojovací hrany kreslíme tečkovaně,
+hrany komprimovaných cest tučně.
\medskip
\fig{mima.eps}{\epsfxsize}
-\s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si ulo¾íme
-mno¾iny ji¾ pøítomných hran (po~bitech jako èísla). Pak si je¹tì pamatujeme zkomprimovanou cestu (hrany
-odpovídají úsekùm a jsou pøítomny právì tehdy, jsou-li pøítomny v¹echny hrany pøíslu¹ného úseku)
-délky $l/\log n$ a pro ni \uv{pøebarvovací} strukturu pro Union-Find.
+\s{Algoritmus pro cesty:} Cestu délky~$l$ rozdělíme na~úseky délky $\log n$, pro něž si uložíme
+množiny již přítomných hran (po~bitech jako čísla). Pak si ještě pamatujeme zkomprimovanou cestu (hrany
+odpovídají úsekům a jsou přítomny právě tehdy, jsou-li přítomny všechny hrany příslušného úseku)
+délky $l/\log n$ a pro ni \uv{přebarvovací} strukturu pro Union-Find.
-\>$\<Union>(x,y)$ (pøidání hrany $e=xy$ do~cesty):
+\>$\<Union>(x,y)$ (přidání hrany $e=xy$ do~cesty):
\algo
-\:Pøidáme $e$ do mno¾iny hran pøítomných v~pøíslu¹ném úseku.
-\:Pokud se tím úsek naplnil, pøidáme odpovídající hranu do~zkomprimované cesty.
+\:Přidáme $e$ do množiny hran přítomných v~příslušném úseku.
+\:Pokud se tím úsek naplnil, přidáme odpovídající hranu do~zkomprimované cesty.
\endalgo
\>$\<Find>(x,y):$
\algo
-\:Pokud $x$ a $y$ jsou v~tém¾e úseku, otestujeme bitovými operacemi, zda
- jsou v¹echny hrany mezi $x$ a $y$ pøítomny.
-\:Pokud jsou v~rùzných úsecích, rozdìlíme cestu z~$x$ do~$y$ na~posloupnost celých úsekù,
- na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních èásteèných úsecích.
+\:Pokud $x$ a $y$ jsou v~témže úseku, otestujeme bitovými operacemi, zda
+ jsou všechny hrany mezi $x$ a $y$ přítomny.
+\:Pokud jsou v~různých úsecích, rozdělíme cestu z~$x$ do~$y$ na~posloupnost celých úseků,
+ na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních částečných úsecích.
\endalgo
-Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$
-amortizovanì, ale za~dobu ¾ivota struktury je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas.
+Operace uvnitř úseků pracují v~čase $\O(1)$, operace na~zkomprimované cestě v~$\O(\log l)$
+amortizovaně, ale za~dobu života struktury je jich $\O(l/\log n)=\O(l/\log l)$, takže celkově zaberou lineární čas.
-\s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem
-pøevádìt na~operace s~jejich cestovì komprimovanými podobami a na~operace s~cestovými strukturami:
+\s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím způsobem
+převádět na~operace s~jejich cestově komprimovanými podobami a na~operace s~cestovými strukturami:
\>$\<Union>(x,y)$:
\algo
-\:Pokud $e=xy$ le¾í uvnitø nìjaké cesty, pøidáme ji do~cesty, co¾ buïto zpùsobí
- pøidávání jiné hrany, a~nebo u¾ jsme hotovi.
-\:Provedeme \<Union> v~komprimovaném stromu.
+\:Pokud $e=xy$ leží uvnitř nějaké cesty, přidáme ji do~cesty, což buďto způsobí
+ pÅ\99idávánà jiné hrany, a~nebo už jsme hotovi.
+\:Provedeme \<Union> v~komprimovaném stromu.
\endalgo
\>$\<Find>(x,y)$:
\algo
-\:Pokud $x$ a $y$ le¾í uvnitø jedné cesty, zeptáme se cestové struktury a konèíme.
-\:Pokud $x$ le¾í uvnitø nìjaké cesty, zjistíme dotazem na~cestovou strukturu,
- ke~kterému krajnímu vrcholu cesty je pøipojen, a~$x$ nahradíme tímto vrcholem.
- Není-li pøipojen k~¾ádnému, je~evidentnì odpovìï na~celý \<Find> negativní;
- pokud k~obìma, vybereme si libovolný, proto¾e jsou stejnì v~cestovì komprimovaném
+\:Pokud $x$ a $y$ leží uvnitř jedné cesty, zeptáme se cestové struktury a končíme.
+\:Pokud $x$ leží uvnitř nějaké cesty, zjistíme dotazem na~cestovou strukturu,
+ ke~kterému krajnímu vrcholu cesty je připojen, a~$x$ nahradíme tímto vrcholem.
+ Není-li připojen k~žádnému, je~evidentně odpověď na~celý \<Find> negativní;
+ pokud k~oběma, vybereme si libovolný, protože jsou stejně v~cestově komprimovaném
stromu spojeny hranou. Analogicky pro~$y$.
-\:Zeptáme se struktury pro komprimovaný strom.
+\:Zeptáme se struktury pro komprimovaný strom.
\endalgo
-\s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$
-vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou
-mno¾inu hran pak mù¾eme reprezentovat $(2\log n)$-bitovým èíslem a mno¾inové operace
-provádìt pomocí bitových v~konstantním èase.
+\s{Algoritmus pro mikrostromy:} Po~kompresi cest má každý mikrostrom nejvýše $2\log n$
+vrcholů, Ä\8dili také nejvýše tolik hran. Hrany si oÄ\8dÃslujeme pÅ\99irozenými Ä\8dÃsly, každou
+množinu hran pak můžeme reprezentovat $(2\log n)$-bitovým číslem a množinové operace
+provádět pomocí bitových v~konstantním čase.
-Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících
-na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat mno¾inu
-pøítomných hran~$F$.
+Pro každý mikrostrom si předpočítáme pro všechny jeho vrcholy~$v$ množiny~$P_v$ hran ležících
+na~cestÄ\9b z~koÅ\99ene mikrostromu do~$v$. NavÃc si budeme pro celý mikrostrom pamatovat množinu
+přítomných hran~$F$.
\>$\<Union>(x,y):$
\algo
-\:Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané).
+\:Najdeme pořadové číslo $i$ hrany $xy$ (máme předpočítané).
\:$F \leftarrow F \cup \{i\}$.
\endalgo
\>$\<Find>(x,y):$
\algo
-\:$P \leftarrow P_x \mathop{\Delta} P_y$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$).
-\:Pokud $P\setminus F=\emptyset$, le¾í $x$ a $y$ ve~stejnì komponentì, jinak ne.
+\:$P \leftarrow P_x \mathop{\Delta} P_y$ (množina hran ležících na~cestě z~$x$ do~$y$).
+\:Pokud $P\setminus F=\emptyset$, leží $x$ a $y$ ve~stejně komponentě, jinak ne.
\endalgo
-\s{Algoritmus pro celý problém:} Strom rozlo¾íme na~mikrostromy, makrostrom a spojovací
-hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme
-vý¹e popsané struktury, pro ka¾dou spojovací hranu si budeme pamatovat jen znaèku,
-zda je pøítomna, a pro makrostrom pøebarvovací strukturu.
+\s{Algoritmus pro celý problém:} Strom rozložíme na~mikrostromy, makrostrom a spojovací
+hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy použijeme
+výše popsané struktury, pro každou spojovací hranu si budeme pamatovat jen značku,
+zda je přítomna, a pro makrostrom přebarvovací strukturu.
\>$\<Union>(x,y)$:
\algo
-\:Pokud $e=xy$ je spojovací, poznamenáme si, ¾e je pøítomna, a~konèíme.
-\:Nyní víme, ¾e $e$ le¾í uvnitø mikrostromu nebo makrostromu, a~tak provedeme \<Union>
- na~pøíslu¹né struktuøe.
+\:Pokud $e=xy$ je spojovací, poznamenáme si, že je přítomna, a~končíme.
+\:Nyní víme, že $e$ leží uvnitř mikrostromu nebo makrostromu, a~tak provedeme \<Union>
+ na~příslušné struktuře.
\endlist
\>$\<Find>(x,y)$:
\algo
-\:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
-\:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostruktury na~spojení s~koøenem mikrostromu.
- Není-li, odpovíme {\sc ne}, stejnì jako kdy¾ není pøítomna pøíslu¹ná spojovací hrana.
- Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobnì pro~$y$.
-\:Odpovíme podle struktury pro makrostrom.
+\:Leží-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
+\:Je-li $x$ uvnitř mikrostromu, zeptáme se mikrostruktury na~spojení s~kořenem mikrostromu.
+ Není-li, odpovíme {\sc ne}, stejně jako když není přítomna příslušná spojovací hrana.
+ Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobně pro~$y$.
+\:Odpovíme podle struktury pro makrostrom.
\endalgo
-\s{Analýza:} Operace \<Find> trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \<Find>ù
-v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \<Union>
-trvá $\O(n)$, jeliko¾ zpùsobí $\O(n)$ amortizovanì konstantních operací s~mikrostromy, spojovacími
-hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovanì
-ka¾dá.%
-\foot{To je v~prùmìru $\O(1)$ na~operaci a dokonce i amortizovanì, pokud necháme inicializaci
-struktury, která je lineární, naspoøit potenciál $\O(n)$, ze~kterého budeme prùbì¾nì platit
-sluèování v~makrostromu.}
+\s{Analýza:} Operace \<Find> trvá konstantní čas, protože se rozloží na~$\O(1)$ \<Find>ů
+v~dílčích strukturách a každý z~nich trvá konstantně dlouho. Všech $n$ operací \<Union>
+trvá $\O(n)$, jelikož způsobí $\O(n)$ amortizovaně konstantních operací s~mikrostromy, spojovacími
+hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovaně
+každá.%
+\foot{To je v~průměru $\O(1)$ na~operaci a dokonce i amortizovaně, pokud necháme inicializaci
+struktury, která je lineární, naspořit potenciál $\O(n)$, ze~kterého budeme průběžně platit
+slučování v~makrostromu.}
-\s{Cvièení:} Zkuste pomocí dekompozice vyøe¹it následující problém: je dán strom,
-jeho¾ ka¾dý vrchol mù¾e být oznaèený. Navrhnìte datovou strukturu, která bude umìt
-v~èase $\O(\log\log n)$ oznaèit nebo odznaèit vrchol a v~èase $\O(\log n/\log\log n)$ najít
-nejbli¾¹ího oznaèeného pøedchùdce.
+\s{Cvičení:} Zkuste pomocí dekompozice vyřešit následující problém: je dán strom,
+jehož každý vrchol může být označený. Navrhněte datovou strukturu, která bude umět
+v~čase $\O(\log\log n)$ označit nebo odznačit vrchol a v~čase $\O(\log n/\log\log n)$ najít
+nejbližšího označeného předchůdce.
\h{Fredericksonova clusterizace}
-Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy
-se více hodí následující my¹lenka:
+Mikro/makro-stromová dekompozice není jediný způsob, jak stromy rozkládat. Někdy
+se více hodí následující myšlenka:
-\s{Definice:} {\I (Fredericksonova clusterizace)} Nech» $k\ge 1$ je pøirozené èíslo
-a $T$~strom s~maximálním stupnìm nejvý¹e~3. Pak $k$-clusterizací stromu~$T$
-nazveme libovolný rozklad $V_1\cup\ldots\cup V_t$ mno¾iny~$V(T)$, pro který platí:
+\s{Definice:} {\I (Fredericksonova clusterizace)} Nechť $k\ge 1$ je přirozené číslo
+a $T$~strom s~maximálním stupněm nejvýše~3. Pak $k$-clusterizací stromu~$T$
+nazveme libovolný rozklad $V_1\cup\ldots\cup V_t$ množiny~$V(T)$, pro který platí:
\itemize\ibull
-\:Podgrafy stromu~$T$ indukované jednotlivými~$V_i$ jsou souvislé.
-Tìmto podgrafùm budeme øíkat {\I clustery} a znaèit je~$C_i$.
-\:Z~ka¾dého clusteru vedou nejvý¹e 3~hrany do sousedních clusterù.
-Takovým hranám øíkáme {\I vnìj¹í,} jejich poèet je {\I vnìj¹í stupeò} clusteru $\<ed>(C_i)$.
-Hrany uvnitø clusterù nazveme {\I vnitøní.}
-\:Nech» $\vert C_i\vert$ znaèí poèet vrcholù clusteru~$C_i$.
-Pak pro v¹echny clustery platí $\vert C_i\vert \le k$
-a pro clustery vnìj¹ího stupnì~3 dokonce $\vert C_i\vert = 1$.
-\:®ádné dva sousední clustery není mo¾né slouèit.
+\:Podgrafy stromu~$T$ indukované jednotlivými~$V_i$ jsou souvislé.
+Těmto podgrafům budeme říkat {\I clustery} a značit je~$C_i$.
+\:Z~každého clusteru vedou nejvýše 3~hrany do sousedních clusterů.
+Takovým hranám říkáme {\I vnější,} jejich počet je {\I vnější stupeň} clusteru $\<ed>(C_i)$.
+Hrany uvnitř clusterů nazveme {\I vnitřní.}
+\:Nechť $\vert C_i\vert$ značí počet vrcholů clusteru~$C_i$.
+Pak pro všechny clustery platí $\vert C_i\vert \le k$
+a pro clustery vnějšího stupně~3 dokonce $\vert C_i\vert = 1$.
+\:Žádné dva sousední clustery není možné sloučit.
\endlist
-\s{Úmluva:}
-Clustery vnìj¹ího stupnì~0 se nazývají {\I izolované,}
-stupnì~1 {\I listové,}
-stupnì~2 {\I cestové} a
-stupnì~3 {\I vìtvicí.}
+\s{Úmluva:}
+Clustery vnějšího stupně~0 se nazývají {\I izolované,}
+stupně~1 {\I listové,}
+stupně~2 {\I cestové} a
+stupně~3 {\I větvicí.}
-\s{Pozorování:} Nech» $C$ a~$D$ jsou sousední clustery (bez újmy na obecnosti $\<ed>(C) \ge \<ed>(D)$).
-Kdy je lze slouèit? Pøedev¹ím $\vert C\vert + \vert D\vert$ musí být nejvý¹e rovno~$k$. Pak mohou
-nastat následující pøípady:
+\s{Pozorování:} Nechť $C$ a~$D$ jsou sousední clustery (bez újmy na obecnosti $\<ed>(C) \ge \<ed>(D)$).
+Kdy je lze sloučit? Především $\vert C\vert + \vert D\vert$ musí být nejvýše rovno~$k$. Pak mohou
+nastat následující případy:
\itemize\ibull
-\:Pokud~$C$ i~$D$ jsou listové, lze je slouèit do jednoho izolovaného clusteru.
-\:Pokud~$C$ je cestový a $D$~listový, lze je slouèit do listového clusteru.
-\:Pokud~$C$ i~$D$ jsou cestové, lze je slouèit do cestového clusteru.
-\:Pokud~$C$ je vìtvicí a $D$~listový, lze je slouèit do cestového clusteru.
-\:V~ostatních pøípadech sluèovat nelze, nebo» by vznikl cluster vnìj¹ího stupnì~4
- nebo stupnì~3 s~více ne¾ jedním vrcholem.
+\:Pokud~$C$ i~$D$ jsou listové, lze je sloučit do jednoho izolovaného clusteru.
+\:Pokud~$C$ je cestový a $D$~listový, lze je sloučit do listového clusteru.
+\:Pokud~$C$ i~$D$ jsou cestové, lze je sloučit do cestového clusteru.
+\:Pokud~$C$ je větvicí a $D$~listový, lze je sloučit do cestového clusteru.
+\:V~ostatních případech slučovat nelze, neboť by vznikl cluster vnějšího stupně~4
+ nebo stupně~3 s~více než jedním vrcholem.
\endlist
-\s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Ka¾dá $k$-clusterizace stromu~$T$
-na $n$~vrcholech obsahuje $\O(n/k)$ clusterù.
+\s{Věta:} (Frederickson \cite{frederickson91ambivalent}) Každá $k$-clusterizace stromu~$T$
+na $n$~vrcholech obsahuje $\O(n/k)$ clusterů.
\proof
-Pokud clusterizace obsahuje pouze izolované nebo listové clustery, pak je konstantnì
-velká a tvrzení triviálnì platí.
-
-Pokud navíc obsahuje cestové clustery, musí být clustery propojeny do jedné cesty,
-která zaèíná a konèí listovými clustery a ostatní clustery jsou cestové. Cestové
-clustery rozdìlíme na velké (alespoò $k/2$ vrcholù) a malé (ostatní). V¹imneme si,
-¾e malé spolu nemohou sousedit. Velkých je pøitom nejvý¹e $n/k$, tak¾e malých
-nejvý¹e $n/k+1$.
-
-Zbývá obecný pøípad, v~nìm¾ jsou i vìtvicí clustery. Uva¾me clusterizaèní strom~$S$:
-jeho vrcholy odpovídají clusterùm, hrany externím hranám mezi nimi. Tento strom zakoøeòme
-v~libovolném vìtvicím clusteru.
-
-Pokud ve~stromu~$S$ nahradíme ka¾dou nevìtvící se cestu hranou, vznikne nìjaký
-komprimovaný strom~$S'$. V~nìm u¾ jsou pouze listové clustery (coby listy) a
-vìtvicí clustery (jako vnitøní vrcholy).
-
-Nyní si v¹imneme, ¾e pro ka¾dý list~$\ell$ stromu~$S$ platí, ¾e tento cluster
-spolu s~cestovými clustery nad ním (které se schovaly do hrany mezi~$\ell$ a jeho
-otcem) musí mít velikost alespoò~$k$. V~opaèném pøípadì by toti¾ bylo mo¾né
-tyto clustery spoleènì s~vìtvicím clusterem nad nimi slouèit do jediného clusteru,
-co¾ by poru¹ilo poslední podmínku z~definice clusterizace.
-
-Proto strom~$S'$ obsahuje nejvý¹e $n/k$ listù. A~jeliko¾ v¹echny jeho vnitøní
-vrcholy mají alespoò~2 syny, musí být vnitøních vrcholù také nanejvý¹ $n/k$.
-
-Zbývá zapoèítat cestové clustery. Uva¾me hranu~$e$ stromu~$S'$ a cestové clustery,
-které se do ní zkomprimovaly. U¾ víme, ¾e je-li celková velikost tìchto clusterù~$r$,
-mù¾e jich být nanejvý¹ $2r/k + 1$. A~jeliko¾ clustery jsou disjunktní, v~souètu
-pøes v¹echny hrany~$e$ dostaneme $2n/k + \hbox{poèet hran stromu~$S'$} = \O(n/k)$.
-
-Clusterù v¹ech typù je tedy dohromady $\O(n/k)$.
+Pokud clusterizace obsahuje pouze izolované nebo listové clustery, pak je konstantně
+velká a tvrzení triviálně platí.
+
+Pokud navíc obsahuje cestové clustery, musí být clustery propojeny do jedné cesty,
+která začíná a končí listovými clustery a ostatní clustery jsou cestové. Cestové
+clustery rozdělíme na velké (alespoň $k/2$ vrcholů) a malé (ostatní). Všimneme si,
+že malé spolu nemohou sousedit. Velkých je přitom nejvýše $n/k$, takže malých
+nejvýše $n/k+1$.
+
+Zbývá obecný případ, v~němž jsou i větvicí clustery. Uvažme clusterizační strom~$S$:
+jeho vrcholy odpovídají clusterům, hrany externím hranám mezi nimi. Tento strom zakořeňme
+v~libovolném větvicím clusteru.
+
+Pokud ve~stromu~$S$ nahradíme každou nevětvící se cestu hranou, vznikne nějaký
+komprimovaný strom~$S'$. V~něm už jsou pouze listové clustery (coby listy) a
+větvicí clustery (jako vnitřní vrcholy).
+
+Nynà si vÅ¡imneme, že pro každý list~$\ell$ stromu~$S$ platÃ, že tento cluster
+spolu s~cestovými clustery nad ním (které se schovaly do hrany mezi~$\ell$ a jeho
+otcem) musí mít velikost alespoň~$k$. V~opačném případě by totiž bylo možné
+tyto clustery společně s~větvicím clusterem nad nimi sloučit do jediného clusteru,
+což by porušilo poslední podmínku z~definice clusterizace.
+
+Proto strom~$S'$ obsahuje nejvýše $n/k$ listů. A~jelikož všechny jeho vnitřní
+vrcholy mají alespoň~2 syny, musí být vnitřních vrcholů také nanejvýš $n/k$.
+
+Zbývá započítat cestové clustery. Uvažme hranu~$e$ stromu~$S'$ a cestové clustery,
+které se do ní zkomprimovaly. Už víme, že je-li celková velikost těchto clusterů~$r$,
+může jich být nanejvýš $2r/k + 1$. A~jelikož clustery jsou disjunktní, v~součtu
+přes všechny hrany~$e$ dostaneme $2n/k + \hbox{počet hran stromu~$S'$} = \O(n/k)$.
+
+Clusterů všech typů je tedy dohromady $\O(n/k)$.
\qed
-\s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Pro ka¾dé~$k$ lze $k$-clusterizaci
-stromu o~$n$~vrcholech najít v~èase $\O(n)$.
+\s{Věta:} (Frederickson \cite{frederickson91ambivalent}) Pro každé~$k$ lze $k$-clusterizaci
+stromu o~$n$~vrcholech najít v~čase $\O(n)$.
\proof
-Clusterizaci lze najít upraveným hledáním do hloubky, ale pøi tom je nutné øe¹it
-mnoho rùzných pøípadù sluèování clusterù. Místo toho pou¾ijeme následující
-hladový algoritmus.
-
-Nejprve vytvoøíme z~ka¾dého vrcholu triviální cluster. Taková clusterizace
-splòuje v¹echny podmínky kromì poslední. Budeme tedy clustery hladovì sluèovat.
-
-Poøídíme si frontu clusterù, u~nich¾ jsme je¹tì nezkontrolovali sluèitelnost.
-Na poèátku do ní umístíme v¹echny clustery. Pak v¾dy odebereme cluster, prozkoumáme
-jeho sousedy a pokud mezi nimi je nìjaký, s~ním¾ lze sluèovat, tak to provedeme.
-Nový cluster ulo¾íme do fronty, oba staré z~fronty odstraníme.
-
-V¹imneme si, ¾e pøi ka¾dé kontrole poklesne velikost fronty o~1 -- buïto jsme
-nesluèovali a zmizel pouze kontrolovaný cluster, anebo sluèovali, ale pak zmizely
-dva clustery a pøibyl jeden. Jeliko¾ kontrolu i slouèení zvládneme v~konstantním
-èase, celý algoritmus dobìhne v~èase $\O(n)$.
+Clusterizaci lze najít upraveným hledáním do hloubky, ale při tom je nutné řešit
+mnoho různých případů slučování clusterů. Místo toho použijeme následující
+hladový algoritmus.
+
+Nejprve vytvoříme z~každého vrcholu triviální cluster. Taková clusterizace
+splňuje všechny podmínky kromě poslední. Budeme tedy clustery hladově slučovat.
+
+Pořídíme si frontu clusterů, u~nichž jsme ještě nezkontrolovali slučitelnost.
+Na počátku do ní umístíme všechny clustery. Pak vždy odebereme cluster, prozkoumáme
+jeho sousedy a pokud mezi nimi je nějaký, s~nímž lze slučovat, tak to provedeme.
+Nový cluster uložíme do fronty, oba staré z~fronty odstraníme.
+
+Všimneme si, že při každé kontrole poklesne velikost fronty o~1 -- buďto jsme
+neslučovali a zmizel pouze kontrolovaný cluster, anebo slučovali, ale pak zmizely
+dva clustery a přibyl jeden. Jelikož kontrolu i sloučení zvládneme v~konstantním
+čase, celý algoritmus doběhne v~čase $\O(n)$.
\qed
-\s{Pou¾ití:} Pøedchozí variantu Union-Find problému bychom také mohli vyøe¹it nahrazením
-vrcholù stupnì vìt¹ího ne¾~3 \uv{kruhovými objezdy bez jedné hrany},
-nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù
-a pøebarvovací struktury na~hrany mezi clustery.
+\s{Použití:} Předchozí variantu Union-Find problému bychom také mohli vyřešit nahrazením
+vrcholů stupně většího než~3 \uv{kruhovými objezdy bez jedné hrany},
+nalezením $(\log n)$-clusterizace, použitím bitové reprezentace množin uvnitř clusterů
+a přebarvovací struktury na~hrany mezi clustery.
-\h{Stromoví pøedchùdci}
+\h{Stromoví předchůdci}
-\s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si pøedzpracovat zakoøenìný strom~$T$
-tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbli¾¹ího
-spoleèného pøedchùdce.
+\s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si předzpracovat zakořeněný strom~$T$
+tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbližšího
+společného předchůdce.
-\s{Triviální øe¹ení LCA:}
+\s{Triviální řešení LCA:}
\itemize\ibull
-\:Vystoupáme z~$x$ i $y$ do~koøene, oznaèíme vrcholy na~cestách a kde se poprvé
- potkají, tam je hledaný pøedchùdce. To je lineární s~hloubkou a nepotøebuje
- pøedzpracování.
-\:Vylep¹ení: Budeme stoupat z~$x$ a $y$ støídavì. Tak potøebujeme jen lineárnì mnoho
- krokù vzhledem ke~vzdálenosti spoleèného pøedchùdce.
-\:Pøedpoèítáme v¹echny mo¾nosti: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
-\:\dots\ co dál?
+\:Vystoupáme z~$x$ i $y$ do~kořene, označíme vrcholy na~cestách a kde se poprvé
+ potkají, tam je hledaný předchůdce. To je lineární s~hloubkou a nepotřebuje
+ předzpracování.
+\:Vylepšení: Budeme stoupat z~$x$ a $y$ střídavě. Tak potřebujeme jen lineárně mnoho
+ kroků vzhledem ke~vzdálenosti společného předchůdce.
+\:Předpočítáme všechny možnosti: předzpracování $\O(n^2)$, dotaz $\O(1)$.
+\:\dots\ co dál?
\endlist
-\>Vìrni vtipùm o~matfyzácích a èlánku \cite{bender00lca} pøevedeme radìji tento problém na~jiný.
+\>Věrni vtipům o~matfyzácích a článku \cite{bender00lca} převedeme raději tento problém na~jiný.
-\s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme pøedzpracovat posloupnost èísel
-$a_1,\ldots a_n$ tak, abychom umìli rychle poèítat $\min_{x\le i\le y} a_i$.%
-\foot{V¹imnìte si, ¾e pro sumu místo minima je tento problém velmi snadný.}
+\s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme předzpracovat posloupnost čísel
+$a_1,\ldots a_n$ tak, abychom uměli rychle počítat $\min_{x\le i\le y} a_i$.%
+\foot{Všimněte si, že pro sumu místo minima je tento problém velmi snadný.}
-\s{Lemma:} LCA lze pøevést na~RMQ s~lineárním èasem na~pøedzpracování a konstantním
-èasem na~pøevod dotazu.
+\s{Lemma:} LCA lze převést na~RMQ s~lineárním časem na~předzpracování a konstantním
+časem na~převod dotazu.
-\proof Strom projdeme do~hloubky a poka¾dé, kdy¾ vstoupíme do~vrcholu (a» ji¾ poprvé nebo se do~nìj vrátíme),
-zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejvy¹¹í vrchol mezi libovolnou
-náv¹tìvou~$x$ a libovolnou náv¹tìvou~$y$.
+\proof Strom projdeme do~hloubky a pokaždé, když vstoupíme do~vrcholu (ať již poprvé nebo se do~něj vrátíme),
+zapíšeme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejvyšší vrchol mezi libovolnou
+návštěvou~$x$ a libovolnou návštěvou~$y$.
\qed
-\s{Triviální øe¹ení RMQ:}
+\s{Triviální řešení RMQ:}
\itemize\ibull
-\:Pøedpoèítáme v¹echny mo¾né dotazy: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
-\:Pro ka¾dé $i$ a $j\le \log n$ pøedpoèítáme $m_{ij} = \min\{ a_i, a_{i+1}, \ldots, a_{i+2^j-1} \}$,
-èili minima v¹ech blokù velkých jako nìjaká mocnina dvojky. Kdy¾ se poté nìkdo zeptá
-na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme nejvìt¹í~$k$ takové, ¾e $2^k < j-i$
-a vrátíme:
+\:Předpočítáme všechny možné dotazy: předzpracování $\O(n^2)$, dotaz $\O(1)$.
+\:Pro každé $i$ a $j\le \log n$ předpočítáme $m_{ij} = \min\{ a_i, a_{i+1}, \ldots, a_{i+2^j-1} \}$,
+čili minima všech bloků velkých jako nějaká mocnina dvojky. Když se poté někdo zeptá
+na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme nejvÄ\9btÅ¡Ã~$k$ takové, že $2^k < j-i$
+a vrátíme:
$$\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} ).$$
-Tak zvládneme dotazy v~èase $\O(1)$ po~pøedzpracování v~èase $\O(n\log n)$.
+Tak zvládneme dotazy v~čase $\O(1)$ po~předzpracování v~čase $\O(n\log n)$.
\endlist
-My si ov¹em v¹imneme, ¾e ná¹ pøevod z~LCA vytváøí dosti speciální instance problému RMQ,
-toti¾ takové, v~nich¾ je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
-øíkat RMQ${\pm}1$ a budeme je umìt øe¹it ¹ikovnou dekompozicí.
+My si ovšem všimneme, že náš převod z~LCA vytváří dosti speciální instance problému RMQ,
+totiž takové, v~nichž je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
+říkat RMQ${\pm}1$ a budeme je umět řešit šikovnou dekompozicí.
-\s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdìlíme na~bloky velikosti $b=1/2\cdot \log n$,
-ka¾dý dotaz umíme rozdìlit na~èást týkající se celých blokù a maximálnì dva dotazy na~èásti blokù.
+\s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdělíme na~bloky velikosti $b=1/2\cdot \log n$,
+každý dotaz umíme rozdělit na~část týkající se celých bloků a maximálně dva dotazy na~části bloků.
-V¹imneme si, ¾e aèkoliv blokù je mnoho, jejich mo¾ných typù (tj. posloupností klesání
-a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky tého¾ typu se li¹í pouze posunutím
-o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro ka¾dý
-blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme èas
-$\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ pøedzpracováním a $\O(1)$ dotazem.
+Všimneme si, že ačkoliv bloků je mnoho, jejich možných typů (tj. posloupností klesání
+a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky téhož typu se liší pouze posunutím
+o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro každý
+blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme čas
+$\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ předzpracováním a $\O(1)$ dotazem.
-Mimo to je¹tì vytvoøíme komprimovanou posloupnost, v~ní¾ ka¾dý blok nahradíme
-jeho minimem. Tuto posloupnost délky $n/b$ budeme pou¾ívat pro èásti dotazù
-týkající se celých blokù a pøipravíme si pro ni \uv{logaritmickou} variantu
-triviální struktury. To nás bude stát $\O(n/b\cdot\log (n/b))=\O(n/\log n\cdot\log n)=\O(n)$ na~pøedzpracování
+Mimo to ještě vytvoříme komprimovanou posloupnost, v~níž každý blok nahradíme
+jeho minimem. Tuto posloupnost délky $n/b$ budeme používat pro části dotazů
+týkající se celých bloků a připravíme si pro ni \uv{logaritmickou} variantu
+triviální struktury. To nás bude stát $\O(n/b\cdot\log (n/b))=\O(n/\log n\cdot\log n)=\O(n)$ na~předzpracování
a $\O(1)$ na~dotaz.
-Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním
-pøedzpracování a vý¹e zmínìným pøevodem i algoritmus na~LCA se stejnými parametry.
-Je¹tì uká¾eme, ¾e pøevod mù¾e fungovat i v~opaèném smìru, a~tak mù¾eme získat
-i konstantní/lineární algoritmus pro obecné RMQ.
+Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním časem na~dotaz po~lineárním
+předzpracování a výše zmíněným převodem i algoritmus na~LCA se stejnými parametry.
+Ještě ukážeme, že převod může fungovat i v~opačném směru, a~tak můžeme získat
+i konstantní/lineární algoritmus pro obecné RMQ.
-\s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
-jeho¾ koøenem je minimum posloupnosti, tj. nìjaké $a_j=\min_i a_i$, jeho levý podstrom je
-kartézský strom pro $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.
+\s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
+jehož kořenem je minimum posloupnosti, tj. nějaké $a_j=\min_i a_i$, jeho levý podstrom je
+kartézský strom pro $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.
-\s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase.
+\s{Lemma:} Kartézský strom je možné zkonstruovat v~lineárním čase.
-\proof Pou¾ijeme inkrementální algoritmus. V¾dy si budeme pamatovat
-kartézský strom pro ji¾ zpracované prvky a pozici posledního zpracovaného
-prvku v~tomto stromu. Kdy¾ pøidáváme dal¹í prvek, hledáme místo, kam ho
-pøipojit, od~tohoto oznaèeného prvku nahoru. Pov¹imnìme si, ¾e vzhledem
-k~potenciálu rovnému hloubce oznaèeného prvku je èasová slo¾itost pøidání
-prvku amortizovanì konstantní.
+\proof Použijeme inkrementálnà algoritmus. Vždy si budeme pamatovat
+kartézský strom pro již zpracované prvky a pozici posledního zpracovaného
+prvku v~tomto stromu. Když přidáváme další prvek, hledáme místo, kam ho
+pÅ\99ipojit, od~tohoto oznaÄ\8deného prvku nahoru. PovÅ¡imnÄ\9bme si, že vzhledem
+k~potenciálu rovnému hloubce označeného prvku je časová složitost přidání
+prvku amortizovaně konstantní.
\qed
-\s{Lemma:} RMQ lze pøevést na~LCA s~lineárním èasem na~pøedzpracování a konstantním
-èasem na~pøevod dotazu.
+\s{Lemma:} RMQ lze převést na~LCA s~lineárním časem na~předzpracování a konstantním
+časem na~převod dotazu.
-\proof Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu.
+\proof Sestrojíme kartézský strom a RMQ převedeme na~LCA v~tomto stromu.
\qed
-Výsledky této podkapitoly mù¾eme shrnout do~následující vìty:
+Výsledky této podkapitoly můžeme shrnout do~následující věty:
-\s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz
-po~pøedzpracování v~lineárním èase.
+\s{Věta:} Problémy LCA i RMQ je možné řešit v~konstantním čase na~dotaz
+po~předzpracování v~lineárním čase.
-\s{Cvièení:} Vymyslete jednodu¹¹í strukturu pro RMQ, víte-li, ¾e v¹echny dotazy budou na~intervaly stejné délky.
+\s{Cvičení:} Vymyslete jednodušší strukturu pro RMQ, víte-li, že všechny dotazy budou na~intervaly stejné délky.
\references
\bye
projects / ga.git / blobdiff