From 983c4c699c83a2687ffa2d732d74823a52a5368c Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 19 Mar 2007 23:04:53 +0100 Subject: [PATCH] Eukliduv algoritmus. Diky, Terko a Katko. --- 1-euklid/1-euklid.tex | 291 ++++++++++++++++++++++++++++++++++++++++++ 1-euklid/Makefile | 3 + 2 files changed, 294 insertions(+) create mode 100644 1-euklid/1-euklid.tex create mode 100644 1-euklid/Makefile diff --git a/1-euklid/1-euklid.tex b/1-euklid/1-euklid.tex new file mode 100644 index 0000000..e063655 --- /dev/null +++ b/1-euklid/1-euklid.tex @@ -0,0 +1,291 @@ +\input ../lecnotes.tex +\input epsf + +\def\N{N} + +\prednaska{1}{Euklidùv algoritmus}{(zapsaly T.~Klimo¹ová a K.~B\"ohmová)} + +\h{} + +\s{Algoritmus:} (Eukleidùv algoritmus verze $1.0$) + +Cílem je najít nejvìt¹ího spoleèného dìlitele zadaných èísel +$a_0, b_0 \in \N $, dále jen $\gcd(a_0, b_0)$, tedy Greatest Common +Divisor. + +\algo +\:while $a\not=b$ : +\::if $a > b \Rightarrow a \leftarrow a-b $ +\::\rlap{else}\phantom{if }$\phantom{a > b} \Rightarrow b \leftarrow b-a $ +\: return $a$. +\endalgo + +\noindent{\sl Dùkaz správnosti: } + +\>{\bf $1)$ EA se zastaví} + +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 +se uskuteèní nanejvý¹ $a+b$ prùchodù cyklem a pak algoritmus skonèí. + +\>{\bf $2)$ EA vydá $\gcd(a_0, b_0)$} + +$($Pøi dùkazech správnosti algoritmu se èasto pou¾ívá invariant.$)$ + +Doká¾eme, ¾e platí invariant: $\gcd(a, b) = \gcd(a_0, b_0)$. + +Algoritmus pøi svém bìhu postupnì mìní hodnoty $a$ a $b$. +Tedy +$(a_0, b_0) \rightarrow (a_1, b_1) \rightarrow +\dots \rightarrow (a_k, b_k)$. +A jakmile je splnìna rovnost $a_k = b_k$, tak skonèí. +My chceme ukázat, ¾e platí +$\gcd(a_0, b_0) = \gcd(a_1, b_1) = \dots = \gcd(a_k, b_k)$. + +\medskip +K tomu bude tøeba nìkolik pozorování: + +\>{\I Pozorování 1:} $\gcd(a, a) = a$ (pro $a>0$) + +Nahlédneme snadno. Nejvìt¹í spoleèný dìlitel jediného èísla je ono samo. \qed + +\>{\I Pozorování 2:} $\gcd(a, b) = \gcd(b, a)$ + +Takté¾ jednoduché. Pøi urèování nejvìt¹ího spoleèného dìlitele +nám na poøadí èísel nezále¾í. \qed + +\>{\I Pozorování 3:} $\gcd(a, b) = \gcd(a \pm b, b)$ + +%%Rozmyslíme si, ¾e a¾ doká¾eme {\I Pozorování 3 }, máme vyhráno. + +Doká¾eme silnìj¹í vìc -- platnost ekvivalence +$k\vert a, k\vert b \Leftrightarrow k\vert(a+b)$. + +\>$\Rightarrow$: Jeliko¾ $k\vert a, k\vert b \Rightarrow +a$ se dá vyjádøit jako $k-$násobek nìjakého $a'$. Tedy $a = k*a'$. +Obdobnì $b = k*b'$, pro nìjaká èísla $a',b'\in \N$. +Tak¾e souèet $a+b$ si mù¾eme rozepsat jako $(a'+b')*k$ z èeho¾ je +ji¾ vidìt, ¾e $k\vert(a+b)$. + +\>$\Leftarrow$: Podobnì $k\vert (a+b), k\vert b \Leftrightarrow k\vert a$. +\qed + +Uvìdomíme si, ¾e tato tøi pozorování nám staèí k tomu, aby invariant +platil. Algoritmus tedy opravdu vydá $\gcd(a_0,b_0)$. + +\>{\bf $3)$Rychlost algoritmu} + +Pøibli¾nì $a+b$. To je velmi pomalé, a proto vyvstává otázka, dá-li se +EA zrychlit. + +\vfill\break + +\s{Algoritmus:} (Eukleidùv algoritmus verze $2.0$) + +Vylep¹ení: místo odèítání budeme poèítat zbytek po dìlení. + +\algo +\:while $b \neq 0:$ + +\::$a \leftarrow a \mod b$ + +\::$a \leftrightarrow b$ + +\: return $a$ +\endalgo + +\>{\sl Dùkaz správnosti: } + +\>{\bf Korektnost: } + +Nahlédneme, ¾e dìlá toté¾ co pøedchozí verze. +\qed + +\>{\bf Rychlost této verze:} + +Uká¾eme, ¾e rychlost verze 2.0 je $\sim \log(\max(a,b))$. + +\s {Lemma: } Za 2 prùchody cyklem se buï hodnota $a$ nebo hodnota $b$ +zmen¹í alespoò na polovinu. + +Uvìdomíme si, ¾e to u¾ staèí k tomu, aby byl èas logaritmický. + +Prùchodù, které zmen¹ují hodnotu $a$ je nejvý¹e $\lceil \log_2 +a \rceil$. Obdobnì prùchodù sni¾ujících hodnotu $b$ je nejvý¹e +$\lceil \log_2 b \rceil$. + +Tedy celkový poèet prùchodù je nejvý¹e $2\cdot(\lceil \log_2 a \rceil+\lceil +\log_2 b\rceil)$, co¾ není více ne¾ $\sim \log(\max(a,b))$. + + +\>{\sl Dùkaz lemmatu: } + +Rozebereme, co se stane po dvojím projití cyklem. + +Na zaèátku máme èísla $a_0$ a $b_0$. Bez újmy na obecnosti pøedpokládejme, + +¾e $a_0>b_0$, jinak potøebujeme navíc jeden prùchod v nìm¾ se èísla +prohodí. + +Po prvním prùchodu: $a_1=b_0; b_1=a_0 \mod b_0$, co¾ je ménì 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 ukázat, ¾e kdy¾ je $b_1 < b_0$, tak $b_0 \mod b_1 \leq b_0/2$. + +\itemize\ibull +\: buï platí $b_1 \leq b_0/2$. Pak jistì $b_0 \mod b_1$ je +nanejvý¹ $b_0/2$. + +\: nebo nastane druhá mo¾nost $b_1 > b_0/2$. +Pak tedy $b_0 \mod b_1 = b_0-b_1$, co¾ je takté¾ maximálnì $b/2$. +\qed +\endlist + +\medskip +\>{Jak nahlédnout, ¾e algoritmus není rychlej¹í ne¾ logaritmický?} + +Skrze Fibonacciho èísla: necháme algoritmus poèítat $\gcd(F_n, F_{n-1})$. + +Díky exponenciální velikosti Fibonacciho èísel tento výpoèet bude +opravdu trvat logaritmicky dlouho vzhledem k velikosti vìt¹ího ze +zadaných èísel. + +$\gcd(F_n, F_{n-1}) \rightarrow \gcd(F_{n-1}, F_{n-2}) \rightarrow +\dots \rightarrow \gcd(1, 1)$. + +$($Zároveò je to asi nejhezèí dùkaz, ¾e Fibonacciho èísla jsou +nesoudìlná.$)$ +\vfill\break + +\h{Výpoèetní model} + +\>{Základní vlastnosti:} +\itemize\ibull +\:vstup: $n$ èísel $($mù¾eme se omezit na èísla, nebo» cokoli jiného +umíme do èísel zakódovat$)$ +\:výstup: $m$ èísel + +\:elementární operace: + +\quad aritmetické operace $(+, -, *, $mod$,\dots)$ + +\quad logické operace + +\quad práce s pamìtí + +\quad øídící operace (skoky, podmínìné skoky, halt,\dots) + +\:èas: $t(x)$ = poèet krokù výpoètu pøi zpracování vstupu $x$ +\endlist + +\s{Definice:} Èasová slo¾itost v nejhor¹ím pøípadì + +$T(n) := \max \{t(x)\vert x$ je vstup délky $n\}$. + +\s{Definice:} Prostorová slo¾itost + +udává kolik pamìti výpoèet pou¾il. + +\bigskip +\>Díry v definici: co jsou to èísla? +Kdy¾ mohou být libovolnì velká, pak se dá podvádìt pøi poèítání prostorové +slo¾itosti. + +\>{Velikost èísel} + +a$)$ polynomiálnì velká vzhledem k tomu kolik jich je + +b$)$ vstup mìøíme v bitech a operace pak trvá $\sim \log(x)$ + +poznámka: pro normální algoritmy tyto dvì definice dávají toté¾ + +\bigskip +\>{Které slo¾itosti jsou rozumné a které nepou¾itelné?} + +\medskip +\>{\bf Srovnání rychlostí algoritmù (pøedpokládáme $10^9$ operací za +sekundu)} + +\def\[#1]{\,\hbox{#1}} +$$\vbox{ +\halign{$#$ \hfil&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil +$#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$\cr +\hbox{funkce / $n=$\hskip-2em}& 10 & 20 & 30 +& 50 & 100 & 1\,000 & 1\,000\,000 \cr +\noalign{\medskip\hrule\bigskip} +\log_2 n & 3.3\[ns] & 4.3\[ns] & 4.9\[ns] +& 5.6\[ns] & 6.6\[ns] & 10.0\[ns] & 19.9\[ns] \cr +n & 10\[ns] & 20\[ns] & 30\[ns] +& 50\[ns] & 100\[ns] & 1\[$\mu$s] & 1\[ms] \cr +n\cdot\log_2 n\hskip-1em & 33\[ns] & 86\[ns] +& 147\[ns] & 282\[ns] & 664\[ns] & 10\[$\mu$s] & 20\[ms] +\cr +n^2 & 100\[ns] & 400\[ns] & 900\[ns] +& 2.5\[$\mu$s] & 100\[$\mu$s] & 1\[ms] & 1\,000\[s] \cr +n^3 & 1\[$\mu$s] & 8\[$\mu$s] & 27\[$\mu$s] +& 125\[$\mu$s] & 1\[ms] & 1\[s] & 10^9\[s] \cr +2^n & 1\[$\mu$s] & 1\[ms] & 1\[s] +& 10^6\[s] & 10^{21}\[s] & 10^{292}\[s] & \approx\infty \cr +n! & 10^6\[s] & 10^{18}\[s] & 10^{32}\[s] +& 10^{64}\[s] & 10^{158}\[s] & 10^{2567}\[s] & \approx\infty \cr +}}$$ + +\bigskip + +\halign{#\hfil&\quad #\hfil\cr +Pro pøedstavu: &$1\,000\[s]$ je asi tak ètvrt hodiny\cr + &$1\,000\,000\[s]$ je necelých 12 dní\cr + &$10^9\[s]$ je 31 let\cr + &$10^{18}\[s]$ je asi tak stáøí Vesmíru. \cr} + + + +\vfill\break + +{\bf Poèítaèe se nám zrychlují aneb Mooreùv zákon} + +\medskip + +\uv{Ka¾dé dva roky se výkon poèítaèù zdvojnásobí} -- Gordon Moore +(prý) + +\medskip + +\qquad \dots\ Není tedy lep¹í chvíli poèkat ne¾ vymý¹let lep¹í +algoritmus? :-) + +$$\vbox{\halign{\hfil$#$\quad&\hfil$#$\quad&\hfil$#$\qquad&#\hfil\cr +\hbox{funkce} & 10^6\;\hbox{op.} & 2\cdot10^6\;\hbox{op.} & zmìna \cr +\noalign{\medskip\hrule\bigskip} +n &1\,000\,000 &2\,000\,000 &2-krát více \cr +n^2 &1\,000 &1\,414 &$\sqrt{2}\approx 1.41$-krát +více \cr +n^3 &100 &126 &$\root3\of2\approx 1.26$-krát +více \cr +2^n &20 &21 &o 1 více \cr +}}$$ + +\bigskip +Poèítaèe se zrychlují, nestaèí chvíli poèkat? Ne, na nìkterých èasových +slo¾itostech se to projeví tak nepatrnì\dots + +\medskip +Vyplatí se tedy nejdøív najít dobrý algoritmus, pak optimalizovat konstanty. + + +\bigskip +Asymptotický rùst funkcí +\hskip2cmAsymptotický rùst funkcí: + +\hskip5cm èleny ni¾¹ích øádù se schovají do konstant + +\>\epsfxsize=0.48\hsize\epsfbox{../slides/funcs.eps} +\epsfxsize = 0.48\hsize\epsfbox{../slides/funcs2.eps} + +\medskip +Malé vstupy se èasto dají øe¹it samostatnì, lépe je tedy pou¾ít dva +algoritmy. Pro velké vstupy nezále¾í na konstantì a na èlenech ni¾¹ích +øádù. + +\bye diff --git a/1-euklid/Makefile b/1-euklid/Makefile new file mode 100644 index 0000000..dc2d95e --- /dev/null +++ b/1-euklid/Makefile @@ -0,0 +1,3 @@ +P=1-euklid + +include ../Makerules -- 2.39.2