From 61bbd7405543de6dfffe8f0932c2e965ecdb19c3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 24 Jan 2007 14:30:35 +0100 Subject: [PATCH] Byl jsem tady. Ispell. --- 0-intro/0-intro.tex | 2 +- 1-toky/1-toky.tex | 4 ++-- 10-decomp/10-decomp.tex | 2 +- 11-planar/11-planar.tex | 4 ++-- 2-dinic/2-dinic.tex | 12 ++++++------ 3-bipcon/3-bipcon.tex | 6 +++--- 6-borjar/6-borjar.tex | 10 +++++----- 8-qheap/8-qheap.tex | 2 +- 9-suffix/9-suffix.tex | 2 +- 9 files changed, 22 insertions(+), 22 deletions(-) diff --git a/0-intro/0-intro.tex b/0-intro/0-intro.tex index 73085c5..30d4590 100644 --- a/0-intro/0-intro.tex +++ b/0-intro/0-intro.tex @@ -45,7 +45,7 @@ Combinatorial Optimization~\cite{schrijver}. \:$G$ bude znaèit koneèný {\I graf} na~vstupu algoritmu (podle potøeby buïto orientovaný nebo neorientovaný; multigraf pouze tehdy, bude-li explicitnì øeèeno). \:$V$ a $E$ budou mno¾iny {\I vrcholù} a {\I hran} grafu~$G$ (pøípadnì jiného grafu - uvedeného v~zavorkách). Hranu z~vrcholu~$u$ + uvedeného v~závorkách). Hranu z~vrcholu~$u$ do~vrcholu~$v$ budeme psát~$uv$, a» u¾ je orientovaná nebo~ne. \:$n$ a $m$ bude {\I poèet vrcholù a hran,} tedy $n:=\vert V\vert$, $m:=\vert E\vert$. \:Pro libovolnou mno¾inu $X$ vrcholù nebo hran bude $\overline X$ oznaèovat doplnìk diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index c8369f7..51fdabc 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -112,7 +112,7 @@ v~na \endalgo \s{Analýza:} Nejdøíve si rozmysleme, ¾e pro celoèíselné kapacity algoritmus v¾dy dobìhne: v~ka¾dém kroku -stoupne velikost toku o~$m \ge 1$, co¾ mù¾e nastat pouze koneènìkrát. Podobnì pro racionální kapacity: +stoupne velikost toku o~$m \ge 1$, co¾ mù¾e nastat pouze koneènì-krát. Podobnì pro racionální kapacity: pøenásobíme-li v¹echny kapacity jejich spoleèným jmenovatelem, dostaneme sí» s~celoèíselnými kapacitami, na~které se bude algoritmus chovat identicky a jak ji¾ víme, skonèí. Pro~iracionální kapacity obecnì dobìhnout nemusí, zkuste vymyslet protipøíklad. @@ -127,7 +127,7 @@ Na je tok maximální a øez minimální. Tím jsme také dokázali Ford-Fulkersonovu vìtu\foot{Dokonce jsme ji dokázali i pro reálné kapacity, proto¾e mù¾eme algoritmus spustit rovnou na maximální tok místo nulového a on se ihned zastaví a vydá certifikující øez.} a existenci maximálního toku. Navíc algoritmus nikdy -nevytváøí z~celých èísel necelá, èim¾ získáme: +nevytváøí z~celých èísel necelá, èím¾ získáme: \s{Dùsledek:} Sí» s~celoèíselnými kapacitami má maximální tok, který je celoèíselný. diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index c7f7fd7..2749ff8 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -188,7 +188,7 @@ nejv \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. -\proof První èast rozborem pøípadù, druhá hladovì pomocí DFS. \qed +\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 vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik}, diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index cbe2d02..0467ef2 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -132,7 +132,7 @@ Druh (jinak by existovala pøíèná hrana, co¾ víme, ¾e není pravda), tak¾e minimum z~\ù v¹ech vrcholù le¾ících uvnitø bloku je pøesnì \ tohoto syna. Ve~statickém grafu by se v¹echny testy redukovaly na~$\(w)$, nám se ov¹em bloková -struktura prùbì¾nì mìní, tak¾e musíme uva¾ovat bloky v~souèasném okam¾iku. Proto si zavademe: +struktura prùbì¾nì mìní, tak¾e musíme uva¾ovat bloky v~souèasném okam¾iku. Proto si zavedeme: \s{Definice:} $\(w)$ je seznam v¹ech blokù pøipojených v~daném okam¾iku pod vrcholem~$w$, reprezentovaných jejich koøeny (klony vrcholu~$w$) a jedinými syny koøenù. @@ -300,7 +300,7 @@ Ozna vrcholy $x$ a~$y$ a pod nimi je pøipojen nìjakou cestou vrchol~$w$. Takový blok musí urèitì existovat, proto¾e jinak by algoritmus v¹echny bloky na~cestì z~$v$ do~$w$ popøeklápìl tak, aby se hrana $wv$ ve¹la. V~grafu se tedy musí vyskytovat jeden -z~následujících minorù (do~vrcholu~$u$ jsme zkontrahovali celou dosud nenakreslenou èást grafu; +z~následujících minorù (do~vrcholu~$u$ jsme kontrahovali celou dosud nenakreslenou èást grafu; vybarvená èást odpovídá vnitøku bloku; hranaté vrcholy jsou externì aktivní): \bigskip diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 6512e00..7a19ca5 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -24,8 +24,8 @@ kdyby neuva \:Iterativnì vylep¹ujeme tok pomocí zlep¹ujících tokù: {\I (vnìj¹í cyklus)} \::Sestrojíme sí» rezerv: vrcholy a hrany jsou tyté¾, kapacity jsou urèeny rezervami v~pùvodní síti. Dále budeme pracovat s~ní. -\::Najdeme nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèime. -\::Proèistime sí», tj. ponecháme v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách. +\::Najdeme nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèíme. +\::Proèistíme sí», tj. ponecháme v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách. \::Najdeme v~proèi¹tìné síti blokující tok $f_B$: \:::$f_B \leftarrow \$ \:::Postupnì pøidáváme $st$-cesty: {\I (vnitøní cyklus)} @@ -34,7 +34,7 @@ D \::::Sma¾eme nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé ulièky, èím¾ se zneèistí sí» a nebude fungovat hladové hledání cest.) \::::Doèistíme sí». -\::Zlep¹ime $f$ podle $f_B$ +\::Zlep¹íme $f$ podle $f_B$ \endalgo \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.4\hsize} @@ -98,7 +98,7 @@ d \h{Poznámky} \itemize\ibull -\:Není potøeba tak puntíèkáøské èi¹tìní. Vrcholy se vstupním stupnìm 0 nám +\:Není potøeba tak puntièkáøské èi¹tìní. Vrcholy se vstupním stupnìm 0 nám nevadí -- stejnì se do nich nedostaneme. Vadí jen vrcholy s výstupním stupnìm 0, kde by mohl havarovat postup v podkroku 9. \:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e prohledáváním do~hloubky: @@ -106,7 +106,7 @@ d 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ì - opravujeme kapacity. Snadno skombinujeme s~prohledáváním do~hloubky. + 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 algoritmu. @@ -216,7 +216,7 @@ $\O(Cn^2 + nm)$. Pokud jsou kapacity hran vìt¹í celá èísla omezená nìjakou konstantou~$C$, mù¾eme si pomoci následujícím algoritmem. Jeho základní my¹lenka je podobná, jako u~tøídìní èísel postupnì po øádech pomocí -radix-sortu neboli pøíhrádkového tøídìní. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední +radix-sortu neboli pøihrádkového tøídìní. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední (nejménì významné) 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.4\hsize} diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index caf2a2e..792d2a5 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -115,7 +115,7 @@ $$\eqalign{ Dokázali jsme, ¾e libovolný øez separující $v_{n-1}$ a $v_n$ je alespoò tak velký jako jednoduchý øez skládající se jen z hran kolem~$v_n$. Kdy¾ tedy sestavíme nìjakou LU posloupnost vrcholù, budeme mít k dispozici jednoduchý minimální øez -$v_{n-1}$ a~$v_n$. Následnì vytvoøíme graf $G'$, v nìm¾ $v_{n-1}$ a $v_n$ skontrahujeme. Rekurzivnì najdeme minimální +$v_{n-1}$ a~$v_n$. Následnì vytvoøíme graf $G'$, v nìm¾ $v_{n-1}$ a $v_n$ kontrahujeme. Rekurzivnì najdeme minimální øez v $G'$ (sestrojíme nové LU atd.). Hledaný minimální øez poté buïto oddìluje vrcholy $v_n$ a $v_{n-1}$ a potom je øez kolem vrcholu $v_n$ minimální, nebo vrcholy $v_n$ a $v_{n-1}$ neoddìluje, a v takovém pøípadì jej najdeme rekurzivnì. Hledaný øez je tedy men¹í z rekurzivnì nalezeného øezu a øezu kolem $v_n$. @@ -126,7 +126,7 @@ Zde se hod napøíklad Fibonacciho halda. Ta zvládne \ v~èase $\O(\log n)$ a \ v~$\O(1)$ amortizovanì. Celkem pak ná¹ algoritmus bude mít slo¾itost $\O(n(m+n\log n))$ pro obecné kapacity. -Pokud jsou kapacity malá celá èísla, mù¾eme vyu¾ít pøíhrádkové struktury. Budeme +Pokud jsou kapacity malá celá èísla, mù¾eme vyu¾ít pøihrádkové struktury. Budeme si udr¾ovat obousmìrný seznam zatím pou¾itých hodnot $z_v$, ka¾dý prvek takového seznamu bude obsahovat v¹echny vrcholy se spoleènou hodnotou $z_v$. Kdy¾ budeme mít seznam seøazený, vybrání minimálního prvku bude znamenat pouze podívat se na @@ -134,7 +134,7 @@ prvn odstranit. Operace \ poté bude reprezentovat pouze pøesunutí vrcholu o malý poèet pøihrádek, pøípadnì zalo¾ení nové pøihrádky na správném místì. \ proto bude mít slo¾itost $\O(1)$, v¹echny \ dohromady $\O(m)$, -jeliko¾ za~ka¾dou hranu pøeskakujeme maximálnì jednu pøíhrádku, a celý algoritmus $\O(mn)$. +jeliko¾ za~ka¾dou hranu pøeskakujeme maximálnì jednu pøihrádku, a celý algoritmus $\O(mn)$. \references \bye diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index f9d16f5..04dbd50 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -8,7 +8,7 @@ kostry. Vesm \h{Upravená verze Borùvkova algoritmu pro rovinné grafy} Vyjdeme z my¹lenky, ¾e mù¾eme po ka¾dém kroku pùvodního Borùvkova algoritmu vzniklé komponenty -souvislosti grafu zkontrahovat do jednoho vrcholu a tím získat men¹í graf, který mù¾eme +souvislosti grafu kontrahovat do jednoho vrcholu a tím získat men¹í graf, který mù¾eme znovu rekurzivnì zmen¹ovat. To funguje obecnì, ale uká¾eme, ¾e pro rovinné grafy tak dosáhneme lineární èasové slo¾itosti. @@ -21,7 +21,7 @@ To n \s{Algoritmus: MST v rovinných grafech} \cite{mm:mst} \algo \:Ke ka¾dému vrcholu najdeme nejlevnìj¹í incidentní hranu -- dostaneme mno¾inu hran $F \subseteq E$. -\:Graf zkontrahujeme podle $F$ následovnì: +\:Graf kontrahujeme podle $F$ následovnì: \::Prohledáme do ¹íøky graf $(V(G), F)$ a pøiøadíme vrcholùm èíslo komponenty, ve které jsou. \::Pøeèíslujeme hrany v~$G$ podle èísel komponent. \:Odstraníme násobné hrany: @@ -106,7 +106,7 @@ do~$T$, nahrad \s{Èasová slo¾itost:} Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnìj¹í cyklus se provede nanejvý¹ $n$-krát, za~\ v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání -vrcholù do~$H$ a~nalezání nejlevnìj¹ích hran zaplatíme celkem $\O(m)$ (na~ka¾dou hranu takto +vrcholù do~$H$ a~nalézání nejlevnìj¹ích hran zaplatíme celkem $\O(m)$ (na~ka¾dou hranu takto sáhneme nanejvý¹ dvakrát), za~sni¾ování vah vrcholù v~haldì rovnì¾ pouze $\O(m)$ (nanejvý¹ $m$-krát provedu porovnání vah a \ v~$\the\algcnt.$ za~$\O(1)$). @@ -134,7 +134,7 @@ tedy nanejv Je¹tì vìt¹ího zrychlení dosáhneme, omezíme-li Jarníkovu algoritmu \#2 vhodnì velikost haldy a takto budeme bìhem jednoho Jarníkova algoritmu skládat pouze jednotlivé podkostøièky zastavené v rùstu pøeteèením haldy, podle kterých -graf následnì zkontrahujeme a budeme pokraèovat s mnohem men¹ím grafem. +graf následnì kontrahujeme a budeme pokraèovat s mnohem men¹ím grafem. \s{Algoritmus: Jarníkùv algoritmus~\#4 (Fredman, Tarjan \cite{ft:fibonacci})} \algo @@ -150,7 +150,7 @@ graf n \::::$H=\emptyset$ (do¹li sousedé) nebo \::::do $T$ jsem pøidal hranu oboustrannì incidentní s~hranami v~$T$ (pøipojil jsem novou podkostru k~nìjaké u¾ nalezené). -\::Zkontrahuji $G$ podle podkoster nalezených v~$T$. +\::Kontrahuji $G$ podle podkoster nalezených v~$T$. \endalgo \s{Pozorování:} diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index 576b7f9..507e78c 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -229,7 +229,7 @@ varianty Jarn jako haldu Q-Heap velikosti $\log^{1/4} n$ a pak u¾ budeme pokraèovat s~Fibonacciho haldou. Tak provedeme tolik prùchodù, kolikrát je potøeba zlogaritmovat $n$, aby výsledek klesl pod~$\log^{1/4} n$, a~to je konstanta. V¹imnìte si, ¾e by nám -dokonce staèila halda velikosti $\O(\log^{(k)} n)$ a~operacemi v~konstantím èase +dokonce staèila halda velikosti $\O(\log^{(k)} n)$ a~operacemi v~konstantním èase pro nìjaké libovolné~$k$. \references diff --git a/9-suffix/9-suffix.tex b/9-suffix/9-suffix.tex index 5c5cf15..0784bbd 100644 --- a/9-suffix/9-suffix.tex +++ b/9-suffix/9-suffix.tex @@ -36,7 +36,7 @@ Podslova jsou pr \:$(\alpha,\beta)\in E \equiv \exists x\in\Sigma: \beta=\alpha x$. \endlist -\s{Pozorování:} Trie je strom s koøenem $\varepsilon$. Jeho listy jsou slova z $X$, která nejsou vlastními prefixemy jiných slov z~$X$. +\s{Pozorování:} Trie je strom s koøenem $\varepsilon$. Jeho listy jsou slova z $X$, která nejsou vlastními prefixy jiných slov z~$X$. Hrany si mù¾eme pøedstavit popsané písmeny, o~nì¾ prefix roz¹iøují, popisky hran na~cestì z~koøene do~vrcholu~$\alpha$ dávají právì slovo~$\alpha$. \s{Definice:} {\I Komprimovaná trie ($\Sigma^+$-strom)} vznikne z trie nahrazením maximálních nevìtvících se cest hranami. Hrany -- 2.39.2