\input ../sgr.tex
-\long\def\onecol#1{\hbox to 0.5\hsize{\vtop{\hsize=0.45\hsize #1}\hss}}
-\long\def\twocol#1#2{\par\line{\onecol{#1}\hss\onecol{#2}}}
-\def\austere{\parskip=0pt\parindent=0pt}
-\def\lines{\obeylines\austere}
-\def\\{\hfil\break}
+% Makra pro bitove operace
\def\rack#1#2{\setbox0=\hbox{#1}\hbox to \wd0{#2}}
-% Alik
-% ----
+\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\shr{\mathop{>\!>}}
\def\opdiv{\mathop{/}}
\def\opmod{\mathop{\%}}
-\def\ALIK{{\sc Alik}}
\def\alik#1{%
\medskip
-\halign{\qquad $ ##$&\hbox to 0.4\hsize{${}##$\hfil}&\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ù}
-
-\s{Poznámka:} V dostateènì silném výpoèetním modelu lze v¹e (a¾ na
-vyjímky) spoèítat v konstantním èase.
+\prednaska{7}{Výpoèetní modely}{}
-\s{Church - Turingova teze:} V¹echny výpoèetní modely které nejsou
-absurdní jsou ekvivalentní.
+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.
- Toto tvrzení ale neplatí a¾ do tìch nejmen¹ích detailù, které by nás zajímaly. Spoèítáme to samé,
-ale pøi zkoumání jemnìj¹ích slo¾itostí ne¾ polynomiálních nejsou
-modely stejnì silné.
+\h{Druhy výpoèetních modelù}
-Následující modely se li¹í v tom, zda vìøíme, ¾e lze pole
-indexovat v konstantním èase nebo ne.
+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:
-\s{Pointer Machine:} Uznává 2 typy dat:
+\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:
-\algo
-\: Èísla - jsou omezená parametry modelu
-\: Pointry -
-ukazují na "krabièky"
-\endalgo
+\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
-Pamì» tohoto modelu je slo¾ená z pevného poètu registrù na èísla a
-na pointry a neomezeného poètu krabièek. Ka¾dá krabièka má pevný
-poèet polo¾ek na èísla a pointry a na krabièku se lze odkázat
-pointrem. Aritmetika není a¾ na triviální pøípady v konstantním
-èase.
+\endlist
-\s{Random Access Machine:} Je rodinka modelù, které se li¹í v
-rùzných detailech. Ov¹em dost podstatných. V¹echny mají spoleèné
-to, ¾e existuje pouze jeden datový typ - {\bf èísla}, mají pevný
-poèet registrù (do jednoho registru se vejde jedno èíslo) a pamì»,
-co¾ je pole indexované èísly, jeho¾ polo¾ky jsou èísla. Instrukce
-jsou operace s èísly.
+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:
-Tento model má dvì nejasnosti:
+\itemize\ibull
-\algo
-\: Velikost èísel
-\: Cena operací
-\endalgo
+\:\<min>, \<max> reprezentované mno¾iny (mohou být i nedefinovaná, pokud je mno¾ina moc malá),
-\h {Typy Random Access Machine (RAM)}
+\:{\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.]
-\s{1) Logaritmická cena instrukcí}
+\:Navíc je¹tì {\I \uv{sumární}} VEBT($\sqrt{U}$) obsahující èísla neprázdných pøihrádek.
+\endlist
-Èasová slo¾itost instrukce roste s poètem bitù èísel, na kterých
-instrukce pracuje. Dojde tím k odstranìní absurdit, ale ¹patnì se
-poèítá $\O(x)$.
+\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.
-\s{2) Omezení velikosti slova; Operace v $\O(1)$}
+\>\<FindMin> -- minimum nalezneme v~koøeni v~èase $\O(1)$.
-$W$ - ¹íøka slova. Mám li vstup délky $n$, pak $W$ je alespoò
-$\log n$. Mù¾eme BÚNO pøedpokládat, ¾e $W = \O(\log n)$. Není to
-zcela ekvivalentní prvnímu RAM, ale dovedeme na nìj pøevést se
-zpomalením $\O(\log n)$. Máme k dispozici nìkolik modelù operací:
+\>$\<Find>(x)$ -- pøímoèaøe rekurzí pøes pøihrádky v~èase $\O(k)$.
+\>$\<Insert>(x)$:
\algo
-\:WordRAM - +, -, *, /, \%, <<, >>, \&,\^{}
-
-\:AC$^0$ RAM - Jsou funkce spoèitatelné hradlovou sítí, která má
-polynomiální poèet hradel, libovolný poèet vstupù a konstantní
-hloubku.
-
-\:AC$^k$ - Jsou funkce spoèitatelné hradlovou sítí, která má
-polynomiální poèet hradel, libovolný poèet vstupù a hloubku $
-\O(\log^k n)$.
-
-\:MC$^k$ - Jsou funkce spoèitatelné hradlovou sítí, která má
-polynomiální poèet hradel a má nejvý¹e 2 vrstvy.
-
-\: Word $\cap$ AC$^0$ - Mù¾eme v¹e, kromì *, /, \%. Nejedná se ale
-o pøíli¹ zajímavý model .
+\: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
-Zamìøíme se pøevá¾nì na WordRAM, ale ve¹keré operace lze vyrobit i
-v AC$^0$RAM.
-
-\s{Poznámka:} Ve¹keré Pointer-Machine polynomiání algoritmy, jsem
-schopen na RAM spoèíst v asymptoticky stejném èase.
-
-\h {Van Emde-Boas Trees}
+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)$.
-Struktura, která si pamatuje mno¾inu uzlù $X$ z nìjakého omezeného
-universa $U$, $X \subseteq \{0..U-1\}$ a podporují "stromové
-operace" v èase $\O(\log\log U)$. Stromovými operacemi jsou
-my¹leny základní mno¾inové operace a operace pracující s
-uspoøádáním. V takovéto struktuøe pak mají operace slo¾itost:
-
-\settabs 5 \columns \+ & VEBT & Best Known\cr \+ Tøídìní &
-$\O(n\log\log U)$ & $\O(n\log\log n)$ \cr \+ MST & $\O(m\log\log
-U)$ & $\O(m)$ - pro integerovì ohodnocené\cr \+ Dijkstra &
-$\O(m\log\log U)$ & $\O(m+n\log\log U)$, neorientovanì $\O(m)$\cr
-
-
-VEBT pro universum velikosti $U$ (WLOG $U=2^{2^K}$) obsahuje:
+\>$\<Delete>(x)$ -- smazání prvku bude opìt pracovat v~èase $\O(k)$.
\algo
-
-\:min, max - alespoò jedno nesmí být ulo¾eno rekurzivnì v
-podstromech
-
-\:pøihrádky $P_0$ -- $P_{\sqrt{U}}$, pøièem¾ $x$ padne do
-$P_{\lfloor x/\sqrt{U} \rfloor}$ a pøihrádky jsou ulo¾ené jako
-VEBT($\sqrt{U}$)
-
-\:"sumární" VEBT($\sqrt{U}$) obsahující èísla neprázdných
-pøihrádek
+\: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
-\s{Find:} - pøímoèaøe v $\O(\log\log U)$
+\>$\<Succ>(x)$ -- nejmen¹í prvek vìt¹í ne¾~$x$, opìt v~èase $\O(k)$:
-\s{Insert:} Slo¾itost $\O(\log\log U)$
\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
-\:o¹etøení triviálních stromù
+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.
-\: je-li tøeba, swap s min/max
+\h{Modely inicializace}
-\: padne do pøihrádky $P_i$, která je buï
+\>Jak mù¾e být definován obsah pamìti na~poèátku výpoètu:
-\:: prázdná $\Rightarrow$ update sumárního stromu + zalo¾ení
-triviálního stromu pro pøihrádku
+\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.
-\:: nìco v ní je $\Rightarrow$ zanoøím do podstromu
-\endalgo
+\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:
-\s{Delete:} - analogicky
+%{\narrower\medskip
-\s{FindMin:} - Slo¾itost $\O(1)$
+\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))$.
-\s{Succ:} - Slo¾itost $\O(\log\log U)$
-\algo
+\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$.
-\: porovnání $x$ s min a max
+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$.
-\:: $x$ = min $\Rightarrow$ i=FindMin(sumarni strom); Succ =
-FindMin($P_i$) \:: $x$ = max $\Rightarrow$ Succ = 0
+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.
-\: $x \in P_i$
-
-\:: $x \not =$ max $P_i$ $\Rightarrow$ vnoøím do $P_i$
-
-\:: $x =$ max $P_i$ $\Rightarrow$ j=Succ(i) v sumárním stromu;
-Succ = FindMin($P_j$)
-\endalgo
-
-Na operace mám hezké slo¾itosti, ale s inicializací to tak pìkné
-není. Nicménì z následujícího vyplyne, ¾e není tøeba inicializaci
-psát.
+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
-\h{Modely inicializace}
+%\medskip}
-\s{1) "Pøi odchodu zhasni":} Pøidáme axióm, ¾e na zaèátku je celá
-pamì» vynulovaná. Za sebou pak pamì» uklidíme.
+\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ì.
-\s{2) Neinicializovano:} V pamìti je cokoliv, musím se postarat
-sám
+\h{Technické triky}
-\s{Vìta:} Buï $P$ program pro WordRAM s nulami inicializované
-pamìti bì¾ící v èase $T(n)$. Pak existuje program $P$' pro WordRAM
-s {\bf neinicializovanou} pamìtí poèítající toté¾ v
-èase$\O(T(n))$.
+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.
-\s{Dùkaz:} Bìhem výpoètu si budeme pamatovat, k terých pamì»ových
-buòkách u¾ nìco máme. Prokládaòe ulo¾íme do pamìti 2 pole:
-\itemize\ibull \:M - pamì» $P$ \:L - seznam pou¾itých bunìk v M a
-L[0] = délka L
-\endlist
+\>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}
-Redukci vylep¹íme tím, ¾e zalo¾íme dal¹í prolo¾ené pole R, ve
-kterém $i$-tá polo¾ka je buï neinicializovaná nebo øíká, na které
-pozici v L je $i$-tá pamì»ová buòka pùvodního stroje.R[$i$] = $j$:
-L[$j$] = $i$ $\vee$ neinicializováno pokud $\not \exists$ takové $j$.
+\>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:
-Tak¾e jsem schopen v konstantním èase rozhodnout,
-jestli u¾ do buòky bylo psáno a ve stejném èase teké buòku pøidat.
+\nobreak
+\alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0 \cr}
-\qed
+\>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)
-\s{3) Zákaz dìr:} $\Rightarrow$ randomizované
+\itemize\ibull
-\s{Dùsledek:}Ani v jednom z pøedchozích pøípadù nemusíme psát
-inicializaci
+\:$\<Replicate>(\alpha)$ -- vytvoøí vektor $(\alpha,\alpha,\ldots,\alpha)$:
+ \alik{\alpha*(\0^b\1)^n \cr}
-\h{Operace s RAM}
+\:$\<Sum>(x)$ -- seète v¹echny slo¾ky vektoru (pøedpokládáme, ¾e se souèet vejde do~$b$~bitù):
-Dá se s jistými omezeními pou¾ívat jako vektorový poèítaè.
- \itemize\ibull
+\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}}
-\:Nejpravìj¹í jednièka:
\alik{
- & & x&=\0\1\9\9\9\0\1\1\0\0\9\9\9\0 \cr
- & & x - 1&=\0\1\9\9\9\0\1\0\1\1\9\9\9\1 \cr
- & & x \land (x - 1)&=\0\1\9\9\9\0\1\0\0\0\9\9\9\0 \cr
- & & x \oplus (x \land (x - 1))&=\0\0\9\9\9\0\0\1\0\0\9\9\9\0 \cr}
+\[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
-Pro následující sadu vektorových operací vezmeme vektor, a
-prolo¾íme jeho jednotlivé prvky zleva nulami. \itemize\ibull
-
- \alik{ & & \0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0 \cr}
-
-\: Replikace:
+\:$\<Cmp>(x,y)$ -- paralelní porovnání dvou vektorù: $i$-tá slo¾ka výsledku je~1, pokud
+$x_i<y_i$, jinak~0.
-Replikace $x$ vytvoøí vektor samých $x$
- \alik{ & & x*(\0\0\9\9\9\0\0\1)^n \cr}
-
-\: Seètení v¹ech slo¾ek $(Sum)$:
+\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
+}
-a) sèítáním modulo $1^{n+1}$
+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.
-b) násobením vhodnou konstantou
-\def\.{\hbox to 3pt{\hfil}}
-\def\z{\rack{$x_1$}{\hss\1\hss}}
-\def\y{\rack{$x_{n-1}$}{\hss\1\hss}}
-\def\xa{\rack{$x_1$}{\hss\.\hss}}
-\def\xb{\rack{$x_{n-1}$}{\hss.\hss}}
-\def\|{\hbox to 3pt{\hfil \vrule height 8pt depth 2pt \hfil}}
+\:$\<Rank>(\alpha,x)$ -- spoèítá, kolik slo¾ek vektoru~$x$ je men¹ích ne¾~$\alpha$:
+$$\<Rank>(\alpha,x) = \<Sum>(\<Cmp>(\<Replicate>(\alpha),x)).$$
-\alik{ & & x_{n-1} x_{n-2} \9\9\9\9 x_1 x_0 \cr
- & & * \y\y \9\9\9\9 \z\z \cr
- & & x_{n-1} x_{n-2} \9\9\9\9 x_1 x_0 \cr
- & & x_{n-1} x_{n-2} \xb\9\9 x_1 x_0 \xa \cr
- & & \| \xa\xa\xa\xa\xa\xa\xa \cr
- & & \| \xa\xa\xa\xa\xa\xa\xa \cr
- & & \9\9\9 x_1x_0\xa\xa\xa\xa\xa\xa\xa \cr
- }
-Výsledkem je vektor v¹ech èásteèných souètù.
+\:$\<Insert>(\alpha,x)$ -- zatøídí hodnotu $\alpha$ do~setøídìného vektoru~$x$:
-\: Paralelní porovnání $(Cmp)$:
+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).
-Compare x $\leq$ y $\equiv z_i = 1 \Leftrightarrow x_i \leq y_i$
-\alik{ & & \1 y_{n-1} \1 y_{n-2} \9\9\9 \1 y_1\1 y_0 \cr & & - \0
-x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0 \cr \cr}
+\:$\<Unpack>(\alpha)$ -- vytvoøí vektor, jeho¾ slo¾ky jsou bity zadaného èísla
+(jinými slovy prolo¾í bity bloky $b$~nul).
-U vektoru y nahradíme prolo¾ené nuly jednièkami a odeèteme vektor
-x. Ve výsledku pak bude na místì prolo¾eného bitu jednièka právì
-tehdy, kdy¾ $x_i \leq y_i$
+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.
-\: Rank ($x$,y):
+\:$\<Unpack>_\varphi(\alpha)$ -- podobnì jako pøedchozí operace, ale bity je¹tì
+prohází podle nìjaké pevné funkce $\varphi$:
-Mám nìjaké èíslo $x$ a vektor y, Rank je poèet slo¾ek vektoru,
-které jsou men¹í nebo rovny $x$. \alik{ & &
-Sum(Cmp((xx\9\9\9xx),y)) \cr}
+Staèí zvolit bitovou masku, která v~$i$-té slo¾ce ponechá právì $\varphi(i)$-tý bit.
-Nareplikuji vektor samých $x$ a ten porovnám s vektorem y.
-Výsledný vektor seètu.
+\finalfix{\goodbreak}
-\: Zatøídìní:
+\:$\<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):
-Zatøídit novou hodnotu do setøídìného vektoru èísel lze také v
-konstantním èase. Nejprve pomocí Rank najdu místo, kam má pøijít,
-pak nìjakým konstantním poètem operací vektor "roz¹oupnu" o ¹íøku
-slo¾ky doleva a vlo¾ím novou hodnotu.
+Pøedstavíme si, ¾e slo¾ky èísla jsou o~jeden bit krat¹í a provedeme \<Sum>.
+Napøíklad pro $n=4$ a $b=4$:
-\: Unpack:
+\setbox0=\hbox{$x_3$}
+\slotwd=\wd0
+\def\z{\[\0]}
-Dostane $k$-bitové èíslo a vyrobí $k$-slo¾kový vektor, jeho¾
-slo¾ky jsou bity pùvodního èísla. Zreplikuji $x$ na vektor \alik{
-& & \0x\0x\9\9\9\0x \cr} a provedu AND s vhodnou bitovou maskou,
-konkrétnì \alik{ & &
-\1\0\9\9\9\0\|\9\9\9\|\0\9\9\9\0\1\0\|\0\9\9\9\0\1 \cr} Tím
-vytvoøím vektor, který má v ka¾dé slo¾ce nulu nebo nenulu, podle
-toho, jestli bit odpovídající této slo¾ce je nulový nebo nenulový,
-ale je na ¹patné pozici. Vektor teï prolo¾ím jednièkami místo nul
-a odeètu jednièku v ka¾dé slo¾ce. Tam kde byla ve slo¾ce nula, tak
-si vypùjèila z jednièky od prostrkání, kde byla nenula tam se
-nevypùjèilo. Prokládací bity jsou teï negace tìch, které tam
-potøebuji mít. Pak staèí znegovat, provést Shift na správné místo
-a AND k odstranìní nepoøádku.
+\def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
+\def\.{\hphantom{\|}}
-\: Pack:
+\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
+}
-Dìlá opak ne¾ unpack, dostane vektor jednièek a nul, ze kterého
-vytvoøí $k$-bitové èíslo. Pøerozdìlím slo¾ky vektoru tak, jako by
-byli o bit krat¹í a provedu $Sum$ - Tím se jednotlivé bity posunou
-a posèítá se to, jak potøebuju.
+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
-Pro dal¹í operace pøedpokládáme, ¾e pro $W$-bitová èísla máme
-slova dlouhá alespoò $b^2$.
+\>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
-\: Poèet jednièek:
-
-Zjistí poèet jednièkových bitù. Provedu Unpack, èím¾ dostanu
-vektor, jeho¾ slo¾ky jsou bity pùvodního èísla a provedu $Sum$.
+\:$\#1(\alpha)$ -- spoèítá jednièkové bity v~zadaném èísle.
-\: Zrcadlení:
+Staèí provést \<Unpack> a následnì \<Sum>.
-Chci dostat zrcadlovì symetrické èíslo ke vstupnímu. Nejprve
-provedu Replicate. V nejni¾¹í kopii si nechám nejvýznamìj¹í bit, v
-dal¹í druhý, a¾ v poslední nejni¾¹í bit. Poté posèítám s o jedna
-men¹í velikostí bloku.
+\:$\<Permute>_\pi(\alpha)$ -- pøehází bity podle zadané fixní permutace.
-\: LSB (Least Significant Bit):
+Provedeme $\<Unpack>_\pi$ a \<Pack> zpìt.
-Poøadové èíslo první jednièky zprava. Izoluji tento bit pomocí
-nalezení nejpravìj¹í jednièky, \alik{& & \0\9\9\9\0\1\0\9\9\9\0
-\cr} odeètu 1 a seètu jednièky. \alik{& & \0\9\9\9\0\0\1\9\9\9\1
-\cr}
+\:$\<LSB>(\alpha)$ -- Least Significant Bit (pozice nejni¾¹í jednièky):
-\: MSB (Most Significant Bit):
+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$:
-Provede se pøes zrcadlení.
+\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 pro normální délu slova:
+\:$\<MSB>(\alpha)$ -- Most Significant Bit (pozice nejvy¹¹í jednièky):
-Rozdìlím èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$,
-nejdøíve v ka¾dém bloku zjistím, zda v nìm nìco je nebo ne -
-$Cmp(x,0)$, provedu Pack, èím¾ dostanu jedno slovo $y$ odmocninové
-délky, které øíká, které bloky jsou prázdné a které ne. Dále
-pustím MSB kvadratické na $y$, èím¾ dostanu blok $B_i$, ve kterém
-je nejpravìj¹í jednièka a nakonec pustím MSB kvadratické na blok
-$B_i$. Tím ji najdu uvnitø bloku.
+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
projects / ga.git / blobdiff