2-ram/2-ram.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{2}{Slo¾itost, grafové algoritmy}
   4 {(zapsal Martin Koutecký)}
   5
   6 \h{Model {\sc Ram}}
   7
   8 Pøi analýze algoritmu bychom chtìli nìjak popsat jeho slo¾itost. Abychom mohli
   9  udìlat toto, potøebujeme nejprve definovat výpoèetní model. Výpoèetních modelù
  10 je více, my vybereme jeden pomìrnì blízký skuteèným poèítaèùm:
  11
  12 \s{Definice:} Random Access Machine ({\sc Ram})
  13
  14 {\sc Ram} poèítá jen s èísly -- znaky, stringy a podobnì reprezentujeme
  15 èísly, jejich posloupnostmi atd. Pamì» je tvoøena buòkami, které obsahují
  16 èísla. Pamì»ové buòky jsou adresované takté¾ èísly. A program samotný je
  17 koneèná posloupnost instrukcí následujících druhù:
  18 \itemize\ibull
  19 \:Aritmetické a logické:
  20 $X \leftarrow Y \oplus Z, \oplus\in\{+, -, \times, \div,\mod, \&\&, \|, <<,
  21 >>\}$
  22 \:Skoky: goto LABEL
  23 \:Podmínky: pro libovolnou nepodmínìnou instrukci mù¾u pou¾ít
  24 if~$X~<~Y~\Rightarrow$~instrukce
  25 \:Øídící: goto, halt.
  26 \endlist
  27
  28 \s{Poznámka} (operandy):
  29 \itemize\ibull
  30 \:Konstanty (1,2,\dots)
  31 \:Adresované pøímo - M[konst.] -- budeme pou¾ívat písmena A-Z jako aliasy pro
  32 registry -1 a¾ -26
  33 (tedy A=M[-1])
  34 \:Adresované nepøímo -- M[M[konst.]] - budeme pou¾ívat zkratku [[konst.]]
  35 \endlist
  36
  37 Samotný výpoèet probíhá takto:
  38 \algo
  39 \:Do smluvených bunìk umístíme vstup, obsah zbylých pamì»ových bunìk není
  40 definován.
  41 \:Provádíme program postupnì po instrukcích, dokud nedojdeme k haltu nebo konci
  42 programu.
  43 \:Pokud se program nezacyklil, tedy pokud skonèil, ze smluvených bunìk pøeèteme
  44 výstup.
  45 \endalgo
  46
  47
  48 \h{Slo¾itost}
  49 Jak dobøe popsat slo¾itost?
  50 \numlist\ndotted
  51 \:{\sc Ram} s jednotkovou cenou: èas $\approx$ \#instrukcí, prostor $\approx$
  52 maximální èíslo buòky minus minimální èíslo buòky pou¾ité pøi výpoètu.
  53 Toto není moc dobrý nápad, proto¾e není nijak penalizována napøíklad práce s
  54 velmi dlouhými èísly -- poøád je to jedna instrukce, tak¾e cena je stejná, ale
  55 poèítaèe se tak pøece nechovají. Velikost èísel ale omezit nesmíme, proto¾e
  56 bychom omezili pamì» (èísly ji adresujeme).
  57 \:{\sc Ram} s logaritmickou cenou: èas $\approx$ \#bitù zpracovávaných èísel,
  58 prostor $\approx$ \# bitù v¹ech pou¾itých bunìk. To je teoreticky pøesné, ale
  59 dost nepraktické (ve v¹ech slo¾itostech by byly logaritmy).
  60 \:{\sc Ram} s omezenými èísly: jednotková cena instrukcí, ale èísla omezíme na
  61 $\leq P(n)$, $P(n)$ je polynom. Tím zmizí paradoxy prvního modelu, ale mù¾eme
  62 adresovat jen polynomiální prostor (to nám obvykle nevadí).
  63 \endlist
  64
  65 % Z minulých zápiskù.
  66 \s{Definice:}
  67 \itemize\ibull
  68 \:{\I Èas bìhu algoritmu} $t(x)$ pro vstup~$x$ mìøíme jako poèet
  69 elementárních operací, které program provedl pøi zpracování vstupu
  70 $x$.
  71 \:{\I Prostor bìhu algoritmu} $s(x)$ je analogicky poèet pamì»ových
  72 bunìk spotøebovaných pøi výpoètu se vstupem~$x$.
  73 \:{\I Èasová slo¾itost} (v~nejhor¹ím pøípadì) je:
  74 $$T(n) := \max \{t(x) ; \hbox{$x$ je vstup délky $n$}\}.$$
  75 \:{\I Prostorová slo¾itost} (v~nejhor¹ím pøípadì) je:
  76 $$S(n) := \max \{s(x) ; \hbox{$x$ je vstup délky $n$}\}.$$
  77 \endlist
  78
  79 Nyní zkusíme zanalyzovat nìjaký konkrétní algoritmus. Vezmìme napøíklad øazení
  80 pomocí pøímeho výbìru (selection sort). Na vstupu dostaneme v registru N poèet
  81 èísel, v buòkách 1\dots n je nesetøídìná posloupnost èísel. Ty pak tøídíme
  82 následujícím algoritmem zapsaném v pseudokódu:
  83 \algo
  84 \:Pro $i=1$ do $n$:
  85 \::$j\leftarrow i$
  86 \::Pro $k=i$ do $n$:
  87 \:::Je-li $[k]<[j]\Rightarrow j\leftarrow k$
  88 \::$[i]\leftrightarrow[j]$
  89 \endalgo
  90
  91 Jak by takový algoritmus vypadal zapsaný v instrukcích {\sc Ram}? Budeme muset
  92 pou¾ít návì¹tí a goto místo cyklù, jména registrù místo promìnných a
  93 tøeba prohození  musíme provést pøes tøetí promìnnou. Nìjak takto:
  94
  95 %Tady vá¾nì nevím jak formátovat, aby to bylo hezké. Nejvíce by se mi líbil
  96 % verbatim, ale jak v nìm udìlat rozumnì ¹ipeèky? Tøeba => a <- ?
  97 \verbatim{
  98         I <- 1
  99 LOOP:   J <- I
 100         M <- I
 101 MIN:    IF [J]<[M] ==> M <- J
 102         J <- J+1
 103         IF J<=N ==> GOTO MIN
 104         X <- [I]
 105         [I] <- [M]
 106         [M] <- X
 107         I <- I+1
 108         IF I<=N ==> GOTO LOOP
 109 }
 110
 111
 112 Pojïme se podívat, jaká je èasová slo¾itost jednotlivých èástí algoritmu.
 113 Cyklus MIN provede $3\cdot (N-I+1)$ instrukcí. Mimo cyklu MIN je v LOOP je¹tì 7
 114 instrukcí, tedy celý LOOP provede $3\cdot (N-I+1)+7$ instrukcí. Celkovì se
 115 dostáváme k souètu
 116 $$1+3\cdot N+7+3\cdot (N-1)+7+3\cdot (N-2)+7+3\cdot (N-3)+\dots +3\cdot 1+7 =$$
 117 $$1+7\dots N+3\dots {{N(N+1)}\over{2}} = {{3}\over{2}}N^2 + 8,5N + 1$$
 118
 119 Na multiplikativních konstantách ale nezále¾í -- zaprvé se na reálných strojích
 120 ceny jednotlivých (pro nás jednotkových) instrukcí stejnì li¹í, zadruhé
 121 asymptoticky pomalej¹í funkce stejnì pro velké N v¾dy prohraje, tak¾e nemá cenu
 122 (alespoò pøi prvním pøiblí¾ení k problému) multiplikativními konstantami se
 123 zabývat. Tím pádem nezále¾í ani na èlenech ni¾¹í øádù:
 124 $$1,5N^2 + 8,5N + 1 \leq 1,5N^2 + 8,5N^2 + N^2 = 11N^2\approx N^2$$
 125 Kdy¾ u¾ toto víme, mù¾eme zanedbávat konstanty prùbì¾nì: $N$ cyklù po
 126 $\approx~N$~krocích $\Rightarrow~\approx~N^2$ krokù. To nás vede k zavedení tzv.
 127 {\I asymptotické notace}
 128
 129 \h{Asymptotická notace}
 130 % Okopírováno z minulých zápiskù, lehké opravy, na konci ukazujeme select sort
 131 % místo E.A.
 132 \s{Definice:} Pro funkce $f,g: {\bb N} \rightarrow {\bb R}^+$ øekneme,
 133 ¾e $f$ je $\O(g)$ právì tehdy, kdy¾ $\exists c>0: \forall ^{*} n \in {\bb N}:
 134 f(n) \leq c \cdot g(n)$.
 135 Zde $\forall^* n \in {\bb N}$ je zkratka za \uv{$\exists n_0 \in {\bb N}:
 136 \forall n \geq n_0$}, tedy
 137 \uv{pro v¹echna~$n$ a¾ na~koneènì mnoho výjimek.}
 138
 139 \s{Poznámka:} $\O$-notace tedy vyjadøuje, ¾e funkce~$f$ je skoro v¹ude men¹í
 140 nebo nejvý¹e rovná nìjakému reálnému násobku funkce~$g$. Aèkoliv zápis vypadá
 141 jako rovnost, rozhodnì není symetrický: napøíklad platí $\log n=\O(n)$, ale
 142 neplatí $n=\O(\log n)$. Formálnì by bylo lep¹í pova¾ovat $\O(g)$ za tøídu
 143 funkcí, pro které platí, ¾e se dají shora odhadnout kladným násobkem funkce~$g$,
 144 a~psát tedy~$f\in\O(g)$, ale zvyk je bohu¾el ¾elezná ko¹ile.
 145
 146 \s{Pøíklady:} $2.5n^{2} = \O(n^{2})$, $2.5n^{2}+30n = \O(n^{2})$.
 147
 148 \>Také platí:
 149 $$
 150 \O(f)+\O(g) \in \O(f+g),
 151 $$
 152 èím¾ myslíme, ¾e pokud vezmeme libovolnou $f'=O(f)$ a $g'=O(g)$, bude
 153 $f'+g'=O(f+g)$.
 154 To platí, jeliko¾ skoro v¹ude je $f' \leq cf$, $g'\leq dg$, a~tedy $f'+g' \le
 155 cf+dg \le (c+d)(f+g)$.
 156
 157 \s{Cvièení:} Uka¾te, ¾e:
 158 \itemize\ibull
 159 \:$\O(f) \cdot \O(g)=\O(f \cdot g)$,
 160 \:$\O(f+g)=\O(\max(f,g))$,
 161 \:$\O(n^{2})+\O(n)=\O(n^{2}+n)=\O(n^{2})$.
 162 \endlist
 163
 164 $\O$-notace popisuje horní odhad asymptotického chování funkce. Mnohdy v¹ak
 165 potøebujeme také odhadnout funkci zespodu (chceme-li øíci, ¾e algoritmus
 166 potøebuje {\I alespoò} nìjaké mno¾ství èasu nebo pamìti), pøípadnì z~obou stran:
 167
 168 \s{Definice:}
 169
 170 \itemize\ibull
 171 \:$f=\Omega(g) \equiv \exists c>0:\forall^* n \in {\bb N}: f(n) \geq c\cdot
 172 g(n)$.
 173
 174 $\Omega$-notace tedy øíká, ¾e hodnota funkce $f$ je v¾dy stejná nebo vy¹¹í ne¾
 175 nìjaký $c$-násobek funkce $g$, a tedy $g=\O(f)$.
 176 \:$f=\Theta(g) \equiv f=O(g) \wedge f=\Omega(g)$
 177
 178 nebo výøeènìji:
 179
 180 $f=\Theta(g) \equiv \exists$ $c_{1},c_{2} > 0: c_{1}\cdot g(n) \leq f(n) \leq
 181 c_{2}\cdot g(n)$ To znamená, ¾e existují nezáporné reálné konstanty
 182 $c_{1},c_{2}$ takové, ¾e se funkce $f(n)$ dá ohranièit $c_{1}$- a
 183 $c_{2}$-násobkem funkce $g(n)$.
 184 \endlist
 185
 186 \s{Porovnání rùstu funkcí:} (aneb jak moc máme algoritmy rádi podle jejich
 187 chování od~nejlep¹ích k~nejhor¹ím)
 188
 189 \itemize\ibull
 190 \:$\Theta(1) \ldots$ funkce zespoda i shora ohranièené konstantami
 191 \:$\Theta(\log{( \log{n} )})$
 192 \:$\Theta(\log{n})$ \dots\ logaritmická
 193 \:$\Theta(n^{\varepsilon}), \varepsilon \in (0,1)$ \dots\ sublineární
 194 \:$\Theta(n)$ \dots\ lineární
 195 \:$\Theta(n^{2})$ \dots\ kvadratická
 196 \:$\Theta(n^{k})$ \dots\ polynomiální
 197 \:$\Theta(2^{n})$ \dots\ exponenciální pøi základu $2$
 198 \:$\Theta(3^{n})$ \dots\ exponenciální pøi základu $3$
 199 \:$\Theta(k^{n})$ \dots\  exponenciální pøi základu $k>1$
 200 \:$\Theta(n!)$ \dots\ faktoriálová
 201 \:$\Theta(n^{n})$
 202 \:\dots\ nekoneènì mnoho dal¹ích tøíd (i mezi tìmi vý¹e uvedenými)
 203 \endlist
 204
 205 \>{\sl Poznámka:} Pokud se v~odhadu slo¾itosti vyskytne logaritmus (jinde ne¾
 206 v~exponentu), nezále¾í na tom, jaký má základ, proto¾e platí:
 207 $$
 208 \log_k{n}={{\log_c{n}}\over{\log_c{k}}}={{1}\over{\log_c{k}}}\cdot \log_c{n},
 209 $$
 210 kde $1/\log_c{k}$ je jen konstanta, tak¾e ji mù¾eme \uv{schovat do~$\O$.}
 211
 212 \s{Pøíklad:} Select sort (rozebraný vý¹e):
 213 Kdy¾ jej pustíme na $n$ èísel, pak èasová slo¾itost je $T(n) = \Theta(n^2)$ a
 214 prostorová $S(n) = \Theta(n)$.
 215
 216 \h{Úvod do grafových algoritmù}
 217 Dal¹í dùle¾itou a zajímavou kapitolou jsou grafové algoritmy. Napøíklad
 218 následující pøíklady lze (i kdy¾ to tak obèas na první pohled nevypadá) øe¹it
 219 nìjakým grafovým algoritmem:
 220 \itemize\ibull
 221 \:Mám mapku silnièní sítì, v ní oznaèené \uv{Doma} a \uv{©kola}. Dostanu se do
 222 ¹koly (le¾í ve stejné komponentì souvislosti)? Dostanu se do ¹koly, kdy¾ v zimì
 223 napadne hodnì snìhu a nìkteré cesty budou neprùjezdné? A jaký nejkrat¹í úsek
 224 cest musí silnièáøi prohrnout, aby byla v¹echna místa na mapì dostupná?
 225 \:Mìjme hlavolam \uv{Lloydova devítka} -- krabièku $3\times3$ s ètvereèky
 226 oznaèenými èísly od jedné do osmi a jednou mezerou, ètvereèky jsou zamíchané a
 227 na¹ím úkolem je správnì je seøadit. Jak to udìlat? Kolik nejménì krokù nám na
 228 to staèí? Jde to vùbec se zadáním, které jsme dostali?
 229 \:Jaké je nejkrat¹í (kladné, celé) èíslo v desítkové soustavì zapsané jen
 230 èíslicemi 1, 0 dìlitelné tøemi? Nakreslíme orientovaný graf s vrcholy 1 a¾ 13
 231 a hranami $(x,y),$ $y=10\cdot x \mod 13$ a $y=(10\cdot x + 1) \mod 13$ (z
 232 ka¾dého vrcholu vychází jedna hrana za pøidání èíslice 1 a dal¹í za èíslici 0).
 233 Hledané èíslo existuje právì tehdy, kdy¾ graf obsahuje orientovaný sled z 0 do
 234 1. Jakým algoritmem takový sled najdeme?
 235 \endlist
 236 Podobné a dal¹í úlohy budeme øe¹it v následujících kapitolách.
 237
 238 \bye