\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.
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)$.
+$\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é
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.
+slo¾itost $\Theta(\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:
+\:{\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 spoèítatelné hradlovou sítí polynomiální
-velikosti a konstantní hloubky s~hradly o~libovolné mnoho vstupech.\foot{Pro zvídavé:
+\:{\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í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í.
\endlist
-V~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
+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}
-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
\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
+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^{2^k}$)
-obsahuje: (ekvivalentní formulace podle \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á)
+\:\<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í.}
+My jsme pro eleganci struktury zvolili ulo¾it 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.]
+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ì:
+\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øíhrádky v~èase $\O(k)$.
+\>$\<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>
+\: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í
+\::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øevedu na~Insert v~podstromu.
+\::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
+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)$)
+\>$\<Delete>(x)$ -- smazání prvku bude opìt pracovat v~èase $\O(k)$.
\algo
-\:O¹etøíme triviální stromy (jednoprvkový a dvouprvkový)
+\: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)
-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.
+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)$: (nalezne nejmen¹í prvek vìt¹í ne¾~$x$, opìt v~èase $\O(k)$)
+\>$\<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øí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$:
+\: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$.
+\::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
\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é,
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
+%{\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
+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
-buòkách u¾ nìco máme. Prokládanì ulo¾íme do pamìti dvì pole:
+\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$.
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.
+takové místo dosud 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,
+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
-\todo{References}
-}
+%\medskip}
\s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst.
V~tomto pøípadì nejsme schopni deterministické redukce, ale alespoò
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:
+\>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 vejdou do~$b$~bitù):
+\:$\<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}$ (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
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.
+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)).$$
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.
+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á na~$i$-té pozici ponechá právì $\varphi(i)$-tý bit.
+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):
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é
+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. Zatím pøedpokládejme,
+\>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.
\>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
+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.
+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
projects / ga.git / blobdiff