\input ../sgr.tex

\long\def\onecol#1{\hbox to 0.5\hsize{\vtop{\hsize=0.45\hsize #1}\hss}}
\long\def\twocol#1#2{\par\line{\onecol{#1}\hss\onecol{#2}}}
\def\austere{\parskip=0pt\parindent=0pt}
\def\lines{\obeylines\austere}
\def\\{\hfil\break}
\def\rack#1#2{\setbox0=\hbox{#1}\hbox to \wd0{#2}}

% Alik
% ----
\def\0{{\bf 0}}
\def\1{{\bf 1}}
\def\9{\rack{\0}{\hss$\cdot$\hss}}
\def\opnot{\mathop{\lnot}}
\def\shl{\mathop{<\!<}}
\def\shr{\mathop{>\!>}}
\def\opdiv{\mathop{/}}
\def\opmod{\mathop{\%}}
\def\ALIK{{\sc Alik}}

\def\alik#1{%
\medskip
\halign{\qquad $ ##$&\hbox to 0.4\hsize{${}##$\hfil}&\hfil $ ##$&\hbox to 0.4\hsize{${}##$ \hss}\cr
#1}
\medskip
}

\prednaska{7}{Výpoèetní modely}{zapsal Zdenìk Vilu¹ínský }

\h{Druhy výpoèetních modelù}

\s{Poznámka:} V dostateènì silném výpoèetním modelu lze v¹e (a¾ na
vyjímky) spoèítat v konstantním èase.

\s{Church - Turingova teze:} V¹echny výpoèetní modely které nejsou
absurdní jsou ekvivalentní.

 Toto tvrzení ale neplatí a¾ do tìch nejmen¹ích detailù, které by nás zajímaly. Spoèítáme to samé,
ale pøi zkoumání jemnìj¹ích slo¾itostí ne¾ polynomiálních nejsou
modely stejnì silné.

Následující modely se li¹í v tom, zda vìøíme, ¾e lze pole
indexovat v konstantním èase nebo ne.

\s{Pointer Machine:} Uznává 2 typy dat:

\algo
\: Èísla - jsou omezená parametry modelu
\: Pointry -
ukazují na "krabièky"
\endalgo

Pamì» tohoto modelu je slo¾ená z pevného poètu registrù na èísla a
na pointry a neomezeného poètu krabièek. Ka¾dá krabièka má pevný
poèet polo¾ek na èísla a pointry a na krabièku se lze odkázat
pointrem. Aritmetika není a¾ na triviální pøípady v konstantním
èase.

\s{Random Access Machine:} Je rodinka modelù, které se li¹í v
rùzných detailech. Ov¹em dost podstatných. V¹echny mají spoleèné
to, ¾e existuje pouze jeden datový typ - {\bf èísla}, mají pevný
poèet registrù (do jednoho registru se vejde jedno èíslo) a pamì»,
co¾ je pole indexované èísly, jeho¾ polo¾ky jsou èísla. Instrukce
jsou operace s èísly.

Tento model má dvì nejasnosti:

\algo
\: Velikost èísel
\: Cena operací
\endalgo

\h {Typy Random Access Machine (RAM)}

\s{1) Logaritmická cena instrukcí}

Èasová slo¾itost instrukce roste s poètem bitù èísel, na kterých
instrukce pracuje. Dojde tím k odstranìní absurdit, ale ¹patnì se
poèítá $\O(x)$.

\s{2) Omezení velikosti slova; Operace v $\O(1)$}

$W$ - ¹íøka slova. Mám li vstup délky $n$, pak $W$ je alespoò
$\log n$. Mù¾eme BÚNO pøedpokládat, ¾e $W = \O(\log n)$. Není to
zcela ekvivalentní prvnímu RAM, ale dovedeme na nìj pøevést se
zpomalením $\O(\log n)$. Máme k dispozici nìkolik modelù operací:

\algo
\:WordRAM - +, -, *, /, \%, <<, >>, \&,\^{}

\:AC$^0$ RAM - Jsou funkce spoèitatelné hradlovou sítí, která má
polynomiální poèet hradel, libovolný poèet vstupù a konstantní
hloubku.

\:AC$^k$ - Jsou funkce spoèitatelné hradlovou sítí, která má
polynomiální poèet hradel, libovolný poèet vstupù a hloubku $
\O(\log^k n)$.

\:MC$^k$ - Jsou funkce spoèitatelné hradlovou sítí, která má
polynomiální poèet hradel a má nejvý¹e 2 vrstvy.

\: Word $\cap$ AC$^0$ - Mù¾eme v¹e, kromì *, /, \%. Nejedná se ale
o pøíli¹ zajímavý model .
\endalgo

Zamìøíme se pøevá¾nì na WordRAM, ale ve¹keré operace lze vyrobit i
v AC$^0$RAM.

\s{Poznámka:} Ve¹keré Pointer-Machine polynomiání algoritmy,  jsem
schopen na RAM spoèíst v asymptoticky stejném èase.

\h {Van Emde-Boas Trees}

Struktura, která si pamatuje mno¾inu uzlù $X$ z nìjakého omezeného
universa $U$, $X \subseteq \{0..U-1\}$ a podporují "stromové
operace" v èase $\O(\log\log U)$. Stromovými operacemi jsou
my¹leny základní mno¾inové operace a operace pracující s
uspoøádáním. V takovéto struktuøe pak mají operace slo¾itost:

\settabs 5 \columns \+ & VEBT & Best Known\cr \+ Tøídìní &
$\O(n\log\log U)$ & $\O(n\log\log n)$ \cr \+ MST & $\O(m\log\log
U)$ & $\O(m)$ - pro integerovì ohodnocené\cr \+ Dijkstra &
$\O(m\log\log U)$ & $\O(m+n\log\log U)$, neorientovanì $\O(m)$\cr


VEBT pro universum velikosti $U$ (WLOG $U=2^{2^K}$) obsahuje:
\algo

\:min, max - alespoò jedno nesmí být ulo¾eno rekurzivnì v
podstromech

\:pøihrádky $P_0$ -- $P_{\sqrt{U}}$, pøièem¾ $x$ padne do
$P_{\lfloor x/\sqrt{U} \rfloor}$ a pøihrádky jsou ulo¾ené jako
VEBT($\sqrt{U}$)

\:"sumární" VEBT($\sqrt{U}$) obsahující èísla neprázdných
pøihrádek
\endalgo

\s{Find:} - pøímoèaøe v $\O(\log\log U)$

\s{Insert:} Slo¾itost $\O(\log\log U)$
\algo

\:o¹etøení triviálních stromù

\: je-li tøeba, swap s min/max

\: padne do pøihrádky $P_i$, která je buï

\:: prázdná $\Rightarrow$ update sumárního stromu + zalo¾ení
triviálního stromu pro pøihrádku

\:: nìco v ní je $\Rightarrow$ zanoøím do podstromu
\endalgo

\s{Delete:} - analogicky

\s{FindMin:} - Slo¾itost $\O(1)$

\s{Succ:} - Slo¾itost $\O(\log\log U)$
\algo

\: porovnání $x$ s min a max

\:: $x$ = min $\Rightarrow$ i=FindMin(sumarni strom); Succ =
FindMin($P_i$) \:: $x$ = max $\Rightarrow$ Succ = 0

\: $x \in P_i$

\:: $x \not =$ max $P_i$ $\Rightarrow$ vnoøím do $P_i$

\:: $x =$ max $P_i$ $\Rightarrow$ j=Succ(i) v sumárním stromu;
Succ = FindMin($P_j$)
\endalgo

Na operace mám hezké slo¾itosti, ale s inicializací to tak pìkné
není. Nicménì z následujícího vyplyne, ¾e není tøeba inicializaci
psát.

\h{Modely inicializace}

\s{1) "Pøi odchodu zhasni":} Pøidáme axióm, ¾e na zaèátku je celá
pamì» vynulovaná. Za sebou pak pamì» uklidíme.

\s{2) Neinicializovano:} V pamìti je cokoliv, musím se postarat
sám

