2007/1-euklid/1-euklid.tex

   1 \input ../lecnotes.tex
   2 \input epsf.tex
   3
   4 \def\N{N}
   5
   6 \prednaska{1}{Eukleidùv algoritmus}{(zapsaly T.~Klimo¹ová a K.~B\"ohmová)}
   7
   8 \h{}
   9 \>{\bf Problém hledání nejvìt¹ího spoleèného dìlitele }
  10
  11 Cílem je najít nejvìt¹ího spoleèného dìlitele zadaných èísel
  12 $a_0, b_0 \in \N $, dále jen $\gcd(a_0, b_0)$, tedy Greatest Common
  13 Divisor.
  14
  15 \s{Algoritmus:} (Eukleidùv algoritmus verze $1.0$; snad 200 let pøed Eukleidem)
  16
  17 \algo
  18 \algin èísla $a_0$, $b_0$.
  19 \:$a\leftarrow a_0, b\leftarrow b_0$.
  20 \:while $a\not=b$ :
  21 \::if $a > b \Rightarrow a \leftarrow a-b $
  22 \::\rlap{else}\phantom{if }$\phantom{a > b} \Rightarrow b \leftarrow b-a $
  23 \algout $a=\gcd(a_0,b_0)$.
  24 \endalgo
  25
  26 \noindent{\sl Dùkaz správnosti: }
  27
  28 \>{\bo 1) EA se zastaví}
  29
  30 V ka¾dém prùchodu cyklem se buï $a$ zmen¹í o hodnotu $b$ anebo se $b$ zmen¹í o~hodnotu $a$. Proto souèet $a+b$ klesne poka¾dé alespoò o $1$. Tedy celkem
  31 se uskuteèní nanejvý¹ $a+b$ prùchodù cyklem a pak algoritmus skonèí.
  32
  33 \>{\bo 2) EA vydá $\gcd(a_0, b_0)$}
  34
  35 Pøi dùkazech správnosti algoritmu se èasto pou¾ívá {\I invariant.}
  36 To je nìco, co se v prùbìhu algoritmu nemìní (obvykle hodnota nìjakého výrazu nebo jeho vlastnost, napø. dìlitelnost dvìma).
  37
  38 Doká¾eme, ¾e platí invariant: $\gcd(a, b) = \gcd(a_0, b_0)$.
  39
  40 Algoritmus pøi svém bìhu postupnì mìní hodnoty $a$ a $b$.
  41 Tedy
  42 $(a_0, b_0) \rightarrow (a_1, b_1) \rightarrow
  43 \dots \rightarrow (a_k, b_k)$.
  44 A jakmile je splnìna rovnost $a_k = b_k$, tak skonèí.
  45 My chceme ukázat, ¾e platí
  46 $\gcd(a_0, b_0) = \gcd(a_1, b_1) = \dots = \gcd(a_k, b_k)$.
  47
  48 K~tomu bude tøeba nìkolik pozorování:
  49
  50 \>{\I Pozorování 1:} $\gcd(a, a) = a$ (pro $a>0$).
  51
  52 Nahlédneme snadno. Nejvìt¹í spoleèný dìlitel jediného èísla je ono samo.
  53
  54 \>{\I Pozorování 2:} $\gcd(a, b) = \gcd(b, a)$.
  55
  56 Takté¾ jednoduché. Pøi urèování nejvìt¹ího spoleèného dìlitele
  57 nám na poøadí èísel nezále¾í.
  58
  59 \>{\I Pozorování 3:} $\gcd(a, b) = \gcd(a \pm b, b)$.
  60
  61 %%Rozmyslíme si, ¾e a¾ doká¾eme {\I Pozorování 3 }, máme vyhráno.
  62
  63 Doká¾eme silnìj¹í vìc -- platnost ekvivalence
  64 $k\vert a, k\vert b \Leftrightarrow k\vert a, k\vert(a\pm b)$.
  65
  66 \>$\Rightarrow$:  Jeliko¾ $k\vert a, k\vert b$, dá se $a$ vyjádøit jako $k$-násobek nìjakého $a'$. Tedy $a = k\cdot a'$.
  67 Obdobnì $b = k\cdot b'$, pro nìjaká èísla  $a',b'\in \N$.
  68 Tak¾e souèet $a\pm b$ si mù¾eme rozepsat jako $(a'\pm b')\cdot k$ z èeho¾ je
  69 ji¾ vidìt, ¾e $k\vert(a\pm b)$.
  70
  71 \>$\Leftarrow$: Podobnì $k\vert (a\pm b), k\vert b \Leftrightarrow k\vert a$.
  72
  73 Uvìdomíme si, ¾e tato tøi pozorování nám staèí k tomu, aby invariant
  74 platil. Algoritmus tedy opravdu vydá $\gcd(a_0,b_0)$.
  75 \qed
  76
  77 \goodbreak
  78
  79 \>{3) \bo Rychlost algoritmu}
  80
  81 Algoritmus provede v~nehor¹ím pøípadì øádovì $a+b$ iterací. To je velmi pomalé,
  82 a proto vyvstává otázka, dá-li se nìjak zrychlit.
  83
  84 V¹imnìme si, ¾e opakované odèítání jednoho èísla od~druhého lze nahradit výpoètem
  85 zbytku po~dìlení. Algoritmus tedy mu¾eme upravit následovnì:
  86
  87 \s{Algoritmus:} (Eukleidùv alg. v$2.0$; neznámý Eukleidùv pokraèovatel, neznámo kdy)
  88
  89 \algo
  90 \algin èísla $a_0$, $b_0$.
  91 \:$a\leftarrow a_0, b\leftarrow b_0$.
  92 \:while $b \neq 0$:
  93 \::$a \leftarrow a \mod b$
  94 \::$a \leftrightarrow b$
  95 \algout $a=\gcd(a_0,b_0)$.
  96 \endalgo
  97
  98 \>{\sl Dùkaz správnosti: }
  99
 100 Algoritmus urèitì vydá správný výsledek, proto¾e poèítá toté¾, co pøedchozí verze.
 101 Uká¾eme, ¾e poèet krokù, který provede verze 2.0, je øádovì $\log(\max(a,b))$.
 102 K~tomu se nám bude hodit následující:
 103
 104 {\narrower
 105 \s{Lemma:}  Za dva prùchody cyklem se buï hodnota $a$ nebo hodnota $b$
 106 zmen¹í alespoò dvakrát.
 107
 108 \proof
 109 Rozebereme, co se stane po dvojím projití cyklem.
 110 Na zaèátku máme èísla $a_0$ a $b_0$. Bez újmy na obecnosti pøedpokládejme,
 111 ¾e $a_0>b_0$. Po~prvním prùchodu získáme $a_1=b_0; b_1=a_0 \mod b_0$, co¾ je ménì
 112 ne¾ $b_0$. Po druhém prùchodu: $a_2=b_1; b_2=a_1 \mod b_1 = b_0 \mod b_1$. Chceme
 113 ukázat, ¾e kdy¾ je $b_1 < b_0$, tak $b_0 \mod b_1 \leq b_0/2$.
 114
 115 \itemize\ibull
 116 \:Buï platí $b_1 \leq b_0/2$. Pak jistì $b_0 \mod b_1 < b_1 \leq b_0/2.$
 117 \:Nebo nastane druhá mo¾nost  $b_1 >  b_0/2$.
 118 Pak tedy $b_0 \mod b_1 = b_0-b_1$, co¾ je takté¾ maximálnì $b_0/2$.
 119 \qed
 120 \endlist
 121
 122 }
 123
 124 Nyní staèí lemma ¹ikovnì vyu¾ít:
 125 Dvojic prùchodù, které zmen¹ují hodnotu $a$, je nejvý¹e $\lceil \log_2
 126 a \rceil$. Obdobnì tìch sni¾ujících hodnotu $b$ je nejvý¹e $\lceil \log_2 b \rceil$.
 127 Celkový poèet prùchodù tedy je nejvý¹e $2(\lceil \log_2 a \rceil+\lceil
 128 \log_2 b\rceil)$.
 129
 130 Je¹tì bychom chtìli dokázat, ¾e ná¹ horní odhad na~poèet prùchodù není pøíli¹
 131 velkorysý. Zkusme se podívat, co se stane, kdy¾ algoritmus necháme spoèítat
 132 $\gcd(F_n, F_{n-1})$, kde~$F_i$ je $i$-té Fibonacciho èíslo. Tehdy v¹echna
 133 modula budou ve~skuteènosti odèítání a algoritmus bude poèítat
 134 $\gcd(F_n, F_{n-1}) \rightarrow \gcd(F_{n-1}, F_{n-2}) \rightarrow
 135 \dots \rightarrow \gcd(1, 1)$.
 136
 137 Díky exponenciální velikosti Fibonacciho èísel tento výpoèet bude
 138 opravdu trvat logaritmicky dlouho vzhledem k~velikosti vìt¹ího ze
 139 zadaných èísel.
 140 (Zároveò je to také pìkný dùkaz toho, ¾e Fibonacciho èísla jsou
 141 navzájem nesoudìlná.)
 142
 143 \h{Výpoèetní model}
 144 Kdy¾ chceme studovat algoritmy, mìli bychom se zaèít zaobírat otázkou, co takový algoritmus vlastnì je.
 145 ®ádná obecnì uznávaná definice algoritmu neexistuje, nadefinujeme si proto alespoò výpoèetní model
 146 a za~algoritmy budeme pova¾ovat programy v tomto modelu.
 147
 148 \s{Základní vlastnosti výpoèetního modelu:}
 149
 150 V první øadì potøebujeme modelu sdìlit, s èím má pracovat, a pak se
 151 dovìdìt, jak to dopadlo. Bez újmy na obecnosti mù¾eme pova¾ovat $n$
 152 èísel za {\sl vstup} a za {\sl výstup} $m$ èísel $($mù¾eme se omezit
 153 na èísla, nebo» cokoli jiného umíme do èísel zakódovat$)$.
 154
 155 Dále by mìl výpoèetní model umìt provádìt {\sl elementární operace},
 156 co¾
 157 jsou nejen ty aritmetické $(+,-,*,/,{\rm mod}, \dots)$ a logické (negace,
 158 and, or, \dots), ale také øídící operace (skoky, podmínìné skoky, halt,
 159 \dots) a práci s pamìtí.
 160
 161 \s{Definice:}
 162 \itemize\ibull
 163 \:{\I Èas bìhu algoritmu} $t(x)$ pro vstup~$x$ mìøíme jako poèet
 164 elementárních operací, které program provedl pøi zpracování vstupu
 165 $x$.
 166 \:{\I Prostor bìhu algoritmu} $s(x)$ je analogicky poèet pamì»ových
 167 bunìk spotøebovaných pøi výpoètu se vstupem~$x$.
 168 \:{\I Èasová slo¾itost} (v~nejhor¹ím pøípadì) je:
 169 $$T(n) := \max \{t(x) ; \hbox{$x$ je vstup délky $n$}\}.$$
 170 \:{\I Prostorová slo¾itost} (v~nejhor¹ím pøípadì) je:
 171 $$S(n) := \max \{s(x) ; \hbox{$x$ je vstup délky $n$}\}.$$
 172 \endlist
 173
 174 \s{Díra v definici:} Co jsou to èísla?
 175 Kdy¾ mohou být libovolnì velká, pak se dá podvádìt pøi poèítání èasové i prostorové
 176 slo¾itosti. Napravit to mù¾eme buïto tak, ¾e vstup budeme mìøit v~bitech a operace
 177 s~$k$-bitovými èísly bude trvat øádovì $\log k$ krokù, nebo ¾e omezíme èísla
 178 na~polynomiálnì velká vzhledem k~velikosti vstupu. Pro normální algoritmy tyto dvì
 179 definice dávají èasové slo¾itosti li¹ící se v¾dy logaritmem velikosti vstupu, tak¾e
 180 pro srovnávání algoritmù nemusíme tento rozdíl uva¾ovat. Pro tuto pøedná¹ku si vybereme
 181 omezení èísel na~polynomiálnì velká.
 182
 183 \h{Panorama slo¾itostí}
 184
 185 Abychom mìli pøedstavu o~tom, jak pou¾itelné jsou algoritmy se kterou
 186 èasovou slo¾itostí, zkusme si pár slo¾itostí srovnat za pøedpokladu,
 187 ¾e ná¹ poèítaè za sekundu provede $10^9$ operací:
 188 \def\[#1]{\,\hbox{#1}}
 189 $$\vbox{
 190 \halign{$#$ \hfil&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil
 191 $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$\cr
 192 \hbox{funkce / $n=$\hskip-2em}& 10              & 20            & 30
 193 & 50            & 100           & 1\,000        & 1\,000\,000 \cr
 194 \noalign{\medskip\hrule\bigskip}
 195 \log_2 n        & 3.3\[ns]      & 4.3\[ns]      & 4.9\[ns]
 196 & 5.6\[ns] & 6.6\[ns]      & 10.0\[ns]     & 19.9\[ns]     \cr
 197 n               & 10\[ns]       & 20\[ns]       & 30\[ns]
 198 & 50\[ns] & 100\[ns]      & 1\[$\mu$s]    & 1\[ms]        \cr
 199 n\cdot\log_2 n\hskip-1em        & 33\[ns]       & 86\[ns]
 200 & 147\[ns] & 282\[ns]      & 664\[ns]      & 10\[$\mu$s]   & 20\[ms]
 201 \cr
 202 n^2             & 100\[ns]      & 400\[ns]      & 900\[ns]
 203 & 2.5\[$\mu$s] & 100\[$\mu$s]  & 1\[ms]        & 1\,000\[s]    \cr
 204 n^3             & 1\[$\mu$s]    & 8\[$\mu$s]    & 27\[$\mu$s]
 205 & 125\[$\mu$s] & 1\[ms]        & 1\[s]         & 10^9\[s]      \cr
 206 2^n             & 1\[$\mu$s]    & 1\[ms]        & 1\[s]
 207 & 10^6\[s] & 10^{21}\[s]   & 10^{292}\[s]  & \approx\infty \cr
 208 n!              & 10^6\[s]      & 10^{18}\[s]   & 10^{32}\[s]
 209 & 10^{64}\[s] & 10^{158}\[s]  & 10^{2567}\[s] & \approx\infty \cr
 210 }}$$
 211 \halign{#\hfil&\quad #\hfil\cr
 212 Pro pøedstavu:  &$1\,000\[s]$ je asi tak ètvrt hodiny\cr
 213                 &$1\,000\,000\[s]$ je necelých 12 dní\cr
 214                 &$10^9\[s]$ je 31 let\cr
 215                 &$10^{18}\[s]$ je asi tak stáøí Vesmíru. \cr}
 216
 217 Poèítaèe se nám ale zrychlují\foot{\uv{Ka¾dé dva roky se výkon poèítaèù
 218 zdvojnásobí} -- Gordon Moore (prý)} -- není tedy lep¹í chvíli poèkat
 219 ne¾ vymý¹let lep¹í algoritmus? :-) Podívejme se, jak velký vstup
 220 doká¾eme zpracovat za $10^6$ a $2\cdot 10^6$ operací:
 221 $$\vbox{\halign{\hfil$#$\quad&\hfil$#$\quad&\hfil$#$\qquad&#\hfil\cr
 222 \hbox{funkce} & 10^6\;\hbox{op.} & 2\cdot10^6\;\hbox{op.} & zmìna \cr
 223 \noalign{\medskip\hrule\bigskip}
 224 n       &1\,000\,000    &2\,000\,000    &2-krát více            \cr
 225 n^2     &1\,000         &1\,414         &$\sqrt{2}\approx 1.41$-krát
 226 více \cr
 227 n^3     &100            &126            &$\root3\of2\approx 1.26$-krát
 228 více \cr
 229 2^n     &20             &21             &o 1 více       \cr
 230 }}$$
 231 Na nìkterých èasových slo¾itostech se tedy exponenciální zrychlování
 232 poèítaèù projevuje jen minimálnì.
 233
 234 Jak je vidìt na~následujícím grafu, konstanty v~èasové slo¾itosti
 235 vùbec nehrají pøíli¹ velkou roli, proto se vyplácí najít nejdøíve
 236 algoritmus, jeho¾ slo¾itost je asymptoticky dobrá, a teprve pak
 237 optimalizovat konstanty.
 238
 239 \>\epsfxsize=1\hsize\epsfbox{../slides/funcs.eps}
 240
 241 V~praxi také èasto pomù¾e zpracovávat velké vstupy asymptoticky rychlým
 242 algoritmem a pro malé vstupy pøepnout na~\uv{hloupý} algoritmus, který
 243 má malé multiplikativní konstanty.
 244
 245 \bye