From 102aa8956641098546890b5803e55c7dc5b50100 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 30 Dec 2006 23:21:04 +0100 Subject: [PATCH] Preklepy. --- 8-qheap/8-qheap.tex | 105 +++++++++++++++++++++++--------------------- 1 file changed, 55 insertions(+), 50 deletions(-) diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index bf7e68b..5242a12 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -11,39 +11,40 @@ \prednaska{8}{Q-Heaps}{zapsal Cyril Strejc} -V~minulé pøedná¹ce jsme mimo jiné ukázali výpoèetní model RAM a nahlédli jsme, -¾e pomocí RAMu mù¾eme celkem snadno (v konstantním èase) simulovat vektorový poèítaè. -Kdy¾ u¾ máme vektorový poèítaè, pojïme si ukázat, jaké datové struktury s~ním mù¾eme +V~minulé kapitole jsme zavedli výpoèetní model RAM a nahlédli jsme, +¾e na~nìm mù¾eme snadno simulovat vektorový poèítaè s~vektorovými operacemi pracujícími v~konstantním èase. +Kdy¾ u¾ máme takový poèítaè, pojïme si ukázat, jaké datové struktury na~nìm mù¾eme vytváøet. -\s{Znaèení:} $w$~bude v¾dy znaèit ¹íøku slova RAMu, $n$~velikost vstupu algoritmu, -v~nìm¾ datovou strukturu vyu¾íváme (tedy speciálnì víme, ¾e $w\ge\log n$). - Bez újmy na~obecnosti budeme pøedpokládat, ¾e hodnoty, které do~struktur ukládáme, jsou navzájem rùzné. -Svým sna¾ením smìrujeme ke strukturám, které zvládnou operace \ a \ +Svým sna¾ením budeme smìøovat ke~strukturám, které zvládnou operace \ a \ v~konstantním èase, pøièem¾ bude omezena buïto velikost èísel nebo maximální velikost struktury nebo obojí. +\s{Znaèení:} $w$~bude v¾dy znaèit ¹íøku slova RAMu a $n$~velikost vstupu algoritmu, +v~nìm¾ datovou strukturu vyu¾íváme (tedy speciálnì víme, ¾e $w\ge\log n$). + \h{Word-Encoded B-Tree} Pùjde o~obyèejný B-strom s daty v~listech, ov¹em kódovaný vektorovì. Do~listù stromu budeme ukládat $k$-bitové hodnoty, vnitøní vrcholy budou obsahovat pouze -pomocné klíèe a budou mít nejvý¹e $B$ synù, strom bude mít hloubku~$h$. Hodnoty +pomocné klíèe a budou mít nejvý¹e $B$ synù. Strom bude mít hloubku~$h$. Hodnoty v¹ech klíèù ve~vrcholu si budeme ukládat jako vektor, ukazatele na~jednotlivé syny jakbysmet. -Se~stromem zacházíme jako s~klasickým B-stromem, ov¹em operace s~vrcholy +Se~stromem zacházíme jako s~klasickým B-stromem, pøitom operace s~vrcholy provádíme vektorovì: vyhledání pozice prvku ve~vektoru pomocí operace \, rozdìlení a sluèování vrcholù pomocí bitových posuvù a maskování, to v¹e -v~èase $\O(1)$. Stromové operace tedy stihneme v~èase $\O(h)$. +v~èase $\O(1)$. Stromové operace (\, \, \, \, \dots) +tedy stihneme v~èase $\O(h)$. Zbývá si rozmyslet, co~musí splòovat parametry struktury, aby se v¹echny vektory ve¹ly do~konstantního poètu slov. Kvùli vektorùm klíèù musí platit $Bk=\O(w)$. Jeliko¾ strom má a¾~$B^h$ listù a nejvý¹e tolik vnitøních vrcholù, -ukazatele zabírají $\O(h\log B)$ bitù, tak¾e pro vektory ukazatelù potøebujeme -$Bh\log B=\O(w)$. Dobrá volba je napøíklad $B=k=\sqrt w$, $h=\O(1)$, èím¾ +ukazatele zabírají $\O(h\log B)$ bitù, tak¾e pro vektory ukazatelù potøebujeme, +aby bylo $Bh\log B=\O(w)$. Dobrá volba je napøíklad $B=k=\sqrt w$, $h=\O(1)$, èím¾ získáme strukturu obsahující $w^{\O(1)}$ prvkù o~$\sqrt w$ bitech pracující v~konstantním èase. @@ -51,27 +52,27 @@ v~konstantn Pøedchozí struktura má zajímavé vlastnosti, ale èasto je její pou¾ití znemo¾nìno omezením na~velikost èísel. Popí¹eme tedy o~nìco slo¾itìj¹í -strukturu, která doká¾e toté¾, ale lze do~ní ukládat a¾ $w$-bitová èísla. +konstrukci, která doká¾e toté¾, ale s~a¾ $w$-bitovými èísly. Tato struktura má spí¹e teoretický význam (konstrukce je znaènì komplikovaná a skryté konstanty nemalé), ale pøekvapivì mnoho my¹lenek je pou¾itelných i v~praxi. \s{Znaèení:} \itemize\ibull -\: $k = \O(w^{1/4})$ -- omezení na~velikost haldy. -\: $r\le k$ -- aktuální poèet prvkù v~haldì. -\: $X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$. +\: $k = \O(w^{1/4})$ -- omezení na~velikost haldy, +\: $r\le k$ -- aktuální poèet prvkù v~haldì, +\: $X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$, \: $c_i = \msb(x_i \oplus x_{i+1})$ -- nejvy¹¹í bit, na kterém se li¹í $x_i$ a -$x_{i+1}$. -\: $\rank_X(x)$, poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$ +$x_{i+1}$, +\: $\rank_X(x)$ -- poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$ (definujeme i~pro $x\not\in X$). \endlist \s{Pøedvýpoèet:} Budeme ochotni obìtovat èas $\O(2^{k^4})$ na~pøedvýpoèet. -To mù¾e znít hroznì, ale ve~vìt¹inì aplikací bude $k=\log^{1/4} n$, tak¾e +To mù¾e znít hrozivì, ale ve~vìt¹inì aplikací bude $k=\log^{1/4} n$, tak¾e pøedvýpoèet stihneme v~èase $\O(n)$. V~tomto èase mimo jiné stihneme pøedpoèítat tabulku pro libovolnou funkci, která má vstup dlouhý $\O(k^3)$ -bitù a pro ka¾dý vstup ji dovedeme vyhodnotit v~polynomiálním èase. +bitù a kterou pro ka¾dý vstup dovedeme vyhodnotit v~polynomiálním èase. Nadále tedy mù¾eme bezpeènì pøedpokládat, ¾e v¹echny takové funkce umíme spoèítat v~konstantním èase. @@ -83,15 +84,15 @@ si pamatovat minimum podstromu a Q-Heap s~hodnotami jeho syn ka¾dé vlo¾ení i odebrání prvku pøevést na~konstantnì mnoho operací s~Q-Heapy. \s{Náèrt} fungování Q-Heapu: -Nad~prvky $x_1,\ldots,x_r$ sestrojíme komprimovanou trii~$T$ (nevìtvící se cesty -nahradíme hranami). Listy trie budou jednotlivá $x_i$, vnitøní vrchol, +Nad~prvky $x_1,\ldots,x_r$ sestrojíme trii~$T$ a nevìtvící se cesty zkomprimujeme +(nahradíme hranami). Listy trie budou jednotlivá $x_i$, vnitøní vrchol, který le¾í mezi $x_i$ a $x_{i+1}$, bude testovat $c_i$-tý bit èísla. Pokud budeme hledat nìkteré z~$x_i$, tyto vnitøní vrcholy (budeme jim øíkat {\I znaèky}) nás správnì dovedou do~pøíslu¹ného listu. Pokud ale budeme hledat nìjaké jiné~$x$, zavedou nás do~nìjakého na~první pohled nesouvisejícího listu a teprve tam zjistíme, ¾e jsme zabloudili. K~na¹emu -pøekvapení ale to, kam jsme se dostali, bude staèit ke~spoèítáním ranku -prvku, a~tím pádem i k~jeho vlo¾ení do~struktury. +pøekvapení v¹ak to, kam jsme se dostali, bude staèit ke~spoèítání ranku +prvku a z~rankù u¾ odvodíme i ostatní operace. \s{Pøíklad:} \nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není @@ -99,20 +100,20 @@ sou \s{Lemma 1:} $\rank_X(x)$ je urèen jednoznaènì: \numlist\pnromanp -\:tvarem stromu $T$ +\:tvarem stromu $T$, \:indexem $i$ listu $x_i$, do~kterého nás zavede hledání hodnoty~$x$ ve~stromu, -\:vztahem mezi $x$ a $x_i$ ($xx_i$ nebo $x=x_i$) -\:$\msb(x \oplus x_i)$ +\:vztahem mezi $x$ a $x_i$ ($xx_i$ nebo $x=x_i$), +\:pozicí $b=\msb(x \oplus x_i)$. \endlist \s{Dùkaz:} Pokud $x=x_i$, je zjevnì $\rank_X(x) = i$. Pøedpokládejme tedy $x\ne x_i$. Hodnoty znaèek klesají ve~smìru od koøene k~listùm a na cestì od koøene k~$x_i$ se v¹echny bity v $x_i$ na~pozicích urèených znaèkami shodují s bity v $x$, pøièem¾ -a¾ do~pozice $c_i$ se shodují i bity znaèkami netestované. Sledujme tuto cestu -od~koøene a¾ po~$c_i$: pokud cesta odboèuje doprava, jsou v¹echny hodnoty +a¾ do~pozice $b$ se shodují i bity znaèkami netestované. Sledujme tuto cestu +od~koøene a¾ po~$b$: pokud cesta odboèuje doprava, jsou v¹echny hodnoty v~levém podstromu men¹í ne¾~$x$, a~tedy se do~ranku zapoèítají. Pokud odboèuje doleva, jsou hodnoty v~pravém podstromu zaruèenì vìt¹í a nezapoèítají se. -Pokud nastala neshoda a $xPoèítání rankù je témìø v¹e, co potøebujeme k~implementaci operací -\, \ a \. Jediná dal¹í pøeká¾ka u¾ je zatøiïování +\, \ a \. Jedinou dal¹í pøeká¾ku tvoøí zatøiïování do~seznamu $x_1,\ldots,x_r$, který je moc velký na~to, aby se ve¹el -do~$\O(1)$ slov. Proto si budeme pamatovat zvlá¹» tyto hodnoty v~libovolném +do~$\O(1)$ slov. Proto si budeme pamatovat zvlá¹» hodnoty v~libovolném poøadí a zvlá¹» permutaci, která je setøídí -- ta se ji¾ do~vektoru vejde. Øeknìme tedy poøádnì, co~v¹e si bude struktura pamatovat: \s{Stav struktury:} \itemize\ibull -\:$k$, $r$ -- kapacita haldy a aktuální poèet prvkù (èísla) -\:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvkù v libovolném poøadí (pole èísel) +\:$k$, $r$ -- kapacita haldy a aktuální poèet prvkù (èísla), +\:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvkù v libovolném poøadí (pole èísel), \:$\varrho$ -- permutace na~$\{1,\ldots,r\}$ taková, ¾e $x_i=X[\varrho(i)]$ - a $x_1Nyní ji¾ uká¾eme, jak provádìt jednotlivé operace: -\s{Find(x)} +\>$\(x):$ \algo -\:$i := \rank_X(x)$ +\:$i := \rank_X(x)$. \:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.} \endalgo -\s{Insert(x)} +\>$\(x):$ \algo \:$i := \rank_X(x)$ \:Pokud $x=x_i$, hodnota u¾ je pøítomna. -\:Ulo¾íme $x$ do~pole~$X$ a vlo¾íme jeho pozici na~$i$-té místo v~permutaci~$\varrho$. +\:Ulo¾íme $x$ do~$X[\mathop{{+}{+}}r]$ a vlo¾íme $r$ na~$i$-té místo v~permutaci~$\varrho$. \:Pøepoèítáme $c_{i-1}$ a $c_i$. Pro ka¾dou zmìnu $c_j$: \::Pokud je¹tì nová hodnota není v~$B$, pøidáme ji tam. \::Upravíme $C(j)$, aby ukazovalo na~tuto hodnotu. -\::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(k)$, sma¾eme ji z~$B$. +\::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(\cdot)$, sma¾eme ji z~$B$. \endalgo -\s{Delete(x)} +\>$\(x):$ \algo \:$i := \rank_X(x)$ (víme, ¾e $x_i=x$). @@ -207,6 +210,8 @@ po \todo{Popsat, jak se poèítá $x[B]$.} +\todo{Na $AC^0$-RAMu staèí $k=\O(w/\log w)$.} + \todo{Aplikace na~kostry.} \bye -- 2.39.2