\input ../sgr.tex

% Makra pro bitove operace
\def\rack#1#2{\setbox0=\hbox{#1}\hbox to \wd0{#2}}

\newdimen\slotwd
\def\slot#1{\hbox to \slotwd{\hfil #1\hfil}}
\def\[#1]{\slot{$#1$}}

\def\0{{\bf 0}}
\def\1{{\bf 1}}
\def\9{\rack{\0}{\hss$\cdot$\hss}}
\def\opnot{\mathop{\lnot}}
\def\shl{\mathop{<\!<}}
\def\shr{\mathop{>\!>}}
\def\opdiv{\mathop{/}}
\def\opmod{\mathop{\%}}

\def\alik#1{%
\medskip
\halign{\hskip 0.3\hsize\hfil $ ##$&\hbox to 0.4\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.

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)} \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ý
poèet polo¾ek na èísla a pointery. Na~krabièku se lze odkázat pouze
pointerem.

Aritmetika v~tomto modelu (a¾ na triviální pøípady) nefunguje v~konstantním
èase, datové struktury popsatelné pomocí pointerù (seznamy, stromy \dots) fungují
pøímoèaøe, ov¹em pole musíme reprezentovat stromem, tak¾e indexování stojí
$\O(\log n)$.

\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),
pøípadnì nepøímo (index je ulo¾en v~nìjaké buòce adresované pøímo).
Je~vidìt, ¾e tento model je alespoò tak silný jako PM, proto¾e odkazy
pomocí pointerù lze v¾dy nahradit indexováním.

Pokud ov¹em povolíme poèítat s~libovolnì velkými èísly v~konstantním èase,
dostaneme velice silný paralelní poèítaè, na~nìm¾ spoèítáme témìø v¹e
v~konstantním èase (modulo kódování vstupu). Proto musíme model nìjak
omezit, aby byl realistický, a~to lze udìlat více zpùsoby:

\itemize\ibull
\:{\I Zavést logaritmickou cenu instrukcí} -- operace trvá tak dlouho,
kolik je poèet bitù èísel, s~nimi¾ pracuje, a~to vèetnì adres v~pamìti.
Elegantnì odstraní absurdity, ale je dost tì¾ké odhadovat èasové slo¾itosti;
u~vìt¹iny normálních algoritmù nakonec po~dlouhém poèítání vyjde, ¾e mají
slo¾itost $\O(\log n)$-krát vìt¹í ne¾ v~neomezeném RAMu.

\:{\I Omezit velikost èísel} na~$w$ bitù a operace ponechat v~èase $\O(1)$.
Jeliko¾ potøebujeme umìt alespoò adresovat vstup, je $w=\Omega(\log n)$.%
\foot{Pøesnìji, plyne z~toho jen, ¾e $w\ge\log_2 n$, ale to je ekvivalentní,
proto¾e aritmetiku s~$\O(1)$-násobnou pøesností mù¾eme simulovat
s~konstantním zpomalením.  S~$\O(\log n)$ bity se ov¹em pracuje daleko
pøíjemnìji, proto¾e si mù¾eme v¾dy dovolit ukládat èísla polynomiálnì
velká vzhledem k~$n$.} Je¹tì bychom si mìli ujasnit, jakou mno¾inu
operací povolíme:

\itemize\ibull
\:{\I Word-RAM} -- \uv{céèkové} operace: $+$, $-$, $*$, $/$, $\bmod$ (aritmetika);
$\shl$, $\shr$ (bitové posuvy); $\land$, $\lor$, $\oplus$, $\opnot$ (bitový and, or, xor a negace).

\:{\I $AC^0$-RAM} -- libovolné funkce spoèítatelné hradlovou sítí polynomiální
velikosti a konstantní hloubky s~hradly o~libovolné mnoho vstupech.\foot{Pro zvídavé:
$AC^k$ je tøída v¹ech funkcí spoèítetelných polynomiálnì velkou hradlovou
sítí hloubky $\O(\log^k n)$ s~libovolnìvstupovými hradly a $NC^k$ toté¾
s~omezením na~hradla se dvìma vstupy. V¹imnìte si, ¾e $NC^0\subseteq AC^0 \subseteq NC^1 \subseteq AC^1 \subseteq NC^2 \subseteq \ldots$.}
To je teoreticky èist¹í, patøí sem v¹e z~pøedchozí skupiny mimo násobení,
dìlení a modula, a~také spousta dal¹ích operací.

\:{\I Kombinace pøedchozího} -- tj. pouze operace Word-RAMu, které jsou v~$AC^0$.
\endlist

\endlist

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
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
\noalign{\smallskip\hrule\smallskip}
tøídìní 	&$\O(n\log\log U)$	&$\O(n\log\log n)$ \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
}}$$

