5-sortnet/5-sortnet.tex

   1 \input ../lecnotes.tex
   2 \input epsf
   3 \def\itm{\item{$\bullet$}}
   4
   5 \prednaska{5}{Goldbergùv algoritmus}{(zapsaly T.~Klimo¹ová
   6 a~K.~B\"ohmová)}
   7
   8 \h{Goldbergùv algoritmus -- pokraèování}
   9
  10 Algoritmus upøesníme tak, ¾e místo libovolného vrcholu s~pøebytkem
  11 budeme v¾dy pracovat s~tím, který je na nejvy¹¹í hladinì. Jak doká¾eme
  12 v~následujícím lemmatu, sní¾í se tím poèet potøebných nenasycených
  13 pøevedení. Takto modifikovaný algoritmus budeme znaèit~$G'$.
  14
  15 \s{Lemma $N'$:} V~algoritmu $G'$ je poèet nenasycených pøevedení
  16 $\O(N^3)$.
  17
  18 \proof
  19 Definujme $H$~jako maximální vý¹ku vrcholù s~pøebytkem:
  20  $$H:=\max\{h(v) : v \not= z,s, f^\triangle (v)\geq 0\}.$$
  21 Bìh algoritmu $G'$ rozdìlíme na fáze tak, ¾e fáze skonèí po ka¾dé zmìnì
  22 $H$. Odhadneme poèet nenasycených pøevedení v~jedné fázi: bude jich
  23 nanejvý¹ stejnì jako vrcholù, které se na zaèátku fáze nacházely na
  24 nejvy¹¹í hladinì -- z~jiných vrcholù v~prùbìhu fáze nic nepøevádíme
  25 a~nenasycené pøevedení mù¾eme provést z~ka¾dého vrcholu nejvý¹e
  26 jednou. Poèet nenasycených pøevedení za fázi je $\leq N$.
  27
  28 Odhadneme poèet fází: rozdìlíme fáze podle toho, jestli konèí sní¾ením
  29 nebo zvý¹ením~$H$ a~odhadneme jejich poèty. Maximálnì $2N^2$ fází mù¾e
  30 konèit zvý¹ením~$H$, proto¾e dle lemmatu Z~provedeme nanejvý¹ $2N^2$
  31 zvednutí. Sní¾ením~$H$ mù¾e konèit nanejvý¹ $2N^2$ fází, proto¾e~$H$
  32 klesne v¾dy alespoò o~jedna, pùvodnì bylo nula a~nikdy nemù¾e být záporné --
  33 klesnout tedy nemù¾e víckrát ne¾ vzrùst.
  34
  35 Máme maximálnì $4N^2$ fází o~nejvý¹e~$N$ nenasycených pøevedení,
  36 celkem tedy algoritmus $G'$ provede $\O(N^3)$ nenasycených pøevedení.
  37 \qed
  38
  39 \medskip
  40 Ve skuteènosti je algoritmus je¹tì lep¹í (alespoò pro øídké grafy):
  41
  42 \s{Lemma $N''$:} V~algoritmu $G'$ je poèet nenasycených pøevedení $\O(N^2
  43 \sqrt M)$.
  44
  45 \proof
  46 (Nezkou¹í se.) Algoritmus rozdìlíme na fáze stejnì jako v~dùkazu
  47 pøedchozího lemmatu a~zvolíme pøirozené èíslo~$K$ (jak velké ho
  48 zvolíme, se rozhodneme a¾ na konci dùkazu).
  49 Fáze tentokrát budeme dìlit na drahé, v~nich¾ se provede více ne¾~$K$
  50 nenasycených pøevedení, a~laciné, v~nich¾ se nenasycených pøevedení
  51 provede maximálnì~$K$.
  52
  53 Nyní budeme zkoumat poèty pøevedení v~obou typech fází.
  54 Jak víme z~minulého lemmatu, v¹ech fází je nanejvý¹ $4N^2$, tak¾e
  55 v~laciných se provede nanejvý¹ $N^2K$ nenasycených pøevedení.
  56 Za úèelem zkoumání drahých fází definujeme potenciál:
  57 $$\psi:=\sum_{v\not=z,s; f^\triangle(x)>0}{ p(v)\over K},$$ kde
  58 $p(v):= \vert\{u : h(u) \leq h(v)\}\vert$, èili poèet vrcholù ve stejné
  59 nebo men¹í vý¹ce ne¾~$v$. Víme, ¾e na zaèátku bude $\psi \leq
  60 {N^2/K}$ a~po celou dobu bude $\psi \geq 0$.
  61
  62 Zvednutím vrcholu~$v$ se hodnota $p(v)$ zvý¹í maximálnì o~$N$, u~libovolného
  63 jiného vrcholu~$w$ $p(w)$ klesne nebo se nezmìní, potenciál tedy
  64 vzroste maximálnì o~$N/K$. %Pøedchozích èástí
  65 Pøi sytém pøevedení po hranì z~$u$ do~$v$ (z~minula víme, ¾e se v¾dy
  66 provádí po hranì spádu nejvý¹e jedna) se mohl potenciál zmen¹it o~$p(u)/K$
  67 a~mohl se zvìt¹it o~$p(v)/K$. Zvìt¹í se tedy nanejvý¹ o~$N/K$
  68 Pøi nenasyceném pøevedení z~potenciálu urèitì ubyde o~$p(u)/K$
  69 a~mo¾ná pøibyde $p(v)/K$. Celkovì se tedy sní¾í nanejvý¹
  70 o~${p(u)/K} - {p(v)/K}$, co¾ je $1/K$~poètu prvkù na nejvy¹¹í
  71 hladinì. Z~minulého lemmatu víme, ¾e poèet nenasycených pøevedení
  72 v~jedné fázi je men¹í nebo roven poètu vrcholù na nejvy¹¹í hladinì na
  73 zaèátku fáze. Vzhledem k~tomu, ¾e zkoumáme drahé fáze, v~nich¾ probìhne
  74 více ne¾~$K$ nenasycených pøevedení, vrcholù na nejvy¹¹í hladinì musí
  75 být na zaèátku fáze také více ne¾~$K$, potenciál se tedy sní¾í o~více
  76 ne¾ ${K/K}=1$.
  77
  78 Potenciál $\psi$ tedy pøijme na zaèátku  nanejvý¹ ${N^2/K}$, pøi
  79 zvedání nevzroste o~víc ne¾ $(N/K)2N^2$, pøi sytém pøevádìní
  80 nevzroste o~víc ne¾ $(N/K)NM$, celkem dostáváme $\psi\leq
  81 (N/2)(N+2N^2+NM)=\O({N^2}M/2)$, v~drahých fázích tak mù¾e probìhnout
  82 nanejvý¹ $\O({N^2}M/2)$ nenasycených pøevedení.
  83 Celkem algoritmus vykoná $\O(N^2K+{N^2}M/K)$ nenasycených
  84 pøevedení. Kdy¾ za~$K$ dosadíme $\sqrt M$ dostaneme slíbený poèet
  85 $\O(N^2\sqrt M)$.
  86 \qed
  87
  88 \medskip
  89 \h{Tøídìní}
  90
  91 \s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou
  92 komparátory:
  93
  94 \centerline{\epsfbox{sortnet.0}}
  95
  96 \>Výstupy komparátorù se nevìtví.
  97
  98 \medskip
  99 \s{Pøíklad:} {\sl Bubble sort}
 100
 101 \twofigures{sortnet.1}{Bubble.1}{143pt}{sortnet.2}{Bubble.2}{143pt}
 102
 103 Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble.2).
 104 Takto se nám podaøilo výpoèet provést pomocí $\O(n^2)$ komparátorù
 105 rozmístìných na $\O(n)$ hladinách. Tøídíme v~èase~$N$ a~prostoru
 106 $N^2$.
 107
 108 \medskip
 109 \s{Pøíklad:} {\>\sl Merge sort}
 110
 111 \centerline{\epsfbox{sortnet.4}}
 112
 113 \medskip
 114 \s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická},
 115 pokud pro nìjaké $x_j\in\{1, \dots, n-1\} $ platí:
 116 $$x_0\leq x_1\leq \dots \leq x_j \geq x_{j+1}\geq\dots \geq x_{n-1}.$$
 117 Posloupnost je {\I bitonická}, pokud existuje $k\in \{1\dots n-1\}$, pro
 118 které platí, ¾e posloupnost
 119 $x_k,x_{k+1 \bmod n},\dots, x_{k+n-1 \bmod n}$ je èistì bitonická.
 120
 121 \s{Definice:} {\I Separátor $S_n$}
 122 je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu
 123 (pro $i=0,\dots, {n/2}-1$) propojeny komparátorem, minimum bude~$i$-tým,
 124 maximum  $(i+{n/2})$-ním prvkem výstupu.
 125 \figure{sortnet.3}
 126 {$(y_i, y_{i+{n/2}}) = CMP(x_i, x_{i+{n/2}})$} {300pt}
 127
 128 \s{Lemma:} Pokud vstup $S_n$ je bitonická posloupnost, pak výstup
 129 $y_0,\dots, y_{n-1}$ je posloupnost,  která splòuje:
 130
 131 (i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou
 132 bitonické posloupnosti,
 133
 134 (ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$.
 135
 136 \proof
 137 (i) Nejprve nahlédneme, ¾e lemma platí je-li vstupem èistì bitonická
 138 posloupnost -- najdeme nejmen¹í~$k$ takové, ¾e $x_k$ a~$x_{k+{n/2}}$
 139 se prohodí. Pokud ho nenajdeme, separátor neudìlá vùbec nic a~obì
 140 tvrzení lemmatu zøejmì tedy platí. Øeknìme, ¾e $x_m$ je maximum
 141 vstupní posloupnosti. Pak~$k$ bude jistì men¹í ne¾~$m$
 142 a~$k+{n/2}$ bude vìt¹í ne¾~$m$, mezi~$k$ a~$m$ je tedy vstupní
 143 posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí.
 144 Uvìdomíme si, ¾e pro ka¾dé~$i$, $k\leq i\leq {n/2}-1$ se prvky
 145 $x_i$ a~$x_{i+{n/2}}$ prohodí. Úsek mezi~$k$ a~${n/2}-1$ tedy
 146 nahradíme nerostoucí posloupností, první polovina výstupu tedy bude
 147 (dokonce èistì) bitonická. Úsek $k+{n/2}$ a~$n-1$ nahradíme èistì
 148 bitonickou posloupností, která bude neklesající, je-li $m\geq {n/2}$,
 149 v~opaèném pøípadì je úsek ${n/2}-1$ a¾ $k+{n/2}$
 150 nerostoucí. V~obou pøípadech budou v~posloupnosti maximálnì dva zlomy
 151 a~mezi $x_{n/2}$ a~$x_{n-1}$ bude správná nerovnost na to, aby
 152 posloupnost byla bitonická.
 153
 154 Dostaneme-li na vstup obecnou bitonickou posloupnost, pøedstavíme si,
 155 ¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO
 156 doprava), a~zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky
 157 jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické
 158 posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾
 159 $x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì polovièní
 160 posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich
 161 bitoniènosti se nic nezmìní.
 162
 163 (ii) Plyne z~definice separátoru.
 164 \qed
 165
 166 \medskip
 167 \centerline{\epsfbox{sortnet.7}}
 168
 169 \medskip
 170 \s{Definice:} {\I Bitonická tøídièka $B_n$}
 171
 172 \centerline{\epsfbox{sortnet.5}}
 173
 174 Separátor má jednu hladinu s~${\O}(N)$ hradly, tøídièka tedy bude
 175 mít
 176 $\log N$ hladin s~${\O}(N\log N)$ hradly.
 177
 178 Tøídièka se dá pou¾ít ke slévání, mù¾eme tak s~její pomocí sestavit
 179 souèástky $M_n$ mergesortové sítì. Setøídìné posloupnosti
 180 $x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické
 181 $x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~takové posloupnosti pomocí
 182 $B_{2n}$ vytvoøíme setøídìnou posloupnost.
 183
 184
 185 \centerline{\epsfbox{sortnet.6}}
 186
 187 Z~bitonických tøídièek tedy mù¾eme postavit mergesortovou sí», která
 188 bude mít
 189 ${\O}(\log^2 N)$ hladin a~${\O}(N\log^2 N)$ hradel.
 190
 191 Existuje tøídicí algoritmus, kterému staèí ${\O}(\log N)$ hladin,
 192 ale jeho multiplikaèní konstanta je pøíli¹ veliká, tak¾e je v~praxi
 193 nepou¾itelný.
 194
 195 \bye