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