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