From 35db8769addf022e6d89c2758b6795078ec45874 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 30 Dec 2006 23:37:57 +0100 Subject: [PATCH] Eh well, fixes. --- 10-decomp/10-decomp.tex | 102 ++++++++++++++++++++++------------------ 1 file changed, 56 insertions(+), 46 deletions(-) diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index 02e4fd0..1be6170 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -17,9 +17,9 @@ zda dva vrcholy le 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 \ -porovnává barvy, operace \ prvky jedné tøídy pøebarví. +porovnává barvy, operace \ prvky jedné tøídy pøebarvuje. -Operace \ tak pracuje v~konstantním èase, \ mù¾e zabrat a¾ lineární. Mù¾eme si ale +Operace \ tak pracuje v~konstantním èase, \ mù¾e zabrat a¾ lineární. 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í @@ -37,14 +37,14 @@ jedn dva stromy s~koøeny $v$, $w$ a $r(v)), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li, rovnou pod koøen. \endlist -\s{Pozorování:} Pravidlo Union by rank samotné zajistí, ¾e strom ranku $r$ bude +\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.} @@ -67,11 +67,11 @@ definujeme: \:{\I Koøeny mikrostromù} $R$ budou nejvy¹¹í vrcholy, pod~nimi¾ je nejvý¹e $\log n$ listù. \:{\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 zbytkem stromu~$T$, který nepatøí ani do~mikrostromù, ani do~spojovacích hran. +\:{\I Makrostrom} je tvoøen ostatní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 makrostrom\foot{Mù¾e jich být i více, pøedstavte si dekompozici hvìzdy.}, tak¾e +alespoò jeden mikrostrom\foot{Mù¾e jich být i více, pøedstavte si dekompozici hvìzdy.}, 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 @@ -79,19 +79,23 @@ vyskytovat dlouh ji nahradíme hranou, která bude existovat právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty. \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si pamatujeme -(jako èísla) mno¾iny ji¾ pøítomných hran. Pak si je¹tì pamatujeme zkomprimovanou cestu (hrany +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. +\>$\(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. +\endalgo + +\>$\(x,y):$ \algo -\:\(x,y) (pøidání hrany $e=xy$ na~cestu): -\::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. -\:\(x,y): -\::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, 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, 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)$ @@ -103,15 +107,21 @@ mno 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 pamatovat mno¾inu pøítomných hran~$F$. +na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat mno¾inu +pøítomných hran~$F$. + +\>$\(x,y):$ + +\algo +\:Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané). +\:$F := F \cup \{i\}$. +\endalgo + +\>$\(x,y):$ \algo -\:\(x,y) -\::Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané). -\::$F := F \cup \{i\}$. -\:\(x,y): -\::$P := P_x \mathop{\Delta} P_v$ (to je 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 := P_x \mathop{\Delta} P_v$ (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:} Zkomprimujeme cesty a výsledný strom rozlo¾íme @@ -157,8 +167,8 @@ rozlo Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy se hodí napøíklad následující my¹lenka: -\s{Definice:} (Fredericksonova clusterizace) Nech» $G$ je graf kde $\forall v \in V(G): {\rm deg}(v)\le 3$ -a $c \in {\bb N}$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad +\s{Definice:} (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) $G_1, G_2, \ldots, G_k$ takový, ¾e platí: \itemize\ibull \:$\forall v \in V \exists ! i: v \in C_i$. @@ -168,10 +178,10 @@ nejv \:®ádné dva sousední clustery nelze spojit. \endlist -\s{Vìta:} (Frederickson) $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù a lze ji -najít v~lineárním èase. +\s{Vìta:} (Frederickson) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje +algoritmus, který jednu takovou najde v~lineárním èase. -\s{Dùkaz:} Hladovì pomocí DFS. \qed +\s{Dùkaz:} První èast 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 vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik}, @@ -199,17 +209,7 @@ V \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 sèítání místo minima je tento problém velmi snadný.} - -\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 délky~$l$, najdeme nejbli¾¹í ni¾¹í mocninu dvojky a spoèteme minimum -z~minim blokù této velikost pøira¾ených k~zaèátku a ke~konci dotazovaného bloku. -Tak zvládneme dotaz v~èase $\O(1)$ za~cenu pøedzpracování v~èase $\O(n\log n)$. -\endlist +\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. @@ -219,7 +219,17 @@ zap náv¹tìvou~$x$ a první náv¹tìvou~$y$, nebo opaènì. \qed -My si ov¹em v¹imneme, ¾e tento pøevod vytváøí dosti speciální instance problému 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 $\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} )$. +Tak zvládneme dotaz v~èase $\O(1)$ za~cenu 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í. @@ -230,22 +240,22 @@ V 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í a $\O(1)$ dotazem. +$\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 +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)=\O(n)$ na~pøedzpracování +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. -To nám tedy dává algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním -pøedzpracováním a vý¹e zmínìným pøevodem i algoritmus na~LCA se stejnými parametry. +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 $a_j=\min_i a_i$, jeho levý syn je kartézský strom pro -$a_1,\ldots,a_{j-1}$ a pravý syn kartézský strom pro $a_{j+1},\ldots,a_n$. +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$. \s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase. -- 2.39.2