From adb296fa19eb857ab07dd411e504df6a8bb363ad Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 30 Jan 2007 15:55:48 +0100 Subject: [PATCH] Drobne opravy a vylepseni formulaci. --- 10-suffix/10-suffix.tex | 10 +++++----- 11-planar/11-planar.tex | 2 +- 2-dinic/2-dinic.tex | 2 +- 3-bipcon/3-bipcon.tex | 3 ++- 4-ght/4-ght.tex | 2 +- 5-mst/5-mst.tex | 5 +++-- 6-borjar/6-borjar.tex | 2 +- 9-decomp/9-decomp.tex | 10 +++++----- 8 files changed, 19 insertions(+), 17 deletions(-) diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex index 9b2268c..f75d476 100644 --- a/10-suffix/10-suffix.tex +++ b/10-suffix/10-suffix.tex @@ -3,7 +3,7 @@ \prednaska{10}{Suffixové stromy}{} V~této kapitole popí¹eme jednu pozoruhodnou datovou strukturu, pomocí ní¾ doká¾eme problémy týkající -se øetìzcù pøevádìt na grafové problémy a tak je øe¹it v~lineárním èase. +se øetìzcù pøevádìt na grafové problémy a øe¹it je tak v~lineárním èase. \h{Øetìzce, trie a suffixové stromy} @@ -100,11 +100,11 @@ vrchol, pod kter mno¾inu slov.\foot{Jen si musíme dát pozor, abychom si moc nezvìt¹ili abecedu, ale to bude jasné, a¾ pøedvedeme konkrétní konstrukce.} -\:{\I Nejdel¹í palindromické podslovo} (tj. takové $\beta\subset\alpha$, pro nì¾ je $\beta_R=\beta$) --- postavíme spoleèný ST\$ pro slova $\alpha$ a $\alpha_R$. Postupnì procházíme pøes v¹echny mo¾né støedy +\:{\I Nejdel¹í palindromické podslovo} (tj. takové $\beta\subset\alpha$, pro nì¾ je $\beta^R=\beta$) +-- postavíme spoleèný ST\$ pro slova $\alpha$ a $\alpha^R$. Postupnì procházíme pøes v¹echny mo¾né støedy palindromického podslova a v¹imneme si, ¾e takové slovo je pro ka¾dý støed nejdel¹ím spoleèným prefixem podslova od~tohoto bodu do~konce a podslova od~tohoto bodu pozpátku k~zaèátku, -èili nìjakého suffixu $\alpha$ a nìjakého suffixu $\alpha_R$. Tyto suffixy ov¹em odpovídají +èili nìjakého suffixu $\alpha$ a nìjakého suffixu $\alpha^R$. Tyto suffixy ov¹em odpovídají listùm sestrojeného ST a jejich nejdel¹í spoleèný prefix je nejbli¾¹ím spoleèným pøedchùdcem ve~stromu, tak¾e staèí pro strom vybudovat datovou strukturu pro spoleèné pøedchùdce a s~její pomocí doká¾eme jeden støed prozkoumat v~konstantním èase. @@ -140,7 +140,7 @@ v~n \s{Vìta:} Suffixový strom pro slovo $\sigma\$$ je lineárnì ekvivalentní s~dvojicí $(A_\sigma,L_\sigma)$. [Jinými slovy, kdy¾ máme jedno, mù¾eme z~toho v~lineárním èase spoèítat druhé, a naopak.] -\proof Kdy¾ projdeme ST($\sigma$) do hloubky, poøadí listù odpovídá $A_\sigma$ a písmenkové hloubky vnitøních +\proof Kdy¾ projdeme ST($\sigma\$$) do hloubky, poøadí listù odpovídá $A_\sigma$ a písmenkové hloubky vnitøních vrcholù v~inorderu odpovídají $L_\sigma$. Naopak ST($\sigma$) získáme tak, ¾e sestrojíme kartézský strom pro~$L_\sigma$ (získáme vnitøní vrcholy ST), doplníme do~nìj listy, pøiøadíme jim suffixy podle~$A_\sigma$ a nakonec podle listù rekonstruujeme nálepky hran. diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index fba5770..8e6f962 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -122,7 +122,7 @@ b i~vrchol, pøes který je~$B$ pøipojen ke~zbytku grafu. Proto externí aktivitu nadefinujeme tak, aby pokrývala i tyto pøípady: -\s{Definice:} Vrchol~$w$ je {\I externì aktivní} pokud buïto z~$w$ vede zpìtná +\s{Definice:} Vrchol~$w$ je {\I externì aktivní,} pokud buïto z~$w$ vede zpìtná hrana do~je¹tì nenakresleného vrcholu, nebo je pod~$w$ pøipojen externì aktivní blok, èili blok obsahující alespoò jeden externì aktivní vrchol. diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index e66560f..fb84500 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -105,7 +105,7 @@ d \uv{Hrrr na nì!} a kdy¾ to nevyjde (dostaneme se do slepé ulièky), kus ustoupíme a pøi ústupu èistíme sí» odstraòováním slepé ulièky. -\:U¾ pøi prohledáváni si rovnou udr¾ujeme minimum z rezerv a pøi zpáteèní cestì +\:U¾ pøi prohledávání si rovnou udr¾ujeme minimum z rezerv a pøi zpáteèní cestì opravujeme kapacity. Snadno zkombinujeme s~prohledáváním do~hloubky. \:V prùbìhu výpoètu udr¾ujeme jen sí» rezerv a tok vypoèteme a¾ nakonec z rezerv a kapacit. \:Kdy¾ budeme chtít hledat minimální øez, spustíme po~Dinicovu algoritmu je¹tì jednu iterací F-F diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 792d2a5..eb96fa3 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -104,7 +104,8 @@ v_{i-1}\},u_{i-1})$, proto nerovnost plyne z~legálnosti uspoøádání. Chceme ukázat, ¾e velikost na¹eho øezu~$C$ je alespoò taková, jako velikost øezu kolem vrcholu $v_n$. -V¹imneme si, ¾e $ \vert C \vert \geq \sum_{i=1}^{n-1} d(v_i,u_i)$. Uká¾eme, ¾e pravá strana je alespoò $d(v_n)$: +V¹imneme si, ¾e $\vert C \vert \geq \sum_{i=1}^{n-1} d(v_i,u_i)$. Hrany mezi $v_i$ a $u_i$ jsou toti¾ navzájem +rùzné a ka¾dá z~nich je souèástí øezu~$C$. Uká¾eme, ¾e pravá strana je alespoò $d(v_n)$: $$\eqalign{ \sum_{i=1}^{n-1} d(v_i,u_i) &= \sum_{i=1}^{n-1} d(\{v_1\ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_i) \geq \cr &\geq \sum_{i=1}^{n-1} d(\{v_1 \ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_{i-1}) = \cr diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 983c38f..d396fec 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -189,7 +189,7 @@ D pøedpokladu ($R_1$ i $R_2$ jsou men¹í ne¾ $R$) existuje \PGHT{} $T_1=((R_1,F_1),C_1)$ pro $R_1$ na $G_1$ a $T_2=((R_2,F_2),C_2)$ pro $R_2$ na $G_2$. -Nyní vytvoøíme \PGHT{} pro pùvodní graf. Oznaème $r_1$ ten vrchol $R_1$, pro který je $v_1 \in C(r_1)$, +Nyní vytvoøíme \PGHT{} pro pùvodní graf. Oznaème $r_1$ ten vrchol $R_1$, pro který je $v_1 \in C_1(r_1)$, a~obdobnì $r_2$. Oba \PGHT{} $T_1$ a $T_2$ spojíme hranou $r_1r_2$, tak¾e \PGHT{} pro $G$ bude $T=((R_1 \cup R_2,F_1 \cup F_2 \cup {r_1r_2}),C)$. Tøídy rozkladu~$C$ zvolíme tak, ¾e pro $r\in R_1$ bude $C(r)=C_1(r)\setminus\{v_1\}$ a pro $r\in R_2$ bude $C(r)=C_2(r)\setminus\{v_2\}$ [odebrali jsme vrcholy $v_1$ a $v_2$ z~rozkladu~$C$]. diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 327c325..86b4218 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -224,7 +224,7 @@ Op a v¹echny tyto nalezené hrany naráz pøidáme (aplikujeme nìkolik modrých pravidel najednou). Pokud jsou v¹echny váhy rùzné, cyklus tím nevznikne. -Poèet stromeèku klesá exponenciálnì $\Rightarrow$ fází je celkem $\log n$. Pokud ka¾dou fázi +Poèet stromeèkù klesá exponenciálnì $\Rightarrow$ fází je celkem $\log n$. Pokud ka¾dou fázi implementujeme lineárním prùchodem celého grafu, dostaneme slo¾itost $\O(m\log n)$. Mimo to lze ka¾dou fázi výteènì paralelizovat. @@ -236,7 +236,8 @@ hrany vedouc Pøi ¹ikovné implementaci pomocí haldy dosáhneme èasové slo¾itosti $\O(m\log n)$, v~pøí¹tí kapitole uká¾eme implementaci je¹tì ¹ikovnìj¹í. \s{Cvièení:} -Naleznìte algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$. +Naleznìte jednoduchý algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$ +nebo dokonce~$\O(m+nk)$. \references \bye diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index 475014d..139ba1d 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -132,7 +132,7 @@ algoritmu s~kontrahov \s{Èasová slo¾itost:} Slo¾itost první èásti je $\O(m\log\log n)$. Poèet vrcholù se po~první èásti algoritmu sní¾í na~$n'\leq n/\log n$ a slo¾itost druhé èásti bude -tedy nanejvý¹ $\O(m+n\log n'/\log n)=\O(m)$. +tedy nanejvý¹ $\O(m+n'\log n'/\log n)=\O(m)$. \h{Jarníkùv algoritmus s~omezením velikosti haldy} diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex index f3f2bed..e36a55b 100644 --- a/9-decomp/9-decomp.tex +++ b/9-decomp/9-decomp.tex @@ -218,7 +218,7 @@ je nejv \:®ádné dva sousední clustery nelze spojit. \endlist -\s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) 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 @@ -254,7 +254,7 @@ $a_1,\ldots a_n$ tak, abychom um \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), +\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 nejhlub¹í vrchol mezi libovolnou náv¹tìvou~$x$ a libovolnou náv¹tìvou~$y$. \qed @@ -275,7 +275,7 @@ toti øí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 @@ -295,8 +295,8 @@ Je 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. -- 2.39.2