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

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

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

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

Pøibli¾nì $a+b$. To je velmi pomalé, a proto vyvstává otázka, dá-li se
EA zrychlit.

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

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

{\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
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 toho, ¾e Fibonacciho èísla jsou
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,
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é $(+,-,*,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
elementárních operací, které program provedl pøi zpracování vstupu
$x$.

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

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

\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? :-)

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

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


\>\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ù.

\bye
