From 6b63912ef3d296e69a2e349b47539ded580112cc Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 24 Jan 2007 16:56:04 +0100 Subject: [PATCH] Kapitola o RAMech: stylisticke ladeni a odkazy na literaturu. --- 7-ram/7-ram.tex | 115 +++++++++++++++++++++++++----------------------- ga.bib | 40 +++++++++++++++++ 2 files changed, 100 insertions(+), 55 deletions(-) diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex index e6e8bd6..c5d314f 100644 --- a/7-ram/7-ram.tex +++ b/7-ram/7-ram.tex @@ -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,7 +95,7 @@ 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} @@ -108,9 +108,9 @@ $$\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}. @@ -119,61 +119,64 @@ 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øhrá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 @@ -198,11 +201,12 @@ n {\narrower \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,15 +219,14 @@ 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} } \s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst. @@ -253,14 +256,16 @@ Libovoln prolo¾enì nulovými bity: \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}$ (proto¾e $\1\0^{b+1}\bmod \1^{b+1}=1$), èi @@ -303,7 +308,7 @@ $x_i(\alpha,x)$ -- spoèítá, kolik slo¾ek vektoru~$x$ je men¹ích ne¾~$\alpha$: $$\(\alpha,x) = \(\(\(\alpha),x)).$$ @@ -324,7 +329,7 @@ a pak provedeme $\$ s~vektorem reprezentovan \:$\_\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. \:$\(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 +351,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. @@ -390,7 +395,7 @@ pro \ takto: Rozd 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 diff --git a/ga.bib b/ga.bib index d13924d..4cc3654 100644 --- a/ga.bib +++ b/ga.bib @@ -401,3 +401,43 @@ year={2005}, publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K} } + +@article{ thorup:usssp, + title={{Undirected single-source shortest paths with positive integer weights in linear time}}, + author={Thorup, M.}, + journal={Journal of the ACM (JACM)}, + volume={46}, + number={3}, + pages={362--394}, + year={1999}, + publisher={ACM Press New York, NY, USA} +} + +@article{ thorup:pq, + title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}}, + author={Thorup, M.}, + journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing}, + pages={149--158}, + year={2003}, + publisher={ACM Press New York, NY, USA} +} + +@article{ thorup:isort, + title={{Integer Sorting in 0 (n sqrt (log log n)) Expected Time and Linear Space}}, + author={Han, Y. and Thorup, M.}, + journal={Proceedings of the 43rd Symposium on Foundations of Computer Science}, + pages={135--144}, + year={2002}, + publisher={IEEE Computer Society Washington, DC, USA} +} + +@article{ han:sort, + title={{Deterministic sorting in O (nloglogn) time and linear space}}, + author={Han, Y.}, + journal={Journal of Algorithms}, + volume={50}, + number={1}, + pages={96--105}, + year={2004}, + publisher={Elsevier} +} -- 2.39.2