Makefile: Changelog zrusen, misto nej pouzijeme Gitweb

[ga.git] / 6-borjar / 6-borjar.tex

diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex
index 139ba1d8f77f6799b9264f630ee554c64a957d2f..f1b0c017165aa8dcbae105935190b0bcf992ca85 100644 (file)
--- a/6-borjar/6-borjar.tex
+++ b/6-borjar/6-borjar.tex
@@ -1,6 +1,6 @@
 \input ../sgr.tex
 
-\prednaska{6}{Rychlej¹í algoritmy na~minimální kostry}{}
+\prednaska{6}{Rychlej¹í algoritmy na minimální kostry}{}
 
 V~této kapitole popí¹eme nìkolik pokroèilej¹ích algoritmù pro problém minimální
 kostry. Vesmìs to budou rùzná vylep¹ení klasických algoritmù z~minulé kapitoly.
@@ -61,7 +61,6 @@ T
 Pokud je $\cal C$ minorovì uzavøená tøída grafù, existuje koneèná mno¾ina grafù $Z$ taková,
 ¾e pro ka¾dý graf $G$ platí:
 $$G \not\in {\cal C} \iff \exists H \in Z: H \preceq G.$$
-
 Jinými slovy, ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù.
 To není samo sebou, dokazuje se to dosti obtí¾nì (a~je to jedna z~nejslavnìj¹ích kombinatorických
 vìt za~posledních mnoho let), ale plyne z~toho spousta zajímavých dùsledkù.
@@ -96,10 +95,10 @@ udr
 \algo
 \:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$.
 \:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$.
-\:Opakuji dokud $H\neq\emptyset$:
+\:Opakujeme, dokud $H\neq\emptyset$:
 \::$vw\leftarrow \<DeleteMin>(H)$, pøièem¾ $v\not\in T, w\in T$.
 \::$T\leftarrow T\cup\{vw\}$
-\::Pro v¹echny sousedy $u$ vrcholu $v$, které dosud nejsou v~$T$, upravíme haldu:
+\::Pro v¹echny sousedy $u$ vrcholu $v$, kteøí dosud nejsou v~$T$, upravíme haldu:
 \:::Pokud je¹tì v~$H$ není hrana incidentní s~$u$, pøidáme hranu~$uv$.
 \:::Pokud u¾ tam nìjaká taková hrana je a je-li tì¾¹í ne¾ $uv$, nahradíme ji
 hranou~$uv$ a provedeme \<DecreaseKey>.
@@ -159,7 +158,8 @@ jsme novou podkostru k~n
 \endalgo
 
 \s{Pozorování:}
-Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami.
+Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami
+(do toho poèítáme i vnitøní hrany vedoucí mezi vrcholy podkostry).
 Jak to vypadá pro jednotlivá ukonèení:
 \numlist\ndotted
 \itemcount=\algcnt
@@ -194,14 +194,15 @@ omezen
   \cite{pettie:optimal}.
   Jeliko¾ ka¾dý deterministický algoritmus zalo¾ený na~porovnávání vah lze popsat rozhodovacím stromem,
   je tento algoritmus zaruèenì optimální. Jen bohu¾el nevíme, jak optimální stromy vypadají, tak¾e
-  je stále otevøeno, zda lze MST nalézt v~lineárním èase. Nicménì jeliko¾ tento algoritmus
+  je stále otevøeno, zda lze MST nalézt v~lineárním èase. Nicménì tento algoritmus
   pracuje i na~Pointer Machine, proèe¾ víme, ¾e pokud je lineární slo¾itosti mo¾né dosáhnout, není k~tomu
   potøeba výpoèetní síla RAMu.\foot{O výpoèetních modelech viz pøí¹tí kapitola.}
 \:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) \cite{fw90trans} -- uká¾eme v~jedné
   z~následujících kapitol.
 \:$\O(m)$, pokud u¾ máme hrany setøídìné podle vah: jeliko¾ víme, ¾e zále¾í jen na~uspoøádání,
-  mù¾eme váhy pøeèíslovat na~$1\ldots n$ a pou¾ít pøedchozí algoritmus.
-\:$\O(m)$ randomizovanì v~prùmìrném pøípadì \cite{karger:randomized}.
+  mù¾eme váhy pøeèíslovat na~$1\ldots m$ a pou¾ít pøedchozí algoritmus.
+\:$\O(m)$ prùmìrnì: randomizovaný algoritmus, který pro libovolný vstupní graf dobìhne v~oèekávaném
+  lineárním èase~\cite{karger:randomized}.
 \:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
   lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí
   randomizovaný algoritmus.