From 58a9d92cd554b4ed0ca48de5ae6a47cc91f92d63 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 3 Apr 2007 11:54:47 +0200 Subject: [PATCH] Nova verze prvni kapitoly. --- 1-euklid/1-euklid.tex | 165 +++++++++++++++++++++--------------------- 1 file changed, 83 insertions(+), 82 deletions(-) diff --git a/1-euklid/1-euklid.tex b/1-euklid/1-euklid.tex index e063655..8953415 100644 --- a/1-euklid/1-euklid.tex +++ b/1-euklid/1-euklid.tex @@ -1,41 +1,42 @@ \input ../lecnotes.tex -\input epsf +\input epsf.tex \def\N{N} -\prednaska{1}{Euklidùv algoritmus}{(zapsaly T.~Klimo¹ová a K.~B\"ohmová)} +\prednaska{1}{Eukleidùv algoritmus}{(zapsaly T.~Klimo¹ová a K.~B\"ohmová)} \h{} +\>{\bf Problém hledání nejvìt¹ího spoleèného dìlitele } -\s{Algoritmus:} (Eukleidùv algoritmus verze $1.0$) - -Cílem je najít nejvìt¹ího spoleèného dìlitele zadaných èísel +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. +\s{Algoritmus:} (Eukleidùv algoritmus verze $1.0$; snad 200 let pøed Eukleidem) + \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 $ +\::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í} +\>{\bo 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 +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)$} +\>{\bo 2) EA vydá $\gcd(a_0, b_0)$} -$($Pøi dùkazech správnosti algoritmu se èasto pou¾ívá invariant.$)$ +Pøi dùkazech správnosti algoritmu se èasto pou¾ívá {\I invariant.} +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). 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 +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èí. @@ -45,44 +46,43 @@ $\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$) +\>{\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 +Nahlédneme snadno. Nejvìt¹í spoleèný dìlitel jediného èísla je ono samo. -\>{\I Pozorování 2:} $\gcd(a, b) = \gcd(b, a)$ +\>{\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 +nám na poøadí èísel nezále¾í. -\>{\I Pozorování 3:} $\gcd(a, b) = \gcd(a \pm b, b)$ +\>{\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)$. +$k\vert a, k\vert b \Leftrightarrow k\vert a, k\vert(a\pm 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)$. +\>$\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'$. +Obdobnì $b = k\cdot b'$, pro nìjaká èísla $a',b'\in \N$. +Tak¾e souèet $a\pm b$ si mù¾eme rozepsat jako $(a'\pm b')\cdot k$ z èeho¾ je +ji¾ vidìt, ¾e $k\vert(a\pm b)$. -\>$\Leftarrow$: Podobnì $k\vert (a+b), k\vert b \Leftrightarrow k\vert a$. -\qed +\>$\Leftarrow$: Podobnì $k\vert (a\pm b), k\vert b \Leftrightarrow k\vert a$. 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)$. +\qed -\>{\bf $3)$Rychlost algoritmu} +\goodbreak + +\>{3) \bo 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$) +\s{Algoritmus:} (Eukleidùv alg. v$2.0$; neznámý Eukleidùv pokraèovatel, neznámo kdy) -Vylep¹ení: místo odèítání budeme poèítat zbytek po dìlení. +\>Vylep¹ení: místo odèítání budeme poèítat zbytek po dìlení. \algo \:while $b \neq 0:$ @@ -94,7 +94,7 @@ Vylep \: return $a$ \endalgo -\>{\sl Dùkaz správnosti: } +\>{\sl Dùkaz správnosti: } \>{\bf Korektnost: } @@ -103,45 +103,44 @@ Nahl \>{\bf Rychlost této verze:} -Uká¾eme, ¾e rychlost verze 2.0 je $\sim \log(\max(a,b))$. +Uká¾eme, ¾e poèet krokù, který provede verze 2.0 je asi $\log(\max(a,b))$. -\s {Lemma: } Za 2 prùchody cyklem se buï hodnota $a$ nebo hodnota $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ý. +(Dùkaz uká¾eme za chvíli.) -Prùchodù, které zmen¹ují hodnotu $a$ je nejvý¹e $\lceil \log_2 +Uvìdomíme si, ¾e toto lemma ji¾ staèí k tomu, aby byl èas výpoètu +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: } +\>{\sl Dùkaz lemmatu: } +{\narrower 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 +¾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 +\: 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$. +\: 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ý?} @@ -154,51 +153,53 @@ zadan $\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 +$($Zároveò je to asi nejhezèí dùkaz toho, ¾e Fibonacciho èísla jsou nesoudìlná.$)$ -\vfill\break \h{Výpoèetní model} +Kdy¾ u¾ známe nìjaký algoritmus, mìli bychom se zaèít zaobírat otázkou, co takový algoritmus vlastnì je. +®ádná obecnì uznávaná definice algoritmu neexistuje, zadefinujeme si alespoò výpoèetní model, +a za~algoritmy budeme pova¾ovat programy v tomto modelu. -\>{Základní vlastnosti:} +\>{Základní vlastnosti výpoèetního modelu:} \itemize\ibull -\:vstup: $n$ èísel $($mù¾eme se omezit na èísla, nebo» cokoli jiného +\: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) +\itemize\idot +\:aritmetické operace $(+, -, *, $mod$,\dots)$ +\:logické operace +\:práce s pamìtí +\:øídící operace (skoky, podmínìné skoky, halt,\dots) +\endlist -\:èas: $t(x)$ = poèet krokù výpoètu pøi zpracování vstupu $x$ +\:èas: $t(x)$ = poèet krokù výpoètu pøi zpracování vstupu~$x$ +\:prostor: $s(x)$ = poèet bunìk pamìti pou¾itých pøi zpracování vstupu~$x$ \endlist -\s{Definice:} Èasová slo¾itost v nejhor¹ím pøípadì +\s{Definice:} {\I Èasová slo¾itost v nejhor¹ím pøípadì } -$T(n) := \max \{t(x)\vert x$ je vstup délky $n\}$. +$T(n) := \max \{t(x) ; \hbox{$x$ je vstup délky $n$}\}$. -\s{Definice:} Prostorová slo¾itost +\s{Definice:} {\I Prostorová slo¾itost} -udává kolik pamìti výpoèet pou¾il. +$S(n) := \max \{s(x) ; \hbox{$x$ je vstup délky $n$}\}$. \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é +\s{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í èasové i prostorové slo¾itosti. -\>{Velikost èísel} +\>{Velikost èísel:} -a$)$ polynomiálnì velká vzhledem k tomu kolik jich je +a) polynomiálnì velká vzhledem k tomu, kolik jich je -b$)$ vstup mìøíme v bitech a operace pak trvá $\sim \log(x)$ +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é¾ +Poznámka: pro normální algoritmy tyto dvì definice dávají toté¾ \bigskip \>{Které slo¾itosti jsou rozumné a které nepou¾itelné?} @@ -231,19 +232,16 @@ 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} +\bigskip +\bigskip - -\vfill\break - -{\bf Poèítaèe se nám zrychlují aneb Mooreùv zákon} +{\>\bf Poèítaèe se nám zrychlují aneb Mooreùv zákon} \medskip @@ -267,21 +265,24 @@ v }}$$ \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 + +\dots Ne, na nìkterých èasových slo¾itostech se to projeví tak nepatrnì. \medskip -Vyplatí se tedy nejdøív najít dobrý algoritmus, pak optimalizovat konstanty. +Vyplatí se nejdøív najít dobrý algoritmus a 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} +\>\epsfxsize=1\hsize\epsfbox{../slides/funcs.eps} + +Asymptotický rùst funkcí: + +(èleny ni¾¹ích øádù se schovají do konstant) + +\>\epsfxsize = 1\hsize\epsfbox{../slides/funcs2.eps} \medskip Malé vstupy se èasto dají øe¹it samostatnì, lépe je tedy pou¾ít dva -- 2.39.2