From a5259f7fafe1f388dcef9de1b736a8707d569050 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Nov 2011 22:03:40 +0100 Subject: [PATCH] Bitonicke trideni, nakonec presunuto do kapitoly o hradlech --- 5-hradla/5-hradla.tex | 163 ++++++++++++++++++++++++ {6-bitonic => 5-hradla}/sortnet.0 | 10 +- {6-bitonic => 5-hradla}/sortnet.1 | 15 ++- {6-bitonic => 5-hradla}/sortnet.2 | 13 +- {6-bitonic => 5-hradla}/sortnet.3 | 49 +++++++- {6-bitonic => 5-hradla}/sortnet.4 | 10 +- {6-bitonic => 5-hradla}/sortnet.5 | 41 ++---- {6-bitonic => 5-hradla}/sortnet.6 | 28 +++-- 5-hradla/sortnet.7 | 86 +++++++++++++ {6-bitonic => 5-hradla}/sortnet.mp | 79 ++++++------ {6-bitonic => 5-hradla}/sortnet.mpx | 189 ++++++++++++++++------------ 6-bitonic/6-bitonic.tex | 130 ------------------- 6-bitonic/Makefile | 3 - 6-bitonic/sortnet.7 | 106 ---------------- 14 files changed, 498 insertions(+), 424 deletions(-) rename {6-bitonic => 5-hradla}/sortnet.0 (87%) rename {6-bitonic => 5-hradla}/sortnet.1 (88%) rename {6-bitonic => 5-hradla}/sortnet.2 (88%) rename {6-bitonic => 5-hradla}/sortnet.3 (67%) rename {6-bitonic => 5-hradla}/sortnet.4 (95%) rename {6-bitonic => 5-hradla}/sortnet.5 (85%) rename {6-bitonic => 5-hradla}/sortnet.6 (93%) create mode 100644 5-hradla/sortnet.7 rename {6-bitonic => 5-hradla}/sortnet.mp (88%) rename {6-bitonic => 5-hradla}/sortnet.mpx (80%) delete mode 100644 6-bitonic/6-bitonic.tex delete mode 100644 6-bitonic/Makefile delete mode 100644 6-bitonic/sortnet.7 diff --git a/5-hradla/5-hradla.tex b/5-hradla/5-hradla.tex index c47a8b3..5e8b695 100644 --- a/5-hradla/5-hradla.tex +++ b/5-hradla/5-hradla.tex @@ -370,4 +370,167 @@ kter hladin kompresorù konstantní hloubky a nakonec jednu sèítaèku hloubky $\Theta(\log n)$. Jistou vadou na kráse ov¹em je, ¾e na to potøebujeme $\Theta(n^2)$ hradel. +\h{Tøídící sítì} + +Je¹tì zkusíme paralelizovat jeden klasický problém, toti¾ tøídìní. +Budeme k~tomu pou¾ívat {\I komparátorovou sí»} -- to je hradlová sí» +slo¾ená z~{\I komparátorù.} + +Jeden komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í +a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva +výstupy: na~jednom z~nich vrací men¹í ze~vstupních hodnot a~na~druhém tu vìt¹í. + +\figure{sortnet.0}{Komparátor}{0.7in} + +V~na¹em formalismu hradlových sítí bychom mohli komparátor reprezentovat dvojicí +hradel: jedno z~nich by poèítalo minimum, druhé maximum. Hodnoty, které tøídíme, +bychom prostì pova¾ovali za prvky abecedy.\foot{Komparátorovou sí» mù¾eme také snadno +pøelo¾it na booleovský obvod. Ka¾dý prvek abecedy reprezentujeme èíslem +o~$b=\lceil\log_2 \Sigma\rceil$ bitech. Zpùsobem podobným paralelní sèítaèce +lze z~booleovských hradel sestrojit komparátor hloubky $\Theta(\log b)$. Zkuste to.} + +Je¹tì se dohodnìme, ¾e výstupy komparátorù se nikdy nebudou vìtvit. Ka¾dý +z~nich pøivedeme na~vstup jiného komparátoru nebo na~výstup sítì. Vìtvení +by nám ostatnì k~nièemu nebylo, proto¾e na~výstupu potøebujeme vydat stejný +poèet hodnot, jako byl na vstupu, a nemáme ¾ádné hradlo, kterým bychom mohli +pøípadných více vìtví slouèit opìt do~jedné. + +\s{Pøíklad:} Zkusíme do øeèi komparátorových sítí pøelo¾it {\I bublinkové tøídìní.} +Z~nìj získáme obvod na~levém obrázku (¹ipky pøedstavují jednotlivé komparátory). +Toto nakreslení ov¹em ponìkud klame -- pokud sí» necháme poèítat, mnohá porovnání +budou probíhat paralelnì. Skuteèný prùbìh výpoètu znázoròuje pravý obrázek, +na~nìm¾ jsme v¹echny operace provádìné souèasnì znázornili vedle sebe. +Ihned vidíme, ¾e paralelní bublinkové tøídìní pracuje v~èase $\Theta(n)$ +a potøebuje kvadratický poèet komparátorù. + +\twofigures{sortnet.1}{Bubblesort}{143pt}{sortnet.2}{Skuteèný prùbìh výpoètu}{143pt} + +Nyní si pøedvedeme rychlej¹í tøídící algoritmus. Pùjdeme na nìj jak se øíká \uv{od lesa}. +Nejdøíve vymyslíme sí», která bude umìt tøídit jenom nìco -- toti¾ bitonické posloupnosti. +Pak z~ní teprve sestrojíme obecné tøidìní. Bez újmy na obecnosti pøitom budeme +pøedpokládat, ¾e ka¾dé dva prvky na vstupu jsou navzájem rùzné a ¾e velikost vstupu +je mocnina dvojky. + +\s{Definice:} Posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická,} pokud ji mù¾eme +rozdìlit na nìjaké pozici $k\in\{0, \dots, n-1\}$ tak, ¾e prvky $x_0,\ldots,x_k$ tvoøí rostoucí +poslopnost, zatímco prvky $x_k,\ldots,x_{n-1}$ tvoøí posloupnost klesající. + +\s{Definice:} Posloupnost $x_0,\dots,x_{n-1}$ je {\I bitonická}, pokud ji lze získat +rotací (cyklickým posunutím) nìjaké èistì bitonické posloupnosti. Jinými slovy pokud existuje +$0\le jJinak øeèeno, separátor rozdìlí bitonickou posloupnost na dvì polovièní +a navíc jsou v¹echny prvky v~první polovinì men¹í ne¾ v¹echny v~té druhé. + +\s{Lemma:} Pro ka¾dé sudé~$n$ existuje separátor~$S_n$ konstantní hloubky, +slo¾ený z~$\Theta(n)$ komparátorù. + +Dùkaz tohoto lemmatu si necháme na konec kapitoly. Nejprve pøedvedeme, k~èemu jsou +separátory dobré. + +\s{Definice:} {\I Bitonická tøídièka øádu~$n$} je komparátorová sí»~$B_n$, +která dostane-li na vstupu bitonickou posloupnost délky~$n$, vydá ji setøídìnou. + +\s{Lemma:} Pro libovolné $n=2^k$ existuje bitonická tøidièka~$B_n$ hloubky $\Theta(\log n)$ +s~$\Theta(n\log n)$ komparátory. + +\proof +Konstrukce bitonické tøidièky je snadná: nejprve separátorem~$S_n$ zadanou bitonickou +posloupnost rozdìlíme na dvì bitonické posloupnosti délky $n/2$, +pak ka¾dou z~nich separátorem~$S_{n/2}$ na dvì délky $n/4$, atd., +a¾ získáme jednoprvkové bitonické posloupnosti ve~správném poøadí. +Celkem pou¾ijeme~$\log n$ hladin slo¾ených z~$n$ separátorù, ka¾dá +hladina má pøitom konstantní hloubku. +\qed + +\figure{sortnet.5}{Bitonická tøidièka $B_n$}{\epsfxsize} + +Bitonické tøidièky nám nyní pomohou ke~konstrukci tøidièky na obecné posloupnosti. +Ta bude zalo¾ena na tøídìní sléváním -- nejprve se tedy musíme nauèit slít dvì +setøídìné posloupnosti do jedné. + +\s{Definice:} {\I Slévaèka øádu~$n$} je komparátorová sí»~$M_n$ s~$2\times n$ +vstupy a~$n$ výstupy, která dostane-li dvì setøídìné posloupnosti délky~$n$, +vydá posloupnost vzniklou jejich slitím. + +\s{Lemma:} Pro $n=2^k$ existuje slévaèka~$M_n$ hloubky $\Theta(\log n)$ +s~$\Theta(n\log n)$ komparátory. + +\proof +Staèí jednu vstupní posloupnost obrátit a \uv{pøilepit} za tu druhou. Tím vznikne +bitonická posloupnost, jí¾ setøídíme bitonickou tøidièkou~$B_{2n}$. +\qed + +\s{Definice:} {\I Tøídící sí» øádu~$n$} je komparátorová sí»~$T_n$ s~$n$~vstupy +a~$n$~výstupy, která pro ka¾dý vstup vydá jeho setøídìnou permutaci. + +\s{Lemma:} Pro $n=2^k$ existuje tøídící sí»~$T_n$ hloubky $\Theta(\log^2 n)$ +slo¾ená z~$\Theta(n\log^2 n)$ komparátorù. + +\proof +Sí» bude tøídit sléváním. Vstup rozdìlí na~$n$ jednoprvkových posloupností. +Ty jsou jistì setøídìné, tak¾e je slévaèkami~$M_1$ mù¾eme slít do dvouprvkových +setøídìných posloupností. Na ty pak aplikujeme slévaèky $M_2$, $M_4$, \dots, $M_{n/2}$, +a¾ v¹echny èásti slijeme do jedné, setøídìné. + +Celkem provedeme $\log n$~krokù slévání, $i$-tý z~nich obsahuje slévaèky $M_{2^i}$ +a ty, jak u¾ víme, mají hloubku $\Theta(i)$. Celkový poèet vrstev tedy èiní +$\Theta(1+2+3+\ldots+\log n) = \Theta(\log^2 n)$. Ka¾dý krok pøitom potøebuje +$\Theta(n\log n)$ komparátorù, co¾ dává celkem $\Theta(n \log^2 n)$ komparátorù. +\qed + +\figure{sortnet.6}{Tøidièka $T_8$}{\epsfxsize} + +\s{Konstrukce separátoru:} Zbývá dokázat, ¾e existují separátory konstantní +hloubky. Vypadají pøekvapivì jednodu¹e: pro $i=0,\ldots,n/2-1$ zapojíme +komparátor se vstupy $x_i$, $x_{i+n/2}$, jeho¾ minimum pøivedeme na~$y_i$ +a maximum na~$y_{i+n/2}$. + +\figure{sortnet.3}{Konstrukce separátoru}{\epsfxsize} + +Proè separátor separuje? Nejprve pøedpokládejme, ¾e vstupem je èistì bitonická +posloupnost. Oznaème~$m$ polohu maxima této posloupnosti; maximum bez újmy +na obecnosti le¾í v~první polovinì (jinak celý dùkaz provedeme \uv{zrcadlovì}). +Oznaème dále~$k$ nejmen¹í index, pro který komparátor mezi $x_k$ a~$x_{k+n/2}$ +hodnoty prohodí, tedy $k=\min \{ i \mid x_i > x_{i+n/2} \}.$ + +Jeliko¾ maximum je jedineèné, musí platit $x_m > x_{m+n/2}$, tak¾e~$k$ +existuje a navíc $0\le k\le m < n/2$. Také platí, ¾e pro ka¾dé~$i$ mezi +$k$ a~$n/2$ u¾ komparátory musí prohazovat, proto¾e od~$x_k$ je posloupnost +a¾ do konce klesající, tak¾e $x_i > x_{i+n/2}$. + +Separátor se tedy chová velice jednodu¹e: první polovina výstupu vznikne +slepením rostoucího úseku $x_0,\ldots,x_{k-1}$ s~klesajícím úsekem $x_{n/2+k},\ldots,x_{n-1}$; +druhou polovinu tvoøí spojení klesajícího úseku $x_{n/2},\ldots,x_{n/2+k-1}$, rostoucího +úseku $x_k,\ldots,x_m$ a klesajícího úseku $x_m,\ldots,x_{n/2-1}$. První polovina +je èistì bitonická a jeliko¾ $x_{n/2-1} > x_{n/2}$, je druhá polovina bitonická +(ov¹em obvykle ne èistì). + +\figure{sortnet.7}{Ilustrace èinnosti separátoru}{\epsfxsize} + +Doplòme, co se stane, pokud vstup není èistì bitonický. Zde vyu¾ijeme +toho, ¾e pokud vstup separátoru zrotujeme o~$p$ pozic, dostaneme o~$p$ pozic +zrotované i obì poloviny výstupu. Podle definice ov¹em pro ka¾dou bitonickou +posloupnost existuje její rotace, která je èistì bitonická, a~pro ní¾, jak +u¾ víme, separátor funguje. Tak¾e pro neèistou bitonickou posloupnost musí +vydat výsledek pouze zrotovaný, co¾ ov¹em na jeho správnosti nic nemìní. +\qed + +Ukázali jsme tedy paralelní tøídící algoritmus o~slo¾itosti $\Theta(\log^2 n)$ +slo¾ený z~$\Theta(n\log^2 n)$ komparátorù. + +Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen $\O(\log n)$ +hladin. Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi +nepou¾itelný. + \bye diff --git a/6-bitonic/sortnet.0 b/5-hradla/sortnet.0 similarity index 87% rename from 6-bitonic/sortnet.0 rename to 5-hradla/sortnet.0 index a2087ec..4566381 100644 --- a/6-bitonic/sortnet.0 +++ b/5-hradla/sortnet.0 @@ -1,13 +1,15 @@ %!PS %%BoundingBox: -1 19 60 100 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 +%%HiResBoundingBox: -0.19925 19.64323 59.7267 99.41167 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 %%Pages: 1 %*Font: cmr10 9.96265 9.96265 61:c08c01 +%%BeginProlog %%EndProlog %%Page: 1 1 - 0 0.3985 dtransform truncate idtransform setlinewidth pop [] 0 setdash - 1 setlinecap 1 setlinejoin 10 setmiterlimit + 0 0 0 setrgbcolor 0 0.3985 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit newpath 0 39.68497 moveto 19.84248 39.68497 lineto 39.68497 39.68497 lineto diff --git a/6-bitonic/sortnet.1 b/5-hradla/sortnet.1 similarity index 88% rename from 6-bitonic/sortnet.1 rename to 5-hradla/sortnet.1 index 5ec51d9..4c20174 100644 --- a/6-bitonic/sortnet.1 +++ b/5-hradla/sortnet.1 @@ -1,13 +1,16 @@ %!PS %%BoundingBox: -15 -1 128 166 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 +%%HiResBoundingBox: -14.5219 -0.19925 127.90752 165.32562 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 %%Pages: 1 -%*Font: cmr10 9.96265 9.96265 31:f80000000000000001 +%*Font: cmr10 9.96265 9.96265 31:f80000000000c08c01 +%%BeginProlog %%EndProlog %%Page: 1 1 - 0.3985 0 dtransform exch truncate exch idtransform pop setlinewidth - [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit + 0 0 0 setrgbcolor 0.3985 + 0 dtransform exch truncate exch idtransform pop setlinewidth [] 0 setdash + 1 setlinecap 1 setlinejoin 10 setmiterlimit newpath 0 0 moveto 0 155.90523 lineto stroke newpath 28.3464 0 moveto @@ -90,7 +93,7 @@ newpath 110.61395 98.06433 moveto closepath gsave fill grestore stroke 0 0.69739 dtransform truncate idtransform setlinewidth pop - [0 3.49998 ] 1.74998 setdash + [0 2.5 ] 1.25 setdash newpath -14.1732 21.25981 moveto 127.55882 21.25981 lineto stroke newpath -14.1732 49.60622 moveto diff --git a/6-bitonic/sortnet.2 b/5-hradla/sortnet.2 similarity index 88% rename from 6-bitonic/sortnet.2 rename to 5-hradla/sortnet.2 index 25656e7..adfbce1 100644 --- a/6-bitonic/sortnet.2 +++ b/5-hradla/sortnet.2 @@ -1,13 +1,16 @@ %!PS %%BoundingBox: -6 42 119 166 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 +%%HiResBoundingBox: -5.1197 42.32036 118.50531 165.32562 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 %%Pages: 1 -%*Font: cmr10 9.96265 9.96265 31:f80000000000000001 +%*Font: cmr10 9.96265 9.96265 31:f80000000000c08c01 +%%BeginProlog %%EndProlog %%Page: 1 1 - 0.3985 0 dtransform exch truncate exch idtransform pop setlinewidth - [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit + 0 0 0 setrgbcolor 0.3985 + 0 dtransform exch truncate exch idtransform pop setlinewidth [] 0 setdash + 1 setlinecap 1 setlinejoin 10 setmiterlimit newpath 0 42.5196 moveto 0 155.90523 lineto stroke newpath 28.3464 42.5196 moveto diff --git a/6-bitonic/sortnet.3 b/5-hradla/sortnet.3 similarity index 67% rename from 6-bitonic/sortnet.3 rename to 5-hradla/sortnet.3 index e30c8cd..a47c504 100644 --- a/6-bitonic/sortnet.3 +++ b/5-hradla/sortnet.3 @@ -1,16 +1,19 @@ %!PS -%%BoundingBox: -6 -1 266 95 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 +%%BoundingBox: -6 -12 266 95 +%%HiResBoundingBox: -5.08165 -11.1732 265.77504 94.65334 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 %%Pages: 1 -%*Font: cmmi10 9.96265 9.96265 3a:8000000000000002 +%*Font: cmmi10 9.96265 9.96265 3a:8000000000000003 %*Font: cmr7 6.97385 6.97385 30:e %*Font: cmmi7 6.97385 6.97385 6e:8 %*Font: cmsy7 6.97385 6.97385 00:8 +%%BeginProlog %%EndProlog %%Page: 1 1 - 0.3985 0 dtransform exch truncate exch idtransform pop setlinewidth - [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit + 0 0 0 setrgbcolor 0.3985 + 0 dtransform exch truncate exch idtransform pop setlinewidth [] 0 setdash + 1 setlinecap 1 setlinejoin 10 setmiterlimit newpath 0 0 moveto 0 85.03922 lineto stroke newpath 28.3464 0 moveto @@ -101,5 +104,39 @@ gsave fill grestore stroke (\000) cmsy7 6.97385 fshow 261.30563 88.86943 moveto (1) cmr7 6.97385 fshow +-4.67696 -9.23601 moveto +(y) cmmi10 9.96265 fshow +0.20755 -10.73041 moveto +(0) cmr7 6.97385 fshow +23.66945 -9.23601 moveto +(y) cmmi10 9.96265 fshow +28.55396 -10.73041 moveto +(1) cmr7 6.97385 fshow +52.01585 -9.23601 moveto +(y) cmmi10 9.96265 fshow +56.90036 -10.73041 moveto +(2) cmr7 6.97385 fshow +135.09032 -11.1732 moveto +(:) cmmi10 9.96265 fshow +139.51811 -11.1732 moveto +(:) cmmi10 9.96265 fshow +143.94592 -11.1732 moveto +(:) cmmi10 9.96265 fshow +216.51854 -8.84859 moveto +(y) cmmi10 9.96265 fshow +221.40305 -10.34299 moveto +(n) cmmi7 6.97385 fshow +226.32794 -10.34299 moveto +(\000) cmsy7 6.97385 fshow +232.55453 -10.34299 moveto +(2) cmr7 6.97385 fshow +244.86494 -8.84859 moveto +(y) cmmi10 9.96265 fshow +249.74945 -10.34299 moveto +(n) cmmi7 6.97385 fshow +254.67435 -10.34299 moveto +(\000) cmsy7 6.97385 fshow +260.90094 -10.34299 moveto +(1) cmr7 6.97385 fshow showpage %%EOF diff --git a/6-bitonic/sortnet.4 b/5-hradla/sortnet.4 similarity index 95% rename from 6-bitonic/sortnet.4 rename to 5-hradla/sortnet.4 index e6ad3e1..7fda675 100644 --- a/6-bitonic/sortnet.4 +++ b/5-hradla/sortnet.4 @@ -1,12 +1,14 @@ %!PS %%BoundingBox: -1 -1 213 100 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 +%%HiResBoundingBox: -0.19925 -0.19925 212.79729 99.41167 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 %%Pages: 1 +%%BeginProlog %%EndProlog %%Page: 1 1 - 0 0.3985 dtransform truncate idtransform setlinewidth pop [] 0 setdash - 1 setlinejoin 10 setmiterlimit + 0 0 0 setrgbcolor 0 0.3985 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinejoin 10 setmiterlimit newpath 0 14.1732 moveto 212.59804 14.1732 lineto 212.59804 28.3464 lineto diff --git a/6-bitonic/sortnet.5 b/5-hradla/sortnet.5 similarity index 85% rename from 6-bitonic/sortnet.5 rename to 5-hradla/sortnet.5 index 6877616..8e9dd3b 100644 --- a/6-bitonic/sortnet.5 +++ b/5-hradla/sortnet.5 @@ -1,17 +1,18 @@ %!PS -%%BoundingBox: -1 -5 213 114 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 +%%BoundingBox: -1 13 213 114 +%%HiResBoundingBox: -0.19925 13.97395 212.79729 113.58487 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 %%Pages: 1 -%*Font: cmr10 9.96265 9.96265 10:98000000000020000000585328 -%*Font: cmmi10 9.96265 9.96265 42:800040000008 +%*Font: cmmi10 9.96265 9.96265 3a:8000004000000803 %*Font: cmmi7 6.97385 6.97385 6e:8 %*Font: cmmi5 4.98132 4.98132 6e:8 %*Font: cmr5 4.98132 4.98132 32:a +%%BeginProlog %%EndProlog %%Page: 1 1 - 0 0.3985 dtransform truncate idtransform setlinewidth pop [] 0 setdash - 1 setlinejoin 10 setmiterlimit + 0 0 0 setrgbcolor 0 0.3985 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinejoin 10 setmiterlimit newpath 0 99.21242 moveto 212.59804 99.21242 lineto 212.59804 85.03922 lineto @@ -202,31 +203,5 @@ newpath 191.94989 32.9609 moveto 196.33748 32.9609 lineto stroke 192.44868 28.81691 moveto (4) cmr5 4.98132 fshow -59.69281 -2.71205 moveto -(Bitonic) cmr10 9.96265 fshow -90.82611 -2.71205 moveto -(k\023) cmr10 9.96265 fshow -96.08421 -2.71205 moveto -(a) cmr10 9.96265 fshow -104.38641 -2.71205 moveto -(t) cmr10 9.96265 fshow -107.72112 -2.71205 moveto -(\024) cmr10 9.96265 fshow -108.2608 -2.71205 moveto -(r) cmr10 9.96265 fshow -111.05591 -2.71205 moveto -(\023) cmr10 9.96265 fshow -112.16281 -2.71205 moveto -(\020di) cmr10 9.96265 fshow -122.9557 -2.71205 moveto -(\024) cmr10 9.96265 fshow -123.23251 -2.71205 moveto -(ck) cmr10 9.96265 fshow -132.36491 -2.71205 moveto -(a) cmr10 9.96265 fshow -140.66711 -2.71205 moveto -(B) cmmi10 9.96265 fshow -148.2239 -4.20645 moveto -(n) cmmi7 6.97385 fshow showpage %%EOF diff --git a/6-bitonic/sortnet.6 b/5-hradla/sortnet.6 similarity index 93% rename from 6-bitonic/sortnet.6 rename to 5-hradla/sortnet.6 index 61b14d5..2372c9e 100644 --- a/6-bitonic/sortnet.6 +++ b/5-hradla/sortnet.6 @@ -1,14 +1,16 @@ %!PS %%BoundingBox: -1 -1 213 100 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 +%%HiResBoundingBox: -0.19925 -0.19925 212.79729 99.41167 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 %%Pages: 1 -%*Font: cmmi10 9.96265 9.96265 4d:8 -%*Font: cmr7 6.97385 6.97385 32:a2 +%*Font: cmmi10 9.96265 9.96265 3a:8000104000000803 +%*Font: cmr7 6.97385 6.97385 30:e8 +%%BeginProlog %%EndProlog %%Page: 1 1 - 0 0.3985 dtransform truncate idtransform setlinewidth pop [] 0 setdash - 1 setlinejoin 10 setmiterlimit + 0 0 0 setrgbcolor 0 0.3985 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinejoin 10 setmiterlimit newpath 0 14.1732 moveto 212.59804 14.1732 lineto 212.59804 28.3464 lineto @@ -183,30 +185,30 @@ gsave fill grestore stroke 99.23177 18.66762 moveto (M) cmmi10 9.96265 fshow 108.89697 17.17322 moveto -(8) cmr7 6.97385 fshow +(4) cmr7 6.97385 fshow 42.53896 47.01402 moveto (M) cmmi10 9.96265 fshow 52.20416 45.51962 moveto -(4) cmr7 6.97385 fshow +(2) cmr7 6.97385 fshow 155.92458 47.01402 moveto (M) cmmi10 9.96265 fshow 165.58978 45.51962 moveto -(4) cmr7 6.97385 fshow +(2) cmr7 6.97385 fshow 14.19255 75.36043 moveto (M) cmmi10 9.96265 fshow 23.85776 73.86603 moveto -(2) cmr7 6.97385 fshow +(1) cmr7 6.97385 fshow 70.88536 75.36043 moveto (M) cmmi10 9.96265 fshow 80.55057 73.86603 moveto -(2) cmr7 6.97385 fshow +(1) cmr7 6.97385 fshow 127.57817 75.36043 moveto (M) cmmi10 9.96265 fshow 137.24338 73.86603 moveto -(2) cmr7 6.97385 fshow +(1) cmr7 6.97385 fshow 184.27098 75.36043 moveto (M) cmmi10 9.96265 fshow 193.93619 73.86603 moveto -(2) cmr7 6.97385 fshow +(1) cmr7 6.97385 fshow showpage %%EOF diff --git a/5-hradla/sortnet.7 b/5-hradla/sortnet.7 new file mode 100644 index 0000000..97baca1 --- /dev/null +++ b/5-hradla/sortnet.7 @@ -0,0 +1,86 @@ +%!PS +%%BoundingBox: 17 -1 182 110 +%%HiResBoundingBox: 17.35184 -0.19925 181.5723 109.33292 +%%Creator: MetaPost 1.208 +%%CreationDate: 2011.11.19:2203 +%%Pages: 1 +%*Font: cmr10 9.96265 9.96265 2b:87e00000000003023004 +%*Font: cmmi10 9.96265 9.96265 3a:8000104000005803 +%*Font: cmr7 6.97385 6.97385 30:e8 +%*Font: cmmi7 6.97385 6.97385 6e:8 +%%BeginProlog +%%EndProlog +%%Page: 1 1 + 0 0 0 setrgbcolor 0 0.3985 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit +newpath 19.84248 99.21242 moveto +19.84248 19.84248 lineto +178.58235 19.84248 lineto +178.58235 99.21242 lineto stroke +newpath 19.84248 39.68497 moveto +69.4487 99.21242 lineto +178.58235 59.52745 lineto stroke + 0.3985 0 dtransform exch truncate exch idtransform pop setlinewidth + [3 3 ] 0 setdash +newpath 69.4487 19.84248 moveto +69.4487 99.21242 lineto stroke +newpath 99.21242 0 moveto +99.21242 109.13367 lineto stroke +newpath 50.9906 77.06291 moveto +50.9906 19.84248 lineto stroke +newpath 130.36052 77.06291 moveto +130.36052 19.84248 lineto stroke + 0 0.79701 dtransform truncate idtransform setlinewidth pop + [0 2.5 ] 1.25 setdash +newpath 130.36052 77.06291 moveto +148.81863 99.21242 lineto stroke +newpath 148.81863 99.21242 moveto +178.58235 88.38937 lineto stroke +newpath 50.9906 77.06291 moveto +99.21242 59.52745 lineto stroke +newpath 52.485 77.06291 moveto +52.485 77.45924 52.32756 77.83936 52.0473 78.11961 curveto +51.76704 78.39987 51.38693 78.55731 50.9906 78.55731 curveto +50.59427 78.55731 50.21416 78.39987 49.9339 78.11961 curveto +49.65364 77.83936 49.4962 77.45924 49.4962 77.06291 curveto +49.4962 76.66658 49.65364 76.28647 49.9339 76.00621 curveto +50.21416 75.72595 50.59427 75.56851 50.9906 75.56851 curveto +51.38693 75.56851 51.76704 75.72595 52.0473 76.00621 curveto +52.32756 76.28647 52.485 76.66658 52.485 77.06291 curveto closepath fill +newpath 131.85492 77.06291 moveto +131.85492 77.45924 131.69748 77.83936 131.41722 78.11961 curveto +131.13696 78.39987 130.75685 78.55731 130.36052 78.55731 curveto +129.96419 78.55731 129.58408 78.39987 129.30382 78.11961 curveto +129.02356 77.83936 128.86612 77.45924 128.86612 77.06291 curveto +128.86612 76.66658 129.02356 76.28647 129.30382 76.00621 curveto +129.58408 75.72595 129.96419 75.56851 130.36052 75.56851 curveto +130.75685 75.56851 131.13696 75.72595 131.41722 76.00621 curveto +131.69748 76.28647 131.85492 76.66658 131.85492 77.06291 curveto closepath fill +17.35184 8.37428 moveto +(0) cmr10 9.96265 fshow +48.2405 8.37428 moveto +(k) cmmi10 9.96265 fshow +65.07504 8.37428 moveto +(m) cmmi10 9.96265 fshow +90.99202 13.1969 moveto +(n) cmmi7 6.97385 fshow + 0 0.3985 dtransform truncate idtransform setlinewidth pop [] 0 setdash + 0 setlinecap +newpath 90.99202 11.765 moveto +95.91693 11.765 lineto stroke +91.46883 5.83879 moveto +(2) cmr7 6.97385 fshow +117.86421 8.37428 moveto +(k) cmmi10 9.96265 fshow +125.57831 8.37428 moveto +(+) cmr10 9.96265 fshow +136.7364 12.29689 moveto +(n) cmmi7 6.97385 fshow +newpath 136.7364 10.86499 moveto +141.66132 10.86499 lineto stroke +137.21321 4.93878 moveto +(2) cmr7 6.97385 fshow +175.59239 8.37428 moveto +(n) cmmi10 9.96265 fshow +showpage +%%EOF diff --git a/6-bitonic/sortnet.mp b/5-hradla/sortnet.mp similarity index 88% rename from 6-bitonic/sortnet.mp rename to 5-hradla/sortnet.mp index 081f9f4..aebdcd1 100644 --- a/6-bitonic/sortnet.mp +++ b/5-hradla/sortnet.mp @@ -128,9 +128,9 @@ drawarrow(z38--z48); drawarrow(z47--z57); pickup pencircle scaled 0.7pt; -draw(z1015--z1615) dashed withdots scaled 0.7; -draw(z1035--z1635) dashed withdots scaled 0.7; -draw(z1065--z1665) dashed withdots scaled 0.7; +draw(z1015--z1615) dashed withdots scaled 0.5; +draw(z1035--z1635) dashed withdots scaled 0.5; +draw(z1065--z1665) dashed withdots scaled 0.5; label.top(btex x1 etex,z111); label.top(btex x2 etex,z211); @@ -291,6 +291,13 @@ label.top(btex \dots etex,z66); label.top(btex $x_{n-2}$ etex,z96); label.top(btex $x_{n-1}$ etex,z106); +label.top(btex $y_0$ etex,z16 shifted (0,-7v)); +label.top(btex $y_1$ etex,z26 shifted (0,-7v)); +label.top(btex $y_2$ etex,z36 shifted (0,-7v)); +label.top(btex \dots etex,z66 shifted (0,-7v)); +label.top(btex $y_{n-2}$ etex,z96 shifted (0,-7v)); +label.top(btex $y_{n-1}$ etex,z106 shifted (0,-7v)); + endfig; @@ -497,7 +504,6 @@ label.bot(btex $S_{n\over 4}$ etex,z515); label.bot(btex $S_{n\over 4}$ etex,z555); label.bot(btex $S_{n\over 4}$ etex,z595); label.bot(btex $S_{n\over 4}$ etex,z513); -label.rt(btex Bitonick\'a t\v r\'\i di\v cka $B_{n}$ etex,z9); endfig; @@ -599,13 +605,13 @@ drawarrow(z335--z235); drawarrow(z311--z211); drawarrow(z175--z1075); -label.top(btex $M_8$ etex,z175); -label.top(btex $M_4$ etex,z335); -label.top(btex $M_4$ etex,z311); -label.top(btex $M_2$ etex,z515); -label.top(btex $M_2$ etex,z555); -label.top(btex $M_2$ etex,z595); -label.top(btex $M_2$ etex,z513); +label.top(btex $M_4$ etex,z175); +label.top(btex $M_2$ etex,z335); +label.top(btex $M_2$ etex,z311); +label.top(btex $M_1$ etex,z515); +label.top(btex $M_1$ etex,z555); +label.top(btex $M_1$ etex,z595); +label.top(btex $M_1$ etex,z513); endfig; @@ -613,18 +619,18 @@ endfig; beginfig(7); v:=u*7mm; -z12=(1v,2v); -z13=(1v,3v); -z16=(1v,6v); -z356=(3.5v,6v); -z40=(5v,1v); -z42=(5v,2v); -z47=(5v,6.5v); -z72=(9v,2v); -z74=(9v,4v); -z76=(9v,6v); - -z100=(0.5v,0.5v); +z12=(1v,1v); +z13=(1v,2v); +z16=(1v,5v); +z356=(3.5v,5v); +z40=(5v,0v); +z42=(5v,1v); +z47=(5v,5.5v); +z72=(9v,1v); +z74=(9v,3v); +z76=(9v,5v); + +z100=(0.5v,-0.5v); z101=(1.5v,0.5v); z0=whatever[z13,z356]; @@ -639,37 +645,36 @@ z5=whatever[z72,z76]; z5=whatever[z4,z1+4v*right]; z6=whatever[z40,z47]; z6=z74+4v*left; +z7=whatever[z12,z72]; +z7=z356+whatever*down; +z8=z2 + whatever*right; +z8=z356+whatever*down; pickup pencircle scaled 0.4pt; draw(z16--z12--z72--z76); draw(z13--z356--z74); +draw(z7--z356) dashed evenly; draw(z40--z47) dashed evenly; -draw(z1--z4) dashed withdots scaled 0.7; -draw(z4--z5) dashed withdots scaled 0.7; -draw(z0--z6) dashed withdots scaled 0.7; draw(z0--z2) dashed evenly; draw(z1--z3) dashed evenly; -draw(z100--z101) dashed withdots scaled 0.7; +pickup pencircle scaled 0.8pt; +draw(z1--z4) dashed withdots scaled 0.5; +draw(z4--z5) dashed withdots scaled 0.5; +draw(z0--z6) dashed withdots scaled 0.5; pickup pencircle scaled 3pt; drawdot(z0); drawdot(z1); label.bot(btex \strut 0 etex,z12); -label.bot(btex $k$ etex,z2); -label.llft(btex \strut ${n\over 2} - 1$ etex,z42); +label.bot(btex \strut $k$ etex,z2); +label.bot(btex \strut $m$ etex,z8); +label.llft(btex \strut ${n\over 2}$ etex,z42); label.bot(btex \strut $k+{n\over 2}$ etex,z3); -label.bot(btex \strut $n-1$ etex,z72); -label.rt(btex posloupnost prohozen\'a separ\'atorem etex,z101); +label.bot(btex \strut $n$ etex,z72); endfig; - - - - - - end; diff --git a/6-bitonic/sortnet.mpx b/5-hradla/sortnet.mpx similarity index 80% rename from 6-bitonic/sortnet.mpx rename to 5-hradla/sortnet.mpx index 9814d6d..58f8d19 100644 --- a/6-bitonic/sortnet.mpx +++ b/5-hradla/sortnet.mpx @@ -1,4 +1,4 @@ -% Written by DVItoMP, Version 0.64/color (Web2C 7.5.4) +% Written by metapost version 1.208 begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; string _n[]; vardef _s(expr _t,_f,_m,_x,_y)(text _c)= @@ -224,6 +224,86 @@ string _n[]; vardef _s(expr _t,_f,_m,_x,_y)(text _c)= addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; _n1="cmmi10"; +_s("y",_n1,1.00000,0.0000,0.0000,); +_n2="cmr7"; +_s("0",_n2,1.00000,4.8845,-1.4944,); +setbounds _p to (0,-1.9372)--(9.3539,-1.9372)-- + (9.3539,4.2895)--(0,4.2895)--cycle; +_p endgroup +mpxbreak +begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; +string _n[]; +vardef _s(expr _t,_f,_m,_x,_y)(text _c)= + addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; +_n1="cmmi10"; +_s("y",_n1,1.00000,0.0000,0.0000,); +_n2="cmr7"; +_s("1",_n2,1.00000,4.8845,-1.4944,); +setbounds _p to (0,-1.9372)--(9.3539,-1.9372)-- + (9.3539,4.2895)--(0,4.2895)--cycle; +_p endgroup +mpxbreak +begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; +string _n[]; +vardef _s(expr _t,_f,_m,_x,_y)(text _c)= + addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; +_n1="cmmi10"; +_s("y",_n1,1.00000,0.0000,0.0000,); +_n2="cmr7"; +_s("2",_n2,1.00000,4.8845,-1.4944,); +setbounds _p to (0,-1.9372)--(9.3539,-1.9372)-- + (9.3539,4.2895)--(0,4.2895)--cycle; +_p endgroup +mpxbreak +begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; +string _n[]; +vardef _s(expr _t,_f,_m,_x,_y)(text _c)= + addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; +_n1="cmmi10"; +_s(":",_n1,1.00000,0.0000,0.0000,); +_s(":",_n1,1.00000,4.4278,0.0000,); +_s(":",_n1,1.00000,8.8556,0.0000,); +setbounds _p to (0,0.0000)--(13.2834,0.0000)-- + (13.2834,1.0516)--(0,1.0516)--cycle; +_p endgroup +mpxbreak +begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; +string _n[]; +vardef _s(expr _t,_f,_m,_x,_y)(text _c)= + addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; +_n1="cmmi10"; +_s("y",_n1,1.00000,0.0000,0.0000,); +_n3="cmmi7"; +_s("n",_n3,1.00000,4.8845,-1.4944,); +_n4="cmsy7"; +_s(char0,_n4,1.00000,9.8094,-1.4944,); +_n2="cmr7"; +_s("2",_n2,1.00000,16.0360,-1.4944,); +setbounds _p to (0,-2.3246)--(20.5054,-2.3246)-- + (20.5054,4.2895)--(0,4.2895)--cycle; +_p endgroup +mpxbreak +begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; +string _n[]; +vardef _s(expr _t,_f,_m,_x,_y)(text _c)= + addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; +_n1="cmmi10"; +_s("y",_n1,1.00000,0.0000,0.0000,); +_n3="cmmi7"; +_s("n",_n3,1.00000,4.8845,-1.4944,); +_n4="cmsy7"; +_s(char0,_n4,1.00000,9.8094,-1.4944,); +_n2="cmr7"; +_s("1",_n2,1.00000,16.0360,-1.4944,); +setbounds _p to (0,-2.3246)--(20.5054,-2.3246)-- + (20.5054,4.2895)--(0,4.2895)--cycle; +_p endgroup +mpxbreak +begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; +string _n[]; +vardef _s(expr _t,_f,_m,_x,_y)(text _c)= + addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; +_n1="cmmi10"; _s("n",_n1,1.00000,0.0000,0.0000,); setbounds _p to (0,0.0000)--(5.9799,0.0000)-- (5.9799,4.2895)--(0,4.2895)--cycle; @@ -251,8 +331,7 @@ _n5="cmmi5"; _s("n",_n5,1.00000,7.3045,1.1829,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); _n6="cmr5"; _s("2",_n6,1.00000,7.8033,-3.8949,); setbounds _p to (0,-3.8949)--(13.3857,-3.8949)-- @@ -269,8 +348,7 @@ _n5="cmmi5"; _s("n",_n5,1.00000,7.3045,1.1829,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); _n6="cmr5"; _s("2",_n6,1.00000,7.8033,-3.8949,); setbounds _p to (0,-3.8949)--(13.3857,-3.8949)-- @@ -287,8 +365,7 @@ _n5="cmmi5"; _s("n",_n5,1.00000,7.3045,1.1829,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); _n6="cmr5"; _s("4",_n6,1.00000,7.8033,-3.8949,); setbounds _p to (0,-3.8949)--(13.3857,-3.8949)-- @@ -305,8 +382,7 @@ _n5="cmmi5"; _s("n",_n5,1.00000,7.3045,1.1829,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); _n6="cmr5"; _s("4",_n6,1.00000,7.8033,-3.8949,); setbounds _p to (0,-3.8949)--(13.3857,-3.8949)-- @@ -323,8 +399,7 @@ _n5="cmmi5"; _s("n",_n5,1.00000,7.3045,1.1829,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); _n6="cmr5"; _s("4",_n6,1.00000,7.8033,-3.8949,); setbounds _p to (0,-3.8949)--(13.3857,-3.8949)-- @@ -341,8 +416,7 @@ _n5="cmmi5"; _s("n",_n5,1.00000,7.3045,1.1829,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((7.3045,0.2491)..(11.6921,0.2491), 0.3985,); _n6="cmr5"; _s("4",_n6,1.00000,7.8033,-3.8949,); setbounds _p to (0,-3.8949)--(13.3857,-3.8949)-- @@ -351,36 +425,12 @@ _p endgroup mpxbreak begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; string _n[]; -vardef _s(expr _t,_f,_m,_x,_y)(text _c)= - addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; -_n0="cmr10"; -_s("Bitonic",_n0,1.00000,0.0000,0.0000,); -_s("k"&char19,_n0,1.00000,31.1333,0.0000,); -_s("a",_n0,1.00000,36.3914,0.0000,); -_s("t",_n0,1.00000,44.6936,0.0000,); -_s(char20,_n0,1.00000,48.0283,0.0000,); -_s("r",_n0,1.00000,48.5680,0.0000,); -_s(char19,_n0,1.00000,51.3631,0.0000,); -_s(char16&"di",_n0,1.00000,52.4700,0.0000,); -_s(char20,_n0,1.00000,63.2629,0.0000,); -_s("ck",_n0,1.00000,63.5397,0.0000,); -_s("a",_n0,1.00000,72.6721,0.0000,); -_n1="cmmi10"; -_s("B",_n1,1.00000,80.9743,0.0000,); -_n3="cmmi7"; -_s("n",_n3,1.00000,88.5311,-1.4944,); -setbounds _p to (0,-1.4944)--(93.9541,-1.4944)-- - (93.9541,6.9185)--(0,6.9185)--cycle; -_p endgroup -mpxbreak -begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; -string _n[]; vardef _s(expr _t,_f,_m,_x,_y)(text _c)= addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; _n1="cmmi10"; _s("M",_n1,1.00000,0.0000,0.0000,); _n2="cmr7"; -_s("8",_n2,1.00000,9.6652,-1.4944,); +_s("4",_n2,1.00000,9.6652,-1.4944,); setbounds _p to (0,-1.4944)--(14.1345,-1.4944)-- (14.1345,6.8078)--(0,6.8078)--cycle; _p endgroup @@ -392,7 +442,7 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= _n1="cmmi10"; _s("M",_n1,1.00000,0.0000,0.0000,); _n2="cmr7"; -_s("4",_n2,1.00000,9.6652,-1.4944,); +_s("2",_n2,1.00000,9.6652,-1.4944,); setbounds _p to (0,-1.4944)--(14.1345,-1.4944)-- (14.1345,6.8078)--(0,6.8078)--cycle; _p endgroup @@ -404,7 +454,7 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= _n1="cmmi10"; _s("M",_n1,1.00000,0.0000,0.0000,); _n2="cmr7"; -_s("4",_n2,1.00000,9.6652,-1.4944,); +_s("2",_n2,1.00000,9.6652,-1.4944,); setbounds _p to (0,-1.4944)--(14.1345,-1.4944)-- (14.1345,6.8078)--(0,6.8078)--cycle; _p endgroup @@ -416,7 +466,7 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= _n1="cmmi10"; _s("M",_n1,1.00000,0.0000,0.0000,); _n2="cmr7"; -_s("2",_n2,1.00000,9.6652,-1.4944,); +_s("1",_n2,1.00000,9.6652,-1.4944,); setbounds _p to (0,-1.4944)--(14.1345,-1.4944)-- (14.1345,6.8078)--(0,6.8078)--cycle; _p endgroup @@ -428,7 +478,7 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= _n1="cmmi10"; _s("M",_n1,1.00000,0.0000,0.0000,); _n2="cmr7"; -_s("2",_n2,1.00000,9.6652,-1.4944,); +_s("1",_n2,1.00000,9.6652,-1.4944,); setbounds _p to (0,-1.4944)--(14.1345,-1.4944)-- (14.1345,6.8078)--(0,6.8078)--cycle; _p endgroup @@ -440,7 +490,7 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= _n1="cmmi10"; _s("M",_n1,1.00000,0.0000,0.0000,); _n2="cmr7"; -_s("2",_n2,1.00000,9.6652,-1.4944,); +_s("1",_n2,1.00000,9.6652,-1.4944,); setbounds _p to (0,-1.4944)--(14.1345,-1.4944)-- (14.1345,6.8078)--(0,6.8078)--cycle; _p endgroup @@ -452,7 +502,7 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= _n1="cmmi10"; _s("M",_n1,1.00000,0.0000,0.0000,); _n2="cmr7"; -_s("2",_n2,1.00000,9.6652,-1.4944,); +_s("1",_n2,1.00000,9.6652,-1.4944,); setbounds _p to (0,-1.4944)--(14.1345,-1.4944)-- (14.1345,6.8078)--(0,6.8078)--cycle; _p endgroup @@ -473,8 +523,18 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; _n1="cmmi10"; _s("k",_n1,1.00000,0.0000,0.0000,); -setbounds _p to (0,0.0000)--(5.5002,0.0000)-- - (5.5002,6.9185)--(0,6.9185)--cycle; +setbounds _p to (0,-3.4869)--(5.5002,-3.4869)-- + (5.5002,8.4682)--(0,8.4682)--cycle; +_p endgroup +mpxbreak +begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; +string _n[]; +vardef _s(expr _t,_f,_m,_x,_y)(text _c)= + addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; +_n1="cmmi10"; +_s("m",_n1,1.00000,0.0000,0.0000,); +setbounds _p to (0,-3.4869)--(8.7473,-3.4869)-- + (8.7473,8.4682)--(0,8.4682)--cycle; _p endgroup mpxbreak begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; @@ -485,16 +545,11 @@ _n3="cmmi7"; _s("n",_n3,1.00000,1.1955,3.9226,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((1.1955,2.4907)..(6.1204,2.4907), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((1.1955,2.4907)..(6.1204,2.4907), 0.3985,); _n2="cmr7"; _s("2",_n2,1.00000,1.6723,-3.4355,); -_n7="cmsy10"; -_s(char0,_n7,1.00000,9.5298,0.0000,); -_n0="cmr10"; -_s("1",_n0,1.00000,19.4924,0.0000,); -setbounds _p to (0,-3.4869)--(24.4737,-3.4869)-- - (24.4737,8.4682)--(0,8.4682)--cycle; +setbounds _p to (0,-3.4869)--(7.3159,-3.4869)-- + (7.3159,8.4682)--(0,8.4682)--cycle; _p endgroup mpxbreak begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; @@ -509,8 +564,7 @@ _n3="cmmi7"; _s("n",_n3,1.00000,18.8722,3.9226,); interim linecap:=0; vardef _r(expr _a,_w)(text _t) = - addto _p doublepath _a withpen pencircle scaled _w _t enddef; -_r((18.8722,2.4907)..(23.7971,2.4907), 0.3985,); + addto _p doublepath _a withpen pencircle scaled _w _t enddef;_r((18.8722,2.4907)..(23.7971,2.4907), 0.3985,); _n2="cmr7"; _s("2",_n2,1.00000,19.3490,-3.4355,); setbounds _p to (0,-3.4869)--(24.9926,-3.4869)-- @@ -523,26 +577,7 @@ vardef _s(expr _t,_f,_m,_x,_y)(text _c)= addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; _n1="cmmi10"; _s("n",_n1,1.00000,0.0000,0.0000,); -_n7="cmsy10"; -_s(char0,_n7,1.00000,8.1938,0.0000,); -_n0="cmr10"; -_s("1",_n0,1.00000,18.1564,0.0000,); -setbounds _p to (0,-3.4869)--(23.1377,-3.4869)-- - (23.1377,8.4682)--(0,8.4682)--cycle; -_p endgroup -mpxbreak -begingroup save _p,_r,_s,_n; picture _p; _p=nullpicture; -string _n[]; -vardef _s(expr _t,_f,_m,_x,_y)(text _c)= - addto _p also _t infont _f scaled _m shifted (_x,_y) _c; enddef; -_n0="cmr10"; -_s("p",_n0,1.00000,0.0000,0.0000,); -_s("osloupnost",_n0,1.00000,5.8116,0.0000,); -_s("prohozen"&char19,_n0,1.00000,55.1821,0.0000,); -_s("a",_n0,1.00000,94.5069,0.0000,); -_s("separ"&char19,_n0,1.00000,102.8091,0.0000,); -_s("atorem",_n0,1.00000,125.5849,0.0000,); -setbounds _p to (0,-1.9372)--(156.0540,-1.9372)-- - (156.0540,6.9185)--(0,6.9185)--cycle; +setbounds _p to (0,-3.4869)--(5.9799,-3.4869)-- + (5.9799,8.4682)--(0,8.4682)--cycle; _p endgroup mpxbreak diff --git a/6-bitonic/6-bitonic.tex b/6-bitonic/6-bitonic.tex deleted file mode 100644 index 549e2f8..0000000 --- a/6-bitonic/6-bitonic.tex +++ /dev/null @@ -1,130 +0,0 @@ -\input ../lecnotes.tex - -\prednaska{6}{Bitonické tøídìní}{} - -Nyní se podíváme na~druhý problém, a~to na~problém tøídìní. Ji¾ známe pomìrnì efektivní sekvenèní algoritmy, které dovedou tøídit v~èase $\O(n\log n)$. Byli bychom jistì rádi, kdybychom to zvládli je¹tì rychleji. Pojïme se podívat, zda by nám v tom nepomohlo problém paralelizovat. - -Budeme pøi tom pracovat ve~výpoèetním modelu, kterému se øíká komparátorová sí». Ta je postavená z~hradel, kterým se øíká komparátory. - -\s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou -komparátory. - -\figure{sortnet.0}{Komparátor}{0.7in} - -Komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í -a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva -výstupy, pøièem¾ na~jednom vrátí men¹í ze~vstupních hodnot a~na~druhém vìt¹í. - -Výstupy komparátorù se nevìtví. Nemù¾eme tedy jeden výstup \uv{rozdvojit} a~pøipojit ho na~dva vstupy. (Vìtvení by dokonce ani nemìlo smysl, proto¾e zatímco rozdvojit bychom mohli, slouèit u¾~ne. Pokud tedy chceme, aby sí» mìla $n$~vstupù i~$n$~výstupù, rozdvojení stejnì nesmíme provést, i kdybychom jej mìli povolené.) - -\s{Pøíklad:} {\sl Bubble sort} - -Obrázek Bubble 1 ilustruje pou¾ití komparátorù pro tøídìní Bubble sortem. -©ipky pøedstavují jednotlivé komparátory. Výpoèet v¹ak je¹tì mù¾eme vylep¹it. - -\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). -Jak je vidìt, komparátory na sebe nemusejí èekat. Tím mù¾eme výpoèet urychlit a místo èasu $\Theta{(n^2)}$ docílit èasové slo¾itosti $\Theta{(n)}$. V obou pøípadech je zachován kvadratický prostor. - -Nyní si uká¾eme je¹tì rychlej¹í tøídící algoritmus. Pùjdeme na nìj v¹ak trochu \uv{od lesa}. Nejdøíve vymyslíme sí», která bude umìt tøídit jenom nìco -- toti¾ bitonické posloupnosti. Bez újmy na obecnosti budeme pøedpokládat, ¾e ka¾dé dva prvky na vstupu jsou navzájem rùzné. - -\medskip -\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická} právì tehdy, kdy¾ -pro nìjaké $x_k, k\in\{0, \dots, n-1\} $ platí, ¾e~v¹echny prvky pøed ním (vèetnì jeho samotného) -tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním tvoøí poslopnost klesající. -Formálnì zapsáno musí platit, ¾e: -$$x_0\leq x_1\leq \dots \leq x_k \geq x_{k+1}\geq\dots \geq x_{n-1}.$$ - -\s{Definice:} Posloupnost $x_0 \dots x_{n-1}$ je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro -které je rotace pùvodní posloupnosti o $j$ prvkù, tedy posloupnost -$$x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n},$$ èistì bitonická. - -\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 se pak stane~$i$-tým, -maximum $(i+{n/2})$-tým prvkem výstupu. -\figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \(x_i, x_{i+{n/2}})$} {300pt} - -\s{Lemma:} Pokud separátor dostane na~vstupu bitonickou posloupnost, pak jeho výstup $y_0, \dots, y_{n-1}$ -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}}$. - -Separátor nám tedy jednu bitonickou posloupnost na~vstupu rozdìlí na~dvì -bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první posloupnosti ($y_0,\dots, y_{n/2 -1}$) -je men¹í nebo roven prvkùm druhé posloupnosti ($y_{n/2}, \dots, y_{n-1}$). - -\>Ne¾ pøistoupíme k dùkazu lemmatu, uka¾me si, k èemu se nám bude hodit. - - -\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$ (BÚNO konstruujeme tøídièku pro $n=2^k$), vydá setøídìnou zadanou posloupnost délky $n$. - -Tøídièka dostane na~vstupu bitonickou posloupnost. Separátor~$S_n$ ji pak dle lemmatu rozdìlí na~dvì bitonické posloupnosti, kdy je ka¾dý prvek z~první posloupnosti men¹í ne¾ libovolný prvek z~druhé. Tyto poloviny pak dal¹í separátory rozdìlí na~ètvrtiny, ..., a¾~na~konci zbudou pouze jednoduché posloupnosti délky jedna (zjevnì setøídìné), které mezi sebou mají po¾adovanou nerovnost -- tedy ka¾dá posloupnost (nebo spí¹e prvek) nalevo je $\leq$ ne¾ prvek napravo od~nìj. - -\centerline{\epsfbox{sortnet.5}} - -Jak je vidìt, bitonická tøídièka nám libovolnou bitonickou posloupnost délky~$n$ -setøídí na~$\Theta(\log n)$ hladin. - -Nyní se dá odvodit, ¾e pokud umíme tøídit bitonické posloupnosti, umíme setøídit v¹echno. -Vzpomeòme si na~tøídìní sléváním -- Merge sort. To funguje tak, ¾e zaène s~jednoprvkovými posloupnostmi, které jsou evidentnì setøídìné, a~poté v¾dy dvì setøídìné posloupnosti slévá do~jedné. Kdybychom nyní umìli paralelnì slévat, mohli bychom vytvoøit i~paralelní Merge sort. Jinými slovy, potøebujeme dvì rostoucí posloupnosti nìjak efektivnì slít do~jedné setøídìné. Uvìdomme si, ¾e to zvládneme jednodu¹e -- staèí druhou z~posloupností obrátit a~\uv{pøilepit} za~první, èím¾ vznikne bitonická posloupnost, kterou poté mù¾eme setøídit na¹í bitonickou tøídièkou. - -\s{Pøíklad:} {\sl Merge sort} - -Bitonická tøídièka se tedy dá pou¾ít ke~slévání setøídìných posloupností. -Uka¾me si, jak s~její pomocí sestavíme souèástky {\I slévaèky} $M_n$: - -Setøídìné posloupnosti $x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické -posloupnosti $x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~této posloupnosti vytvoøíme pomocí bitonické tøídièky -$B_{2n}$ setøídìnou posloupnost. Vytvoøíme tedy blok $M_{2n}$, který se ov¹em sestává de~facto pouze z~bloku $B_{2n}$, jeho¾ druhá polovina vstupù je zapojena v~obráceném poøadí. -\figure{sortnet.6}{Paralelní MergeSort.}{3in} - -Nyní se pokusme odhadnout èasovou slo¾itost. Ná¹ MergeSort bude mít øádovì hloubku blokù $\log n$. -V ka¾dém bloku $M_n$ je navíc ukryta bitonická tøídièka s takté¾ logaritmickou hloubkou. -Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^k + \dots + \log n$. -Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$. - -Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen ${\O}(\log n)$ hladin. -Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný. - -Vra»me se nyní k dùkazu lemmatu, který jsme na pøedminulé stránce vynechali. - -\h{Dùkaz Lemmatu:} -(i) Nejprve nahlédneme, ¾e lemma platí, je-li vstupem èistì bitonická -posloupnost. Dále BÚNO pøedpokládejme, ¾e vrchol posloupnosti je v~první polovinì (kdyby -byl vrchol za~polovinou, staèilo by zrcadlovì obrátit posloupnost i~komparátory a~øe¹ili -bychom stejný problém). Nyní si definujme $k := \min j: x_j > x_{j+n/2}$. (Pokud -by~takové~$k$ neexistovalo, znamenalo by~to, ¾e vstupní posloupnost je monotónní. -Separátor by tedy nic nedìlal a~pouze zkopíroval vstup na~výstup, co¾ jistì lemma splòuje.) Nyní si v¹imìme, -¾e jakmile jednou zaène platit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude -nám tato relace platit a¾~do~konce. Oznaème vrchol vstupní posloupnosti jako~$x_m$. -Pak~$k$ bude jistì men¹í ne¾~$m$ a~$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í. - -Do pozice~$k$ tedy separátor bude pouze kopírovat vstup na~výstup, od~pozice~$k$ -dál u¾~jen prohazuje. 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á. Podobnì úsek $k+{n/2}$ a¾~$n-1$ nahradíme èistì -bitonickou posloupností. Obì poloviny tedy budou bitonické. - -Dostaneme-li na vstupu obecnou bitonickou posloupnost, pøedstavíme si, -¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO -doprava). 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ì výstupní -posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich -bitoniènosti se nic nezmìní. - -(ii) Z dùkazu (i) pro èistì bitonickou posloupnost víme, ¾e $y_0\dots y_{n/2-1}$ je è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). -\qed - -\medskip - -\centerline{\epsfbox{sortnet.7}} - -\bye diff --git a/6-bitonic/Makefile b/6-bitonic/Makefile deleted file mode 100644 index 496cb3d..0000000 --- a/6-bitonic/Makefile +++ /dev/null @@ -1,3 +0,0 @@ -P=6-bitonic - -include ../Makerules diff --git a/6-bitonic/sortnet.7 b/6-bitonic/sortnet.7 deleted file mode 100644 index 94619ca..0000000 --- a/6-bitonic/sortnet.7 +++ /dev/null @@ -1,106 +0,0 @@ -%!PS -%%BoundingBox: 9 5 191 130 -%%Creator: MetaPost -%%CreationDate: 2008.01.20:2138 -%%Pages: 1 -%*Font: cmr10 9.96265 9.96265 13:80000086000000000002247de1 -%*Font: cmmi10 9.96265 9.96265 6b:9 -%*Font: cmr7 6.97385 6.97385 32:8 -%*Font: cmmi7 6.97385 6.97385 6e:8 -%*Font: cmsy10 9.96265 9.96265 00:8 -%%EndProlog -%%Page: 1 1 - 0 0.3985 dtransform truncate idtransform setlinewidth pop [] 0 setdash - 1 setlinecap 1 setlinejoin 10 setmiterlimit -newpath 19.84248 119.0549 moveto -19.84248 39.68497 lineto -178.58235 39.68497 lineto -178.58235 119.0549 lineto stroke -newpath 19.84248 59.52745 moveto -69.4487 119.0549 lineto -178.58235 79.36993 lineto stroke - 0.3985 0 dtransform exch truncate exch idtransform pop setlinewidth - [3 3 ] 0 setdash -newpath 99.21242 19.84248 moveto -99.21242 128.97615 lineto stroke - 0 0.3985 dtransform truncate idtransform setlinewidth pop - [0 3.49998 ] 1.74998 setdash -newpath 130.36052 96.9054 moveto -148.81863 119.0549 lineto stroke -newpath 148.81863 119.0549 moveto -178.58235 108.23186 lineto stroke -newpath 50.99059 96.9054 moveto -99.21242 79.36993 lineto stroke - 0.3985 0 dtransform exch truncate exch idtransform pop setlinewidth - [3 3 ] 0 setdash -newpath 50.99059 96.9054 moveto -50.99059 39.68497 lineto stroke -newpath 130.36052 96.9054 moveto -130.36052 39.68497 lineto stroke - 0 0.3985 dtransform truncate idtransform setlinewidth pop - [0 3.49998 ] 1.74998 setdash -newpath 9.92125 9.92125 moveto -29.76373 9.92125 lineto stroke -newpath 52.48499 96.9054 moveto -52.48499 97.30173 52.32755 97.68184 52.04729 97.9621 curveto -51.76703 98.24236 51.38692 98.3998 50.99059 98.3998 curveto -50.59425 98.3998 50.21414 98.24236 49.93388 97.9621 curveto -49.65363 97.68184 49.49619 97.30173 49.49619 96.9054 curveto -49.49619 96.50906 49.65363 96.12895 49.93388 95.8487 curveto -50.21414 95.56844 50.59425 95.411 50.99059 95.411 curveto -51.38692 95.411 51.76703 95.56844 52.04729 95.8487 curveto -52.32755 96.12895 52.48499 96.50906 52.48499 96.9054 curveto closepath fill -newpath 131.85492 96.9054 moveto -131.85492 97.30173 131.69748 97.68184 131.41722 97.9621 curveto -131.13696 98.24236 130.75685 98.3998 130.36052 98.3998 curveto -129.96419 98.3998 129.58408 98.24236 129.30382 97.9621 curveto -129.02356 97.68184 128.86612 97.30173 128.86612 96.9054 curveto -128.86612 96.50906 129.02356 96.12895 129.30382 95.8487 curveto -129.58408 95.56844 129.96419 95.411 130.36052 95.411 curveto -130.75685 95.411 131.13696 95.56844 131.41722 95.8487 curveto -131.69748 96.12895 131.85492 96.50906 131.85492 96.9054 curveto closepath fill -17.35184 28.21677 moveto -(0) cmr10 9.96265 fshow -48.24048 29.76646 moveto -(k) cmmi10 9.96265 fshow -73.83423 33.03938 moveto -(n) cmmi7 6.97385 fshow - [] 0 setdash 0 setlinecap -newpath 73.83423 31.60748 moveto -78.75914 31.60748 lineto stroke -74.31104 25.68127 moveto -(2) cmr7 6.97385 fshow -82.16853 29.11678 moveto -(\000) cmsy10 9.96265 fshow -92.13113 29.11678 moveto -(1) cmr10 9.96265 fshow -117.86421 28.21677 moveto -(k) cmmi10 9.96265 fshow -125.57831 28.21677 moveto -(+) cmr10 9.96265 fshow -136.7364 32.13937 moveto -(n) cmmi7 6.97385 fshow -newpath 136.7364 30.70747 moveto -141.66132 30.70747 lineto stroke -137.21321 24.78127 moveto -(2) cmr7 6.97385 fshow -167.0135 28.21677 moveto -(n) cmmi10 9.96265 fshow -175.2073 28.21677 moveto -(\000) cmsy10 9.96265 fshow -185.1699 28.21677 moveto -(1) cmr10 9.96265 fshow -32.76373 7.43059 moveto -(p) cmr10 9.96265 fshow -38.57533 7.43059 moveto -(osloupnost) cmr10 9.96265 fshow -87.94583 7.43059 moveto -(prohozen\023) cmr10 9.96265 fshow -127.27063 7.43059 moveto -(a) cmr10 9.96265 fshow -135.57283 7.43059 moveto -(separ\023) cmr10 9.96265 fshow -158.34863 7.43059 moveto -(atorem) cmr10 9.96265 fshow -showpage -%%EOF -- 2.39.2