\s{Vìta:} Buï $P$ program pro WordRAM s nulami inicializované
pamìti bì¾ící v èase $T(n)$. Pak existuje program $P$' pro WordRAM
s {\bf neinicializovanou} pamìtí poèítající toté¾ v
èase$\O(T(n))$.

\s{Dùkaz:} Bìhem výpoètu si budeme pamatovat, k terých pamì»ových
buòkách u¾ nìco máme. Prokládaòe ulo¾íme do pamìti 2 pole:
\itemize\ibull \:M - pamì» $P$  \:L - seznam pou¾itých bunìk v M a
L[0] = délka L
\endlist

Redukci vylep¹íme tím, ¾e zalo¾íme dal¹í prolo¾ené pole R, ve
kterém $i$-tá polo¾ka je buï neinicializovaná nebo øíká, na které
pozici v L je $i$-tá pamì»ová buòka pùvodního stroje.R[$i$] = $j$:
L[$j$] = $i$ $\vee$ neinicializováno pokud $\not \exists$ takové $j$.

Tak¾e jsem schopen v konstantním èase rozhodnout,
jestli u¾ do buòky bylo psáno a ve stejném èase teké buòku pøidat.

\qed

\s{3) Zákaz dìr:} $\Rightarrow$ randomizované

\s{Dùsledek:}Ani v jednom z pøedchozích pøípadù nemusíme psát
inicializaci

\h{Operace s RAM}

Dá se s jistými omezeními pou¾ívat jako vektorový poèítaè.
 \itemize\ibull

\:Nejpravìj¹í jednièka:
\alik{
  &      & x&=\0\1\9\9\9\0\1\1\0\0\9\9\9\0 \cr
  & & x - 1&=\0\1\9\9\9\0\1\0\1\1\9\9\9\1 \cr
  & & x \land (x - 1)&=\0\1\9\9\9\0\1\0\0\0\9\9\9\0 \cr
  & & x \oplus (x \land (x - 1))&=\0\0\9\9\9\0\0\1\0\0\9\9\9\0 \cr}
\endlist

Pro následující sadu vektorových operací vezmeme vektor, a
prolo¾íme jeho jednotlivé prvky zleva nulami. \itemize\ibull

 \alik{ & & \0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr}

\: Replikace:

Replikace $x$ vytvoøí vektor samých $x$
 \alik{ & & x*(\0\0\9\9\9\0\0\1)^n \cr}

\: Seètení v¹ech slo¾ek $(Sum)$:

a) sèítáním modulo $1^{n+1}$

b) násobením vhodnou konstantou
\def\.{\hbox to 3pt{\hfil}}
\def\z{\rack{$x_1$}{\hss\1\hss}}
\def\y{\rack{$x_{n-1}$}{\hss\1\hss}}
\def\xa{\rack{$x_1$}{\hss\.\hss}}
\def\xb{\rack{$x_{n-1}$}{\hss.\hss}}
\def\|{\hbox to 3pt{\hfil \vrule height 8pt depth 2pt \hfil}}

\alik{ & & x_{n-1} x_{n-2} \9\9\9\9 x_1 x_0  \cr
 &  & * \y\y \9\9\9\9 \z\z \cr
 &  & x_{n-1} x_{n-2} \9\9\9\9 x_1 x_0 \cr
 &  & x_{n-1} x_{n-2} \xb\9\9 x_1 x_0 \xa \cr
 &  & \| \xa\xa\xa\xa\xa\xa\xa \cr
 &  & \| \xa\xa\xa\xa\xa\xa\xa \cr
 &  & \9\9\9 x_1x_0\xa\xa\xa\xa\xa\xa\xa  \cr
 }
Výsledkem je vektor v¹ech èásteèných souètù.

\: Paralelní porovnání $(Cmp)$:

Compare x $\leq$ y $\equiv z_i = 1 \Leftrightarrow x_i \leq y_i$
\alik{ & & \1 y_{n-1} \1 y_{n-2} \9\9\9 \1 y_1\1 y_0  \cr & & - \0
x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr   \cr}

