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 \:while $a\not=b$ :
  19 \::if $a > b \Rightarrow a \leftarrow a-b $
  20 \::\rlap{else}\phantom{if }$\phantom{a > b} \Rightarrow b \leftarrow b-a $
  21 \: return $a$.
  22 \endalgo
  23
  24 \noindent{\sl Dùkaz správnosti: }
  25
  26 \>{\bo 1) EA se zastaví}
  27
  28 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
  29 se uskuteèní nanejvý¹ $a+b$ prùchodù cyklem a pak algoritmus skonèí.
  30
  31 \>{\bo 2) EA vydá $\gcd(a_0, b_0)$}
  32
  33 Pøi dùkazech správnosti algoritmu se èasto pou¾ívá {\I invariant.}
  34 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).
  35
  36 Doká¾eme, ¾e platí invariant: $\gcd(a, b) = \gcd(a_0, b_0)$.
  37
  38 Algoritmus pøi svém bìhu postupnì mìní hodnoty $a$ a $b$.
  39 Tedy
  40 $(a_0, b_0) \rightarrow (a_1, b_1) \rightarrow
  41 \dots \rightarrow (a_k, b_k)$.
  42 A jakmile je splnìna rovnost $a_k = b_k$, tak skonèí.
  43 My chceme ukázat, ¾e platí
  44 $\gcd(a_0, b_0) = \gcd(a_1, b_1) = \dots = \gcd(a_k, b_k)$.
  45
  46 \medskip
  47 K tomu bude tøeba nìkolik pozorování:
  48
  49 \>{\I Pozorování 1:} $\gcd(a, a) = a$ (pro $a>0$).
  50
  51 Nahlédneme snadno. Nejvìt¹í spoleèný dìlitel jediného èísla je ono samo.
  52
  53 \>{\I Pozorování 2:} $\gcd(a, b) = \gcd(b, a)$.
  54
  55 Takté¾ jednoduché. Pøi urèování nejvìt¹ího spoleèného dìlitele
  56 nám na poøadí èísel nezále¾í.
  57
  58 \>{\I Pozorování 3:} $\gcd(a, b) = \gcd(a \pm b, b)$.
  59
  60 %%Rozmyslíme si, ¾e a¾ doká¾eme {\I Pozorování 3 }, máme vyhráno.
  61
  62 Doká¾eme silnìj¹í vìc -- platnost ekvivalence
  63 $k\vert a, k\vert b \Leftrightarrow k\vert a, k\vert(a\pm b)$.
  64
  65 \>$\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'$.
  66 Obdobnì $b = k\cdot b'$, pro nìjaká èísla  $a',b'\in \N$.
  67 Tak¾e souèet $a\pm b$ si mù¾eme rozepsat jako $(a'\pm b')\cdot k$ z èeho¾ je
  68 ji¾ vidìt, ¾e $k\vert(a\pm b)$.
  69
  70 \>$\Leftarrow$: Podobnì $k\vert (a\pm b), k\vert b \Leftrightarrow k\vert a$.
  71
  72 Uvìdomíme si, ¾e tato tøi pozorování nám staèí k tomu, aby invariant
  73 platil. Algoritmus tedy opravdu vydá $\gcd(a_0,b_0)$.
  74 \qed
  75
  76 \goodbreak
  77
  78 \>{3) \bo Rychlost algoritmu}
  79
  80 Pøibli¾nì $a+b$. To je velmi pomalé, a proto vyvstává otázka, dá-li se
  81 EA zrychlit.
  82
  83 \s{Algoritmus:} (Eukleidùv alg. v$2.0$; neznámý Eukleidùv pokraèovatel, neznámo kdy)
  84
  85 \>Vylep¹ení: místo odèítání budeme poèítat zbytek po dìlení.
  86
  87 \algo
  88 \:while $b \neq 0:$
  89
  90 \::$a \leftarrow a \mod b$
  91
  92 \::$a \leftrightarrow b$
  93
  94 \: return $a$
  95 \endalgo
  96
  97 \>{\sl Dùkaz správnosti: }
  98
  99 \>{\bf Korektnost: }
 100
 101 Nahlédneme, ¾e dìlá toté¾ co pøedchozí verze.
 102 \qed
 103
 104 \>{\bf Rychlost této verze:}
 105
 106 Uká¾eme, ¾e poèet krokù, který provede verze 2.0 je asi $\log(\max(a,b))$.
 107
 108 \s {Lemma:}  Za 2 prùchody cyklem se buï hodnota $a$ nebo hodnota $b$
 109 zmen¹í alespoò na polovinu.
 110
 111 (Dùkaz uká¾eme za chvíli.)
 112
 113 Uvìdomíme si, ¾e toto lemma ji¾ staèí k tomu, aby byl èas výpoètu
 114 logaritmický.
 115 Prùchodù, které zmen¹ují hodnotu $a$, je nejvý¹e $\lceil \log_2
 116 a \rceil$. Obdobnì prùchodù sni¾ujících hodnotu $b$ je nejvý¹e
 117 $\lceil \log_2 b \rceil$.
 118 Tedy celkový poèet prùchodù je nejvý¹e $2\cdot(\lceil \log_2 a \rceil+\lceil
 119 \log_2 b\rceil)$, co¾ není více ne¾ $\sim \log(\max(a,b))$.
 120
 121
 122 \>{\sl Dùkaz lemmatu: }
 123
 124 {\narrower
 125 Rozebereme, co se stane po dvojím projití cyklem.
 126 Na zaèátku máme èísla $a_0$ a $b_0$. Bez újmy na obecnosti pøedpokládejme,
 127 ¾e $a_0>b_0$, jinak potøebujeme navíc jeden prùchod, v nìm¾ se èísla
 128 prohodí.
 129 Po prvním prùchodu: $a_1=b_0; b_1=a_0 \mod b_0$, co¾ je ménì ne¾ $b_0$.
 130 Po druhém prùchodu: $a_2=b_1; b_2=a_1 \mod b_1 = b_0 \mod b_1$.
 131 Chceme ukázat, ¾e kdy¾ je $b_1 < b_0$, tak $b_0 \mod b_1 \leq b_0/2$.
 132
 133 \itemize\ibull
 134 \: Buï platí $b_1 \leq b_0/2$. Pak jistì $b_0 \mod b_1$ je
 135 nanejvý¹ $b_0/2$.
 136
 137 \: Nebo nastane druhá mo¾nost  $b_1 >  b_0/2$.
 138 Pak tedy $b_0 \mod b_1 = b_0-b_1$, co¾ je takté¾ maximálnì $b/2$.
 139 \qed
 140 \endlist
 141
 142 }
 143
 144 \medskip
 145 \>{Jak nahlédnout, ¾e algoritmus není rychlej¹í ne¾ logaritmický?}
 146
 147 Skrze Fibonacciho èísla: necháme algoritmus poèítat $\gcd(F_n, F_{n-1})$.
 148
 149 Díky exponenciální velikosti Fibonacciho èísel tento výpoèet bude
 150 opravdu trvat logaritmicky dlouho vzhledem k velikosti vìt¹ího ze
 151 zadaných èísel.
 152
 153 $\gcd(F_n, F_{n-1}) \rightarrow \gcd(F_{n-1}, F_{n-2}) \rightarrow
 154 \dots \rightarrow \gcd(1, 1)$.
 155
 156 $($Zároveò je to asi nejhezèí dùkaz toho, ¾e Fibonacciho èísla jsou
 157 nesoudìlná.$)$
 158
 159 \h{Výpoèetní model}
 160 Kdy¾ u¾ známe nìjaký algoritmus, mìli bychom se zaèít zaobírat otázkou, co takový algoritmus vlastnì je.
 161 ®ádná obecnì uznávaná definice algoritmu neexistuje, zadefinujeme si alespoò výpoèetní model,
 162 a za~algoritmy budeme pova¾ovat programy v tomto modelu.
 163
 164 \>{Základní vlastnosti výpoèetního modelu:}
 165 \itemize\ibull
 166 \:vstup: $n$ èísel $($mù¾eme se omezit na èísla, nebo» cokoli jiného
 167 umíme do èísel zakódovat$)$
 168 \:výstup: $m$ èísel
 169
 170 \:elementární operace:
 171
 172 \itemize\idot
 173 \:aritmetické operace $(+, -, *, $mod$,\dots)$
 174 \:logické operace
 175 \:práce s pamìtí
 176 \:øídící operace (skoky, podmínìné skoky, halt,\dots)
 177 \endlist
 178
 179 \:èas: $t(x)$ = poèet krokù výpoètu pøi zpracování vstupu~$x$
 180 \:prostor: $s(x)$ = poèet bunìk pamìti pou¾itých pøi zpracování vstupu~$x$
 181 \endlist
 182
 183 \s{Definice:} {\I Èasová slo¾itost v nejhor¹ím pøípadì }
 184
 185 $T(n) := \max \{t(x) ; \hbox{$x$ je vstup délky $n$}\}$.
 186
 187 \s{Definice:} {\I Prostorová slo¾itost}
 188
 189 $S(n) := \max \{s(x) ; \hbox{$x$ je vstup délky $n$}\}$.
 190
 191 \bigskip
 192 \s{Díry v definici:} co jsou to èísla?
 193 Kdy¾ mohou být libovolnì velká, pak se dá podvádìt pøi poèítání èasové i prostorové
 194 slo¾itosti.
 195
 196 \>{Velikost èísel:}
 197
 198 a) polynomiálnì velká vzhledem k tomu, kolik jich je
 199
 200 b) vstup mìøíme v bitech a operace pak trvá $\sim \log(x)$
 201
 202 Poznámka: pro normální algoritmy tyto dvì definice dávají toté¾
 203
 204 \bigskip
 205 \>{Které slo¾itosti jsou rozumné a které nepou¾itelné?}
 206
 207 \medskip
 208 \>{\bf Srovnání rychlostí algoritmù (pøedpokládáme $10^9$ operací za
 209 sekundu)}
 210
 211 \def\[#1]{\,\hbox{#1}}
 212 $$\vbox{
 213 \halign{$#$ \hfil&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil
 214 $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$\cr
 215 \hbox{funkce / $n=$\hskip-2em}& 10              & 20            & 30
 216 & 50            & 100           & 1\,000        & 1\,000\,000 \cr
 217 \noalign{\medskip\hrule\bigskip}
 218 \log_2 n        & 3.3\[ns]      & 4.3\[ns]      & 4.9\[ns]
 219 & 5.6\[ns] & 6.6\[ns]      & 10.0\[ns]     & 19.9\[ns]     \cr
 220 n               & 10\[ns]       & 20\[ns]       & 30\[ns]
 221 & 50\[ns] & 100\[ns]      & 1\[$\mu$s]    & 1\[ms]        \cr
 222 n\cdot\log_2 n\hskip-1em        & 33\[ns]       & 86\[ns]
 223 & 147\[ns] & 282\[ns]      & 664\[ns]      & 10\[$\mu$s]   & 20\[ms]
 224 \cr
 225 n^2             & 100\[ns]      & 400\[ns]      & 900\[ns]
 226 & 2.5\[$\mu$s] & 100\[$\mu$s]  & 1\[ms]        & 1\,000\[s]    \cr
 227 n^3             & 1\[$\mu$s]    & 8\[$\mu$s]    & 27\[$\mu$s]
 228 & 125\[$\mu$s] & 1\[ms]        & 1\[s]         & 10^9\[s]      \cr
 229 2^n             & 1\[$\mu$s]    & 1\[ms]        & 1\[s]
 230 & 10^6\[s] & 10^{21}\[s]   & 10^{292}\[s]  & \approx\infty \cr
 231 n!              & 10^6\[s]      & 10^{18}\[s]   & 10^{32}\[s]
 232 & 10^{64}\[s] & 10^{158}\[s]  & 10^{2567}\[s] & \approx\infty \cr
 233 }}$$
 234
 235 \halign{#\hfil&\quad #\hfil\cr
 236 Pro pøedstavu:  &$1\,000\[s]$ je asi tak ètvrt hodiny\cr
 237                 &$1\,000\,000\[s]$ je necelých 12 dní\cr
 238                 &$10^9\[s]$ je 31 let\cr
 239                 &$10^{18}\[s]$ je asi tak stáøí Vesmíru. \cr}
 240
 241 \bigskip
 242 \bigskip
 243
 244 {\>\bf Poèítaèe se nám zrychlují aneb Mooreùv zákon}
 245
 246 \medskip
 247
 248 \uv{Ka¾dé dva roky se výkon poèítaèù zdvojnásobí} -- Gordon Moore
 249 (prý)
 250
 251 \medskip
 252
 253 \qquad \dots\ Není tedy lep¹í chvíli poèkat ne¾ vymý¹let lep¹í
 254 algoritmus? :-)
 255
 256 $$\vbox{\halign{\hfil$#$\quad&\hfil$#$\quad&\hfil$#$\qquad&#\hfil\cr
 257 \hbox{funkce} & 10^6\;\hbox{op.} & 2\cdot10^6\;\hbox{op.} & zmìna \cr
 258 \noalign{\medskip\hrule\bigskip}
 259 n       &1\,000\,000    &2\,000\,000    &2-krát více            \cr
 260 n^2     &1\,000         &1\,414         &$\sqrt{2}\approx 1.41$-krát
 261 více \cr
 262 n^3     &100            &126            &$\root3\of2\approx 1.26$-krát
 263 více \cr
 264 2^n     &20             &21             &o 1 více       \cr
 265 }}$$
 266
 267 \bigskip
 268
 269 \dots Ne, na nìkterých èasových slo¾itostech se to projeví tak nepatrnì.
 270
 271 \medskip
 272 Vyplatí se nejdøív najít dobrý algoritmus a pak optimalizovat konstanty.
 273
 274
 275 \bigskip
 276 Asymptotický rùst funkcí
 277
 278
 279 \>\epsfxsize=1\hsize\epsfbox{../slides/funcs.eps}
 280
 281 Asymptotický rùst funkcí:
 282
 283 (èleny ni¾¹ích øádù se schovají do konstant)
 284
 285 \>\epsfxsize = 1\hsize\epsfbox{../slides/funcs2.eps}
 286
 287 \medskip
 288 Malé vstupy se èasto dají øe¹it samostatnì, lépe je tedy pou¾ít dva
 289 algoritmy. Pro velké vstupy nezále¾í na konstantì a na èlenech ni¾¹ích
 290 øádù.
 291
 292 \bye