\input ../lecnotes.tex
\input epsf.tex

\prednaska{3}{Rozdìl a panuj II}{(zapsali Luká¹ Hermann, Vincent Krí¾, Oto Petøík)}

\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:

$$ 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$ 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}

\break

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). $$

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) = 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 $\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.

\s{Lemma:} (vzorce pro násobení blokových matic ve~Strassenovì algoritmu)

\def\\{\noalign{\vskip 7pt}}

$$
\pmatrix{A & B \cr\\ C & D \cr}
\cdot
\pmatrix{P & Q \cr\\ R & S \cr}
=
\pmatrix{
T_1 + T_4 - T_5 + T_7 &
T_3 + T_5 \cr\\
T_2 + T_4 &
T_1 - T_2 + T_3 + T_6 \cr
},$$

kde:

$$\vbox{\halign{$#$\hfil\qquad &$#$\hfil\qquad \cr
T_1 = (A+D)\cdot(P+S)		& T_5 = (A+B)\cdot S \cr\\
T_2 = (C+D)\cdot P		& T_6 = (C-A)\cdot (P+Q) \cr\\
T_3 = A\cdot(Q-S)		& T_7 = (B-D)\cdot (R+S) \cr\\
T_4 = D\cdot(R-P)					 \cr
}}$$

\medskip

\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}
\def\zz#1#2#3#4{\bb#1\bb#2\bb#3\bb#4}
\def\qq#1#2#3#4{{\offinterlineskip\vcenter{\halign{\vrule ##\vrule \cr\noalign{\hrule}\zz#1\cr\zz#2\cr\zz#3\cr\zz#4\cr\noalign{\hrule}}}}}

$$
T_1 = \qq{+..+}{....}{....}{+..+} \qquad
T_2 = \qq{....}{....}{+...}{+...} \qquad
T_3 = \qq{.+.-}{....}{....}{....} \qquad
T_4 = \qq{....}{....}{....}{-.+.}
$$
$$
T_5 = \qq{...+}{...+}{....}{....} \qquad
T_6 = \qq{--..}{....}{++..}{....} \qquad
T_7 = \qq{....}{..++}{....}{..--}
$$

\medskip

\def\\{\noalign{\vskip 7pt}}
$$
\eqalign{
T_1 + T_4 - T_5 + T_7 &= \qq{+...}{..+.}{....}{....} = AP + BR \cr\\
T_3 + T_5 &= \qq{.+..}{...+}{....}{....} = AQ + BS \cr\\
T_2 + T_4 &= \qq{....}{....}{+...}{..+.} = CP + DR \cr\\
T_1 - T_2 + T_3 + T_6 &= \qq{....}{....}{.+..}{...+} = CQ + DS \cr
}
$$

% 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í. Touto kapitolou jsme tedy dokázali následující vìtu:

\s{Vìta:}
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.

\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, 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 nejvý¹e $n/2$ prvkù je men¹ích ne¾ $m$ a nejvý¹e $n/2$ prvkù je vìt¹ích ne¾ $m$.

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.

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 \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 \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:

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). $$

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 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 \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 \<Select>($n / 10$, {mediány pìtic}) a to je pivot.
\endalgo

Abychom dokázali, ¾e tento algoritmus bude mít opravdu lineární èasovou slo¾itost, musíme si nejdøíve dokázat následující lemma:

\s{Lemma:} V ka¾dém kroku vypadne alespoò ${3/10}\cdot n$ prvkù.

\proof Ten provedeme obrázkem. Pøedstavme si vybrané pìtice seøazené podle velikosti od nejvìt¹ího prvku a zakresleme je do sloupcù. Jejich mediány tedy vyplòují prostøední øadu. Tyto pìtice pak seøaïme podle velikosti jejich mediánù (nejmen¹í vlevo). Hledaný pivot se tedy nachází (pokud pøedpokládáme pro jednoduchost lichý poèet pìtic) pøesnì uprostøed. O prvcích nad pivotem a napravo od nìj mù¾eme urèitì øíct, ¾e jsou vìt¹í nebo rovny pivotu, prvky pod ním a nalevo od nìj jsou zase urèitì men¹í nebo rovny pivotu.

Podle konstrukce algoritmu tedy zaruèenì vypadne jedna nebo druhá skupina prvkù. Obì tyto skupiny pøitom obsahují, jak je vidìt z obrázku, alespoò $3/10 \cdot n$ prvkù.
\qed

\figure{petice.eps}{Pìtice}{125mm}

Nyní u¾ se tedy mù¾eme pustit do výpoètu èasové slo¾itosti. V ka¾dém kroku funkce zavolá sama sebe nejdøíve na vstup velikosti ${n \over 5}$ a poté na vstup velikosti nejvý¹e ${7 \over 10}n$. Ostatní operace zùstávají lineární. Èasovou slo¾itost v nejhor¹ím pøípadì tedy mù¾eme zapsat rekurentním vzorcem:

$$ T(n) = \O(n) + T\left({n \over 5}\right) + T\left({7 \over 10}n\right). $$

Tento rekurentní vzorec ale zatím neumíme obecnì øe¹it. Mohli bychom ho postupnì rozepsat, ale trvalo by dlouho, ne¾ bychom z toho nìco vykoukali. Lep¹í bude rovnou dokázat, ¾e tento rekurentní vzorec odpovídá lineární slo¾itosti, zkusíme tedy dosadit $T(n) = cn$:

$$ cn = n + {1 \over 5}cn + {7 \over 10}cn \quad\Longleftrightarrow\quad c = 10. $$

Tímto jsme tedy dokázali, ¾e èasová slo¾itost tohoto algoritmu v nejhor¹ím pøípadì je $\O(n)$.
Jeliko¾ to rychleji urèitì není mo¾né, mù¾eme na závìr této kapitoly zformulovat tuto vìtu:

\s{Vìta:} Hledání k-tého nejmen¹ího prvku v posloupnosti délky n má èasovou slo¾itost v nejhor¹ím pøípadì $\Theta(n)$. \qed

\bye
