From 05b291da1f82143341ad3dd1c74efeb37c7fea1a Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 May 2007 12:13:24 +0200 Subject: [PATCH] Korektury prvni kapitoly. --- 1-euklid/1-euklid.tex | 209 ++++++++++++++++-------------------------- 1 file changed, 81 insertions(+), 128 deletions(-) diff --git a/1-euklid/1-euklid.tex b/1-euklid/1-euklid.tex index 7c36a2d..c62e9df 100644 --- a/1-euklid/1-euklid.tex +++ b/1-euklid/1-euklid.tex @@ -15,10 +15,12 @@ Divisor. \s{Algoritmus:} (Eukleidùv algoritmus verze $1.0$; snad 200 let pøed Eukleidem) \algo +\algin èísla $a_0$, $b_0$. +\:$a\leftarrow a_0, b\leftarrow b_0$. \: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$. +\algout $a=\gcd(a_0,b_0)$. \endalgo \noindent{\sl Dùkaz správnosti: } @@ -43,8 +45,7 @@ A jakmile je spln 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í: +K~tomu bude tøeba nìkolik pozorování: \>{\I Pozorování 1:} $\gcd(a, a) = a$ (pro $a>0$). @@ -77,88 +78,71 @@ platil. Algoritmus tedy opravdu vyd \>{3) \bo Rychlost algoritmu} -Pøibli¾nì $a+b$. To je velmi pomalé, a proto vyvstává otázka, dá-li se -EA zrychlit. +Algoritmus provede v~nehor¹ím pøípadì øádovì $a+b$ iterací. To je velmi pomalé, +a proto vyvstává otázka, dá-li se nìjak zrychlit. -\s{Algoritmus:} (Eukleidùv alg. v$2.0$; neznámý Eukleidùv pokraèovatel, neznámo kdy) +V¹imnìme si, ¾e opakované odèítání jednoho èísla od~druhého lze nahradit výpoètem +zbytku po~dìlení. Algoritmus tedy mu¾eme upravit následovnì: -\>Vylep¹ení: místo odèítání budeme poèítat zbytek po dìlení. +\s{Algoritmus:} (Eukleidùv alg. v$2.0$; neznámý Eukleidùv pokraèovatel, neznámo kdy) \algo -\:while $b \neq 0:$ - +\algin èísla $a_0$, $b_0$. +\:$a\leftarrow a_0, b\leftarrow b_0$. +\:while $b \neq 0$: \::$a \leftarrow a \mod b$ - \::$a \leftrightarrow b$ - -\: return $a$ +\algout $a=\gcd(a_0,b_0)$. \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 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$ -zmen¹í alespoò na polovinu. - -(Dùkaz uká¾eme za chvíli.) - -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: } +Algoritmus urèitì vydá správný výsledek, proto¾e poèítá toté¾, co pøedchozí verze. +Uká¾eme, ¾e poèet krokù, který provede verze 2.0, je øádovì $\log(\max(a,b))$. +K~tomu se nám bude hodit následující: {\narrower +\s{Lemma:} Za dva prùchody cyklem se buï hodnota $a$ nebo hodnota $b$ +zmen¹í alespoò dvakrát. + +\proof 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$. +¾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ì +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$. +\:Buï platí $b_1 \leq b_0/2$. Pak jistì $b_0 \mod b_1 < b_1 \leq 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_0/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. +Nyní staèí lemma ¹ikovnì vyu¾ít: +Dvojic prùchodù, které zmen¹ují hodnotu $a$, je nejvý¹e $\lceil \log_2 +a \rceil$. Obdobnì tìch sni¾ujících hodnotu $b$ je nejvý¹e $\lceil \log_2 b \rceil$. +Celkový poèet prùchodù tedy je nejvý¹e $2(\lceil \log_2 a \rceil+\lceil +\log_2 b\rceil)$. +Je¹tì bychom chtìli dokázat, ¾e ná¹ horní odhad na~poèet prùchodù není pøíli¹ +velkorysý. Zkusme se podívat, co se stane, kdy¾ algoritmus necháme spoèítat +$\gcd(F_n, F_{n-1})$, kde~$F_i$ je $i$-té Fibonacciho èíslo. Tehdy v¹echna +modula budou ve~skuteènosti odèítání a algoritmus bude poèítat $\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 toho, ¾e Fibonacciho èísla jsou -nesoudìlná.$)$ +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. +(Zároveò je to také pìkný dùkaz toho, ¾e Fibonacciho èísla jsou +navzájem nesoudìlná.) \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, +Kdy¾ chceme studovat algoritmy, mìli bychom se zaèít zaobírat otázkou, co takový algoritmus vlastnì je. +®ádná obecnì uznávaná definice algoritmu neexistuje, nadefinujeme si proto alespoò výpoèetní model a za~algoritmy budeme pova¾ovat programy v tomto modelu. \s{Základní vlastnosti výpoèetního modelu:} @@ -170,44 +154,37 @@ na Dále by mìl výpoèetní model umìt provádìt {\sl elementární operace}, co¾ -jsou nejen ty aritmetické $(+,-,*,mod \dots)$ a logické $($negace, -and, or -\dots$)$, ale také øídící operace $($skoky, podmínìné skoky, halt -\dots$)$ -a práci s pamìtí. +jsou nejen ty aritmetické $(+,-,*,/,{\rm mod}, \dots)$ a logické (negace, +and, or, \dots), ale také øídící operace (skoky, podmínìné skoky, halt, +\dots) a práci s pamìtí. -{\sl Èas bìhu algoritmu $t(x)$} pro vstup $x$ mìøíme jako poèet +\s{Definice:} +\itemize\ibull +\:{\I Èas bìhu algoritmu} $t(x)$ pro vstup~$x$ mìøíme jako poèet elementárních operací, které program provedl pøi zpracování vstupu $x$. +\:{\I Prostor bìhu algoritmu} $s(x)$ je analogicky poèet pamì»ových +bunìk spotøebovaných pøi výpoètu se vstupem~$x$. +\:{\I Èasová slo¾itost} (v~nejhor¹ím pøípadì) je: +$$T(n) := \max \{t(x) ; \hbox{$x$ je vstup délky $n$}\}.$$ +\:{\I Prostorová slo¾itost} (v~nejhor¹ím pøípadì) je: +$$S(n) := \max \{s(x) ; \hbox{$x$ je vstup délky $n$}\}.$$ +\endlist -\s{Definice:} {\I Èasová slo¾itost v nejhor¹ím pøípadì } - -$T(n) := \max \{t(x) ; \hbox{$x$ je vstup délky $n$}\}$. - -\s{Definice:} {\I Prostorová slo¾itost} - -$S(n) := \max \{s(x) ; \hbox{$x$ je vstup délky $n$}\}$. - -\bigskip -\s{Díry v definici:} co jsou to èísla? +\s{Díra 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:} - -a) polynomiálnì velká vzhledem k tomu, kolik jich je - -b) vstup mìøíme v bitech a operace pak trvá $\sim \log(x)$ - -\>(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)} - +slo¾itosti. Napravit to mù¾eme buïto tak, ¾e vstup budeme mìøit v~bitech a operace +s~$k$-bitovými èísly bude trvat øádovì $\log k$ krokù, nebo ¾e omezíme èísla +na~polynomiálnì velká vzhledem k~velikosti vstupu. Pro normální algoritmy tyto dvì +definice dávají èasové slo¾itosti li¹ící se v¾dy logaritmem velikosti vstupu, tak¾e +pro srovnávání algoritmù nemusíme tento rozdíl uva¾ovat. Pro tuto pøedná¹ku si vybereme +omezení èísel na~polynomiálnì velká. + +\h{Panorama slo¾itostí} + +Abychom mìli pøedstavu o~tom, jak pou¾itelné jsou algoritmy se kterou +èasovou slo¾itostí, zkusme si pár slo¾itostí srovnat za pøedpokladu, +¾e ná¹ poèítaè za sekundu provede $10^9$ operací: \def\[#1]{\,\hbox{#1}} $$\vbox{ \halign{$#$ \hfil&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil @@ -231,28 +208,16 @@ n^3 & 1\[$\mu$s] & 8\[$\mu$s] & 27\[$\mu$s] n! & 10^6\[s] & 10^{18}\[s] & 10^{32}\[s] & 10^{64}\[s] & 10^{158}\[s] & 10^{2567}\[s] & \approx\infty \cr }}$$ - \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 - -{\>\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? :-) - +Poèítaèe se nám ale zrychlují\foot{\uv{Ka¾dé dva roky se výkon poèítaèù +zdvojnásobí} -- Gordon Moore (prý)} -- není tedy lep¹í chvíli poèkat +ne¾ vymý¹let lep¹í algoritmus? :-) Podívejme se, jak velký vstup +doká¾eme zpracovat za $10^6$ a $2\cdot 10^6$ operací: $$\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} @@ -263,30 +228,18 @@ n^3 &100 &126 &$\root3\of2\approx 1.26$-kr více \cr 2^n &20 &21 &o 1 více \cr }}$$ +Na nìkterých èasových slo¾itostech se tedy exponenciální zrychlování +poèítaèù projevuje jen minimálnì. -\bigskip - -\dots Ne, na nìkterých èasových slo¾itostech se to projeví tak nepatrnì. - -\medskip -Vyplatí se nejdøív najít dobrý algoritmus a pak optimalizovat konstanty. - - -\bigskip -Asymptotický rùst funkcí - +Jak je vidìt na~následujícím grafu, konstanty v~èasové slo¾itosti +vùbec nehrají pøíli¹ velkou roli, proto se vyplácí najít nejdøíve +algoritmus, jeho¾ slo¾itost je asymptoticky dobrá, a teprve pak +optimalizovat konstanty. \>\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 -algoritmy. Pro velké vstupy nezále¾í na konstantì a na èlenech ni¾¹ích -øádù. +V~praxi také èasto pomù¾e zpracovávat velké vstupy asymptoticky rychlým +algoritmem a pro malé vstupy pøepnout na~\uv{hloupý} algoritmus, který +má malé multiplikativní konstanty. \bye -- 2.39.5