7-ram/7-ram.tex

   1 \input ../sgr.tex
   2
   3 \long\def\onecol#1{\hbox to 0.5\hsize{\vtop{\hsize=0.45\hsize #1}\hss}}
   4 \long\def\twocol#1#2{\par\line{\onecol{#1}\hss\onecol{#2}}}
   5 \def\austere{\parskip=0pt\parindent=0pt}
   6 \def\lines{\obeylines\austere}
   7 \def\\{\hfil\break}
   8 \def\rack#1#2{\setbox0=\hbox{#1}\hbox to \wd0{#2}}
   9
  10 % Alik
  11 % ----
  12 \def\0{{\bf 0}}
  13 \def\1{{\bf 1}}
  14 \def\9{\rack{\0}{\hss$\cdot$\hss}}
  15 \def\opnot{\mathop{\lnot}}
  16 \def\shl{\mathop{<\!<}}
  17 \def\shr{\mathop{>\!>}}
  18 \def\opdiv{\mathop{/}}
  19 \def\opmod{\mathop{\%}}
  20 \def\ALIK{{\sc Alik}}
  21
  22 \def\alik#1{%
  23 \medskip
  24 \halign{\qquad $ ##$&\hbox to 0.4\hsize{${}##$\hfil}&\hfil $ ##$&\hbox to 0.4\hsize{${}##$ \hss}\cr
  25 #1}
  26 \medskip
  27 }
  28
  29 \prednaska{7}{Výpoèetní modely}{zapsal Zdenìk Vilu¹ínský }
  30
  31 \h{Druhy výpoèetních modelù}
  32
  33 \s{Poznámka:} V dostateènì silném výpoèetním modelu lze v¹e (a¾ na
  34 vyjímky) spoèítat v konstantním èase.
  35
  36 \s{Church - Turingova teze:} V¹echny výpoèetní modely které nejsou
  37 absurdní jsou ekvivalentní.
  38
  39  Toto tvrzení ale neplatí a¾ do tìch nejmen¹ích detailù, které by nás zajímaly. Spoèítáme to samé,
  40 ale pøi zkoumání jemnìj¹ích slo¾itostí ne¾ polynomiálních nejsou
  41 modely stejnì silné.
  42
  43 Následující modely se li¹í v tom, zda vìøíme, ¾e lze pole
  44 indexovat v konstantním èase nebo ne.
  45
  46 \s{Pointer Machine:} Uznává 2 typy dat:
  47
  48 \algo
  49 \: Èísla - jsou omezená parametry modelu
  50 \: Pointry -
  51 ukazují na "krabièky"
  52 \endalgo
  53
  54 Pamì» tohoto modelu je slo¾ená z pevného poètu registrù na èísla a
  55 na pointry a neomezeného poètu krabièek. Ka¾dá krabièka má pevný
  56 poèet polo¾ek na èísla a pointry a na krabièku se lze odkázat
  57 pointrem. Aritmetika není a¾ na triviální pøípady v konstantním
  58 èase.
  59
  60 \s{Random Access Machine:} Je rodinka modelù, které se li¹í v
  61 rùzných detailech. Ov¹em dost podstatných. V¹echny mají spoleèné
  62 to, ¾e existuje pouze jeden datový typ - {\bf èísla}, mají pevný
  63 poèet registrù (do jednoho registru se vejde jedno èíslo) a pamì»,
  64 co¾ je pole indexované èísly, jeho¾ polo¾ky jsou èísla. Instrukce
  65 jsou operace s èísly.
  66
  67 Tento model má dvì nejasnosti:
  68
  69 \algo
  70 \: Velikost èísel
  71 \: Cena operací
  72 \endalgo
  73
  74 \h {Typy Random Access Machine (RAM)}
  75
  76 \s{1) Logaritmická cena instrukcí}
  77
  78 Èasová slo¾itost instrukce roste s poètem bitù èísel, na kterých
  79 instrukce pracuje. Dojde tím k odstranìní absurdit, ale ¹patnì se
  80 poèítá $\O(x)$.
  81
  82 \s{2) Omezení velikosti slova; Operace v $\O(1)$}
  83
  84 $W$ - ¹íøka slova. Mám li vstup délky $n$, pak $W$ je alespoò
  85 $\log n$. Mù¾eme BÚNO pøedpokládat, ¾e $W = \O(\log n)$. Není to
  86 zcela ekvivalentní prvnímu RAM, ale dovedeme na nìj pøevést se
  87 zpomalením $\O(\log n)$. Máme k dispozici nìkolik modelù operací:
  88
  89 \algo
  90 \:WordRAM - +, -, *, /, \%, <<, >>, \&,\^{}
  91
  92 \:AC$^0$ RAM - Jsou funkce spoèitatelné hradlovou sítí, která má
  93 polynomiální poèet hradel, libovolný poèet vstupù a konstantní
  94 hloubku.
  95
  96 \:AC$^k$ - Jsou funkce spoèitatelné hradlovou sítí, která má
  97 polynomiální poèet hradel, libovolný poèet vstupù a hloubku $
  98 \O(\log^k n)$.
  99
 100 \:MC$^k$ - Jsou funkce spoèitatelné hradlovou sítí, která má
 101 polynomiální poèet hradel a má nejvý¹e 2 vrstvy.
 102
 103 \: Word $\cap$ AC$^0$ - Mù¾eme v¹e, kromì *, /, \%. Nejedná se ale
 104 o pøíli¹ zajímavý model .
 105 \endalgo
 106
 107 Zamìøíme se pøevá¾nì na WordRAM, ale ve¹keré operace lze vyrobit i
 108 v AC$^0$RAM.
 109
 110 \s{Poznámka:} Ve¹keré Pointer-Machine polynomiání algoritmy,  jsem
 111 schopen na RAM spoèíst v asymptoticky stejném èase.
 112
 113 \h {Van Emde-Boas Trees}
 114
 115 Struktura, která si pamatuje mno¾inu uzlù $X$ z nìjakého omezeného
 116 universa $U$, $X \subseteq \{0..U-1\}$ a podporují "stromové
 117 operace" v èase $\O(\log\log U)$. Stromovými operacemi jsou
 118 my¹leny základní mno¾inové operace a operace pracující s
 119 uspoøádáním. V takovéto struktuøe pak mají operace slo¾itost:
 120
 121 \settabs 5 \columns \+ & VEBT & Best Known\cr \+ Tøídìní &
 122 $\O(n\log\log U)$ & $\O(n\log\log n)$ \cr \+ MST & $\O(m\log\log
 123 U)$ & $\O(m)$ - pro integerovì ohodnocené\cr \+ Dijkstra &
 124 $\O(m\log\log U)$ & $\O(m+n\log\log U)$, neorientovanì $\O(m)$\cr
 125
 126
 127 VEBT pro universum velikosti $U$ (WLOG $U=2^{2^K}$) obsahuje:
 128 \algo
 129
 130 \:min, max - alespoò jedno nesmí být ulo¾eno rekurzivnì v
 131 podstromech
 132
 133 \:pøihrádky $P_0$ -- $P_{\sqrt{U}}$, pøièem¾ $x$ padne do
 134 $P_{\lfloor x/\sqrt{U} \rfloor}$ a pøihrádky jsou ulo¾ené jako
 135 VEBT($\sqrt{U}$)
 136
 137 \:"sumární" VEBT($\sqrt{U}$) obsahující èísla neprázdných
 138 pøihrádek
 139 \endalgo
 140
 141 \s{Find:} - pøímoèaøe v $\O(\log\log U)$
 142
 143 \s{Insert:} Slo¾itost $\O(\log\log U)$
 144 \algo
 145
 146 \:o¹etøení triviálních stromù
 147
 148 \: je-li tøeba, swap s min/max
 149
 150 \: padne do pøihrádky $P_i$, která je buï
 151
 152 \:: prázdná $\Rightarrow$ update sumárního stromu + zalo¾ení
 153 triviálního stromu pro pøihrádku
 154
 155 \:: nìco v ní je $\Rightarrow$ zanoøím do podstromu
 156 \endalgo
 157
 158 \s{Delete:} - analogicky
 159
 160 \s{FindMin:} - Slo¾itost $\O(1)$
 161
 162 \s{Succ:} - Slo¾itost $\O(\log\log U)$
 163 \algo
 164
 165 \: porovnání $x$ s min a max
 166
 167 \:: $x$ = min $\Rightarrow$ i=FindMin(sumarni strom); Succ =
 168 FindMin($P_i$) \:: $x$ = max $\Rightarrow$ Succ = 0
 169
 170 \: $x \in P_i$
 171
 172 \:: $x \not =$ max $P_i$ $\Rightarrow$ vnoøím do $P_i$
 173
 174 \:: $x =$ max $P_i$ $\Rightarrow$ j=Succ(i) v sumárním stromu;
 175 Succ = FindMin($P_j$)
 176 \endalgo
 177
 178 Na operace mám hezké slo¾itosti, ale s inicializací to tak pìkné
 179 není. Nicménì z následujícího vyplyne, ¾e není tøeba inicializaci
 180 psát.
 181
 182 \h{Modely inicializace}
 183
 184 \s{1) "Pøi odchodu zhasni":} Pøidáme axióm, ¾e na zaèátku je celá
 185 pamì» vynulovaná. Za sebou pak pamì» uklidíme.
 186
 187 \s{2) Neinicializovano:} V pamìti je cokoliv, musím se postarat
 188 sám
 189
 190 \s{Vìta:} Buï $P$ program pro WordRAM s nulami inicializované
 191 pamìti bì¾ící v èase $T(n)$. Pak existuje program $P$' pro WordRAM
 192 s {\bf neinicializovanou} pamìtí poèítající toté¾ v
 193 èase$\O(T(n))$.
 194
 195 \s{Dùkaz:} Bìhem výpoètu si budeme pamatovat, k terých pamì»ových
 196 buòkách u¾ nìco máme. Prokládaòe ulo¾íme do pamìti 2 pole:
 197 \itemize\ibull \:M - pamì» $P$  \:L - seznam pou¾itých bunìk v M a
 198 L[0] = délka L
 199 \endlist
 200
 201 Redukci vylep¹íme tím, ¾e zalo¾íme dal¹í prolo¾ené pole R, ve
 202 kterém $i$-tá polo¾ka je buï neinicializovaná nebo øíká, na které
 203 pozici v L je $i$-tá pamì»ová buòka pùvodního stroje.R[$i$] = $j$:
 204 L[$j$] = $i$ $\vee$ neinicializováno pokud $\not \exists$ takové $j$.
 205
 206 Tak¾e jsem schopen v konstantním èase rozhodnout,
 207 jestli u¾ do buòky bylo psáno a ve stejném èase teké buòku pøidat.
 208
 209 \qed
 210
 211 \s{3) Zákaz dìr:} $\Rightarrow$ randomizované
 212
 213 \s{Dùsledek:}Ani v jednom z pøedchozích pøípadù nemusíme psát
 214 inicializaci
 215
 216 \h{Operace s RAM}
 217
 218 Dá se s jistými omezeními pou¾ívat jako vektorový poèítaè.
 219  \itemize\ibull
 220
 221 \:Nejpravìj¹í jednièka:
 222 \alik{
 223   &      & x&=\0\1\9\9\9\0\1\1\0\0\9\9\9\0 \cr
 224   & & x - 1&=\0\1\9\9\9\0\1\0\1\1\9\9\9\1 \cr
 225   & & x \land (x - 1)&=\0\1\9\9\9\0\1\0\0\0\9\9\9\0 \cr
 226   & & x \oplus (x \land (x - 1))&=\0\0\9\9\9\0\0\1\0\0\9\9\9\0 \cr}
 227 \endlist
 228
 229 Pro následující sadu vektorových operací vezmeme vektor, a
 230 prolo¾íme jeho jednotlivé prvky zleva nulami. \itemize\ibull
 231
 232  \alik{ & & \0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr}
 233
 234 \: Replikace:
 235
 236 Replikace $x$ vytvoøí vektor samých $x$
 237  \alik{ & & x*(\0\0\9\9\9\0\0\1)^n \cr}
 238
 239 \: Seètení v¹ech slo¾ek $(Sum)$:
 240
 241 a) sèítáním modulo $1^{n+1}$
 242
 243 b) násobením vhodnou konstantou
 244 \def\.{\hbox to 3pt{\hfil}}
 245 \def\z{\rack{$x_1$}{\hss\1\hss}}
 246 \def\y{\rack{$x_{n-1}$}{\hss\1\hss}}
 247 \def\xa{\rack{$x_1$}{\hss\.\hss}}
 248 \def\xb{\rack{$x_{n-1}$}{\hss.\hss}}
 249 \def\|{\hbox to 3pt{\hfil \vrule height 8pt depth 2pt \hfil}}
 250
 251 \alik{ & & x_{n-1} x_{n-2} \9\9\9\9 x_1 x_0  \cr
 252  &  & * \y\y \9\9\9\9 \z\z \cr
 253  &  & x_{n-1} x_{n-2} \9\9\9\9 x_1 x_0 \cr
 254  &  & x_{n-1} x_{n-2} \xb\9\9 x_1 x_0 \xa \cr
 255  &  & \| \xa\xa\xa\xa\xa\xa\xa \cr
 256  &  & \| \xa\xa\xa\xa\xa\xa\xa \cr
 257  &  & \9\9\9 x_1x_0\xa\xa\xa\xa\xa\xa\xa  \cr
 258  }
 259 Výsledkem je vektor v¹ech èásteèných souètù.
 260
 261 \: Paralelní porovnání $(Cmp)$:
 262
 263 Compare x $\leq$ y $\equiv z_i = 1 \Leftrightarrow x_i \leq y_i$
 264 \alik{ & & \1 y_{n-1} \1 y_{n-2} \9\9\9 \1 y_1\1 y_0  \cr & & - \0
 265 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr   \cr}
 266
 267 U vektoru y nahradíme prolo¾ené nuly jednièkami a odeèteme vektor
 268 x. Ve výsledku pak bude na místì prolo¾eného bitu jednièka právì
 269 tehdy, kdy¾ $x_i \leq y_i$
 270
 271 \: Rank ($x$,y):
 272
 273 Mám nìjaké èíslo $x$ a vektor y, Rank je poèet slo¾ek vektoru,
 274 které jsou men¹í nebo rovny $x$. \alik{ & &
 275 Sum(Cmp((xx\9\9\9xx),y)) \cr}
 276
 277 Nareplikuji vektor samých $x$ a ten porovnám s vektorem y.
 278 Výsledný vektor seètu.
 279
 280 \: Zatøídìní:
 281
 282 Zatøídit novou hodnotu do setøídìného vektoru èísel lze také v
 283 konstantním èase. Nejprve pomocí Rank najdu místo, kam má pøijít,
 284 pak nìjakým konstantním poètem operací vektor "roz¹oupnu" o ¹íøku
 285 slo¾ky doleva a vlo¾ím novou hodnotu.
 286
 287 \: Unpack:
 288
 289 Dostane $k$-bitové èíslo a vyrobí $k$-slo¾kový vektor, jeho¾
 290 slo¾ky jsou bity pùvodního èísla. Zreplikuji $x$ na vektor \alik{
 291 & & \0x\0x\9\9\9\0x \cr} a provedu AND s vhodnou bitovou maskou,
 292 konkrétnì \alik{ & &
 293 \1\0\9\9\9\0\|\9\9\9\|\0\9\9\9\0\1\0\|\0\9\9\9\0\1 \cr} Tím
 294 vytvoøím vektor, který má v ka¾dé slo¾ce nulu nebo nenulu, podle
 295 toho, jestli bit odpovídající této slo¾ce je nulový nebo nenulový,
 296 ale je na ¹patné pozici. Vektor teï prolo¾ím jednièkami místo nul
 297 a odeètu jednièku v ka¾dé slo¾ce. Tam kde byla ve slo¾ce nula, tak
 298 si vypùjèila z jednièky od prostrkání, kde byla nenula tam se
 299 nevypùjèilo. Prokládací bity jsou teï negace tìch, které tam
 300 potøebuji mít. Pak staèí znegovat, provést Shift na správné místo
 301 a AND k odstranìní nepoøádku.
 302
 303 \: Pack:
 304
 305 Dìlá opak ne¾ unpack, dostane vektor jednièek a nul, ze kterého
 306 vytvoøí $k$-bitové èíslo. Pøerozdìlím slo¾ky vektoru tak, jako by
 307 byli o bit krat¹í a provedu $Sum$ - Tím se jednotlivé bity posunou
 308 a posèítá se to, jak potøebuju.
 309
 310 \endlist
 311
 312 Pro dal¹í operace pøedpokládáme, ¾e pro $W$-bitová èísla máme
 313 slova dlouhá alespoò $b^2$.
 314
 315 \itemize\ibull
 316
 317 \: Poèet jednièek:
 318
 319 Zjistí poèet jednièkových bitù. Provedu Unpack, èím¾ dostanu
 320 vektor, jeho¾ slo¾ky jsou bity pùvodního èísla a provedu $Sum$.
 321
 322 \: Zrcadlení:
 323
 324 Chci dostat zrcadlovì symetrické èíslo ke vstupnímu. Nejprve
 325 provedu Replicate. V nejni¾¹í kopii si nechám nejvýznamìj¹í bit, v
 326 dal¹í druhý, a¾ v poslední nejni¾¹í bit. Poté posèítám s o jedna
 327 men¹í velikostí bloku.
 328
 329 \: LSB (Least Significant Bit):
 330
 331 Poøadové èíslo první jednièky zprava. Izoluji tento bit pomocí
 332 nalezení nejpravìj¹í jednièky,  \alik{& & \0\9\9\9\0\1\0\9\9\9\0
 333 \cr} odeètu 1 a seètu jednièky. \alik{& & \0\9\9\9\0\0\1\9\9\9\1
 334 \cr}
 335
 336 \: MSB (Most Significant Bit):
 337
 338 Provede se pøes zrcadlení.
 339
 340 \: MSB pro normální délu slova:
 341
 342 Rozdìlím èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$,
 343 nejdøíve v ka¾dém bloku zjistím, zda v nìm nìco je nebo ne -
 344 $Cmp(x,0)$, provedu Pack, èím¾ dostanu jedno slovo $y$ odmocninové
 345 délky, které øíká, které bloky jsou prázdné a které ne. Dále
 346 pustím MSB kvadratické na $y$, èím¾ dostanu blok $B_i$, ve kterém
 347 je nejpravìj¹í jednièka a nakonec pustím MSB kvadratické na blok
 348 $B_i$. Tím ji najdu uvnitø bloku.
 349
 350 \endlist
 351 \bye