Dalsi korektury od Honzy Volce.

[ads2.git] / 6-kmp / 6-kmp.tex

diff --git a/6-kmp/6-kmp.tex b/6-kmp/6-kmp.tex
index 53041769c1b74ebe52d2322e3df89502d1903828..08f4edac1b00022e1addfc68ca33d5cc94e52aae 100644 (file)
--- a/6-kmp/6-kmp.tex
+++ b/6-kmp/6-kmp.tex
@@ -30,7 +30,7 @@ znakem vzorov
 \itemize\ibull
 \s{Definice:}
 \itemize\ibull
-\:{\I Abeceda $\Sigma$} je koneèná mno¾ina znakù, ze kterých tvoøíme text, øetìzece, slova jako koneèné posloupnosti znakù ze $\Sigma$. Pøíkladem extrémních abeced je lineární abeceda slo¾ená z~nul a jednièek. Pøíklad s~druhého konce je abeceda, která má jako znaky slova èeského jazyka. V algoritmech nebudeme uva¾ovat velikost abecedy (poèet znakù).
+\:{\I Abeceda $\Sigma$} je koneèná mno¾ina znakù, ze kterých tvoøíme text, øetìzece, slova jako koneèné posloupnosti znakù ze $\Sigma$. Pøíkladem extrémních abeced je binární abeceda slo¾ená z~nul a jednièek. Pøíklad z~druhého konce je abeceda, která má jako znaky slova èeského jazyka. V algoritmech nebudeme uva¾ovat velikost abecedy (poèet znakù).
 \:{\I $\Sigma$*} je mno¾ina v¹ech slov nad abecedou $\Sigma$.
 \endlist
 \s{Znaèení:}
@@ -70,22 +70,22 @@ Vyhled
 \s{Vyhledávaní:}
 \algo
 \:$\alpha \leftarrow \varepsilon$.
-\:Pro $C\in\Sigma$ postupnì:
-\:$\indent$Dokud $\neg \exists d(\alpha , C) \wedge \alpha\neq\varepsilon : \alpha \leftarrow z(\alpha)$.
-\:$\indent$Jestli¾e $\exists d(\alpha , C) \Rightarrow \alpha \leftarrow d(\alpha , C)$.
-\:$\indent$Jestli¾e $\alpha = \iota \Rightarrow$ hledané slovo je v~textu.
+\:Pro $C\in\sigma$ postupnì:
+\::Dokud $\neg \exists d(\alpha , C) \wedge \alpha\neq\varepsilon$: $\alpha \leftarrow z(\alpha)$.
+\::Pokud $\exists d(\alpha , C)$: $\alpha \leftarrow d(\alpha , C)$.
+\::Pokud $\alpha = \iota$: vrátíme, ¾e hledané slovo je v~textu.
 \endalgo
 
 \s{Alternativa:}
 \algo
 \:$k \leftarrow 0$.
-\:Pro $C\in\Sigma$ postupnì:
-\:$\indent$Dokud $C\neq \iota[k] \wedge k>0: k \leftarrow z(k)$.
-\:$\indent$Jestli¾e $C=\iota[k] \Rightarrow k++$.
-\:$\indent$Jestli¾e $k = J \Rightarrow$ hledané slovo je v~textu.
+\:Pro $C\in\sigma$ postupnì:
+\::Dokud $C\neq \iota[k] \wedge k>0$: $k \leftarrow z(k)$.
+\::Pokud $C=\iota[k]$: $k \leftarrow k+1$.
+\::Pokud $k = J$: vrátíme, ¾e hledané slovo je v~textu.
 \endalgo
 
-\s{Invariant:} Stav po pøeètení vstupu $\beta$: $\alpha(\beta)$ $=$ nejdel¹í suffix $\beta$, který je prefixem $\iota$.
+\s{Invariant:} Stav po pøeètení vstupu $\beta$: $\alpha(\beta)$ je nejdel¹í suffix $\beta$, který je prefixem $\iota$.
 Z~invariantu vyplývá korektnost vyhledávací èásti algoritmu KMP.
 
 \proof