X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=5-sortnet%2F5-sortnet.tex;h=01bf212d80dde126955580347e312e9928246176;hb=c3db7103f942ee420b7d525802bbc6b9b2a98b90;hp=fb047a15613ee212a73dcd36ea875eb15f228334;hpb=ba8385df7e883beadd6dcd1e7b05e42f660376a5;p=ads2.git diff --git a/5-sortnet/5-sortnet.tex b/5-sortnet/5-sortnet.tex index fb047a1..01bf212 100644 --- a/5-sortnet/5-sortnet.tex +++ b/5-sortnet/5-sortnet.tex @@ -16,12 +16,12 @@ p $\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\}$$ +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, +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$. @@ -29,7 +29,7 @@ Odhadneme po 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é -- +klesne v¾dy alespoò o~jedna, pùvodnì bylo nula 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í, @@ -53,7 +53,7 @@ provede maxim 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 +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 @@ -61,16 +61,16 @@ nebo men 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í +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$ +provádí po hranì spádu nejvý¹e jedna) 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 +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$. @@ -88,15 +88,15 @@ $\O(N^2\sqrt M)$. \medskip \h{Tøídìní} -\s{Definice:} Komparátorová sí» je kombinaèní obvod jeho¾ hradla jsou +\s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou komparátory: \centerline{\epsfbox{sortnet.0}} -Výstupy komparátorù se nevìtví. +\>Výstupy komparátorù se nevìtví. \medskip -{\>\sl Bubble sort} +\s{Pøíklad:} {\sl Bubble sort} \twofigures{sortnet.1}{Bubble.1}{143pt}{sortnet.2}{Bubble.2}{143pt} @@ -106,22 +106,22 @@ rozm $N^2$. \medskip -{\>\sl Merge sort} +\s{Pøíklad:} {\>\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 +\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická}, +pokud pro nìjaké $x_j\in\{1, \dots, n-1\} $ platí: +$$x_0\leq x_1\leq \dots \leq x_j \geq x_{j+1}\geq\dots \geq x_{n-1}.$$ +Posloupnost je {\I 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. +\s{Definice:} {\I Separátor $S_n$} +je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu +(pro $i=0,\dots, {n/2}-1$) 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} @@ -129,12 +129,12 @@ maximum $i+1$-n $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. +bitonické posloupnosti, -(ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_j + {n/2}$ +(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á +(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 @@ -161,12 +161,13 @@ posloupnosti tedy budou zrotovan bitoniènosti se nic nezmìní. (ii) Plyne z~definice separátoru. +\qed \medskip \centerline{\epsfbox{sortnet.7}} \medskip -\s{Definice: Bitonická tøídièka $B_n$} +\s{Definice:} {\I Bitonická tøídièka $B_n$} \centerline{\epsfbox{sortnet.5}} @@ -177,7 +178,7 @@ $\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í +$x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~takové posloupnosti pomocí $B_{2n}$ vytvoøíme setøídìnou posloupnost. @@ -187,7 +188,7 @@ Z~bitonick 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, +Existuje tøídicí algoritmus, kterému staèí ${\O}(\log N)$ hladin, ale jeho multiplikaèní konstanta je pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný.