\input ../lecnotes.tex
\input epsf.tex

\def\N{N}

\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 }

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
\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 $
\algout $a=\gcd(a_0,b_0)$.
\endalgo

\noindent{\sl Dùkaz správnosti: }

\>{\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
se uskuteèní nanejvý¹ $a+b$ prùchodù cyklem a pak algoritmus skonèí.

\>{\bo 2) EA vydá $\gcd(a_0, b_0)$}

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
$(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)$.

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.

\>{\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¾í.

\>{\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, k\vert(a\pm 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\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

\goodbreak

\>{3) \bo Rychlost algoritmu}

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.

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ì:

\s{Algoritmus:} (Eukleidùv alg. v$2.0$; neznámý Eukleidùv pokraèovatel, neznámo kdy)

\algo
\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$
\algout $a=\gcd(a_0,b_0)$.
\endalgo

\>{\sl Dùkaz správnosti: }

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$. 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 < 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

}

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)$.

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¾ 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:}

V první øadì potøebujeme modelu sdìlit, s èím má pracovat, a pak se
dovìdìt, jak to dopadlo. Bez újmy na obecnosti mù¾eme pova¾ovat $n$
èísel za {\sl vstup} a za {\sl výstup} $m$ èísel $($mù¾eme se omezit
na èísla, nebo» cokoli jiného umíme do èísel zakódovat$)$.

Dále by mìl výpoèetní model umìt provádìt {\sl elementární operace},
co¾
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í.

\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{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. 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
$#$&\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
}}$$
\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}

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}
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
}}$$
Na nìkterých èasových slo¾itostech se tedy exponenciální zrychlování
poèítaèù projevuje jen minimálnì.

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}

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
