X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=7-ram%2F7-ram.tex;h=e6e8bd6423e8154eb3dff8d6d2903048a64d98a4;hb=54cc78bb075fface0e93040801f496bf76e9f353;hp=5ae37080ad3579f84482a4f6f75ad730ef000510;hpb=86640ac5551fb360cda06a524819704e8af3812c;p=ga.git

diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex
index 5ae3708..e6e8bd6 100644
--- a/7-ram/7-ram.tex
+++ b/7-ram/7-ram.tex
@@ -18,21 +18,21 @@
 
 \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}{}
 
-\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.
 
+\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.
 
@@ -94,17 +94,16 @@ d
 
 \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}
 
-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:
-
 $$\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
 }}$$
+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}$)
-obsahuje: (ekvivalentní formulace podle \cite{demaine})
+obsahuje:
 
 \itemize\ibull
 
@@ -185,7 +185,7 @@ odpustit.
 
 \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é,
@@ -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))$.
 
-\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
@@ -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
-\: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