\s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$)
obsahuje: (ekvivalentní formulace podle \cite{demaine})

\itemize\ibull

\:\<min>, \<max> reprezentované mno¾iny (mohou být i nedefinovaná, pokud je mno¾ina moc malá)

\:{\I pøihrádky} $P_0, \ldots, P_{\sqrt{U}}$ obsahující zbývající
hodnoty.\foot{Alespoò jedno z~\<min>, \<max> musí být ulo¾eno zvlá¹»,
aby strom obsahující pouze jednu hodnotu nemìl ¾ádné podstromy.
My jsme pro eleganci struktury zvolili zvlá¹» obojí.}
Hodnota $x$ padne do~$P_{\lfloor x/\sqrt{U} \rfloor}$.
Ka¾dá pøíhrádka je ulo¾ena jako VEBT($\sqrt{U}$), který obsahuje pøíslu¹ná èísla $\bmod \sqrt{U}$.
[Bity ka¾dého èísla jsme tedy rozdìlili na~vy¹¹ích $k/2$, které indexují
pøíhrádku, a~ni¾¹ích $k/2$ uvnitø pøíhrádky.]

\:Navíc je¹tì {\I \uv{sumární}} VEBT($\sqrt{U}$) obsahující èísla neprázdných pøihrádek.
\endlist

\s{Operace} se~strukturou budeme provádìt následovnì:

\>\<FindMin> -- minimum nalezneme v~koøeni v~èase $\O(1)$.

\>$\<Find>(x)$ -- pøímoèaøe rekurzí pøes pøíhrádky v~èase $\O(k)$.

\>$\<Insert>(x)$:
\algo
\:O¹etøíme triviální stromy (prázdný a jednoprvkový)
\:Je-li tøeba, prohodíme $x$ s \<min>, \<max>
\:Prvek $x$ padne do pøihrádky $P_i$, která je buï:
\::prázdná $\Rightarrow$ Insert~$i$ do~sumárního stromu a zalo¾ení
triviálního stromu pro pøihrádku; nebo
\::neprázdná $\Rightarrow$ pøevedu na~Insert v~podstromu.
\endalgo

V~ka¾dém pøípadì buï rovnou skonèíme nebo pøevedeme na~Insert v~jednom stromu
ni¾¹ího øádu a k~tomu vykonáme konstantní práci. Celkem tedy $\O(k)$.

\>$\<Delete>(x)$: (slo¾itost opìt $\O(k)$)
\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 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
\::vìt¹í $\Rightarrow$ Delete ve~stromu pøíhrádky.
\endalgo

\>$\<Succ>(x)$: (nalezne nejmen¹í prvek vìt¹í ne¾~$x$, opìt v~èase $\O(k)$)

\algo
\:Triviální pøípady: pokud $x<\<min>$, vrátíme \<min>; pokud $x\ge\<max>$,
vrátíme, ¾e následník neexistuje.
\:Prvek~$x$ padne do~pøíhrádky $P_i$ a buïto:
\::$P_i$ je prázdná nebo $x=\<max>(P_i)$ $\Rightarrow$ pomocí Succ
v~sumárním stromu najdeme nejbli¾¹í dal¹í neprázdnou pøíhrádku $P_j$:
\:::existuje-li $\Rightarrow$ vrátíme $\<min>(P_j)$,
\:::neexistuje-li $\Rightarrow$ vrátíme \<max>.
\::nebo $x<\<max>(P_i)$ $\Rightarrow$ pøevedeme na~Succ v~$P_i$.
\endalgo

Slo¾itosti operací jsou pìkné, ale nesmíme zapomenout, ¾e strukturu
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 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é,
aby programy ¹lo iterovat). To u~VEBT není problém zaøídit.

\s{Neinicializovano:} Na~¾ádné konkrétní hodnoty se nemù¾eme spolehnout,
ale je definováno, ¾e neinicializovanou buòku mù¾eme pøeèíst a dostaneme
nìjakou korektní, i kdy¾ libovolnou, hodnotu. Tehdy nám pomù¾e:

{\narrower

\s{Vìta:} Buï $P$ program pro Word-RAM s~nulami inicializovanou
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))$.

\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
délku seznamu~$L$.

Program nyní zaène tím, ¾e vynuluje $L[0]$ a bude simulovat pùvodní
program, pøièem¾ kdykoliv ten bude chtít pøeèíst nìjakou buòku
z~$M$, podíváme se do~$L$, zda u¾ je inicializovaná, a~pøípadnì
vrátíme nulu a buòku pøipí¹eme do~$L$.

