Prvni cast planarity.

[ga.git] / 10-decomp / 10-decomp.tex

diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex
index 1be6170957fd8354faf25e16606c5c877546136f..03d484d44c759ff3ecbcbba2206d7c989c0a28a3 100644 (file)
--- a/10-decomp/10-decomp.tex
+++ b/10-decomp/10-decomp.tex
@@ -1,6 +1,6 @@
 \input ../sgr.tex
 
-\prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek}
+\prednaska{10}{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,
@@ -49,7 +49,7 @@ m
 bude omezena $\O(\log n)$.%
 \foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.}
 
-\s{Vìta:} (Tarjan et al.) Kombinace Union by rank a Path compression vede k~amortizované
+\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.}
@@ -59,7 +59,8 @@ p
 Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe
 posloupnost unionù, èili strom, který spojováním komponent vznikne. 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.
+konstantním èase. Tento algoritmus je kombinací dekompozic popsaných v~\cite{alstrup97optimal}
+a \cite{alstrup98marked}.
 
 \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
 definujeme:
@@ -157,15 +158,19 @@ zda je p
 \:Odpovíme podle struktury pro makrostrom.
 \endalgo
 
-\s{Analýza:} Operace s~mikrostromy, spojovacími hranami a cestami jsou, jak u¾ víme,
-amortizovanì konstantní. Operace s~makrostromy také, jeliko¾ trvají $\O(\log n)$,
-ale provede se jich pouze $\O(n/\log n)$. Ka¾dou operaci \<Union> nebo \<Find>
-rozlo¾íme $\O(1)$ tìchto dílèích operací, tak¾e bude také trvat $\O(1)$ amortizovanì.
+\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ì
+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.}
 
 \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:
+se hodí napøíklad následující my¹lenka: \cite{frederickson91ambivalent}
 
 \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
@@ -205,7 +210,7 @@ spole
 \:\dots\ co dál?
 \endlist
 
-Vìrni vtipùm o~matfyzácích 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$.%
@@ -278,4 +283,5 @@ V
 \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.
 
+\references
 \bye