U vektoru y nahradíme prolo¾ené nuly jednièkami a odeèteme vektor
x. Ve výsledku pak bude na místì prolo¾eného bitu jednièka právì
tehdy, kdy¾ $x_i \leq y_i$

\: Rank ($x$,y):

Mám nìjaké èíslo $x$ a vektor y, Rank je poèet slo¾ek vektoru,
které jsou men¹í nebo rovny $x$. \alik{ & &
Sum(Cmp((xx\9\9\9xx),y)) \cr}

Nareplikuji vektor samých $x$ a ten porovnám s vektorem y.
Výsledný vektor seètu.

\: Zatøídìní:

Zatøídit novou hodnotu do setøídìného vektoru èísel lze také v
konstantním èase. Nejprve pomocí Rank najdu místo, kam má pøijít,
pak nìjakým konstantním poètem operací vektor "roz¹oupnu" o ¹íøku
slo¾ky doleva a vlo¾ím novou hodnotu.

\: Unpack:

Dostane $k$-bitové èíslo a vyrobí $k$-slo¾kový vektor, jeho¾
slo¾ky jsou bity pùvodního èísla. Zreplikuji $x$ na vektor \alik{
& & \0x\0x\9\9\9\0x \cr} a provedu AND s vhodnou bitovou maskou,
konkrétnì \alik{ & &
\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
vytvoøím vektor, který má v ka¾dé slo¾ce nulu nebo nenulu, podle
toho, jestli bit odpovídající této slo¾ce je nulový nebo nenulový,
ale je na ¹patné pozici. Vektor teï prolo¾ím jednièkami místo nul
a odeètu jednièku v ka¾dé slo¾ce. Tam kde byla ve slo¾ce nula, tak
si vypùjèila z jednièky od prostrkání, kde byla nenula tam se
nevypùjèilo. Prokládací bity jsou teï negace tìch, které tam
potøebuji mít. Pak staèí znegovat, provést Shift na správné místo
a AND k odstranìní nepoøádku.

\: Pack:

Dìlá opak ne¾ unpack, dostane vektor jednièek a nul, ze kterého
vytvoøí $k$-bitové èíslo. Pøerozdìlím slo¾ky vektoru tak, jako by
byli o bit krat¹í a provedu $Sum$ - Tím se jednotlivé bity posunou
a posèítá se to, jak potøebuju.

\endlist

Pro dal¹í operace pøedpokládáme, ¾e pro $W$-bitová èísla máme
slova dlouhá alespoò $b^2$.

\itemize\ibull

\: Poèet jednièek:

Zjistí poèet jednièkových bitù. Provedu Unpack, èím¾ dostanu
vektor, jeho¾ slo¾ky jsou bity pùvodního èísla a provedu $Sum$.

\: Zrcadlení:

Chci dostat zrcadlovì symetrické èíslo ke vstupnímu. Nejprve
provedu Replicate. V nejni¾¹í kopii si nechám nejvýznamìj¹í bit, v
dal¹í druhý, a¾ v poslední nejni¾¹í bit. Poté posèítám s o jedna
men¹í velikostí bloku.

\: LSB (Least Significant Bit):

Poøadové èíslo první jednièky zprava. Izoluji tento bit pomocí
nalezení nejpravìj¹í jednièky,  \alik{& & \0\9\9\9\0\1\0\9\9\9\0
\cr} odeètu 1 a seètu jednièky. \alik{& & \0\9\9\9\0\0\1\9\9\9\1
\cr}

\: MSB (Most Significant Bit):

Provede se pøes zrcadlení.

\: MSB pro normální délu slova:

Rozdìlím èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$,
nejdøíve v ka¾dém bloku zjistím, zda v nìm nìco je nebo ne -
$Cmp(x,0)$, provedu Pack, èím¾ dostanu jedno slovo $y$ odmocninové
délky, které øíká, které bloky jsou prázdné a které ne. Dále
pustím MSB kvadratické na $y$, èím¾ dostanu blok $B_i$, ve kterém
je nejpravìj¹í jednièka a nakonec pustím MSB kvadratické na blok
$B_i$. Tím ji najdu uvnitø bloku.

\endlist
\bye
