\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.2\hsize\hfil $ ##$&\hbox to 0.6\hsize{${}##$ \hss}\cr
#1}
\medskip
}

\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,
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.

\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í
$\Theta(\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 $\Theta(\log n)$-krát větší než v~neomezeném RAMu.

\:{\I Omezit velikost čísel} na~nějaký pevný počet bitů (budeme mu říkat
{\I šířka slova} a značit~$w$) a operace ponechat v~čase $\O(1)$.
Abychom mohli alespoň adresovat vstup, musí být $w\ge\log N$,
kde $N$ je celková velikost vstupu.
Jelikož aritmetiku s~$\O(1)$-násobnou přesností lze simulovat s~konstantním
zpomalením, můžeme předpokládat, že $w=\Omega(\log N)$, tedy že lze přímo pracovat
s~čísly polynomiálně velkými 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 vyčíslitelné hradlovou sítí polynomiální
velikosti a konstantní hloubky s~hradly o~libovolně mnoha 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 na~Word-RAM, ale podobné konstrukce
jdou provést i na~$AC^0$-RAMu. (Kombinace obou omezení vede ke~slabšímu modelu.)

\h{Van Emde-Boas Trees}

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
\noalign{\smallskip\hrule\smallskip}
třídění 	&$\O(n\log\log U)$	&$\O(n\log\log n)$ \cite{han:sort} \cr
MST		&$\O(m\log\log U)$	&$\O(m)$ [viz příští kapitola]\cr
Dijkstra	&$\O(m\log\log U)$	&$\O(m+n\log\log n)$ \cite{thorup:pq}, neorientovaně $\O(m)$~\cite{thorup:usssp}\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^k=2^{2^\ell}$)
obsahuje:

\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 uložit zvlášť obojí.}
Hodnota $x$ padne do~$P_{\lfloor x/\sqrt{U} \rfloor}$.
Každá přihrá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řihrádku, a~nižších $k/2$ uvnitř přihrá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ě. Budeme si přitom představovat,
že v~přihrádkách jsou uložena přímo čísla reprezentované množiny, nikoliv jen části
jejich bitů -- z~čísla přihrádky a hodnoty uvnitř přihrádky ostatně dokážeme celou
hodnotu rekonstruovat a naopak hodnotu kdykoliv rozložit na~tyto části.

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

\>$\<Find>(x)$ -- přímočaře rekurzí přes přihrá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> hodnoty~$i$ do~sumárního stromu a založení
triviálního stromu pro přihrádku; nebo
\::neprázdná $\Rightarrow$ převedeme 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)$ -- smazání prvku bude opět pracovat v~čase $\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řihrádky (tu najdeme podle sumárního stromu v~konstantním čase)
a převedeme na~\<Delete> v~této přihrádce.
\:Prvek~$x$ padne do~přihrádky $P_i$, která je buď:
\::jednoprvková $\Rightarrow$ zrušení přihrádky a \<Delete> ze~sumárního stromu; nebo
\::větší $\Rightarrow$ \<Delete> ve~stromu přihrádky.
\endalgo

\>$\<Succ>(x)$ -- 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řihrá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řihrá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\medskip

\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, do~kterých paměťových
buněk už bylo něco zapsáno, a~které tedy mají definovanou hodnotu.
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 dosud neexistuje.

Před čtením $M[i]$ se teď 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 zjistíme,
jestli je $M[i]$ již inicializovaná, a~jsme také schopni tuto informaci
v~témže čase udržovat.
\qed

%\medskip}

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

\nobreak
\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: (latinkou značíme vektory,
alfabetou čísla, \0 a \1 jsou jednotlivé bity, $(\ldots)^k$ je $k$-násobné
opakování binárního zápisu)

\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 součet vejde do~$b$~bitů):

\numlist\nalpha
\: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
\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 a znegovat.

\:$\<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 samých nul.

\:$\<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á v~$i$-té složce ponechá právě $\varphi(i)$-tý bit.

\finalfix{\goodbreak}

\:$\<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$. To můžeme
buď 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. Chvíli 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> a 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
