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}
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}}
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.
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 \<Select>($k$, $M$).
-\:Jestli¾e $k <= \vert M\vert + \vert P\vert$, pak vra» pivota $p$.
-\:Jinak vra» výsledek funkce \<Select>($k - \vert M\vert - \vert P\vert, V$).
+\:Jestli¾e $k \le \vert M\vert$, vrátím výsledek funkce \<Select>($k$, $M$).
+\:Jestli¾e $k \le \vert M\vert + \vert P\vert$, vrátíme pivota $p$.
+\:Jinak vrátíme výsledek funkce \<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 $\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:
projects / ads1.git / blobdiff