To je funkèní, ale pomalé. Redukci tedy vylep¹íme tak, ¾e zalo¾íme dal¹í
prolo¾ené pole~$R$, jeho¾ hodnota $R[i]$ bude øíkat, kde v~$L$ se vyskytuje
èíslo $i$-té buòky, nebo bude neinicializována, pokud
takové místo neexistuje.

Pøed ètením $M[i]$ se tedy podíváme na~$R[i]$ a ovìøíme, zda $R[i]$ nele¾í
mimo seznam~$L$ a zda je $L[R[i]]=i$. Tím v~konstantním èase ovìøíme,
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.
V~tomto pøípadì nejsme schopni deterministické redukce, ale alespoò
mu¾eme pou¾ít randomizovanou -- ukládat si obsah pamìti do~hashovací
tabulky, co¾ pøí pou¾ití universálního hashování dá~slo¾itost $\O(1)$
na~operaci v~prùmìrném pøípadì.

\h{Technické triky}

VEBT nedosahují zdaleka nejlep¹ích mo¾ných parametrù -- lze sestrojit
i struktury pracující v~konstantním èase. To v~následující kapitole také
udìláme, ale nejdøíve v~této ponìkud technické stati vybudujeme repertoár
základních operací proveditelných na~Word-RAMu v~konstantním èase.

\>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\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}

\>Nyní uká¾eme, jak RAM pou¾ívat jako vektorový poèítaè, který umí paralelnì
poèítat se v¹emi prvky vektoru, pokud se dají zakódovat do~jediného slova.
Libovolný $n$-slo¾kový vektor, jeho¾ slo¾ky jsou $b$-bitová èísla
($n(b+1)\le w$), zakódujeme poskládáním jednotlivých slo¾ek vektoru za~sebe,
prolo¾enì nulovými bity:
\alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr}

\>S~vektory budeme provádìt následující operace:

\itemize\ibull

