From cf60238a8aa4b32e52ba613ca13af7f8249fbcfd Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 10 Apr 2007 14:33:13 +0200 Subject: [PATCH] Drobne upravy. --- 3-strassen/3-strassen.tex | 153 +++++++++++++++++++------------------- 3-strassen/petice.eps | 54 ++++++++++---- 2 files changed, 119 insertions(+), 88 deletions(-) diff --git a/3-strassen/3-strassen.tex b/3-strassen/3-strassen.tex index a500aa4..4b38463 100644 --- a/3-strassen/3-strassen.tex +++ b/3-strassen/3-strassen.tex @@ -1,11 +1,11 @@ \input ../lecnotes.tex \input epsf.tex -\prednaska{3}{Rozdìl a panuj}{(zapsali Luká¹ Hermann, Vincent Krí¾, Oto Petøík)} +\prednaska{3}{Rozdìl a panuj II}{(zapsali Luká¹ Hermann, Vincent Krí¾, Oto Petøík)} -\h{Násobení matic n$\times$n} +\h{Násobení matic n$\times$n a Strassenùv algoritmus} -Nejdøíve si pøipomeneme definici násobení dvou ètvercových matic typu $n \times n$. Platí, ¾e prvek v $i$-tém øádku a $j$-tém sloupci výsledné matice $Z$ se rovná standardnímu skalárnímu souèinu $i$-tého øádku první matice $X$ a $j$-tého sloupce druhé matice $Y$. Formálnì zapsáno: +Nejdøíve si pøipomeneme definici násobení dvou ètvercových matic typu $n \times n$. Platí, ¾e prvek v $i$-tém øádku a $j$-tém sloupci výsledné matice $Z$ se rovná standardnímu skalárnímu souèinu $i$-tého øádku první matice $X$ a $j$-tého sloupce druhé matice~$Y$. Formálnì zapsáno: $$ Z_{ij} = \sum_{k=1}^n X_{ik} \cdot Y_{kj} $$ @@ -13,24 +13,24 @@ $$ Z_{ij} = \sum_{k=1}^n X_{ik} \cdot Y_{kj} $$ Algoritmus, který by násobil matice podle této definice, by mìl èasovou slo¾itost $ \Theta(n^3) $, proto¾e poèet prvkù ve výsledné matici je $n^2$ a jeden skalární souèin vektorù dimenze $n$ vy¾aduje lineární poèet operací. -My se s touto èasovou slo¾itostí ov¹em nespokojíme a budeme postupovat podobnì jako pøi vylep¹ování algoritmu na násobení velkých èísel. Bez újmy na obecnosti pøedpokládejme, ¾e budeme násobit dvì matice typu $n \times n$, kde $n=2^k, k \in N$. Obì tyto matice rozdìlíme na ètvrtiny a tyto èásti postupnì oznaèíme u matice X - A, B, C a D, u matice Y - P, Q, R a S. Z definice násobení matic zjistíme, ¾e ètvrtiny výsledné matice Z mù¾eme zapsat pomocí èástí násobených matic. Levá horní ètvrtina bude odpovídat výsledku operací AP+BR, pravá horní ètvrtina bude AQ+BS, levá dolní CP+DR a zbylá CQ+DS (viz obrázek). +My se s touto èasovou slo¾itostí ov¹em nespokojíme a budeme postupovat podobnì jako pøi vylep¹ování algoritmu na násobení velkých èísel. Bez újmy na obecnosti pøedpokládejme, ¾e budeme násobit dvì matice typu $n \times n$, kde $n=2^k, k \in \bb N$. Obì tyto matice rozdìlíme na ètvrtiny a tyto èásti postupnì oznaèíme u matice $X$ - $A$, $B$, $C$ a $D$, u matice $Y$ - $P$, $Q$, $R$ a $S$. Z definice násobení matic zjistíme, ¾e ètvrtiny výsledné matice $Z$ mù¾eme zapsat pomocí èástí násobených matic. Levá horní ètvrtina bude odpovídat výsledku operací $AP+BR$, pravá horní ètvrtina bude $AQ+BS$, levá dolní $CP+DR$ a zbylá $CQ+DS$ (viz obrázek). \figure{nasobeni-matic-2.eps}{Násobení rozètvrcených matic}{\epsfxsize} -\break +\break -Pøevedli jsme tedy problém násobení ètvercových matic øádu $n$ na násobení ètvercových matic øádu ${n \over 2}$. Tímto rozdìlovánín bychom mohli pokraèovat, dokud bychom se nedostali na matice øádu 1, jejich¾ vynásobení je triviální. Dostali jsme tedy klasický algoritmus typu {\it rozdìl a panuj}. Pomohli jsme si ale nìjak ? V ka¾dém kroku provádíme 8 násobení matic polovièního øádu a navíc konstantní poèet operací na $n^2$ prvcích. Dostáváme tedy rekurentní zápis èasové slo¾itosti: +Pøevedli jsme tedy problém násobení ètvercových matic øádu $n$ na násobení ètvercových matic øádu ${n/2}$. Tímto rozdìlováním bychom mohli pokraèovat, dokud bychom se nedostali na matice øádu 1, jejich¾ vynásobení je triviální. Dostali jsme tedy klasický algoritmus typu {\it rozdìl a panuj}. Pomohli jsme si ale nìjak ? V ka¾dém kroku provádíme 8 násobení matic polovièního øádu a navíc konstantní poèet operací na $n^2$ prvcích. Dostáváme tedy rekurentní zápis èasové slo¾itosti: -$$ T(n) = 8T\left({n \over 2}\right) + \O(n^2) $$ +$$ T(n) = 8\ T\left({n \over 2}\right) + \O(n^2). $$ -Po aplikaci Master Theoremu pak lehce dojdeme k závìru, ¾e slo¾itost je stále $O(n^3)$, tedy stejná jako pøi násobení matic z definice. Zdánlivì jsme si tedy nepomohli, ale stejnì jako tomu bylo u násobení velkých èísel, i teï mù¾eme zredukovat poèet násobení matic polovièního øádu, které nejvíce ovlivòuje èasovou slo¾itost algoritmu. Není to bohu¾el nic triviálního, a proto si radìji rovnou øekneme správné øe¹ení. Jedná se o Strassenùv algoritmus, který redukuje potøebný poèet násobení na 7, a je¹tì pøed tím, ne¾ si uká¾eme, jak funguje, doká¾eme si, jak nám to s èasovou slo¾itostí vlastnì pomù¾e: +Po aplikaci Master Theoremu pak lehce dojdeme k závìru, ¾e slo¾itost je stále $\Theta(n^3)$, tedy stejná jako pøi násobení matic z definice. Zdánlivì jsme si tedy nepomohli, ale stejnì jako tomu bylo u násobení velkých èísel, i teï mù¾eme zredukovat poèet násobení matic polovièního øádu, které nejvíce ovlivòuje èasovou slo¾itost algoritmu. Není to bohu¾el nic triviálního, a proto si radìji rovnou øekneme správné øe¹ení. Jedná se o Strassenùv algoritmus, který redukuje potøebný poèet násobení na~7, a je¹tì pøed tím, ne¾ si uká¾eme, jak funguje, doká¾eme si, jak nám to s èasovou slo¾itostí vlastnì pomù¾e: -$$ T(n) = 7T\left({n \over 2}\right) + \O(n^2) \Longrightarrow \O(n^{log_2 7}) \doteq \O(n^{2.808}) $$ +$$ T(n) = 7\ T\left({n \over 2}\right) + \O(n^2) \Longrightarrow \O(n^{log_2 7}) = \O(n^{2.808}). $$ -Výsledná slo¾itost Strassenova algoritmu je tedy pøibli¾nì $\O(n^{2.808})$, co¾ je sice malé, ale pro velké matice znatelné zlep¹ení oproti algoritmu vycházejícího pøímo z definice. A nyní u¾ obrázkový dùkaz tohoto algoritmu: +Výsledná slo¾itost Strassenova algoritmu je tedy pøibli¾nì $\O(n^{2.808})$, co¾ je sice malé, ale pro velké matice znatelné zlep¹ení oproti algoritmu vycházejícího pøímo z~definice. % zacatek slidu z prednasky -\s{Strassenùv algoritmus: vzorce} +\s{Lemma:} Strassenùv algoritmus \def\\{\noalign{\vskip 7pt}} @@ -57,17 +57,7 @@ T_4 = D\cdot(R-P) \cr \medskip -7 násobení místo 8 $\Rightarrow$ èasová slo¾itost $\O(n^{\log_2 7}) = \O(n^{2.808})$. - -\medskip - -[Zatím nejlep¹í výsledek: $\O(n^{2.376})$ \uv{s~opravdu velkým~$\O$.}] - -\break - -\s{Strassenùv algoritmus: dùkaz} - -Do ètvercù $4 \times 4$ si napí¹eme znaky $+$ nebo $-$ podle toho, jestli se pøi výpoètu dané matice pøièítá nebo odeèítá pøíslu¹ný souèin dvou matic. Øádky znamenají matice A, B, C a D a sloupce znaèí matice P, Q, R a S. Pokud se tedy v prvním øádku a prvním sloupci vyskytuje znak +, znamená to ¾e pøièteme souèin matic A a P. Nejdøíve si spoèítáme pomocné matice $T_1$ a¾ $T_7$ a z nich pak dopoèítáme, co bude na pøíslu¹ných místech ve výsledné matici. +\proof Do ètvercù $4 \times 4$ si napí¹eme znaky $+$ nebo $-$ podle toho, jestli se pøi výpoètu dané matice pøièítá nebo odeèítá pøíslu¹ný souèin dvou matic. Øádky znamenají matice $A$, $B$, $C$ a $D$ a sloupce znaèí matice $P$, $Q$, $R$ a $S$. Pokud se tedy v prvním øádku a prvním sloupci vyskytuje znak $+$, znamená to ¾e pøièteme souèin matic $A$~a~$P$. Nejdøíve si spoèítáme pomocné matice $T_1$ a¾ $T_7$ a z nich pak dopoèítáme, co bude na pøíslu¹ných místech ve výsledné matici. \def\bbb#1{\vbox to 10pt{\vss\hbox to 10pt{\hss\tenrm #1\hss}\vss}} \def\bb#1{\ifx#1.\bbb{$\cdot$}\else\bbb#1\fi} @@ -100,80 +90,93 @@ $$ % konec slidu z prednasky -Jak je vidìt, výsledná matice je tvoøena stejnými èástmi jako pøi obyèejném násobení. Tím je dùkaz dokonèen. +Jak je vidìt, výsledná matice je tvoøena stejnými èástmi jako pøi obyèejném násobení. Touto kapitolou jsme tedy dokázali následující vìtu: + +\s{Vìta:} +Násobení matic $n \times n$ má èasovou slo¾itost v nejhor¹ím pøípadì $\O(n^{2.808})$. \qed + +\s{Poznámka:} +Zatím nejlep¹í dokázaný algoritmus má èasovou slo¾itost $\O(n^{2.376})$, $ $ ov¹em s velkou multiplikativní konstantou. \h{Hledání $k$-tého nejmen¹ího prvku (mediánu)} -V tomto oddílu se budeme zabývat tím, jak co nejrychleji najít v jakékoli posloupnosti $n$ èísel $k$-tý nejmen¹í prvek popøípadì medián. Pro ty, co medián neznají, tu máme definici: +V tomto oddílu se budeme zabývat tím, jak co nejrychleji najít v jakékoli posloupnosti $n$ èísel $k$-tý nejmen¹í prvek popøípadì medián. Pro ty, kdo medián neznají, tu máme definici: -\s{Definice:} Medián posloupnosti $a_1, a_2,\ldots , a_n$ je takové $m=a_i$, kde $\vert{j:a_j < m}\vert < {n \over 2}$ a $\vert{j:a_j > m}\vert < {n \over 2}$. kde $i,j \in {1, 2,\ldots , n} $ - -Nejjednodu¹¹ím øe¹ením by urèitì bylo celou posloupnost nejdøíve setøídit a pak u¾ jednodu¹e vyhmátnout po¾adovaný prvek. To bychom dokázali v celkem slu¹ném èase $\O(n\ log(n))$, ale u¾ teï mù¾eme prozradit, ¾e to jde v èase $\O(n)$. Jak? +\s{Definice:} +Medián posloupnosti $a_1, a_2,\ldots , a_n$ je takové $m=a_i$, kde ménì ne¾ $n/2$ prvkù je men¹ích ne¾ $m$ a ménì ne¾ $n/2$ prvkù je vìt¹ích ne¾ $m$. -Pou¾ívat budeme metodu {\it rozdìl a panuj}. Nìjakým zpùsobem si zvolíme jeden prvek posloupnosti, který nazveme {\it pivot}. Poté rozdìlíme zadanou posloupnost na tøi disjunktní mno¾iny. Do první dáme v¹echny prvky men¹í ne¾ pivot, do druhé stejné jako pivot a do tøetí vìt¹í ne¾ pivot. Tímto máme zaji¹tìno, ¾e prvky z první mno¾iny jsou urèitì men¹í ne¾ prvky z druhé a ty ne¾ prvky z tøetí. +Nejjednodu¹¹ím øe¹ením by urèitì bylo celou posloupnost nejdøíve setøídit a pak u¾ jednodu¹e vyhmátnout po¾adovaný prvek. To bychom dokázali v celkem slu¹ném èase $\O(n\log n)$, ale u¾ teï mù¾eme prozradit, ¾e to jde v èase $\O(n)$. Jak? -O tom, jak jsou prvky uspoøádány uvnitø tìchto mno¾in ale nic nevíme. V posledním kroku na¹eho algoritmu se pak rozhodneme, na kterou mno¾inu ná¹ algoritmus rekurzivnì zavoláme. Pokud je $k$ men¹í ne¾ velikost první mno¾iny, pokraèujeme v první mno¾inì, pokud je $k$ men¹í ne¾ souèet velikostí první a druhé mno¾iny, pak hledaným prvkem je právì vybraný pivot a algoritmus skonèí, a nakonec pokud ani jedna podmínka splnìna nebyla, pustíme se do hledání v tøetí mno¾inì, ov¹em u¾ nehledáme $k$-tý nejmen¹í prvek, ale $l$-tý, kde $l$ se rovná $k$ minus velikost prvních dvou mno¾in. Pro vìt¹í názornost zapí¹eme tento algoritmus schematicky: +Pou¾ívat budeme metodu {\it rozdìl a panuj}. Nìjakým zpùsobem si zvolíme jeden prvek posloupnosti, který nazveme {\it pivot}. Poté rozdìlíme zadanou posloupnost na~tøi disjunktní mno¾iny. Do první dáme v¹echny prvky men¹í ne¾ pivot, do druhé stejné jako pivot a do tøetí vìt¹í ne¾ pivot. Tímto máme zaji¹tìno, ¾e prvky z první mno¾iny jsou urèitì men¹í ne¾ prvky z druhé a ty ne¾ prvky z tøetí. +O tom, jak jsou prvky uspoøádány uvnitø tìchto mno¾in, ale nic nevíme. V posledním kroku na¹eho algoritmu se pak rozhodneme, na kterou mno¾inu svùj algoritmus rekurzivnì zavoláme. Pokud je $k$ men¹í ne¾ velikost první mno¾iny, pokraèujeme v první mno¾inì, pokud je $k$ men¹í ne¾ souèet velikostí první a druhé mno¾iny, pak hledaným prvkem je právì vybraný pivot a algoritmus skonèí, a nakonec pokud ani jedna podmínka splnìna nebyla, pustíme se do hledání ve tøetí mno¾inì, ov¹em u¾ nehledáme $k$-tý nejmen¹í prvek, ale $l$-tý, kde $l$ se rovná $k$ minus velikost prvních dvou mno¾in. Pro vìt¹í názornost zapí¹eme tento algoritmus pøedhlednìji: -{\bo Select($k,X$)} + +{\bo Select($k,X$):} (Hledání $k$-tého nejmen¹ího prvku v mno¾ine $X$) \algo -\:if $\vert M\vert \leq 1 \Rightarrow $ triviální o¹etøení -\:zvolíme pivota $p \in X$ -\:$M = \{x \in X; x < p\}, P = \{x \in X; x = p\}, V = \{x \in X; x > p\}$ -\:if $k \leq \vert M \vert \Rightarrow $ return {\bo Select($k,M$)} -\:else if $k \leq\vert M\vert +\vert P\vert \Rightarrow $ return $p$ -\:else return \bo{Select($k-\vert M \vert -\vert P\vert , V$)} -\endalgo -Na první pohled je vidìt, ¾e se algoritmus zastaví (vstup se v¾dy zmen¹í alespoò o 1) a ¾e vydá v¾dy správný výsledek. Jak je to ov¹em s èasovou slo¾itostí? Rozdìlení do mno¾in a podmínky v druhém a tøetím kroku mají lineární slo¾itost, èemu¾ se nevyhneme. Pøi ne¹»astné volbì pivota se nám mù¾e stát, ¾e poèet rekurencí mù¾e být a¾ $n$, tedy celková slo¾itost v nejhor¹ím pøípadì je $\O(n^2)$, èím¾ jsme si oproti prostému setøídìní je¹tì pohor¹ili. Co s tím? Jak je vidìt, velmi dùle¾itá je volba pivota. Tu mù¾eme provést nìkolika zpùsoby: -a) Pivot by se v setøídìné posloupnosti vyskytoval uprostøed, vstup by se tedy stále pùlil. Èasovou slo¾itost vypoèteme z rekurentního zápisu: +\:Jestli¾e $\vert X\vert <= 1$, pak triviálnì o¹etøíme. +\:Zvolíme pivota $p \in X$. +\:Rozdìlíme mno¾inu X na tøi podmno¾iny: $M = \{x \in X; x < p\},$ $ P = \{x \in X; x = p\}, V = \{x \in X; x > p\}$. +\:Jestli¾e $k <= \vert M\vert$, pak vra» výsledek funkce \($k - \vert M\vert - \vert P\vert, V$). +\endalgo + +Na první pohled je vidìt, ¾e se algoritmus zastaví (vstup se v¾dy zmen¹í alespoò o 1) a ¾e vydá v¾dy správný výsledek. Jak je to ov¹em s èasovou slo¾itostí? Rozdìlení do mno¾in a podmínky v druhém a tøetím kroku mají lineární slo¾itost, èemu¾ se nevyhneme. Pøi ne¹»astné volbì pivota se nám mù¾e stát, ¾e poèet rekurencí mù¾e být a¾ $n$, tedy celková slo¾itost v nejhor¹ím pøípadì je $\Theta(n^2)$, èím¾ jsme si oproti prostému setøídìní je¹tì pohor¹ili. Co s tím? Jak je vidìt, velmi dùle¾itá je volba pivota. Tu mù¾eme provést nìkolika zpùsoby: + +a) Pivot by se v setøídìné posloupnosti vyskytoval uprostøed, vstup by se tedy stále pùlil. Èasovou slo¾itost vypoèteme z rekurentního zápisu: + +$$ T(n) = T\left({n \over 2}\right) + \O(n) = \O\left(n + {n \over 2} + {n \over 4} + \dots\right) = \O(n). $$ -$$ T(n) = T\left({n \over 2}\right) + \O(n) \Longrightarrow \O(n) $$ - -To by bylo sice skvìlé, ale nalezení takového pivota je vlastnì vyøe¹ení úlohy hledání mediánu, o co¾ se sna¾íme. Tedy jsme si vùbec nepomohli. +To by bylo sice skvìlé, ale nalezení takového pivota je vlastnì vyøe¹ení úlohy hledání mediánu, o co¾ se sna¾íme. Tedy jsme si vùbec nepomohli. \break - -b) Pivot by se v setøídìné posloupnosti nacházel v prostøedních dvou ètvrtinách. Tím bychom v ka¾dém kroku urèitì odstranili mno¾inu velikosti ètvrtiny vstupu. Èasová slo¾itost tohoto øe¹ení by byla: - -$$ T(n) = T\left({3 \over 4}n\right) + \O(n) \Longrightarrow \O(n) $$ - -Tímto bychom tedy také dosáhli lineární èasové slo¾itosti. Ale jak vybrat pivota tak, aby se nacházel v prostøedních dvou ètvrtinách, aby nám nám to nepokazilo lineární slo¾itost? - -c) Pivot bude v¾dy prostøední prvek zadané posloupnosti. V tomto pøípadì je zøejmé, ¾e existují urèité vstupy, pro které bude èasová slo¾itost $\O(n^2)$, ale v prùmìrném pøípadì, který je¹tì neumíme analyzovat, bude èasová slo¾itost $\O(n)$. - -d) Pivot bude náhodnì zvolený prvek zadané posloupnosti. Tímto dosáhneme nìèeho podobného jako v pøedchozím pøípadì, ale u¾ nebude existovat vstup, pro který by èasová slo¾itost byla $\O(n^2)$, jen nìkteré prùbìhy tohoto algoritmu na rùzných vstupech budou trvat takto dlouho. Prùmìrná èasová slo¾itost je tedy zase $O(n)$. - -My se ale nespokojíme pouze s lineární prùmìrnou èasovou slo¾itostí. Chceme dosáhnout lineární slo¾itosti i v nejhor¹ím pøípadì. Ne¾ si ale prozradíme takové øe¹ení, rozmyslíme si, ¾e u¾ teï známe 3 èasové slo¾itosti, i kdy¾ ne v¹echny je¹tì umíme analyzovat. Je to èasová slo¾itost v nejhor¹ím pøídadì, v prùmìrném pøípadì pøes v¹echny vstupy a v prùmìrném pøípadì pøes v¹echny bìhy programu. V¹imnìte si hlavnì rozdílu posledních dvou. - -A nyní u¾ slibované øe¹ení s lineární nejhor¹í èasovou slo¾itostí. Vyjdeme z mo¾nosti b), tedy pokusíme se najít takového pivota, který by na pøí¹tí krok zaruèenì omezil velikost analyzované mno¾iny. Dosáhneme toho tímto algoritmem: - -{\bo Volba pivota} + +b) Pivot by se v setøídìné posloupnosti náchazel v prostøedních dvou ètvrtinách (nazvìme tento prvek "l¾imedián"). Tím bychom v ka¾dém kroku urèitì odstranili mno¾inu velikosti ètvrtiny vstupu. Èasová slo¾itost tohoto øe¹ení by byla: + +$$ T(n) = T\left({3 \over 4}n\right) + \O(n) = \O\left(n + {3 \over 4}n + {9 \over 16}n + \dots\right) = \O(n). $$ + +Tímto bychom tedy také dosáhli lineární èasové slo¾itosti. Ale jak vybrat pivota tak, aby se nacházel v prostøedních dvou ètvrtinách, aby nám nám to nepokazilo lineární slo¾itost? + +c) Pivot bude v¾dy prostøední prvek zadané posloupnosti. V tomto pøípadì je zøejmé, ¾e existují urèité vstupy, pro které bude èasová slo¾itost $\Omega(n^2)$, ale v~prùmìrném pøípadì, bude èasová slo¾itost $\O(n)$, co¾ doká¾eme v pøí¹tí kapitole. + +d) Pivot bude náhodnì zvolený prvek zadané posloupnosti. Tímto dosáhneme nìèeho podobného jako v pøedchozím pøípadì, ale u¾ nebude existovat vstup, pro který by èasová slo¾itost byla $\Omega(n^2)$, jen nìkteré prùbìhy tohoto algoritmu na rùzných vstupech budou trvat takto dlouho. Prùmìrná èasová slo¾itost je tedy zase $O(n)$. + +My se ale nespokojíme pouze s lineární prùmìrnou èasovou slo¾itostí. Chceme dosáhnout lineární slo¾itosti i v nejhor¹ím pøípadì. Ne¾ si ale prozradíme takové øe¹ení, rozmyslíme si, ¾e u¾ teï známe 3 èasové slo¾itosti, i kdy¾ ne v¹echny je¹tì umíme analyzovat. Je to èasová slo¾itost v nejhor¹ím pøídadì, v prùmìrném pøípadì pøes v¹echny vstupy a v prùmìrném pøípadì pøes v¹echny bìhy programu. V¹imnìte si hlavnì rozdílu posledních dvou. + +A nyní u¾ slibované øe¹ení s lineární nejhor¹í èasovou slo¾itostí. Vyjdeme z~mo¾nosti b), tedy pokusíme se najít takového pivota, který by na pøí¹tí krok zaruèenì omezil velikost analyzované mno¾iny. Dosáhneme toho tímto algoritmem: + +\s{Volba pivota:} \algo -\:rozdìlíme vstup na pìtice - $\O(n)$ -\:spoèteme medián ka¾dé pìtice - $\O(n)$ -\:spoèteme medián mediánù pìtic = Select(${n \over 10}$, {mediány pìtic}) a to je pivot +\:Rozdìlíme vstup na pìtice \dots $\O(n)$ +\:Spoèteme medián ka¾dé pìtice \dots $\O(n)$ +\:Spoèteme medián mediánù pìtic tak, ¾e rekurzivnì zavoláme tentý¾ algoritmus \