které u¾ umíme (obvykle vhodným kódováním èísly) øe¹it v~konstantním
èase.
-\h{Union-Find problem}
+\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>
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í:} Ka¾dé tøídì pøiøadíme unikátní barvu, kterou obarvíme prvky tøídy. Operace \<Find>
-porovnává barvy, operace \<Union> prvky jedné tøídy pøebarvuje.
+\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
\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ì podmínky:
+jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì pravidla:
\itemize\ibull
-\:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Pokud spojujeme
+\:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. 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 by size,} které pøipojuje men¹í
\s{Pozorování:} Samotné pravidlo Union by rank zajistí, ¾e strom ranku $r$ bude
mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací
-bude omezena $\O(\log n)$.%
-\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.}
+bude omezena $\O(\log n)$ v~nejhor¹ím pøípadì.%
+\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila. \cite{tarjan84setunion}}
-Ve~skuteènosti se popsaná struktura chová daleko lépe:
+Amortizovanì se ale popsaná struktura chová daleko lépe:
\s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) Kombinace Union by rank a Path compression vede k~amortizované
slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
\foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím
pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.}
+Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný, ale naznaèíme alespoò,
+¾e amortizovaná èasová slo¾itost je omezena iterovaným logaritmem, konkrétnì ¾e
+ve~struktuøe s~$n$ prvky trvá provedení $\ell$~operací Union a Find $\O((n+\ell)\cdot\log^* n)$.
+
+\def\up{\mathop{\uparrow}}
+
+\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í.
+
+Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù (vrchol, který ji¾ není
+koøenem, si pamatuje svùj poslední rank z~doby, kdy je¹tì koøenem byl):
+$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ì, vyu¾ívajíce toho, ¾e vrcholù s~rankem~$r$ je nejvý¹e~$n/2^r$:
+$$
+{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} =
+{n \over 2^{2\up(k-1)}} \cdot 1 =
+{n \over 2\up k}.
+$$
+
+Operace Union a Find potøebují nekonstantní èas pouze na~vystoupání ze~zadaného vrcholu~$v$ do~koøene stromu
+a tento èas je pøímo úmìrný poètu hran na~cestì z~$v$ do~koøene. Tato cesta je následnì 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 jistì $\O(\log^* n)$), naúètujeme právì provádìné operaci, tak¾e
+jimi celkem strávíme èas $\O(\ell\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ì, který ji¾ není koøenem stromu. Hrana z~$v$ do~jeho rodièe
+bude úètována vrcholu~$v$ pouze tehdy, le¾í-li rodiè také v~$k$-té skupinì. Jen¾e
+ranky vrcholù na~cestì z~libovolného vrcholu do~koøene ostøe rostou, tak¾e pøi ka¾dém pøepojení
+rank rodièe vrcholu~$v$ vzroste, a~proto po~$2\up k$ pøepojeních bude rodiè vrcholu~$v$ v~$(k+1)$-ní
+nebo vy¹¹í skupinì. Ka¾dému vrcholu v~$k$-té skupinì tedy úè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)$.
+
\h{Union-Find s~pøedem známými Uniony}
-Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe
+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
-v~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních
+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 a umíme smazat hranu a otestovat, zda jsou
+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,
\s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
definujeme:
\itemize\ibull
-\:{\I Koøeny mikrostromù} $R$ budou nejvy¹¹í vrcholy, pod~nimi¾ je nejvý¹e $\log n$ listù
+\:{\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ù.
\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
+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
\>$\<Find>(x,y):$
\algo
-\:$P \leftarrow P_x \mathop{\Delta} P_v$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$).
+\:$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, makrostromy a spojovací
-hrany. V~mikrostromech i makrostromech zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme
+\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{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~makrostromy, které trvají $\O(\log n)$ amortizovanì
+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
\h{Fredericksonova clusterizace}
Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy
-se hodí napøíklad následující my¹lenka: \cite{frederickson91ambivalent}
+se hodí napøíklad následující my¹lenka:
-\s{Definice:} (Fredericksonova clusterizace) Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3
+\s{Definice:} {\I (Fredericksonova clusterizace)} Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3
a $c\ge 1$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad
-$G$ na~souvislé podgrafy (clustery) $C_1, C_2, \ldots, C_k$ takový, ¾e platí:
+$G$ na~souvislé podgrafy {\I (clustery)} $C_1, C_2, \ldots, C_k$ takový, ¾e platí:
\itemize\ibull
-\:$\forall v \in V \exists ! i: v \in C_i$.
-\:$\forall i: \vert C_i\vert \le c$.
-\:$\forall i$ je vnìj¹í stupeò $C_i$ (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu)
-nejvý¹e~3. Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$.
+\:Ka¾dý vrchol se nachází v~právì jednom clusteru (hrany mohou vést i mezi clustery).
+\:Ka¾dý cluster má nejvý¹e~$c$ vrcholù.
+\:Vnìj¹í stupeò ka¾dého clusteru (tj. poèet hran, které vedou mezi $C_i$ a ostatními
+clustery; mezi ka¾dou dvojicí clusterù poèítáme jen jednu hranu) je nejvý¹e~3.
+Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$.
\:®ádné dva sousední clustery nelze spojit.
\endlist
-\s{Vìta:} (Frederickson) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje
+\s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Ka¾dá $c$-clusterizace grafu $G$ má $\O(\vert V(G)\vert /c)$ clusterù. Existuje
algoritmus, který jednu takovou najde v~lineárním èase.
\proof První èást rozborem pøípadù, druhá hladovì pomocí DFS. \qed
-\s{Pou¾ití:} Pøedchozí variantu Union-Find problemu bychom také mohli vyøe¹it nahrazením
+\s{Pou¾ití:} Pøedchozí variantu Union-Find problému bychom také mohli vyøe¹it nahrazením
vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik},
nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù
a pøebarvovací struktury na~hrany mezi clustery.
\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¾ nav¹tívíme vrchol (v~inorderu),
-zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejhlub¹í vrchol mezi libovolnou
+\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
øí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~èásteèné bloky.
+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
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 $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$.
+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{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.
+
\references
\bye
projects / ga.git / blobdiff