From da9dbe725aff0c0dbc16aa442e1e897419a9f1ca Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 May 2007 13:33:36 +0200 Subject: [PATCH] Drobne korektury. --- 3-strassen/3-strassen.tex | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-) diff --git a/3-strassen/3-strassen.tex b/3-strassen/3-strassen.tex index b8abdea..923083f 100644 --- a/3-strassen/3-strassen.tex +++ b/3-strassen/3-strassen.tex @@ -7,13 +7,13 @@ 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} $$ +$$ Z_{ij} = \sum_{k=1}^n X_{ik} \cdot Y_{kj}. $$ \figure{nasobeni-matic.eps}{Násobení matic}{\epsfxsize} 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 \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). +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$ písmeny $A$, $B$, $C$ a $D$, u matice $Y$ písmeny $P$, $Q$, $R$ a $S$. Z definice násobení matic zjistíme, ¾e ètvrtiny výsledné matice $Z$ mù¾eme zapsat pomocí souèinù èá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} @@ -21,16 +21,15 @@ My se s touto 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) = 8\ T\left({n \over 2}\right) + \O(n^2). $$ +$$ T(n) = 8T\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 $\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: +Pou¾itím Master Theoremu 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) = 7\ T\left({n \over 2}\right) + \O(n^2) \Longrightarrow \O(n^{log_2 7}) = \O(n^{2.808}). $$ +$$ T(n) = 7T\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. +Výsledná slo¾itost Strassenova algoritmu je tedy $\O(n^{2.808})$, co¾ je sice malé, ale pro velké matice znatelné zlep¹ení oproti algoritmu vycházejícímu pøímo z~definice. -% zacatek slidu z prednasky -\s{Lemma:} Strassenùv algoritmus +\s{Lemma:} (vzorce pro násobení blokových matic ve~Strassenovì algoritmu) \def\\{\noalign{\vskip 7pt}} @@ -93,7 +92,8 @@ $$ 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 +Strassenùv algoritmus pro 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. @@ -108,20 +108,18 @@ Medi 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? 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. -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: - +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 formálnìji: {\bo Select($k,X$):} (Hledání $k$-tého nejmen¹ího prvku v mno¾ine $X$) \algo - - -\:Jestli¾e $\vert X\vert <= 1$, pak triviálnì o¹etøíme. +\:Jestli¾e $\vert X\vert \le 1$, vyøe¹íme triviálnì. \: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$). +\:Jestli¾e $k \le \vert M\vert$, vrátím 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: -- 2.39.2