\:$\<Replicate>(\alpha)$ -- vytvoøí vektor $(\alpha,\alpha,\ldots,\alpha)$:
 \alik{\alpha*(\0^b\1)^n \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
\:násobením vhodnou konstantou:
\setbox0=\hbox{~$x_{n-1}$}
\slotwd=\wd0
\def\.{\[]}
\def\z{\[\0^b\1]}
\def\dd{\slot{$\cdots$}}
\def\vd{\slot{$\vdots$}}
\def\rule{\noalign{\medskip\nointerlineskip}
$\hrulefill$\cr
\noalign{\nointerlineskip\medskip}}

\alik{
\[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
*~~ \z \dd \z\z\z \cr
\rule
\[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
\[x_{n-1}] \[x_{n-2}] \dd \[x_1] \[x_0] \. \cr
\[x_{n-1}] \[x_{n-2}] \[x_{n-3}] \dd \[x_0] \. \. \cr
\vd\vd\vd\vd\.\.\.\cr
\[x_{n-1}] \dd \[x_2]\[x_1]\[x_0] \. \. \. \. \cr
\rule
\[r_{n-1}] \dd \[r_2] \[r_1] \[s_n] \dd \[s_3] \[s_2] \[s_1] \cr
}
Zde je výsledkem dokonce vektor v¹ech èásteèných souètù:
$s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{n-1}x_i$.
\endlist

\:$\<Cmp>(x,y)$ -- paralelní porovnání dvou vektorù: $i$-tá slo¾ka výsledku je~1, pokud
$x_i<y_i$, jinak~0.

\setbox0=\vbox{\hbox{~$x_{n-1}$}\hbox{~$y_{n-1}$}}
\slotwd=\wd0
\alik{
   \1 \[x_{n-1}] \1 \[x_{n-2}] \[\cdots] \1 \[x_1] \1 \[x_0]  \cr
-~ \0 \[y_{n-1}] \0 \[y_{n-2}] \[\cdots] \0 \[y_1] \0 \[y_0]  \cr
}

Ve~vektoru $x$ nahradíme prokládací nuly jednièkami a odeèteme vektor~$y$.
Ve~výsledku se tyto jednièky zmìní na~nuly právì u tìch slo¾ek, kde $x_i < y_i$.
Pak je ji¾ staèí posunout na~správné místo a okolní bity vynulovat.

\:$\<Rank>(\alpha,x)$ -- spoèítá, kolik slo¾ek vektoru~$x$ je men¹ích ne¾~$\alpha$:
$$\<Rank>(\alpha,x) = \<Sum>(\<Cmp>(\<Replicate>(\alpha),x)).$$

\:$\<Insert>(\alpha,x)$ -- zatøídí hodnotu $\alpha$ do~setøídìného vektoru~$x$:

Zde staèí pomocí operace \<Rank> zjistit, na~jaké místo novou hodnotu
zatøídit, a~pak to pomocí bitových operací provést (\uv{roz¹oupnout}
existující hodnoty).

\:$\<Unpack>(\alpha)$ -- vytvoøí vektor, jeho¾ slo¾ky jsou bity zadaného èísla
(jinými slovy prolo¾í bity bloky $b$~nul).

Nejdøíve èíslo~$\alpha$ replikujeme, pak andujeme vhodnou bitovou maskou,
aby v~$i$-té slo¾ce zùstal pouze $i$-tý bit a ostatní se vynulovaly,
a pak provedeme $\<Cmp>$ s~vektorem reprezentovaným touté¾ bitovou maskou.

\:$\<Unpack>_\varphi(\alpha)$ -- podobnì jako pøedchozí operace, ale bity je¹tì
prohází podle nìjaké pevné funkce $\varphi$:

Staèí zvolit bitovou masku, která na~$i$-té pozici ponechá právì $\varphi(i)$-tý bit.

\:$\<Pack>(x)$ -- dostane vektor nul a jednièek a vytvoøí èíslo, jeho¾ bity
jsou právì slo¾ky vektoru (jinými slovy ¹krtne nuly mezi bity):

Pøedstavíme si, ¾e slo¾ky èísla jsou o~jeden bit krat¹í a provedeme \<Sum>.
Napøíklad pro $n=4$ a $b=4$:

\setbox0=\hbox{$x_3$}
\slotwd=\wd0
\def\z{\[\0]}

\def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
\def\.{\hphantom{\|}}

\alik{
\|\z\.\z\.\z\.\z\.\[x_3]\|\z\.\z\.\z\.\z\.\[x_2]\|\z\.\z\.\z\.\z\[x_1]\|\z\.\z\.\z\.\z\.\[x_0]\|\cr
\|\z\.\z\.\z\.\z\|\[x_3]\.\z\.\z\.\z\|\z\.\[x_2]\.\z\.\z\|\z\.\z\[x_1]\.\z\|\z\.\z\.\z\.\[x_0]\|\cr
}

Jen si musíme dát pozor na~to, ¾e vytvoøený vektor s~krat¹ími slo¾kami
není korektnì prostrkán nulami. Konstrukce \<Sum> pomocí modula proto
nebude správnì fungovat a místo $\1^b$ vygeneruje $\0^b$, co¾ mù¾eme
buïto o¹etøit zvlá¹», nebo pou¾ít konstrukci pøes násobení, které
to nevadí.

\endlist

\>Nyní je¹tì nìkolik operací s~normálními èísly. Zatím pøedpokládejme,
¾e pro~$b$-bitová èísla na~vstupu budeme mít k~dispozici $b^2$-bitový
pracovní prostor, tak¾e budeme moci pou¾ívat vektory s~$b$ slo¾kami
po~$b$ bitech.

\itemize\ibull

\:$\#1(\alpha)$ -- spoèítá jednièkové bity v~zadaném èísle.

Staèí provést \<Unpack> a následnì \<Sum>.

\:$\<Permute>_\pi(\alpha)$ -- pøehází bity podle zadané fixní permutace.

Provedeme $\<Unpack>_\pi$ a \<Pack> zpìt.

\:$\<LSB>(\alpha)$ -- Least Significant Bit (pozice nejni¾¹í jednièky):

Podobnì jako v~rozcvièce nejdøíve vytvoøíme èíslo, které obsahuje
nejni¾¹í jednièku a vpravo od~ní dal¹í jednièky, a~pak tyto jednièky
posèítáme pomocí $\#1$:

\alik{
\alpha&=			\9\9\9\9\9\1\0\0\0\0\cr
\alpha-1&=			\9\9\9\9\9\0\1\1\1\1\cr
\alpha\oplus(\alpha-1)&=	\0\9\9\9\0\1\1\1\1\1\cr
}

\:$\<MSB>(\alpha)$ -- Most Significant Bit (pozice nejvy¹¹í jednièky):

Z~\<LSB> pomocí zrcadlení (operací \<Permute>).

\endlist

\>Poslední dvì operace doká¾eme spoèítat i v~lineárním prostoru, napøíklad
pro \<MSB> takto: Rozdìlíme èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$.
Pak pro ka¾dý blok zjistíme, zda v nìm je aspoò jedna jednièka, zavoláním
$\<Cmp>(0,x)$. Pomocí \<Pack> z~toho dostaneme slovo~$y$ odmocninové
délky, jeho¾ bity indikují neprázdné bloky. Na~toto èíslo zavoláme pøedchozí
kvadratické \<MSB>, èím¾ zjistíme index nejvy¹¹ího neprázdného bloku.
Ten pak izolujeme a druhým voláním kvadratického algoritmu najdeme nejlevìj¹í
jednièku uvnitø nìj.\foot{Dopou¹tíme se drobného podvùdku -- vektorové operace
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
