\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}{zapsal Zdenìk Vilu¹ínský }
-
-\h{Druhy výpoèetních modelù}
+\prednaska{7}{Výpoèetní modely}{}
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,
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.
\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
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
\algo
\:O¹etøíme triviální stromy (jednoprvkový a dvouprvkový)
\:Pokud ma¾eme \<min> (analogicky \<max>), nahradíme ho minimem
-z~první neprázdné pøíhrádky (tu najdeme podle sumárního stromu)
+z~první neprázdné pøíhrádky (tu najdeme podle sumárního stromu v~konstantním èase)
a pøevedeme na~Delete v~této pøíhrádce.
\:Prvek~$x$ padne do~pøíhrádky $P_i$, která je buï:
\::jednoprvková $\Rightarrow$ zru¹ení pøíhrádky a Delete ze~sumárního stromu; nebo
\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é,
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
\:$\<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