\medskip
}
-\prednaska{7}{Výpoèetní modely}{}
+\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.
+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ù}
+\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.
+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
+\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í
+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.
+\s{Random Access Machine (RAM)} \cite{demaine} je rodinka modelů, které majà spoleÄ\8dné 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Ä\9bt, že tento model je alespoÅ\88 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:
+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:
+\:{\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Ä\9b odstranà absurdity, ale je dost tÄ\9bžké odhadovat Ä\8dasové 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$.
+\:{\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Ä\9b-vstupovými hradly a $NC^k$ totéž
+s~omezenÃm na~hradla se dvÄ\9bma vstupy. VÅ¡imnÄ\9bte 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.)
+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:
+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Å\99Ãklad dokážeme:
$$\vbox{\halign{
#\hfil\quad &#\hfil\quad &#\hfil\cr
- & pomocí VEBT &nejlep¹í známé pro celá èísla \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
+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}.
+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}$)
+\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 ulo¾it zvlá¹» obojí.}
+\:{\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.]
+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.
+\: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.
+\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~Ä\8dÃsla pÅ\99ihrádky a hodnoty uvnitÅ\99 pÅ\99ihrádky ostatnÄ\9b dokážeme celou
+hodnotu rekonstruovat a naopak hodnotu kdykoliv rozložit na~tyto části.
-\>\<FindMin> -- minimum nalezneme v~koøeni v~èase $\O(1)$.
+\>\<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)$.
+\>$\<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.
+\: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)$.
+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)$.
+\>$\<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.
+\: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)$:
+\>$\<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$.
+\: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
+Složitosti operacà jsou pÄ\9bkné, 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Å\99ihrádky neinicializované a nejdÅ\99Ãve se vždy zeptat
+sumárnÃho stromu, ale tÃm bychom si pokazili Ä\8dasovou 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:
+\>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{\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:
+\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Ä\9bjakou 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.
+\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 Ä\8dase 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ì.
+\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Å\99à použità universálnÃho hashovánà dá~složitost $\O(1)$
+na~operaci v~průměrném případě.
-\h{Technické triky}
+\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.
+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):
+\>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:
+\>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)
+\>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)$:
+\:$\<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ù):
+\:$\<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:
+\: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\.{\[]}
\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ù:
+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
+\:$\<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}$}}
-~ \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.
+Ve~vektoru $x$ nahradíme prokládací nuly jedničkami a odečteme vektor~$y$.
+Ve~výsledku se tyto jedniÄ\8dky zmÄ\9bnà na~nuly právÄ\9b u tÄ\9bch 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)$ -- spoÄ\8dÃ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$:
+\:$\<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).
+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).
+\:$\<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.
+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$:
+\:$\<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.
+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):
+\:$\<Pack>(x)$ -- dostane vektor nul a jedniÄ\8dek a vytvoÅ\99à Ä\8dÃ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$:
+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
\|\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í.
+Jen si musÃme dát pozor na~to, že vytvoÅ\99ený vektor s~kratÅ¡Ãmi složkami
+není korektně prostrkán nulami. Konstrukce \<Sum> pomocí modula proto
+nebude správnÄ\9b 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
+\>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.
+\:$\#1(\alpha)$ -- spočítá jedničkové bity v~zadaném čísle.
-Staèí provést \<Unpack> a následnì \<Sum>.
+Stačí provést \<Unpack> a následně \<Sum>.
-\:$\<Permute>_\pi(\alpha)$ -- pøehází bity podle zadané fixní permutace.
+\:$\<Permute>_\pi(\alpha)$ -- přehází bity podle zadané fixní permutace.
-Provedeme $\<Unpack>_\pi$ a \<Pack> zpìt.
+Provedeme $\<Unpack>_\pi$ a \<Pack> zpět.
-\:$\<LSB>(\alpha)$ -- Least Significant Bit (pozice nejni¾¹í jednièky):
+\:$\<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$:
+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\oplus(\alpha-1)&= \0\9\9\9\0\1\1\1\1\1\cr
}
-\:$\<MSB>(\alpha)$ -- Most Significant Bit (pozice nejvy¹¹í jednièky):
+\:$\<MSB>(\alpha)$ -- Most Significant Bit (pozice nejvyšší jedničky):
-Z~\<LSB> pomoc
í zrcadlení (operací \<Permute>).
+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á¹».}
+\>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