From f81463b774c133e8023c605dfc96be9343f5d5c1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 11 Dec 2007 12:01:04 +0100 Subject: [PATCH] Par oprav AC, prejmenovane soubory s obrazky. --- 7-ac/7-ac.tex | 42 +++++++++---------- 7-ac/{Graphic100.CDR => Graphic100.cdr} | Bin 7-ac/{Graphic101.CDR => Graphic101.cdr} | Bin 7-ac/{Graphic102.CDR => Graphic102.cdr} | Bin 7-ac/{graf1.cdr => polynom.cdr} | Bin 7-ac/{Graphic3.cdr => vyhl_automat_full.cdr} | Bin 6 files changed, 21 insertions(+), 21 deletions(-) rename 7-ac/{Graphic100.CDR => Graphic100.cdr} (100%) rename 7-ac/{Graphic101.CDR => Graphic101.cdr} (100%) rename 7-ac/{Graphic102.CDR => Graphic102.cdr} (100%) rename 7-ac/{graf1.cdr => polynom.cdr} (100%) rename 7-ac/{Graphic3.cdr => vyhl_automat_full.cdr} (100%) diff --git a/7-ac/7-ac.tex b/7-ac/7-ac.tex index bbf79e7..f8408a3 100644 --- a/7-ac/7-ac.tex +++ b/7-ac/7-ac.tex @@ -4,7 +4,7 @@ \h{Zopakujeme si základní znaèení} \itemize\ibull -\:$\iota_1 \ldots \iota_k$ - jehly +\:$\iota_1 \ldots \iota_k$ -- jehly \:$\sigma$ text (seno) \endlist @@ -27,18 +27,18 @@ Konkr \:$s \leftarrow koren$ (zaèínáme v koøeni) \:$\forall$ c písmenka $\sigma$ \::$s \leftarrow krok(s,c)$ -\::je-li $slovo(s) \ne 0 \Rightarrow vypi¹(slovo(s))$ +\::je-li \ $\ne 0 \Rightarrow$ \ \::$v \leftarrow out(s)$ \::dokud $v \ne 0 $ -\:::vypi¹ $slovo(v)$ -\:::$v \leftarrow out(v)$ +\:::vypi¹ \ +\:::$v \leftarrow$ \ \endalgo -\s{krok($s$,$c$)}:= jeden $krok$ vytváøení vyhledávacího algoritmu +\s{\}:= jeden \ vytváøení vyhledávacího algoritmu \algo -\:dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow z(s)$ -\:pokud $\exists f(s,c) : s \leftarrow f(s,c)$ +\:dokud $\not\exists f(s,c) \wedge s \ne$ koøen: $s \leftarrow$ \ +\:pokud $\exists$ \: $s \leftarrow$ \ \:vrátíme s \endalgo @@ -52,42 +52,42 @@ Konkr \s{Vypisování nalezených slov} \itemize\ibull -\:slovo, které v daném stavu konèí - nefunguje -\:projít v¹echy zpìtné hrany - funguje, ale pomalé -\:pøepoèítat mno¾iny - najít mno¾inu slov, aby celková velikost slov byla vìt¹í ne¾ lineární - nestihneme konstrukci -\:$slovo(s)$ = index $\iota_i$, která konèí ve stavu S, nebo $\emptyset$ -\par $out(s)$ = nejbli¾¹í vrchol , do kterého se dá z s dostat po zpìtných hranách a $slovo(v) \ne 0$ (konèí tam slovo) -\figure{Graphic2.eps}{Vyhledávací automat - se zpìtnýma hranama}{1.3in} +\:slovo, které v daném stavu konèí -- nefunguje +\:projít v¹echy zpìtné hrany -- funguje, ale pomalé +\:pøepoèítat mno¾iny - najít mno¾inu slov, aby celková velikost slov byla vìt¹í ne¾ lineární -- nestihneme konstrukci +\:\ = index $\iota_i$, která konèí ve stavu S, nebo $\emptyset$ +\par $out(s)$ = nejbli¾¹í vrchol , do kterého se dá z s dostat po zpìtných hranách a \ $\ne 0$ (konèí tam slovo) +\figure{Graphic2.eps}{Vyhledávací automat -- se zpìtnými hranami}{1.3in} \endlist \h{Slo¾itost} \itemize\ibull -\:kroky 2.-5. mají èasouvou slo¾itost $O(s)$, kterou jednodu¹e doká¾eme pomocí potenciálu - kroku nahoru $ \leq $ kroku dolu $= max(\vert \sigma \vert) $ -\:kroky 6.-8. mají èasovou slo¾itost $O($poèet výskytù$)$, co¾ je celkem logické, proto¾e rychleji opravdu nejdou vèechny výskyty vypsat +\:kroky 2.-5. mají èasouvou slo¾itost \, kterou jednodu¹e doká¾eme pomocí potenciálu - kroku nahoru $ \leq $ kroku dolu $= max(\vert \sigma \vert) $ +\:kroky 6.-8. mají èasovou slo¾itost \, co¾ je celkem logické, proto¾e rychleji opravdu nejdou vèechny výskyty vypsat \endlist \s{Konstrukce automatu} (Aho, Coracisková) \algo \:postavíme strom dopøedných hran r $\leftarrow$ koøen -\:spoèteme $slovo(\ast)$ +\:spoèteme \$(\ast)$ \:spoèteme $z(\ast)$: $z(\beta)=\alpha(\beta[1:]) \{\beta[1:]$ slovo $\beta$ bez prvního písmene$\}$ \itemize\ibull \:$z(\beta) = \alpha(\beta[1:])$ - v¹echny zpìtné hrany vedou do vy¹¹ích hladin -\:$z(v) = krok(z(u),c)$ +\:\ \endlist \figure{Graphic100.eps}{z(v)=Krok(z(u),c)}{0.7in} -\:$z(r) \leftarrow 0, Q \leftarrow \{ synové(r) \}, \forall v \in Q : z(v) \leftarrow r$ +\:$z(r) \leftarrow 0, Q \leftarrow \{$ \ $\}, \forall v \in Q : z(v) \leftarrow r$ \:dokud $ Q \ne 0$ \::$u\leftarrow$ vyber z $Q$ (7-9 ¹ipka) \::pro syny $v$ vrcholu $u$: -\:::$z \leftarrow krok(z(u)$, znak $n \geq uv)$ +\:::$z \leftarrow$ \, znak $n \geq uv)$ \:::$z(v)\leftarrow R$ \figure{Graphic101.eps}{}{0.7in} \:::je-li $slovo(z) \not= 0 \Rightarrow out(v) \leftarrow z$, jinak $out(v) = out(z)$ \figure{Graphic102.eps}{}{0.7in} \endalgo -\figure{vyhl_automat_full.eps}{Vyhledávací automat - kompletní}{1in} +\figure{vyhl_automat_full.eps}{Vyhledávací automat -- kompletní}{1in} \s{Vìta:} Algoritmus A-C najde v¹echny výskyty slov $\iota_1, \ldots, \iota_k$ ve slove $\sigma$ v èase $$O(\Sigma \vert \iota_i \vert + \vert \sigma \vert + \# výskytù)$$ @@ -95,7 +95,7 @@ Algoritmus A-C najde v \s{Reprezentace v pamìti} \itemize\ibull \:pole se seznamem synù -\:hashovací tabulka $(stav-znak) \rightarrow f(stav-znak)$ - pro velké abecedy +\:hashovací tabulka \<(stav-znak)> $\rightarrow$ \ -- pro velké abecedy \endlist \h{Polynomy a násobení} diff --git a/7-ac/Graphic100.CDR b/7-ac/Graphic100.cdr similarity index 100% rename from 7-ac/Graphic100.CDR rename to 7-ac/Graphic100.cdr diff --git a/7-ac/Graphic101.CDR b/7-ac/Graphic101.cdr similarity index 100% rename from 7-ac/Graphic101.CDR rename to 7-ac/Graphic101.cdr diff --git a/7-ac/Graphic102.CDR b/7-ac/Graphic102.cdr similarity index 100% rename from 7-ac/Graphic102.CDR rename to 7-ac/Graphic102.cdr diff --git a/7-ac/graf1.cdr b/7-ac/polynom.cdr similarity index 100% rename from 7-ac/graf1.cdr rename to 7-ac/polynom.cdr diff --git a/7-ac/Graphic3.cdr b/7-ac/vyhl_automat_full.cdr similarity index 100% rename from 7-ac/Graphic3.cdr rename to 7-ac/vyhl_automat_full.cdr -- 2.39.2