\input ../lecnotes.tex
\input epsf
\def\itm{\item{$\bullet$}}

\prednaska{5}{Goldbergùv algoritmus}{(zapsaly T.~Klimo¹ová 
a~K.~B\"ohmová)}

\h{Goldbergùv algoritmus -- pokraèování}

Algoritmus upøesníme tak, ¾e místo libovolného vrcholu s~pøebytkem
budeme v¾dy pracovat s~tím, který je na nejvy¹¹í hladinì. Jak doká¾eme
v~následujícím lemmatu, sní¾í se tím poèet potøebných nenasycených
pøevedení. Takto modifikovaný algoritmus budeme znaèit~$G'$.

\s{Lemma $N'$:} V~algoritmu $G'$ je poèet nenasycených pøevedení
$\O(N^3)$.

\proof
Definujme $H$~jako maximální vý¹ku vrcholù s~pøebytkem.
 $$H:=\max\{h(v);v \not= z,s, f^\triangle (v)\geq 0\}$$
Bìh algoritmu $G'$ rozdìlíme na fáze tak, ¾e fáze skonèí po ka¾dé zmìnì
$H$. Odhadneme poèet nenasycených pøevedení v~jedné fázi: bude jich
nanejvý¹ stejnì, jako vrcholù, které se na zaèátku fáze nacházely na
nejvy¹¹í hladinì -- z~jiných vrcholù v~prùbìhu fáze nic nepøevádíme,
a~nenasycené pøevedení mù¾eme provést z~ka¾dého vrcholu nejvý¹e
jednou. Poèet nenasycených pøevedení za fázi je $\leq N$.

Odhadneme poèet fází: rozdìlíme fáze podle toho, jestli konèí sní¾ením
nebo zvý¹ením~$H$ a~odhadneme jejich poèty. Maximálnì $2N^2$ fází mù¾e
konèit zvý¹ením~$H$, proto¾e dle lemmatu Z~provedeme nanejvý¹ $2N^2$
zvednutí. Sní¾ením~$H$ mù¾e konèit nanejvý¹ $2N^2$ fází, proto¾e~$H$
klesne v¾dy alespoò o~1, pùvodnì bylo 0 a~nikdy nemù¾e být záporné --
klesnout tedy nemù¾e víckrát ne¾ vzrùst. 

Máme maximálnì $4N^2$ fází o~nejvý¹e~$N$ nenasycených pøevedení,
celkem tedy algoritmus $G'$ provede $\O(N^3)$ nenasycených pøevedení.
\qed

\medskip
Ve skuteènosti je algoritmus je¹tì lep¹í (alespoò pro øídké grafy):

\s{Lemma $N''$:} V~algoritmu $G'$ je poèet nenasycených pøevedení $\O(N^2
\sqrt M)$.

\proof
(Nezkou¹í se.) Algoritmus rozdìlíme na fáze stejnì jako v~dùkazu
pøedchozího lemmatu a~zvolíme pøirozené èíslo~$K$ (jak velké ho
zvolíme, se rozhodneme a¾ na konci dùkazu).
Fáze tentokrát budeme dìlit na drahé, v~nich¾ se provede více ne¾~$K$
nenasycených pøevedení, a~laciné, v~nich¾ se nenasycených pøevedení
provede maximálnì~$K$.

Nyní budeme zkoumat poèty pøevedení v~obou typech fází.
Jak víme z~minulého lemmatu, v¹ech fází je nanejvý¹ $4N^2$, tak¾e
v~laciných se provede nanejvý¹ $N^2K$ nenasycených pøevedení.
Za úèelem zkoumání drahých fází definujeme potenciál
$$\psi:=\sum_{v\not=z,s; f^\triangle(x)>0}{ p(v)\over K},$$ kde
$p(v):= \vert\{u : h(u) \leq h(v)\}\vert$, èili poèet vrcholù ve stejné
nebo men¹í vý¹ce ne¾~$v$. Víme, ¾e na zaèátku bude $\psi \leq
{N^2/K}$ a~po celou dobu bude $\psi \geq 0$.

Zvednutím vrcholu~$v$ se hodnota $p(v)$ zvý¹í maximálnì o~$N$, u~libovolného
jiného vrcholu~$w$ $p(w)$ klesne nebo se nezmìní, potenciál tedy
vzroste maximálnì o~$N/K$. Pøedchozích èástí
Pøi sytém pøevedení po hranì z~$u$ do~$v$ (z~minula víme, ¾e se v¾dy
provádí po hranì spádu nejvý¹e 1) se mohl potenciál zmen¹it o~$p(u)/K$
a~mohl se zvìt¹it o~$p(v)/K$. Zvìt¹í se tedy nanejvý¹ o~$N/K$
Pøi nenasyceném pøevedení z~potenciálu urèitì ubyde o~$p(u)/K$
a~mo¾ná pøibyde $p(v)/K$. Celkovì se tedy sní¾í nanejvý¹
o~${p(u)/K} - {p(v)/K}$, co¾ je $1/K$~poètu prvkù na nejvy¹¹í
hladinì. Z~minulého lemmatu víme, ¾e poèet nenasycených pøevedení
v~jedné fázi je men¹í nebo roven poètu vrcholù na nejvy¹¹í hladinì na
zaèátku fáze. Vzhledem k~tomu, ¾e zkoumáme drahé fáze v~nich¾ probìhne
více ne¾~$K$ nenasycených pøevedení, vrcholù na nejvy¹¹í hladinì musí
být na zaèátku fáze také více ne¾~$K$, potenciál se tedy sní¾í o~více
ne¾ ${K/K}=1$.

Potenciál $\psi$ tedy pøijme na zaèátku  nanejvý¹ ${N^2/K}$, pøi
zvedání nevzroste o~víc ne¾ $(N/K)2N^2$, pøi sytém pøevádìní
nevzroste o~víc ne¾ $(N/K)NM$, celkem dostáváme $\psi\leq
(N/2)(N+2N^2+NM)=\O({N^2}M/2)$, v~drahých fázích tak mù¾e probìhnout
nanejvý¹ $\O({N^2}M/2)$ nenasycených pøevedení.
Celkem algoritmus vykoná $\O(N^2K+{N^2}M/K)$ nenasycených
pøevedení. Kdy¾ za~$K$ dosadíme $\sqrt M$ dostaneme slíbený poèet
$\O(N^2\sqrt M)$.
\qed

\medskip
\h{Tøídìní}

\s{Definice:} Komparátorová sí» je kombinaèní obvod jeho¾ hradla jsou
komparátory: 

\centerline{\epsfbox{sortnet.0}}

Výstupy komparátorù se nevìtví.

\medskip
{\>\sl Bubble sort}

\twofigures{sortnet.1}{Bubble.1}{143pt}{sortnet.2}{Bubble.2}{143pt}

Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble.2). 
Takto se nám podaøilo výpoèet provést pomocí $\O(n^2)$ komparátorù
rozmístìných na $\O(n)$ hladinách. Tøídíme v~èase~$N$ a~prostoru
$N^2$.

\medskip
{\>\sl Merge sort}

\centerline{\epsfbox{sortnet.4}}

\medskip
\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je èistì bitonická,
pokud pro nìjaké $x_j\in\{1\dots n-1\} $ platí, ¾e 
$$x_0\leq x_1\leq \dots \leq x_j \geq x_{j+1}\geq\dots \geq x_{n-1}$$
Posloupnost je bitonická, pokud existuje $k\in \{1\dots n-1\}$, pro
které platí, ¾e posloupnost
$x_k,x_{k+1 \bmod n},\dots, x_{k+n-1 \bmod n}$ je èistì bitonická.

\s{Definice: Separátor $S_n$}
Je sí», ve které jsou v¾dy~$i$-tý a~$i+1$-ní (pro $i=0,\dots,
{n/2}-1$) prvek vstupu propojeny komparátorem, minimum bude~$i$-tým,
maximum  $i+1$-ním prvkem výstupu.
\figure{sortnet.3} 
{$(y_i, y_{i+{n/2}}) = CMP(x_i, x_{i+{n/2}})$} {300pt}

\s{Lemma:} Pokud vstup $S_n$ je bitonická posloupnost, pak výstup
$y_0,\dots, y_{n-1}$ je posloupnost,  která splòuje:

(i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou 
bitonické posloupnosti.

(ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_j + {n/2}$

\proof
(i) Nejprve nahlédneme, ¾e Lemma platí je-li vstupem èistì bitonická
posloupnost -- najdeme nejmen¹í~$k$ takové, ¾e $x_k$ a~$x_{k+{n/2}}$
se prohodí. Pokud ho nenajdeme, separátor neudìlá vùbec nic a~obì
tvrzení lemmatu zøejmì tedy platí. Øeknìme, ¾e $x_m$ je maximum
vstupní posloupnosti. Pak~$k$ bude jistì men¹í ne¾~$m$
a~$x_{k+{n/2}}$ bude vìt¹í ne¾~$m$, mezi~$k$ a~$m$ je tedy vstupní
posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí.
Uvìdomíme si, ¾e pro ka¾dé~$i$, $k\leq i\leq {n/2}-1$ se prvky
$x_i$ a~$x_{i+{n/2}}$ prohodí. Úsek mezi~$k$ a~${n/2}-1$ tedy
nahradíme nerostoucí posloupností, první polovina výstupu tedy bude
(dokonce èistì) bitonická. Úsek $k+{n/2}$ a~$n-1$ nahradíme èistì
bitonickou posloupností, která bude neklesající, je-li $m\geq {n/2}$, 
v~opaèném pøípadì je úsek ${n/2}-1$ a¾ $k+{n/2}$
nerostoucí. V~obou pøípadech budou v~posloupnosti maximálnì dva zlomy
a~mezi $x_{n/2}$ a~$x_{n-1}$ bude správná nerovnost na to, aby
posloupnost byla bitonická.

Dostaneme-li na vstup obecnou bitonickou posloupnost, pøedstavíme si,
¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO
doprava), a~zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky
jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické
posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾
$x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì polovièní
posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich
bitoniènosti se nic nezmìní.

(ii) Plyne z~definice separátoru.

\medskip
\centerline{\epsfbox{sortnet.7}}

\medskip
\s{Definice: Bitonická tøídièka $B_n$}  

\centerline{\epsfbox{sortnet.5}}

Separátor má jednu hladinu s~${\O}(N)$ hradly, tøídièka tedy bude
mít 
$\log N$ hladin s~${\O}(N\log N)$ hradly.

Tøídièka se dá pou¾ít ke slévání, mù¾eme tak s~její pomocí sestavit
souèástky $M_n$ mergesortové sítì. Setøídìné posloupnosti 
$x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické 
$x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~takové posloupmosti pomocí
$B_{2n}$ vytvoøíme setøídìnou posloupnost.


\centerline{\epsfbox{sortnet.6}}

Z~bitonických tøídièek tedy mù¾eme postavit mergesortovou sí», která
bude mít
${\O}(\log^2 N)$ hladin a~${\O}(N\log^2 N)$ hradel.

Existuje tøídící algoritmus, kterému staèí ${\O}(\log N)$ hladin,
ale jeho multiplikaèní konstanta je pøíli¹ veliká, tak¾e je v~praxi 
nepou¾itelný.

\bye
