From 16b2d363cbf0fffb38a3f40fe1b12e04e77d584d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 17 Jan 2007 17:23:59 +0100 Subject: [PATCH] Presli jsme na stranky formatu A5. K tomu se poji spousta drobnych zmen v umisteni obrazku do textu. --- 1-toky/1-toky.tex | 18 ++++++++--------- 10-decomp/10-decomp.tex | 11 ++++++---- 11-planar/11-planar.tex | 13 +++++++----- 2-dinic/2-dinic.tex | 14 ++++++------- 3-bipcon/3-bipcon.tex | 7 ++++--- 4-ght/4-ght.tex | 45 +++++++++++++++++++++-------------------- 7-ram/7-ram.tex | 14 ++++++------- 8-qheap/8-qheap.tex | 16 +++++++-------- 9-suffix/9-suffix.tex | 22 +++++++++++--------- Makerules | 20 +++++++----------- all/ga.tex | 4 +++- sgr.tex | 24 +++++++++++++++------- 12 files changed, 112 insertions(+), 96 deletions(-) diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index bf7abce..6788966 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -13,7 +13,7 @@ Intuitivn ze~zdroje~$s$ (source) do~spotøebièe~$t$ (target), pøièem¾ tekutina se nikde mimo tato dvì místa neztrácí ani nevzniká. -\s{Definice:} +\ss{Definice:} \itemize\ibull \:{\I Sí»} je uspoøádaná pìtice $(V,E,s,t,c)$, kde: @@ -61,12 +61,10 @@ a~tedy i spojit analýzy Ford-Fulkersonova algoritmu. \qed -\s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾: -$$\eqalign{ -\sum_v f^\Delta(v) &= f^\Delta(s) + f^\Delta(t) \hbox{~~~(podle Kirchhoffova zákona jsou v¹echna ostatní $f^\Delta(v)=0$), ale také:} \cr -\sum_v f^\Delta(v) &= \sum_e f(e) - f(e) = 0 \hbox{~~~(ka¾dá hrana pøispìje k~jednomu $f^+(v)$ a k~jednomu $f^-(v)$),} -}$$ -tak¾e $\vert f\vert = -f^\Delta(s) = f^\Delta(t).$ +\s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾. Platí toti¾: +$$f^\Delta(s) + f^\Delta(t) = \sum_v f^\Delta(v) = \sum_e f(e) - f(e) = 0$$ +(první rovnost plyne z~Kirchoffova zákona -- v¹echna ostatní $f^\Delta(v)$ jsou nulová; druhá pak z~toho, +¾e ka¾dá hrana pøispìje k~jednomu $f^+(v)$ a k~jednomu $f^-(v)$). Proto je $\vert f\vert = -f^\Delta(s) = f^\Delta(t).$ Stejnì tak mù¾eme velikost toku zmìøit na~libovolném øezu: @@ -95,7 +93,7 @@ To~bohu pro~které je $f(e) < c(e)$, ale také hrany, po~kterých nìco teèe v~protismìru a my mù¾eme tok v~na¹em smìru simulovat odeètením od~toku v~protismìru. Trochu formálnìji: -\s{Definice:} +\ss{Definice:} \itemize\ibull \:{\I Rezerva} hrany $e=(v,w)$ pøi toku~$f$ se definuje jako $r(e) = (c(e) - f(e)) + f(e^\prime)$, kde $e^\prime=(w,v)$. @@ -104,7 +102,7 @@ v~na \:{\I Zlep¹ující cesta} je orientovaná cesta taková, ¾e v¹echny její hrany mají nenulovou rezervu. \endlist -\s{Algoritmus:} +\ss{Algoritmus:} \algo \:$f \leftarrow \$ @@ -150,7 +148,7 @@ a nav nové hrany z~$s$ do~v¹ech vrcholù partity~$A$ a ze~v¹ech vrcholù partity~$B$ do~$t$. Kapacity v¹ech hran nastavíme na jednièky: -\figure{bipartitni.eps}{Bipartitní graf a z~nìj odvozená sí» (v¹echny kapacity jsou jednièky).}{0.4\hsize} +\fig{bipartitni.eps}{0.4\hsize} Nyní si v¹imneme, ¾e ke~ka¾dému párování existuje celoèíselný tok stejné velikosti a naopak. Tak¾e najdeme maximální celoèíselný tok (tøeba F-F algoritmem) a do~párování umístíme diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index 7a248f0..c7f7fd7 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -1,5 +1,7 @@ \input ../sgr.tex +\hyphenation{mikro-strom mikro-stro-mo-vé} + \prednaska{10}{Dekompozice stromù}{} V~této kapitole uká¾eme nìkolik datových struktur zalo¾ených @@ -151,7 +153,7 @@ zda je p stromu spojeny hranou. Analogicky pro~$y$. \:[Nyní jsou $x$ a $y$ vrcholy cestovì zkomprimovaného stromu.] \:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom. -\:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostromové struktury na~spojení s~koøenem mikrostromu. +\: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$. \:[Nyní jsou $x$ a $y$ vrcholy makrostromu.] @@ -230,8 +232,9 @@ n \: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)$. +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)$. \endlist My si ov¹em v¹imneme, ¾e ná¹ pøevod z~LCA vytváøí dosti speciální instance problému RMQ, @@ -268,7 +271,7 @@ $a_1,\ldots,a_{j-1}$ a prav 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¹imneme si, ¾e vzhledem -k~potenciálu urèenému hloubkou oznaèeného prvku je èasová slo¾itost pøidání +k~potenciálu rovnému hloubce oznaèeného prvku je èasová slo¾itost pøidání prvku amortizovanì konstantní. \qed diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 2372ebd..cbe2d02 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -104,7 +104,8 @@ extern po~okraji bloku touto hranou (tím vytvoøí novou stìnu) a také mù¾e slouèit nìkolik blokù do~jednoho: -\twofigures{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize}{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize} +\figure{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize} +\figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize} Bude se nám hodit, ¾e èas potøebný na~tuto operaci je pøímo úmìrný poètu hran, které ubyly z~vnìj¹í stìny, co¾ je amortizovanì konstanta. @@ -125,7 +126,7 @@ nadefinujeme tak, aby pokr 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. -Jinými slovy $w$ je externì aktivní pøi zpracovávání vrcholu~$v$, pokud je $\(w) < \(v)$, +Jinými slovy vrchol $w$ je externì aktivní pøi zpracování vrcholu~$v$, pakli¾e $\(w) < \(v)$, nebo pokud pro nìkterého ze~synù $x$ le¾ícího v~jiném bloku je $\(x) < \(v)$. Druhá podmínka funguje díky tomu, ¾e koøen bloku má v~tomto bloku právì jednoho syna (jinak by existovala pøíèná hrana, co¾ víme, ¾e není pravda), tak¾e minimum z~\ù @@ -137,7 +138,7 @@ struktura pr pod vrcholem~$w$, reprezentovaných jejich koøeny (klony vrcholu~$w$) a jedinými syny koøenù. Tento seznam udr¾ujeme setøídìný vzestupnì podle $\$ù synù. -\s{Lemma:} Vrchol~$w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud buïto $\(w) < \(v)$, +\s{Lemma:} Vrchol~$w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud je buïto $\(w) < \(v)$, nebo první prvek seznamu $\(w)$ má $\ < \(v)$. Navíc seznamy \ lze udr¾ovat v~amortizovanì konstantním èase. @@ -290,7 +291,7 @@ graf nebyl rovinn \s{Lemma:} Pokud existuje zpìtná hrana, kterou algoritmus nenakreslil, graf na~vstupu není rovinný. -\proof Pro spor pøedpokládejme, ¾e pøi zpracování vrcholu~$v$ existuje +\proof Pro spor pøedpokládejme, ¾e po~zpracování vrcholu~$v$ existuje nìjaká zpìtná hrana~$wv$, kterou algoritmus nenakreslil, èili ¾e pøístup z~$v$ k~$w$ je v~obou smìrech blokován externì aktivními vrcholy. Rozborem pøípadù uká¾eme, ¾e tato situace vede ke~sporu buïto s~pravidly \#1 a \#2 nebo s~rovinností grafu. @@ -313,7 +314,9 @@ bloku br nerovinných minorù ($N_1$ a¾ $N_3$ jsou isomorfní s~$K_{3,3}$ a $N_4$ s~$K_5$): \bigskip -\centerline{\epsfbox{minor3.eps}\qquad\epsfbox{minor4.eps}\qquad\epsfbox{minor5.eps}\qquad\epsfbox{minor6.eps}} +\centerline{\epsfbox{minor3.eps}\qquad\epsfbox{minor4.eps}} +\bigskip +\centerline{\epsfbox{minor5.eps}\qquad\epsfbox{minor6.eps}} \bigskip \>Uva¾me, jak bude $B$ vypadat po~odebrání vrcholu~$v$ a hran z~nìj vedoucích: diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index d818983..62016ce 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -35,7 +35,7 @@ kdyby neuva \::Zlep¹i $f$ podle $f_B$ \endalgo -\figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.3\hsize} +\figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.4\hsize} \s{Slo¾itost algoritmu:} Oznaèíme $l$ délku nejkrat¹í $st$-cesty, $n$ poèet vrcholù sítì a $m$ poèet hran sítì. @@ -86,19 +86,19 @@ vrstvy do~$(i+1)$-n èervené vedou zpìt èi za~spotøebiè èi do~slepých ulièek. Pøi vyti¹tìní na papír není snadné je barevnì odli¹it od èerných.} se zahodí. -\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.3\hsize} +\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.5\hsize} Nové hrany mohou vznikat výhradnì jako opaèné k~èerným hranám (hrany ostatních barev padly za obì» proèi¹tìní). Jsou to tedy v¾dy zpìtné hrany vedoucí z~$i$-té vrstvy do~$(i-1)$-ní. -\figure{dinic-zpetnahrana.eps}{Vznik nové zpìtné hrany}{0.3\hsize} +\figure{dinic-zpetnahrana.eps}{Vznik nové zpìtné hrany}{0.4\hsize} Vznikem nových hran by proto mohly vzniknout nové $st$-cesty, které pou¾ívají zpìtné hrany. Jen¾e $st$-cesta, která pou¾ije zpìtnou hranu, musí alespoò jednou skoèit zpìt a nikdy nemù¾e skoèit dopøedu o~více ne¾ jednu vrstvu, a~proto je její délka alespoò $l+2$. Tím je vìta dokázána. \qed -\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.3\hsize} +\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize} \h{Implementaèní poznámky} @@ -213,7 +213,7 @@ radix-sortu. Pro jistotu si ho p \foot{Poslední cifrou myslíme nejménì významnou cifru.} cifry, poté podle pøedposlední, pøedpøedposlední a tak dále. -\figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.2\hsize} +\figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.4\hsize} V na¹em pøípadì budeme postupnì budovat sítì a v nich poèítat toky, a¾ nakonec získáme tok pro celou sí». @@ -222,7 +222,7 @@ budeme zv Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus. Pomocí pøedchozího odhadu uká¾eme, ¾e jedno volání Dinice nebude pøíli¹ drahé. -\figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.2\hsize} +\figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.4\hsize} Oznaème $k$ poèet bitù v zápisu nejvìt¹í kapacity z celé sítì. $k = \lfloor \log_2C \rfloor$. Postupnì budeme budovat sítì $G_i$ s~kapacitami $c_i(e) = \lfloor {c(e) / 2^{k-i}} \rfloor$. @@ -236,7 +236,7 @@ $$ c_{i+1}(e) = \left\{ \right. $$ -\figure{dinic-scaling-g.eps}{Sítì $G_0$, $G_1$ a $G_2$, jak vyjdou pro sí» z~pøedchozího obrázku}{0.8\hsize} +\figure{dinic-scaling-g.eps}{Sítì $G_0$, $G_1$ a $G_2$, jak vyjdou pro sí» z~pøedchozího obrázku}{0.9\hsize} Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus, ov¹em do zaèátku nepou¾ijeme nulový tok, nýbr¾ tok $2f_{i-1}$. Rozdíl toku z inicializace diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 12bdd67..71c2415 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -104,10 +104,11 @@ nerovnost plyne z LU vrchol Chceme ukázat, ¾e velikost libovolného øezu je alespoò taková, jako velikost øezu kolem vrcholu $v_n$. Platí, ¾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)$: - $$\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 \sum_{i=1}^{n-1} d(\{v_1 \ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_{i-1}) = \cr -&= d(\{v_1 \ldots v_{n-1}\},u_{n-1}) - d(\{v_1 \ldots v_0\},u_0) = d(\{v_1 \ldots v_{n-1}\},v_n) - 0 = d(v_n).\cr +\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 +&= d(\{v_1 \ldots v_{n-1}\},u_{n-1}) - d(\{v_1 \ldots v_0\},u_0) = \cr +&=d(\{v_1 \ldots v_{n-1}\},v_n) - 0 = d(v_n).\cr }$$ \qed diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 53d870e..2b26b1e 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -47,11 +47,12 @@ Pak $\d(e)$ je minim \proof Nejprve si doká¾eme jedno drobné {\advance\leftskip by 2em\advance\rightskip by 2em -\s{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e $r(x,z) \ge \min(r(x,y),r(y,z))$. +\s{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e: +$$r(x,z) \ge \min(r(x,y),r(y,z)).$$ \proof Buï $W$ minimální $xz$-øez. -\fig{4-ght-rez.eps}{5cm} +\fig{4-ght-rez.eps}{\epsfxsize} \noindent Vrchol $y$ musí být v~jedné z~komponent, BÚNO v~komponentì s~$x$. Pak ale $r(y,z) \le c(W)$, proto¾e $\d(W)$ je také $yz$-øez. Tedy $\min(r(x,y),r(y,z)) \le r(x,z)$.\qed @@ -83,27 +84,25 @@ p Nyní se nauèíme \GHT{} konstruovat, èím¾ také rozptýlíme obavy o~jejich existenci. Nejprve v¹ak budeme potøebovat jedno u¾iteèné lemma s~hnusnì technickým dùkazem: -\vbox to 0pt{\vskip-\baselineskip\rightline{\epsfysize=2cm\epsfbox{4-ght-htl.eps}}\vss}\vskip-\baselineskip -{ -\advance\rightskip by 17em \s{Hnusnì technické lemma (HTL):} Buïte¾ $s,t$ vrcholy grafu $(V,E)$, $\d(U)$ minimální \st-øez a $u\ne v$ dva rùzné vrcholy z~$U$. Pak existuje mno¾ina vrcholù $W \subseteq U$ taková, ¾e $\d(W)$ je minimální $uv$-øez. [To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.] +\fig{4-ght-htl.eps}{\epsfxsize} + \proof Nech» je $\d(X)$ minimální $uv$-øez. BÚNO mù¾eme pøedpokládat, ¾e $s\in U$ a $t\not\in U$, $u\in X$ a $v\not\in X$ a $s\in X$. Pokud by tomu tak nebylo, mù¾eme vrcholy pøeznaèit nebo nìkterou z~mno¾in nahradit jejím doplòkem. -} - Nyní mohou nastat dva pøípady:\numlist\nalpha -\vbox to 0pt{\vskip -1cm\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip +\vbox to 0pt{\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip {\advance\hsize by -14em -\:$t\not\in X$.\par -Doká¾eme dvì nerovnosti. Nerovnost $$\eqalignno{c(U \cup X) &\ge c(U)&(1)}$$ -platí proto, ¾e $U \cup X$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. Dal¹í -$$\eqalignno{c(U \cap X) + c(U \cup X) &\le c(U) + c(X)&(2)}$$ -doká¾eme \uv{rozborem pøípadù}. +\:$t\not\in X$. Tehdy si v¹imneme, ¾e platí: +$$\eqalignno{ +c(U \cup X) &\ge c(U),&(1) \cr +c(U \cap X) + c(U \cup X) &\le c(U) + c(X)&(2)}$$ +První nerovnost plyne z toho, ¾e $U \cup X$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. +Druhou doká¾eme rozborem pøípadù. } @@ -124,15 +123,16 @@ Vid a navíc hrany mezi $U\setminus X$ a $X \setminus U$ poèítáme jenom vpravo. Nerovnost $(2)$ tedy platí. -Nyní staèí nerovnosti $(2)$ a $(1)$ odeèíst, èím¾ získáme $$c(U \cap X) \le c(X),$$ +Nyní staèí nerovnosti $(2)$ a $(1)$ odeèíst, èím¾ získáme: $$c(U \cap X) \le c(X),$$ co¾ spolu s~obrázkem dokazuje, ¾e $\d(U \cap X)$ je také minimální $uv$-øez. \vbox to 0pt{\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-b.eps}}\vss}\vskip-\baselineskip {\advance\hsize by -14em\itemcount=1 -\:$t\in X$.\par -Postupovat budeme obdobnì jako v~pøedchozím pøípadì. Nerovnost $$\eqalignno{c(X \setminus U) &\ge c(U)&(3)}$$ -platí proto, ¾e $X \setminus U$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. Dal¹í -$$\eqalignno{c(U \setminus X) + c(X \setminus U) &\le c(U) + c(X)&(4)}$$ +\:$t\in X$. Postupovat budeme obdobnì jako v~pøedchozím pøípadì. Tentokrát se budou +hodit nerovnosti: +$$\eqalignno{c(X \setminus U) &\ge c(U)&(3)\cr +c(U \setminus X) + c(X \setminus U) &\le c(U) + c(X)&(4)}$$ +První platí proto, ¾e $X \setminus U$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez, druhou doká¾eme opìt \uv{rozborem pøípadù}. } @@ -145,7 +145,7 @@ U \setminus X&&&\hbox{---}&L_1,P_1\cr \&&&&\hbox{---}\cr }$$ -Stejnì jako v~pøedchozím pøípadì nerovnost $(4)$ platí. Odeètením $(4)$ a $(3)$ získáme +Stejnì jako v~pøedchozím pøípadì nerovnost $(4)$ platí. Odeètením $(4)$ a $(3)$ získáme: $$c(U \setminus X) \le c(X),$$ z~èeho¾ opìt dostaneme, ¾e $\d(U \setminus X)$ je také minimální $uv$-øez. \qeditem @@ -160,8 +160,8 @@ kde $(R,F)$ je strom a mno nám øíká, k~jakým vrcholùm \PGHT{} máme pøilepit které vrcholy pùvodního grafu. Navíc musí platit, ¾e:\numlist\ndotted \:$\forall r: r\in C(r)$, neboli ka¾dý vrchol \PGHT{} je pøilepen sám k~sobì, -\:$\forall st \in F: \d\left(\bigcup_{r\in K_1} C(r)\right)=\d\left(\bigcup_{r\in K_2} C(r)\right) -\hbox{ je minimální \st-øez, kde $K_1$ a $K_2$ jsou komponenty $(R,F) \setminus st$}.$ +\:$\forall st \in F: \d\left(\bigcup_{r\in K_1} C(r)\right)=\d\left(\bigcup_{r\in K_2} C(r)\right)$ +je minimální \st-øez, kde $K_1$ a $K_2$ jsou komponenty $(R,F) \setminus st$. \endlist @@ -182,7 +182,8 @@ hrany, kter do $v_1$ \ hrana, která z~nìj vedla do mno¾iny $V\setminus W$, pøípadnì ¾ádná, pokud do této mno¾iny ¾ádná hrana nevedla.} -\fig{4-ght-g1g2.eps}{0.9\hsize} +\fig{4-ght-g1g2-before.eps}{0.45\hsize} +\fig{4-ght-g1g2-after.eps}{0.9\hsize} Dále vytvoøíme mno¾iny vrcholù $R_1=R \cap \overline W$ a $R_2=R \cap W$. Dle indukèního pøedpokladu ($R_1$ i $R_2$ jsou men¹í ne¾ $R$) existuje \PGHT{} $T_1=((R_1,F_1),C_1)$ diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex index 0dd0211..e6e8bd6 100644 --- a/7-ram/7-ram.tex +++ b/7-ram/7-ram.tex @@ -18,21 +18,21 @@ \def\alik#1{% \medskip -\halign{\hskip 0.3\hsize\hfil $ ##$&\hbox to 0.4\hsize{${}##$ \hss}\cr +\halign{\hskip 0.2\hsize\hfil $ ##$&\hbox to 0.6\hsize{${}##$ \hss}\cr #1} \medskip } \prednaska{7}{Výpoèetní modely}{} -\h{Druhy výpoèetních modelù} - Kdy¾ jsme v~pøede¹lých kapitolách studovali algoritmy, nezabývali jsme se tím, v~jakém pøesnì výpoèetním modelu pracujeme. Konstrukce, které jsme pou¾ívali, toti¾ fungovaly ve~v¹ech obvyklých modelech a mìly tam stejnou èasovou i prostorovu slo¾itost. Ne~v¾dy tomu tak je, tak¾e se výpoèetním modelùm podívejme na~zoubek trochu blí¾e. +\h{Druhy výpoèetních modelù} + Obvykle se pou¾ívají následující dva modely, které se li¹í zejména v~tom, zda je mo¾né pamì» indexovat v~konstantním èase èi nikoliv. @@ -100,11 +100,10 @@ jdou prov \h{Van Emde-Boas Trees} -VEBT \cite{boas77} jsou RAMová struktura, která si pamatuje mno¾inu prvkù $X$ z nìjakého +Van Emde-Boas Trees neboli VEBT \cite{boas77} jsou RAMová struktura, která si pamatuje mno¾inu prvkù $X$ z~nìjakého omezeného universa $X \subseteq \{0,\ldots,U-1\}$, a umí s~ní provádìt \uv{stromové operace} (vkládání, mazání, nalezení následníka apod.) v~èase $\O(\log\log U)$. Pomocí takové struktury pak napøíklad doká¾eme: - $$\vbox{\halign{ #\hfil\quad &#\hfil\quad &#\hfil\cr & pomocí VEBT &nejlep¹í známé pro celá èísla \cr @@ -113,9 +112,10 @@ t MST &$\O(m\log\log U)$ &$\O(m)$ \cr Dijkstra &$\O(m\log\log U)$ &$\O(m+n\log\log n)$, neorientovanì $\O(m)$\cr }}$$ +My se pøidr¾íme ekvivalentní, ale jednodu¹¹í definice podle Erika Demaine~\cite{demaine}. \s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$) -obsahuje: (ekvivalentní formulace podle \cite{demaine}) +obsahuje: \itemize\ibull @@ -263,7 +263,7 @@ prolo \:$\(x)$ -- seète v¹echny slo¾ky vektoru (pøedpokládáme, ¾e se vejdou do~$b$~bitù): \numlist\nalpha -\:vymodulením èíslem $\1^{b+1}$ (to funguje, proto¾e $\1\0^{b+1}\bmod \1^{b+1}=1$), nebo +\:vymodulením èíslem $\1^{b+1}$ (proto¾e $\1\0^{b+1}\bmod \1^{b+1}=1$), èi \:násobením vhodnou konstantou: \setbox0=\hbox{~$x_{n-1}$} \slotwd=\wd0 diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index a0ee4d1..576b7f9 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -56,12 +56,12 @@ i v~praxi. \s{Znaèení:} \itemize\ibull -\: $k = \O(w^{1/4})$ -- omezení na~velikost haldy, -\: $r\le k$ -- aktuální poèet prvkù v~haldì, -\: $X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$, -\: $c_i = \msb(x_i \oplus x_{i+1})$ -- nejvy¹¹í bit, na kterém se li¹í $x_i$ a +\:$k = \O(w^{1/4})$ -- omezení na~velikost haldy, +\:$r\le k$ -- aktuální poèet prvkù v~haldì, +\:$X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$, +\:$c_i = \msb(x_i \oplus x_{i+1})$ -- nejvy¹¹í bit, na kterém se li¹í $x_i$ a $x_{i+1}$, -\: $\rank_X(x)$ -- poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$ +\:$\rank_X(x)$ -- poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$ (definujeme i~pro $x\not\in X$). \endlist @@ -91,9 +91,9 @@ nesouvisej pøekvapení v¹ak to, kam jsme se dostali, bude staèit ke~spoèítání ranku prvku a z~rankù u¾ odvodíme i ostatní operace. -\s{Pøíklad:} +\ss{Pøíklad:} \figure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není -souèástí trie.}{\epsfxsize} +souèástí trie.}{\hsize} \s{Lemma 1:} $\rank_X(x)$ je urèen jednoznaènì: \numlist\pnromanp @@ -211,7 +211,7 @@ nal Jak si pomù¾eme: \itemize\ibull -\:Vyu¾ijeme toho, ¾e operace $x[B]$ je v~${\rm AC}^0$ a vystaèíme si se strukturou pro ${\rm AC}^0$-RAM. +\:Vyu¾ijeme toho, ¾e operace $x[B]$ je v~${\rm AC}^0$, a vystaèíme si se strukturou pro ${\rm AC}^0$-RAM. Zde dokonce mù¾eme vytváøet haldy velikosti a¾ $w\log w$. Také pøi praktické implementaci mù¾eme vyu¾ít toho, ¾e souèasné procesory mají instrukce na~spoustu zajímavých ${\rm AC}^0$-operací, viz napø. pìkný rozbor v \cite{thorup:ac0}. diff --git a/9-suffix/9-suffix.tex b/9-suffix/9-suffix.tex index 0ea06a6..5c5cf15 100644 --- a/9-suffix/9-suffix.tex +++ b/9-suffix/9-suffix.tex @@ -7,13 +7,15 @@ se \h{Øetìzce, trie a suffixové stromy} -\s{Definice:} +\ss{Definice:} \nointerlineskip \halign{\qquad#\dotfill&~#\hfil\cr -\hbox to 0.3\hsize{}\cr -$\Sigma$ & koneèná abeceda (mno¾ina znakù, budeme je znaèit latinskými písmeny)\cr -$\Sigma^*$ & mno¾ina v¹ech slov nad $\Sigma$ (slova budeme znaèit øeckými písmeny)\cr +\hbox to 0.35\hsize{}\cr +$\Sigma$ & koneèná abeceda -- mno¾ina znakù \cr +\omit & (znaky budeme znaèit latinskými písmeny)\cr +$\Sigma^*$ & mno¾ina v¹ech slov nad $\Sigma$ \cr +\omit & (slova budeme znaèit øeckými písmeny)\cr $\varepsilon$ & prázdné slovo\cr $\vert\alpha\vert$ & délka slova $\alpha$\cr $\alpha\beta$ & zøetìzení slov $\alpha$ a $\beta$ ($\alpha\varepsilon=\varepsilon\alpha=\alpha$)\cr @@ -21,7 +23,8 @@ $\alpha^R$ & slovo $\alpha$ napsan $\alpha$ je {\I prefixem} $\beta$ & $\exists\gamma: \beta=\alpha\gamma$ ($\beta$ zaèíná na~$\alpha$)\cr $\alpha$ je {\I suffixem} $\beta$ & $\exists\gamma: \beta=\gamma\alpha$ ($\beta$ konèí na~$\alpha$)\cr $\alpha$ je {\I podslovem} $\beta$ & $\exists\gamma,\delta: \beta=\gamma\alpha\delta$ (znaèíme $\alpha \subset \beta$)\cr -$\alpha$ je {\I vlastním prefixem} $\beta$ & je prefixem a $\alpha\ne\beta$ (analogicky vlastní suffix a podslovo)\cr +$\alpha$ je {\I vlastním prefixem} $\beta$ & je prefixem a $\alpha\ne\beta$ \cr +\omit & (analogicky vlastní suffix a podslovo)\cr } \s{Pozorování:} Prázdné slovo je prefixem, suffixem i podslovem ka¾dého slova vèetnì sebe sama. @@ -134,13 +137,14 @@ $1,\ldots,n+1$, pro n \s{Definice:} {\I Longest Common Prefix Array} $L_\sigma$ pro slovo $\sigma$ je posloupnost, v~ní¾ $L_\sigma[i]:={\rm LCP}(A_\sigma[i],A_\sigma[i+1])$. -\s{Vìta:} Suffixový strom s~dolarem 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.] +\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 vrcholù v~inorderu odpovídají $L_\sigma$. Naopak ST($\sigma$) získáme tak, ¾e sestrojíme kartézský strom pro~$L_\sigma$ (to jsou vnitøní vrcholy ST), doplníme do~nìj listy a pøiøadíme jim suffixy podle~$A_\sigma$ a nakonec podle listù rekonstruujeme nálepky hran. +\qed \h{Rekurzivní konstrukce} @@ -180,8 +184,8 @@ tak $$\eqalign{ \sigma_0[i:{}] < \sigma_1[j:{}] &\equiv A_{01}^{-1}[i] < A_{01}^{-1}[\vert\sigma_0\vert+j]\cr \sigma_0[i:{}] < \sigma_2[k:{}] &\equiv \sigma[3i]\,\sigma_1[i:{}] < \sigma[3k+2]\,\sigma_0[k+1:{}]\cr -&\Leftrightarrow (\sigma[3i] < \sigma[3k+2]) \vee (\sigma[3i] = \sigma[3k+2] \wedge \sigma_1[i:{}] < \sigma_0[k+1:{}])\cr -\sigma_1[j:{}]<\sigma_2[k:{}] &\equiv \sigma[3j+1]\,\sigma[3j+2]\,\sigma_0[j+1:{}] < \sigma[3k+2]\,\sigma[3k+3]\,\sigma_1[k+1:{}] +&\Leftrightarrow (\sigma[3i] < \sigma[3k+2]) \vee {} \cr&\hphantom{{}\Leftrightarrow{}} (\sigma[3i] = \sigma[3k+2] \wedge \sigma_1[i:{}] < \sigma_0[k+1:{}])\cr +\sigma_1[j:{}]<\sigma_2[k:{}] &\equiv \sigma[3j+1]\,\sigma[3j+2]\,\sigma_0[j+1:{}] < \cr&\hphantom{{}\equiv{}} \sigma[3k+2]\,\sigma[3k+3]\,\sigma_1[k+1:{}] }$$ \:Dopoèítáme $L$ -- pokud sousedí suffix ze~$\sigma_{0,1}$ se suffixem ze~$\sigma_{0,1}$, diff --git a/Makerules b/Makerules index 5016830..94309e8 100644 --- a/Makerules +++ b/Makerules @@ -3,26 +3,20 @@ all: $P.ps %.dvi: %.tex ../sgr.tex ../ga.bib csplain $< && if grep -q citation $*.aux ; then bibtex $* && csplain $< && csplain $< ; fi -%.pdf: %.tex ../sgr.tex +%.pdf: %.tex ../sgr.tex ../ga.bib pdfcsplain $< -%-700.tex: %.tex - ( echo '\magnification=700' ; cat $< ) >$@ - %.ps: %.dvi - dvips -D600 -o $@ -O-0.5in,-0.5in -t a4 $< - -%-a5.ps: %-700.dvi - dvips -D600 -o $@ -O-1in,-1in -T148mm,210mm $< + dvips -D600 -o $@ -O-15.4mm,-15.4mm -t a5 $< -%-booklet.ps: %-a5.ps - psbook <$< | pstops '2:0L(210mm,0)+1L(210mm,148mm)' | sed 's/^%%BoundingBox: .*/%%BoundingBox: 0 0 595 842/' >$@ +%-booklet.ps: %.ps + psbook <$< | pstops '2:0L(210mm,0)+1L(210mm,148mm)' | sed 's/^%%BoundingBox: .*/%%BoundingBox: 0 0 595 842/;s/^%%DocumentPaperSizes:.*/%%DocumentPaperSizes: a4\n%%Orientation: Landscape/' >$@ -%-2in1.ps: %-a5.ps - pstops '2:0L(212mm,0mm)+1L(212mm,150mm)' <$< | sed 's/^%%BoundingBox: .*/%%BoundingBox: 0 0 595 842/' >$@ +%-2in1.ps: %.ps + pstops '2:0L(210mm,0mm)+1L(210mm,148mm)' <$< | sed 's/^%%BoundingBox: .*/%%BoundingBox: 0 0 595 842/;s/^%%DocumentPaperSizes:.*/%%DocumentPaperSizes: a4\n%%Orientation: Landscape/' >$@ mostlyclean: - rm -f *.dvi *.log *~ core *.o *-700.tex *-a5.ps *.aux *.bbl *.blg + rm -f *.dvi *.log *~ core *.o *.aux *.bbl *.blg clean:: mostlyclean rm -f *.ps *.pdf diff --git a/all/ga.tex b/all/ga.tex index 4b5e505..bf8b460 100644 --- a/all/ga.tex +++ b/all/ga.tex @@ -4,5 +4,7 @@ \input body.tex -\references +\prednaska{L}{Literatura}{} + +\dumprefs \bye diff --git a/sgr.tex b/sgr.tex index 4900e31..3347f16 100644 --- a/sgr.tex +++ b/sgr.tex @@ -6,12 +6,19 @@ \language=\czech \chyph +\lefthyphenmin=2 +\righthyphenmin=2 % A4 s 0.5in okraji -\hsize=184.6mm -\vsize=271.6mm +%\hsize=184.6mm +%\vsize=271.6mm +%\parindent=0.25in -\parindent=0.25in +% A5 s 1cm okraji, dolni rozsiren o 10pt, aby se tam veslo cislo stranky +\hsize=128mm +\vsize=190mm +\advance\vsize by -10pt +\parindent=0.8cm % Zacatek prednasky {cislo prednasky}{jmeno prednasky}{jmeno zapisovatele} \def\prednaska#1#2#3{% @@ -27,15 +34,18 @@ % Zvyrazneny zacatek odstavce coby podnadpis (napr. vety apod.) \def\s#1{\noindent {\bo #1}} +% A kdyz stoji samostatne (aby se naodlamoval) +\def\ss#1{\noindent {\bo #1}\par\nobreak} + % Dùkaz \def\proof{\noindent {\sl Dùkaz:} } % Ctverecek na konci dukazu %\def\qed{{\parfillskip=0pt\quad\hfil\hbox{\I QED} \par}} -\def\qed{\hfill\allowbreak\hfill\nobreak $\heartsuit$\par} +\def\qed{{\parfillskip=0pt\allowbreak\hfill\nobreak $\heartsuit$\par}} % pokud je v seznamu: -\def\qeditem{\hfill\rlap{\hskip\rightskip\llap{$\heartsuit$}}\par} +\def\qeditem{{\parfillskip=0pt\hfill\rlap{\hskip\rightskip\llap{$\heartsuit$}}\par}} % Poznamky pod carou \newcount\footcnt @@ -101,8 +111,8 @@ % Reference na konci kapitoly \bibliographystyle{abbrv} -\def\references{ -\h{Literatura} +\def\references{\h{Literatura}\dumprefs} +\def\dumprefs{ \def\bblhook{\parskip=2pt plus 1pt minus 0.5pt} \bibliography{../ga} } -- 2.39.2