]> mj.ucw.cz Git - ads1.git/blob - 13-trideni/13-trideni.tex
Trideni a Strassen: Zapisky od Karla
[ads1.git] / 13-trideni / 13-trideni.tex
1 \input ../lecnotes.tex
2
3 \prednaska{13}{Tøídící algoritmy a násobení matic}{}
4
5 Minulou pøedná¹ku jsme probírali QuickSort, jeden z historicky prvních tøídících algoritmù,
6 které pøekonaly kvadratickou slo¾itost aspoò v~prùmìrném pøípadì.
7
8 Proè se dodnes pou¾ívá, kdy¾ známe algoritmy, které mají slo¾itost $\Theta(n\log n)$ i
9 v nejhor¹ím pøípadì? Proto¾e QuickSort se k pamìti chová témìø sekvenènì, tak¾e na
10 dne¹ních poèítaèích bì¾í rychle.
11
12 Podívejme se na pár nápadù pro skuteèné naprogramování tohoto algoritmu.
13
14 Urèitì nám vadí pøekopírovávat z a do pomocných polí. Na¹tìstí mù¾eme pøerovnávat
15 pøímo v pùvodním poli. Zleva budeme dávat prvky men¹í ne¾ pivot, zprava vìt¹í ne¾
16 pivot. Na toto staèí udr¾ovat si dva indexy $a$ a $b$, které znaèí, jak daleko vlevo
17 (vpravo) u¾ jsou správné prvky.
18
19 Rekurzivní programy mohou být pro poèítaè zátì¾í. Proto implementujme vlastní zásobník
20 na hranice úsekù, které zbývá setøídit. V¾dy vìt¹í interval vlo¾íme na zásobník a men¹í
21 rovnou zpracujeme. Na zásobníku tedy bude maximálnì $\log n$ polo¾ek.
22
23 Malé podproblémy dotøídíme nìjakým triviálním algoritmem napøíklad InsertSortem.
24 Odhadem pro $n=10$ je to pro dne¹ní poèítaèe výhodné.
25
26 \h{Zoo tøídících algoritmù}
27
28 Porovnejme nyní známé tøídící algoritmy.
29
30 Bude nás zajímat i jejich stabilita, tedy jestli zachovají poøadí polo¾ek se stejným
31 klíèem. Stabilita je dùle¾itá pøi lexikografickém tøídìní, kde se napøed tøídí podle
32 nejménì významné slo¾ky a pak podle významìj¹ích.
33
34 \s{Definice:} {\it Stabilní tøídìní} øíkáme takovému, které u~prvkù se stejnou hodnotou
35 klíèe zachová jejich vzájemné poøadí, v~jakém byly na~vstupu.
36
37 \medskip
38
39 \settabs 4 \columns
40 \+              & \<Èas>                & \<Pomocná pamì»>      & \<Stabilní> \cr
41 \smallskip
42 \+ InsertSort   & $\Theta (n^2)$        & $\Theta (1)$          & $+$ \cr
43 \+ MergeSort    & $\Theta (n\log n)$    & $\Theta (n)$          & $+$ \cr
44 \+ HeapSort     & $\Theta (n\log n)$    & $\Theta (1)$          & $-$ \cr
45 \+ QuickSort    & $\Theta (n\log n)$    & $\Theta (\log n)$     & $-$ \cr
46
47 \medskip
48
49 \>Poznámky k tabulce:
50 \itemize\ibull
51 \:QuickSort má jen prùmìrnou èasovou slo¾itost $\Theta (\log n)$. Mù¾eme ale øíct, ¾e
52 porovnáváme prùmìrné èasové slo¾itosti, proto¾e u ostatních algoritmù vyjdou stejnì
53 jako jejich èasové slo¾itosti v~nejhor¹ím pøípadì.
54 \:HeapSort -- tøídìní pomocí haldy. Do haldy vlo¾íme v¹echny prvky a pak je vybereme.
55 Celkem $n$ operací s haldou, ka¾dá za $\log n$. Navíc tuto haldu mohu stavìt i boøit
56 v poli, ve kterém dostanu vstup.
57 \:MergeSort jde implementovat s konstantní pamì»ovou slo¾itostí.
58 \:MergeSort je stabilní, kdy¾ dìlím pole na poloviny. Není pøi tøídìní spojových seznamù
59 s~rozdìlováním prvkù na sudé a liché.
60 \:QuickSort se dá naprogramovat stabilnì, ale potøebuje lineárnì pomocné pamìti.
61 \endlist
62
63 \>®ádný algoritmus v tabulce netøídil rychleji ne¾ $\Theta(n\log n)$. To není náhoda
64 -- nasledující vìta nám øíká, ¾e to nejde:
65
66 {\bf XXX: Letos jsem vìtu dokazoval trochu jinak, nutno pøedìlat.}
67
68 \s{Vìta:}
69 Ka¾dý tøídící algoritmus zalo¾ený na porovnávání a prohazování prvkù
70 potøebuje na vstup délky $n$ v nejhor¹ím pøípadì $\Omega (n \log n)$ porovnání.
71
72 \proof
73 Bez újmy na obecnosti budeme nejdøíve pøedpokládat o algoritmu dvì vìci:
74 Jednak to, ¾e algoritmus nejprve porovnává, a teprve potom prohazuje.\foot{Algoritmus
75 mù¾eme upravit tak, aby si pamatoval aktuální permutaci prvkù a podle ní prohazoval a¾ na konci.}
76 Také pøedpokládáme, ¾e vstup algoritmu je permutace na mno¾inì $\{1, \ldots, n\}$.
77
78 Chování tohoto algoritmu popí¹eme rozhodovacím stromem. V rozhodovacím stromu vnitøní vrcholy
79 urèují jednotlivá porovnání prvkù a listy odpovídají okam¾ikùm, kdy algoritmus pøestal porovnávat a zaèal prohazovat.
80
81 \figure{RozhodovaciStrom.eps}{Rozhodovací Strom}{0.3\hsize}
82
83 Vstup je permutace $n$ prvkù, a víme ¾e poèet rùzných permutací je $n!$. Existuje tedy právì $n!$ rùzných vstupù.
84 Dále si v¹imneme, ¾e nemohou existovat dvì vstupní permutace, pro které by algoritmus skonèil v tém¾e listu rozhodovacího stromu.
85 Listù stromu je tedy alespoò tolik, kolik je rùzných vstupù, tedy $n!$.
86
87 {\narrower
88   \s{Lemmátko:} Binární strom hloubky $k$ má nejvý¹e $2^k$ listù.
89   \par\noindent {\sl Dùkazík:} Uva¾me binární strom hloubky $k$ s maximálním poètem
90   listù. V takovém stromu budou v¹echny listy urèitì le¾et na poslední hladinì
91   (kdyby nele¾ely, mù¾eme pod nìkterý list na vy¹¹í hladinì pøidat dal¹í dva vrcholy a získat
92   tak \uv{listnatìj¹í} strom stejné hloubky). Jeliko¾ na $i$-té hladinì je nejvý¹e $2^i$
93   vrcholù, v¹ech listù je nejvý¹e $2^k$.
94   \qed
95 }
96
97 \>Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò $\log n!$.
98
99 \>Zbytek je u¾ snadné cvièení z diskrétní matematiky:
100
101 {\narrower
102   \s{Lemmátko:} $ n! \ge n^{n / 2}$.
103   \par\noindent {\sl Dùkazík:} $n! = \sqrt{(n!)^2} = \sqrt{1(n-1)\cdot 2(n-2) \cdot \ldots \cdot n\cdot 1}$,
104   co¾ mù¾eme také zapsat jako $\sqrt{1(n-1)}\cdot \sqrt{2(n-2)} \cdot \ldots \cdot \sqrt{n\cdot 1}$.
105   Pøitom pro ka¾dé $1\le k\le n$ je $k(n+1-k) = kn + k - k^2 = n + (k-1)n + k(1-k) = n + (k-1)(n-k) \ge n$.
106   Proto je ka¾dá z~odmocnin vìt¹í nebo rovna $n^{1/2}$ a $n!\ge (n^{1/2})^n = n^{n/2}$.
107   \qed
108 }
109
110 \>Hloubka stromu tedy èiní minimálnì $\log n! \ge \log(n^{n/2}) = n/2 \cdot \log n = \Omega(n\log n)$,
111 co¾ také zdola odhaduje poèet porovnání, který algoritmus provede v nejhor¹ím pøípadì.
112 \qed
113
114 Ukázali jsme si tøídìní v èase $ \O(N\log{N}) $ a také dokázali, ¾e líp to v obecném
115 pøípadì nejde. Na¹e tøídící algoritmy jsou tedy optimální (a¾ na multiplikativní konstantu).
116 Opravdu?
117
118 Pøekvapivì mù¾eme tøídit i rychleji -- vìta omezuje pouze tøídìní pomocí porovnávaní.
119 Co kdy¾ o~vstupu víme víc, tøeba ¾e je tvoøen èísly z~omezeného rozsahu.
120
121 \h{Counting sort}
122
123 Counting sort je algoritmus pro tøídìní $N$ celých èísel s maximálním rozsahem hodnot
124 $R$. Tøídí v èase $ \O(N + R) $ s~pamì»ovou nároèností $ \O(R) $.
125
126 Algoritmus postupnì prochází vstup a poèítá si ke ka¾dému prvku z~rozsahu kolikrát jej
127 vidìl. Poté a¾ projde celý vstup, projde poèítadla a indexy u~tech, kde nìco napoèítal
128 vydá jako výstup.
129
130 \s{Algoritmus:} (tøídìní posloupnosti $\left ( x_i \right )_0^N$ pomocí {\it Counting sort}u)
131
132 \algo
133 \:Pro $ i \leftarrow 1 $ do $R$ opakuj:
134 \::$ p_i \leftarrow 0 $
135 \:Pro $ i \leftarrow 1 $ do $N$ opakuj:
136 \::$ p_{x_i} \leftarrow p_{x_i} + 1 $
137 \:$ j \leftarrow 1 $
138 \:Pro $ i \leftarrow 1 $ do $R$ opakuj:
139 \::Pokud $ p_i \neq 0 $
140 \:::$ v_j \leftarrow i $
141 \:::$ j \leftarrow j + 1 $
142 \:Vra» $v$
143 \endalgo
144
145 \h{Pøihrádkové tøídìní}
146
147 Counting sort nám moc nepomù¾e, pokud chceme tøídit neco jiného ne¾ celá èísla, ale i
148 to se dá øe¹it. Pøihrádkové, popøípadì kbelíkové tøídìní, neboli bucket-sort umí
149 tøídit mno¾inu prvkù oèíslovaných èísly $ 1 \ldots R $.
150
151 \>Potøebuje k tomu èas $ \O(N + R) $ a pamì» $ \O(N + R) $.
152
153 Bucket sort ma je¹tì jednu pøíjemnou vlastnost: jedná se o stabilní tøídìní.
154
155 \s{Algoritmus:} (tøídìní mno¾iny $x_1, x_2, \ldots, x_n $ oèíslované $c_1, c_2, \ldots, c_n$ pomocí {\it bucket-sort}u)
156 \algo
157 \:$P_1 \dots P_R \leftarrow \emptyset$
158 \:Pro $i=1\dots n$:
159 \::vlo¾ $x_i$ do $P_{x_i}$
160 \:Pro $j=1\dots R$
161 \::vypi¹ co je v $P_j$
162 \endalgo
163
164 \h{Lexikografické tøídìní k-tic}
165 Mìjme $n$ uspoøádaných $k$-tic prvkù z mno¾iny $ \{1 \ldots R \}^k $. Úkol zní seøadit
166 \hbox{$k$-tice} slovníkovì (lexikograficky). Mù¾eme pou¾ít metodu rozdìl a panuj,
167 tak¾e prvky setøídíme nejprve podle první souøadnice $k$-tic a pak se rekurzivnì
168 zavoláme na ka¾dou pøihrádku a tøídíme podle následující souøadnice.
169 % a dal??
170 Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto:
171
172 \s{Algoritmus: } (tøídìní $k$-tic $ x_1, x_2, \ldots ,x_n $ lexikograficky pomocí {\it Bucket-sort}u)
173 \algo
174 \:$ S \leftarrow \{x_1, x_2, \dots, x_n\} $
175 \:Pro $ i \leftarrow k $ do $ 1 $ opakuj:
176 \::$ S \leftarrow $ bucket-sort $ S $ podle $i$-té souøadnice
177 \:vysledek $ S $
178 \endalgo
179
180 Pro pøehlednost v následujícím pozorování oznaème $ l = k - i + 1 $, co¾ pøesnì odpovídá tomu, v kolikátém prùchodu cyklu jsme.
181
182 \s{Pozorování:}
183 Po $l$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice.
184
185 \proof
186 Indukcí podle $l$:
187 \itemize\ibull
188 \:Pro $ l = 1 $ jsou prvky uspoøádány podle poslední souøadnice.
189 \:Po $l$ prùchodech ji¾ máme prvky setøídìny lexikograficky podle $i$-té a¾ $k$-té souøadnice a spou¹tíme $(l + 1)$-ní prùchod, tj. budeme tøídít podle $(i - 1)$-ní souøadnice.
190 Proto¾e bucket-sort tøídí stabilnì, zùstanou prvky se stejnou $(i - 1)$-ní souøadnicí vùèi sobì seøazeny tak, jak byly seøazeny na vstupu.
191 Z IP tam v¹ak byly seøazeny lexikograficky podle $i$-té a¾ $k$-té souøadnice. Tudí¾ po $(l + 1)$-ním prùchodu jsou prvky seøazeny podle $(i - 1)$-ní a¾ $k$-té souøadnice.
192 \endlist
193 \qed
194
195 Èasová slo¾itost je $\O( k \cdot (n + R))$, co¾ je lineární s délkou vstupu $(k \cdot n)$ pro pevné $k$; pamì»ová slo¾itost èiní $\O(n + R)$.
196
197 \h{Tøídìní èísel $ 1 \ldots R $ podruhé (Radix sort)}
198 Zvolíme základ $Z$ a èísla zapí¹eme v soustavì o základu $Z$, èím¾ získáme $ ( \lfloor \log_z{R} \rfloor +1) $-tice, na které spustíme pøedcházející algoritmus.
199 Díky tomu budeme tøídít v èase $\O({\log{R} \over \log{Z}} \cdot (n + Z))$. A jak zvolit vhodnì $Z$?
200
201 Pokud bychom zvolili $Z$ konstantní, èasová slo¾itost bude $\O(\log{R} \cdot n) $, co¾ mù¾e být $ n \log{n} $ nebo i víc.
202 Zvolíme-li $ Z = n $, dostáváme $ \O({\log{R} \over \log{n}} \cdot n) $, co¾ pro $ R \leq n^\alpha $ znamená $ \O(\alpha n) $.
203
204 \h{Tøídìní øetìzcù}
205
206 \>{\I (Na pøedná¹ce letos nebylo, ale pro úplnost uvádíme.)}
207
208 Mìjme $n$ øetìzcù $ r_1, r_2 \dots r_n $ dlouhých $ l_1, l_2 \dots
209 l_n $ Oznaème si $ L = \max_{1 \leq i \leq n} l_i $ délku nejdel¹ího øetìzce a $R$
210 poèet znakù abecedy.
211
212 Problém je, ¾e øetìzce nemusí být stejnì dlouhé (pokud by byly, lze se na øetìzce
213 dívat jako na $k$-tice, které u¾ tøídít umíme). S tím se mù¾eme pokusit vypoøádat
214 doplnìním øetìzcù mezerami tak, aby mìly v¹echny stejnou délku, a spustit na nìj
215 algoritmus pro $k$-tice. Tím dostaneme algoritmus, který bude mít èasovou slo¾itost $
216 \O(Ln) $, co¾ bohu¾el mù¾e být a¾ kvadratické vzhledem k velikosti vstupu.
217
218 Pøíklad: na vstupu mìjme k øetìzcù, kde prvních $k-1$ z nich bude mít délku $1$ a
219 poslední øetìzec bude dlouhý pøesnì $k$. Vstup má tedy celkovou délku $2k-1$ a my teï
220 doplníme prvních $k-1$ øetìzcù mezerami. Vidíme, ¾e algoritmus teï bude pracovat v
221 èase $ \O(k^2) $. To, co nám nejvíce zpùsobovalo problémy u pøedchozího pøíkladu, bylo
222 velké mno¾ství èasu zabraného porovnáváním doplnìných mezer. Zkusíme proto øe¹it ná¹
223 problem trochu chytøeji a koncové mezery do øetìzù vùbec pøidávat nebudeme.
224
225 Nejprve roztøídíme bucket-sortem øetìzce do pøihrádek (mno¾in) $ P_i $ podle jejich
226 délek, kde $i$ znaèí délku øetìzcù v dané pøihrádce, neboli definujme $ P_i = \left\{
227 r_j \vert l_j = i \right\} $. Dále si zavedeme seznam setøídìných øetìzcù $S$
228 takový, ¾e v nìm po $k$-tém prùchodu tøídícím cyklem budou øetìzce s délkou
229 alespoò $ L - k + 1 $ (oznaème $l$) a zároveò v nìm tyto øetìzce budou
230 setøídìny lexikograficky od $l$-tého znaku po $L$-tý. Z definice tohoto
231 seznamu je patrné, ¾e po $L$ krocích tøídícího cyklu bude tento seznam
232 obsahovat v¹echny øetìzce a tyto øetìzce v nìm budou lexikograficky seøazeny.
233
234 Zbývá u¾ jen popsat, jak tento cyklus pracuje. Nejprve vezme $l$-tou mno¾inu $ P_l $ a
235 její øetìzce roztøídí do pøihrádek $ Q_j $ (kde index $j$ znaèí j-tý znak abecedy)
236 podle jejich $l$-tého (neboli posledního) znaku. Dále vezme seznam $S$ a jeho øetìzce
237 pøidá opìt podle jejich $l$-tého znaku do stejných pøihrádek $ Q_j $ za ji¾ døíve
238 pøidané øetìzce z $ P_l $. Na závìr postupnì projde v¹echny pøihrádky $ Q_j $ a
239 øetìzce v nich pøesune do seznamu $S$. Proto¾e øetìzce z pøihrádek $ Q_j $ bude brát
240 ve stejném poøadí, v jakém do nich byly umístìny, a proto¾e ze seznamu $S$, který je
241 setøízený podle $ (l + 1) $-ního znaku po $L$-tý, bude také brát øetìzce postupnì,
242 bude seznam $S$ po $k$-tém prùchodu pøesnì takový, jaký jsme chtìli (indukcí bychom
243 dokázali, ¾e cyklus pracuje skuteènì správnì). Zároveò z popisu algoritmu je jasné, ¾e
244 bìhem tøídìní ka¾dý znak ka¾dého øetìzce pou¾ijeme právì jednou, tudí¾ algoritmus bude
245 lineární s délkou vstupu (pro úplnost dodejme, ¾e popsaný algoritmus funguje v
246 pøípadech, kdy abeceda má pevnou velikost).
247
248 Algoritmus: (tøídìní øetìzcù)
249 \algo 
250 \:$L \leftarrow \max(l_1, l_2,\ldots,l_n)$
251 \:Pro $ i \leftarrow 1 $ do $L$ opakuj:
252 \::$ P_i \leftarrow \emptyset $
253 \:Pro $ i \leftarrow 1 $ do $ n $ opakuj:
254 \::$ \<pridej>(P_{l_i}, r_i) $
255
256 \:$ S \leftarrow \emptyset $
257 \:Pro $ i \leftarrow L $ do $ 1 $ opakuj:
258 \::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
259 \:::$ Q_j \leftarrow \emptyset $
260
261 \::Pro $ j \leftarrow 1 $ do velikost($P_i$) opakuj:
262 \:::$ \<vezmi>(P_i, r) $
263 \:::$ \<pridej>(Q_{r[i]}, r) $
264 \::Pro $ j \leftarrow 1 $ do velikost($S$) opakuj:
265 \:::$ \<vezmi>(S, r) $
266 \:::$ \<pridej>(Q_{r[i]}, r) $
267
268 \::$ S \leftarrow \emptyset $
269 \::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
270 \:::Pro $ k \leftarrow 1 $ do velikost($Q_j$) opakuj:
271 \::::$ \<vezmi>(Q_j, r) $
272 \::::$ \<pridej>(S, r) $
273
274 \:výsledek $S$
275 \endalgo
276
277 Èasová slo¾itost tohoto algoritmu tedy bude $ \O(RN) $, kde $N$ je délka vstupu a $R$ poèet znakù abecedy.
278
279 \h{Zoo tøídících algoritmù podruhé}
280
281 \>Doplòme tedy na¹i tabulku:
282
283 \medskip
284
285 \settabs 4 \columns
286 \+              & \<Èas>                & \<Pomocná pamì»>      & \<Stabilní> \cr
287 \smallskip
288 \+ InsertSort   & $\Theta (n^2)$        & $\Theta (1)$          & $+$ \cr
289 \+ MergeSort    & $\Theta (n\log n)$    & $\Theta (n)$          & $+$ \cr
290 \+ HeapSort     & $\Theta (n\log n)$    & $\Theta (1)$          & $-$ \cr
291 \+ QuickSort    & $\Theta (n\log n)$    & $\Theta (\log n)$     & $-$ \cr
292 \+ BucketSort   & $\Theta (n+R)$        & $\Theta (n+R)$        & $+$ \cr
293 \+ k-tice       & $\Theta (k(n+R))$     & $\Theta (n+R)$        & $+$ \cr
294 \+ RadixSort    & $\Theta (n\log _n R)$ & $\Theta (n)$          & $+$ \cr
295
296 \smallskip
297
298 \h{K èemu je vlastnì tøídìní dobré?} Díky nìmu mù¾eme rychle vyhledávat prvky v
299 mno¾inì, konkrétnì v èase $ \O(\log n) $ napø. pomocí pùlení intervalù. Dal¹ím
300 problémem, na který se hodí pou¾ít tøídìní, je zji¹tìní, zda se v posloupnosti nìjaké
301 její hodnoty opakují. Dá se dokázat, ¾e tuto úlohu nelze vyøe¹it lépe (rychleji), ne¾
302 tak, ¾e hodnoty nejprve setøídíme a poté setøidìnou posloupnost projdeme.
303
304 \h{Násobení matic n$\times$n a Strassenùv algoritmus}
305
306 Nejdøíve si pøipomeneme definici násobení dvou ètvercových matic typu $n \times n$.
307 Platí, ¾e prvek v $i$-tém øádku a $j$-tém sloupci výsledné matice $Z$ se rovná
308 standardnímu skalárnímu souèinu $i$-tého øádku první matice $X$ a $j$-tého sloupce
309 druhé matice~$Y$. Formálnì zapsáno:
310
311 $$ Z_{ij} = \sum_{k=1}^n X_{ik} \cdot Y_{kj}. $$
312
313 \figure{nasobeni-matic.eps}{Násobení matic}{\epsfxsize}
314
315 Algoritmus, který by násobil matice podle této definice, by mìl èasovou slo¾itost $
316 \Theta(n^3) $, proto¾e poèet prvkù ve výsledné matici je $n^2$ a jeden skalární souèin
317 vektorù dimenze $n$ vy¾aduje lineární poèet operací.
318
319 My se s touto èasovou slo¾itostí ov¹em nespokojíme a budeme postupovat podobnì jako
320 pøi vylep¹ování algoritmu na násobení velkých èísel. Bez újmy na obecnosti
321 pøedpokládejme, ¾e budeme násobit dvì matice typu $n \times n$, kde $n=2^k, k \in \bb
322 N$. Obì tyto matice rozdìlíme na ètvrtiny a tyto èásti
323 postupnì oznaèíme u matice $X$ písmeny $A$, $B$, $C$ a $D$, u matice $Y$ písmeny $P$,
324 $Q$, $R$ a $S$. Z~definice násobení matic zjistíme, ¾e ètvrtiny výsledné matice $Z$
325 mù¾eme zapsat pomocí souèinù èástí násobených matic. Levá horní ètvrtina bude
326 odpovídat výsledku operací $AP+BR$, pravá horní ètvrtina bude $AQ+BS$, levá dolní
327 $CP+DR$ a zbylá $CQ+DS$ (viz obrázek).
328
329 \figure{nasobeni-matic-2.eps}{Násobení rozètvrcených matic}{\epsfxsize}
330
331 Pøevedli jsme tedy problém násobení ètvercových matic øádu $n$ na násobení ètvercových
332 matic øádu ${n/2}$. Tímto rozdìlováním bychom mohli pokraèovat, dokud bychom se
333 nedostali na matice øádu 1, jejich¾ vynásobení je triviální. Dostali jsme tedy
334 klasický algoritmus typu {\it rozdìl a panuj}. Pomohli jsme si ale nìjak? V ka¾dém
335 kroku provádíme 8 násobení matic polovièního øádu a navíc konstantní poèet operací na
336 $n^2$ prvcích. Dostáváme tedy rekurentní zápis èasové slo¾itosti:
337
338 $$ T(n) = 8T\left({n \over 2}\right) + \Theta(n^2). $$
339
340 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:
341
342 $$ T(n) = 7T\left({n \over 2}\right) + \Theta(n^2) \Longrightarrow \Theta(n^{\log_2 7}) = \O(n^{2.808}). $$
343
344 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.
345
346 \s{Lemma:} (vzorce pro násobení blokových matic ve~Strassenovì algoritmu)
347
348 \def\\{\noalign{\vskip 7pt}}
349
350 $$
351 \pmatrix{A & B \cr\\ C & D \cr}
352 \cdot
353 \pmatrix{P & Q \cr\\ R & S \cr}
354 =
355 \pmatrix{
356 T_1 + T_4 - T_5 + T_7 &
357 T_3 + T_5 \cr\\
358 T_2 + T_4 &
359 T_1 - T_2 + T_3 + T_6 \cr
360 },$$
361
362 kde:
363
364 $$\vbox{\halign{$#$\hfil\qquad &$#$\hfil\qquad \cr
365 T_1 = (A+D)\cdot(P+S)           & T_5 = (A+B)\cdot S \cr\\
366 T_2 = (C+D)\cdot P              & T_6 = (C-A)\cdot (P+Q) \cr\\
367 T_3 = A\cdot(Q-S)               & T_7 = (B-D)\cdot (R+S) \cr\\
368 T_4 = D\cdot(R-P)                                        \cr
369 }}$$
370
371 \medskip
372
373 \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.
374
375 \def\bbb#1{\vbox to 10pt{\vss\hbox to 10pt{\hss\tenrm #1\hss}\vss}}
376 \def\bb#1{\ifx#1.\bbb{$\cdot$}\else\bbb#1\fi}
377 \def\zz#1#2#3#4{\bb#1\bb#2\bb#3\bb#4}
378 \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}}}}}
379
380 $$
381 T_1 = \qq{+..+}{....}{....}{+..+} \qquad
382 T_2 = \qq{....}{....}{+...}{+...} \qquad
383 T_3 = \qq{.+.-}{....}{....}{....} \qquad
384 T_4 = \qq{....}{....}{....}{-.+.}
385 $$
386 $$
387 T_5 = \qq{...+}{...+}{....}{....} \qquad
388 T_6 = \qq{--..}{....}{++..}{....} \qquad
389 T_7 = \qq{....}{..++}{....}{..--}
390 $$
391
392 \medskip
393
394 \def\\{\noalign{\vskip 7pt}}
395 $$
396 \eqalign{
397 T_1 + T_4 - T_5 + T_7 &= \qq{+...}{..+.}{....}{....} = AP + BR \cr\\
398 T_3 + T_5 &= \qq{.+..}{...+}{....}{....} = AQ + BS \cr\\
399 T_2 + T_4 &= \qq{....}{....}{+...}{..+.} = CP + DR \cr\\
400 T_1 - T_2 + T_3 + T_6 &= \qq{....}{....}{.+..}{...+} = CQ + DS \cr
401 }
402 $$
403
404 % konec slidu z prednasky
405
406 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:
407
408 \s{Vìta:}
409 Strassenùv algoritmus pro násobení matic $n \times n$ má èasovou slo¾itost
410 v nejhor¹ím pøípadì $\O(n^{2.808})$. \qed
411
412 \s{Poznámka:}
413 Zatím nejlep¹í dokázaný algoritmus má èasovou slo¾itost $\O(n^{2.376})$, leè s velkou multiplikativní konstantou.
414
415 \h{Dosa¾itelnost v grafech pomocí Strassenova algoritmu}
416
417 Matice mohou souviset s mnoha na první pohled nesouvisejícími problémy.
418
419 \s{Lemma:} Nech» $A$ je matice sousednosti grafu, nech» $S^{(k)}_{z,j}$
420 oznaèíme poèet sledù délky~$k$ z vrcholu~$j$ do vrcholu $i$. Pak $S^{(k)}=A^k$.
421
422 \proof
423 Indukcí podle~$k$:
424
425 \itemize\ibull
426 \:$S^{(1)}=A$
427 \:$S^{(k+1)}_{i,j}=\sum_{z:(i, z)\in E(G)} S^{(k)}_{z, j} = \sum _{z=1}^n A_{i, z}
428 S_{z, j}^{(k)}=(AS^{(k)})_{i, j}$
429 \endlist
430 \qed
431
432 Pøidáním smyèek do matice $A$ zjistíme dostupnost vrcholù po cestách dlouhých $k$ nebo
433 krat¹ích.
434
435 Staèí tedy spoèítat matici $B=(A+E)^k$ pro libovolné $k\geq n$ ($E$ je jednotková matice).
436 Pak $B_{i,j}\neq 0$ právì kdy¾ existuje cesta z vrcholu $i$ do vrcholu $j$.
437
438 Pro vypoèítání $B$ nám staèí $\lceil \log n \rceil$ umocnìní matice na druhou, co¾ je
439 speciální pøípad násobení matic. Èasová slo¾itost celého algoritmu tedy èiní $\O(n^{\log _2 7} \cdot \log n)$.
440
441 Musíme v¹ak dávat pozor a normovat èísla (nulu necháme, nenulová nahradíme pøi ka¾dém
442 násobení jednièkou), aby nám nepøerostla pøes hlavu a hlavnì pøes maximální
443 integer.
444
445 \bye