1-euklid/1-euklid.tex

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