X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=7-ram%2F7-ram.tex;h=7ad0c1c2c32eafc3c95dcbb719050d326ff4b190;hb=ea07b111e73879c9799f53c1643d92652992aeb1;hp=0dd02118d79bd922b144a14b61629e164632541f;hpb=d81fc4332bc40324dbcbc8d6e1059632bde705c4;p=ga.git diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex index 0dd0211..7ad0c1c 100644 --- a/7-ram/7-ram.tex +++ b/7-ram/7-ram.tex @@ -18,21 +18,21 @@ \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}{} -\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. +\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. @@ -46,7 +46,7 @@ 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)$. +$\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é @@ -66,25 +66,25 @@ omezit, aby byl realistick 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í. @@ -95,85 +95,88 @@ d \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 +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 -\:\, \ reprezentované mno¾iny (mohou být i nedefinovaná, pokud je mno¾ina moc malá) +\:\, \ 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~\, \ 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. \>\ -- minimum nalezneme v~koøeni v~èase $\O(1)$. -\>$\(x)$ -- pøímoèaøe rekurzí pøes pøíhrádky v~èase $\O(k)$. +\>$\(x)$ -- pøímoèaøe rekurzí pøes pøihrádky v~èase $\O(k)$. \>$\(x)$: \algo \:O¹etøíme triviální stromy (prázdný a jednoprvkový) -\:Je-li tøeba, prohodíme $x$ s \, \ +\:Je-li tøeba, prohodíme $x$ s \, \. \: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$ \ 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~\ 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~\ v~jednom stromu ni¾¹ího øádu a k~tomu vykonáme konstantní práci. Celkem tedy $\O(k)$. -\>$\(x)$: (slo¾itost opìt $\O(k)$) +\>$\(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 \ (analogicky \), 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. +z~první neprázdné pøihrádky (tu najdeme podle sumárního stromu v~konstantním èase) +a pøevedeme na~\ 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 \ ze~sumárního stromu; nebo +\::vìt¹í $\Rightarrow$ \ ve~stromu pøihrádky. \endalgo -\>$\(x)$: (nalezne nejmen¹í prvek vìt¹í ne¾~$x$, opìt v~èase $\O(k)$) +\>$\(x)$ -- nejmen¹í prvek vìt¹í ne¾~$x$, opìt v~èase $\O(k)$: \algo \:Triviální pøípady: pokud $x<\$, vrátíme \; pokud $x\ge\$, 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=\(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=\(P_i)$ $\Rightarrow$ pomocí \ +v~sumárním stromu najdeme nejbli¾¹í dal¹í neprázdnou pøihrádku $P_j$: \:::existuje-li $\Rightarrow$ vrátíme $\(P_j)$, \:::neexistuje-li $\Rightarrow$ vrátíme \. -\::nebo $x<\(P_i)$ $\Rightarrow$ pøevedeme na~Succ v~$P_i$. +\::nebo $x<\(P_i)$ $\Rightarrow$ pøevedeme na~\ v~$P_i$. \endalgo Slo¾itosti operací jsou pìkné, ale nesmíme zapomenout, ¾e strukturu @@ -195,14 +198,15 @@ aby programy 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))$. -\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: +\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$. @@ -215,16 +219,15 @@ vr 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ò @@ -251,19 +254,23 @@ po 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 \:$\(\alpha)$ -- vytvoøí vektor $(\alpha,\alpha,\ldots,\alpha)$: \alik{\alpha*(\0^b\1)^n \cr} -\:$\(x)$ -- seète v¹echny slo¾ky vektoru (pøedpokládáme, ¾e se vejdou do~$b$~bitù): +\:$\(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 @@ -303,7 +310,7 @@ $x_i(\alpha,x)$ -- spoèítá, kolik slo¾ek vektoru~$x$ je men¹ích ne¾~$\alpha$: $$\(\alpha,x) = \(\(\(\alpha),x)).$$ @@ -319,12 +326,14 @@ existuj 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 $\$ s~vektorem reprezentovaným touté¾ bitovou maskou. +a pak provedeme $\$ s~vektorem samých nul. \:$\_\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} \:$\(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): @@ -346,13 +355,13 @@ Nap Jen si musíme dát pozor na~to, ¾e vytvoøený vektor s~krat¹ími slo¾kami není korektnì prostrkán nulami. Konstrukce \ 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. @@ -387,10 +396,10 @@ Z~\ pomoc \>Poslední dvì operace doká¾eme spoèítat i v~lineárním prostoru, napøíklad pro \ 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 $\(0,x)$. Pomocí \ z~toho dostaneme slovo~$y$ odmocninové délky, jeho¾ bity indikují neprázdné bloky. Na~toto èíslo zavoláme pøedchozí -kvadratické \, èím¾ zjistíme index nejvy¹¹ího neprázdného bloku. +kvadratické \ 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