\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.
-\s{Pointer Machine (PM)} pracuje se dvìma typy dat: {\I èísly} v~pevnì omezeném
+\s{Pointer Machine (PM)} \cite{benamram95what} pracuje se dvìma typy dat: {\I èísly} v~pevnì omezeném
rozsahu a {\I pointery,} které slou¾í k~odkazování na~data ulo¾ená v~pamìti.
Pamì» tohoto modelu je slo¾ená z pevného poètu registrù na~èísla a
na~pointery a z~neomezeného poètu {\I krabièek.} Ka¾dá krabièka má pevný
pøímoèaøe, ov¹em pole musíme reprezentovat stromem, tak¾e indexování stojí
$\O(\log n)$.
-\s{Random Access Machine (RAM)} je rodinka modelù, které mají spoleèné to, ¾e
+\s{Random Access Machine (RAM)} \cite{demaine} je rodinka modelù, které mají spoleèné to, ¾e
pracují výhradnì s~(pøirozenými) èísly a ukládají je do~pamìti indexované
opìt èísly. Instrukce v~programu (podobné assembleru) pracují s~operandy,
které jsou buï konstanty nebo buòky pamìti adresované pøímo (èíslem buòky),
\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 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:
\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
\endalgo
Slo¾itosti operací jsou pìkné, ale nesmíme zapomenout, ¾e strukturu
-je na~poèátku nutné inicializovat, co¾ trvá $\Omega(\sqrt U)$.
+je na~poèátku nutné inicializovat, co¾ trvá $\Omega(\sqrt U)$.\foot{Svádí
+to k~nápadu ponechat pøihrádky neinicializované a nejdøíve se v¾dy zeptat
+sumárního stromu, ale tím bychom si pokazili èasovou slo¾itost.}
Z~následujících úvah ov¹em vyplyne, ¾e si inicializaci mù¾eme
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é,
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
jestli je $M[i]$ ji¾ inicializovaná, a~jsme také schopni tuto informaci
v~tém¾e èase udr¾ovat.
\qed
+
+\todo{References}
}
\s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst.
\>Rozcvièka: {\I nejpravìj¹í jednièka} ve~dvojkovém èísle (hodnota, nikoliv pozice):
\alik{
x&=\0\1\9\9\9\0\1\1\0\0\0\0\0\0 \cr
- x - 1&=\0\1\9\9\9\0\1\0\1\1\0\0\0\1 \cr
+ x - 1&=\0\1\9\9\9\0\1\0\1\1\1\1\1\1 \cr
x \land (x - 1)&=\0\1\9\9\9\0\1\0\0\0\0\0\0\0 \cr
x \oplus (x \land (x - 1))&=\0\0\9\9\9\0\0\1\0\0\0\0\0\0 \cr}
\:$\<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
\:$\#1(\alpha)$ -- spoèítá jednièkové bity v~zadaném èísle.
-Staèí provést \<Unpack> (výsledek se dokonce vejde do~$b\log b$ bitù)
-a následnì \<Sum>.
+Staèí provést \<Unpack> a následnì \<Sum>.
\:$\<Permute>_\pi(\alpha)$ -- pøehází bity podle zadané fixní permutace.
pøedpokládaly prostrkané nuly a ty tu nemáme. Mù¾eme si je ale snadno poøídit
a bity, které jsme nulami pøepsali, prostì zpracovat zvlá¹».}
+\references
\bye
projects / ga.git / blobdiff