Doplnen dukaz Koenigovy vety a rozsiren uvodni odstavec.

[ga.git] / 7-ram / 7-ram.tex

diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex
index 5ae37080ad3579f84482a4f6f75ad730ef000510..e6e8bd6423e8154eb3dff8d6d2903048a64d98a4 100644 (file)
--- a/7-ram/7-ram.tex
+++ b/7-ram/7-ram.tex
@@ -18,21 +18,21 @@
 
 \def\alik#1{%
 \medskip
 
 \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}{}
 
 #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.
 
 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.
 
 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.
 


@@ -94,17 +94,16 @@ d
 
 \endlist
 
 
 \endlist
 

-V~zbytku této kapitoly uká¾eme, ¾e na~RAMu lze poèítat mnohé vìci
+Ve~zbytku této kapitoly uká¾eme, ¾e na~RAMu lze poèítat mnohé vìci

 efektivnìji ne¾ na~PM. Zamìøíme se pøevá¾nì na~Word-RAM, podobné konstrukce
 jdou provést i na~$AC^0$-RAMu. (Kombinace obou omezení vede ke~slab¹ímu modelu.)
 
 \h{Van Emde-Boas Trees}
 
 efektivnìji ne¾ na~PM. Zamìøíme se pøevá¾nì na~Word-RAM, podobné konstrukce
 jdou provést i na~$AC^0$-RAMu. (Kombinace obou omezení vede ke~slab¹ímu modelu.)
 
 \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:
 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
 $$\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
 }}$$
 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}$)
 
 \s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$)

-obsahuje: (ekvivalentní formulace podle \cite{demaine})
+obsahuje:

 
 \itemize\ibull
 
 
 \itemize\ibull
 


@@ -185,7 +185,7 @@ odpustit.
 
 \h{Modely inicializace}
 
 
 \h{Modely inicializace}
 

-\>Jak mù¾e definován obsah pamìti na~poèátku výpoètu:
+\>Jak mù¾e být definován obsah pamìti na~poèátku výpoètu:

 
 \s{\uv{Pøi odchodu zhasni}:} Zavedeme, ¾e pamì» RAMu je na~poèátku
 inicializována nulami a program ji po~sobì musí uklidit (to je nutné,
 
 \s{\uv{Pøi odchodu zhasni}:} Zavedeme, ¾e pamì» RAMu je na~poèátku
 inicializována nulami a program ji po~sobì musí uklidit (to je nutné,


@@ -201,7 +201,7 @@ n
 pamìtí bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM
 s~neinicializovanou pamìtí poèítající toté¾ v~èase~$\O(T(n))$.
 
 pamìtí bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM
 s~neinicializovanou pamìtí poèítající toté¾ v~èase~$\O(T(n))$.
 

-\s{Dùkaz:} Bìhem výpoètu si budeme pamatovat, ve~kterých pamì»ových
+\proof Bìhem výpoètu si budeme pamatovat, ve~kterých pamì»ových

 buòkách u¾ nìco máme. Prokládanì ulo¾íme do pamìti dvì pole:
 $M$, co¾ bude pamì» pùvodního stroje, a~$L$ -- seznam èísel bunìk
 v~$M$, do~kterých u¾ program zapsal. Pøitom $L[0]$ bude udávat
 buòkách u¾ nìco máme. Prokládanì ulo¾íme do pamìti dvì pole:
 $M$, co¾ bude pamì» pùvodního stroje, a~$L$ -- seznam èísel bunìk
 v~$M$, do~kterých u¾ program zapsal. Pøitom $L[0]$ bude udávat


@@ -263,7 +263,7 @@ prolo
 \:$\<Sum>(x)$ -- seète v¹echny slo¾ky vektoru (pøedpokládáme, ¾e se vejdou do~$b$~bitù):
 
 \numlist\nalpha
 \:$\<Sum>(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
 \:násobením vhodnou konstantou:
 \setbox0=\hbox{~$x_{n-1}$}
 \slotwd=\wd0