\input ../lecnotes.tex

\prednaska{2}{Slo¾itost, grafové algoritmy}
{(zapsal Martin Koutecký)}

\h{Model {\csc Ram}}

Pøi analýze algoritmu bychom chtìli nìjak popsat jeho slo¾itost. Abychom mohli
 udìlat toto, potøebujeme nejprve definovat výpoèetní model. Výpoèetních modelù
je více, my vybereme jeden pomìrnì blízký skuteèným poèítaèùm:

\s{Definice:} Random Access Machine ({\csc Ram})

{\csc Ram} poèítá jen s celými èísly -- znaky, stringy a podobnì reprezentujeme
èísly, jejich posloupnostmi atd. Pamì» je tvoøena buòkami, které obsahují
èísla. Pamì»ové buòky jsou adresované takté¾ èísly. A program samotný je
koneèná posloupnost instrukcí následujících druhù:
\itemize\ibull
\:Aritmetické a logické:
$X$ |<-| $Y \oplus Z, \oplus\in\{|+|, |-|, |*|, |div|, |mod|, \&,
{\tt\char124}, |<<|, |>>|\}$
\:Øídící: |goto| \<label>, |halt|
\:Podmínky: pro libovolnou nepodmínìnou instrukci mù¾u pou¾ít \hfil \break
if~$X$~|<|~$Y$~|==>|~instrukce % Tady to prosím je¹tì zkontroluj. Myslím, ¾e
% zápis je správný, ale sází se to divnì a vidím èerný obdélníèek na konci
% øádku. Díky.
\endlist

\s{Poznámka} (operandy):
\itemize\ibull
\:Konstanty (1, 2, \dots)
\:Adresované pøímo -- M[konst.] -- budeme pou¾ívat písmena {\tt A-Z} jako aliasy
pro
buòky pamìti $-1$ a¾ $-26$, které nazýváme registry.
(tedy A={\tt M[-1]})
\:Adresované nepøímo -- {\tt M[M[konst.]]} -- budeme pou¾ívat zkratku [[konst.]]
\endlist

Samotný výpoèet probíhá takto:
\algo
\:Do smluvených bunìk umístíme vstup, obsah zbylých pamì»ových bunìk není
definován.
\:Provádíme program postupnì po instrukcích, dokud nedojdeme k haltu nebo konci
programu.
\:Pokud se program nezacyklil, tedy pokud skonèil, ze smluvených bunìk pøeèteme
výstup.
\endalgo


\h{Slo¾itost}
\> Jak dobøe popsat slo¾itost?
\numlist\ndotted
\:{\I {\csc Ram} s jednotkovou cenou}: èas $\approx$ \#instrukcí, prostor
$\approx$
maximální èíslo buòky minus minimální èíslo buòky pou¾ité pøi výpoètu.
Toto není moc dobrý nápad, proto¾e není nijak penalizována napøíklad práce s
velmi dlouhými èísly -- poøád je to jedna instrukce, tak¾e cena je stejná, ale
poèítaèe se tak pøece nechovají. Velikost èísel ale omezit nesmíme, proto¾e
bychom omezili pamì» (èísly ji adresujeme).
\:{\I{\csc Ram} s logaritmickou cenou}: cena instrukce $\approx$ \#bitù
zpracovávaných èísel,
prostor $\approx$ \# bitù v¹ech pou¾itých bunìk. To je teoreticky pøesné, ale
dost nepraktické (ve v¹ech slo¾itostech by byly logaritmy).
\:{\I{\csc Ram} s omezenými èísly}: jednotková cena instrukcí, ale èísla omezíme
nìjakým polynomem $P(n)$. Tím zmizí paradoxy prvního modelu, ale
mù¾eme adresovat jen polynomiální prostor (to nám ov¹em obvykle nevadí).
\endlist

Nadále tedy budeme pøedpokládat tøetí zmínìný model.

% Z minulých zápiskù.
\s{Definice:}
\itemize\ibull
\:{\I Èas bìhu algoritmu} $t(x)$ pro vstup~$x$ mìøíme jako sumu èasù provedený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

Nyní zkusíme zanalyzovat nìjaký konkrétní algoritmus. Vezmìme napøíklad øazení
pomocí pøímeho výbìru (selection sort). Na vstupu dostaneme poèet èísel $n$ (v
registru {\tt N}), v buòkách $1,\dots, n$ je nesetøídìná posloupnost èísel. Ta
pak
tøídíme následujícím algoritmem zapsaným v pseudokódu:
\algo
\:Pro $i=1$ do $n$:
\::$j\leftarrow i$
\::Pro $k=i$ do $n$:
\:::Je-li $[k]<[j]\Rightarrow j\leftarrow k$
\::$[i]$ prohodíme s $[j]$.
\endalgo

Jak by takový algoritmus vypadal zapsaný v instrukcích {\csc Ram}? Budeme muset
pou¾ít návì¹tí a goto místo cyklù, jména registrù místo promìnných a
tøeba prohození musíme provést pøes tøetí promìnnou. Nìjak takto:

\verbatim{	I <- 1
LOOP:	J <- I
	M <- I
MIN:	IF [J]>=[M] ==> GOTO NEXT
	M <- J
NEXT:	J <- J+1
	IF J<=N ==> GOTO MIN
	X <- [I]
	[I] <- [M]
	[M] <- X
	I <- I+1
	IF I<=N ==> GOTO LOOP
}

Pojïme se podívat, jaká je èasová slo¾itost jednotlivých èástí algoritmu.
Cyklus |MIN| provede za prùchod 3 nebo 4 instrukce, ale zajímá nás nejhor¹í
pøípad, tak¾e 4. Zavolá se $(N-I+1)$-krát, tedy celkem provede $4\cdot (N-I+1)$
instrukcí.

Mimo cyklu |MIN| je v |LOOP| je¹tì 7 instrukcí, tedy celý |LOOP| provede
$4\cdot (N-I+1)+7 = 4(N-1) + 11$ instrukcí.

Celkovì se dostáváme k souètu $$1+(\sum_{I=1}^{N} 4(N-I) + 11) = 1 + 11N +
4\cdot{N(N-1)\over 2} = 2N^2+9N + 1.$$

Na multiplikativních konstantách ale nezále¾í -- Na reálných strojích se
ceny jednotlivých (pro nás jednotkových) instrukcí stejnì li¹í, tak¾e
nemá cenu se multiplikativními konstantami zabývat (alespoò pøi prvním
pøiblí¾ení k problému).

$$2N^2 + 9N + 1 \approx N^2 + N$$

Navíc asymptoticky pomalej¹í funkce nakonec pro velké $N$ v¾dy prohraje. Tím
pádem nezále¾í ani na èlenech ni¾¹ích øádù:

$$N^2 + N \approx N^2$$

Kdy¾ u¾ toto víme, mù¾eme zanedbávat konstanty prùbì¾nì: $N$ cyklù po
$\approx\nobreak N$~krocích $\Rightarrow~\approx N^2$ krokù. To nás vede k zavedení
tzv.  {\I asymptotické notace:}

\h{Asymptotická notace}
\s{Definice:} Pro funkce $f,g: {\bb N} \rightarrow {\bb R}^+$ øekneme,
¾e $f$ je $\O(g)$ právì tehdy, kdy¾ $\exists c>0: \forall ^{*} n \in {\bb N}:
f(n) \leq c \cdot g(n)$.
Zde $\forall^* n \in {\bb N}$ je zkratka za \uv{$\exists n_0 \in {\bb N}:
\forall n \geq n_0$}, tedy
\uv{pro v¹echna~$n$ a¾ na~koneènì mnoho výjimek.}

\s{Poznámka:} $\O$-notace tedy vyjadøuje, ¾e funkce~$f$ je skoro v¹ude men¹í
nebo nejvý¹e rovná nìjakému reálnému násobku funkce~$g$. Aèkoliv zápis vypadá
jako rovnost, rozhodnì není symetrický: napøíklad platí $\log n=\O(n)$, ale
neplatí $n=\O(\log n)$. Formálnì by bylo lep¹í pova¾ovat $\O(g)$ za tøídu
funkcí, pro které platí, ¾e se dají shora odhadnout kladným násobkem funkce~$g$,
a~psát tedy~$f\in\O(g)$, ale zvyk je bohu¾el ¾elezná ko¹ile.

\s{Pøíklady:} $2{,}5n^{2} = \O(n^{2})$, $2{,}5n^{2}+30n = \O(n^{2})$.

\>Také platí:
$$
\O(f)+\O(g) \in \O(f+g),
$$
èím¾ myslíme, ¾e pokud vezmeme libovolnou $f'=O(f)$ a $g'=O(g)$, bude
$f'+g'=O(f+g)$.
To platí, jeliko¾ skoro v¹ude je $f' \leq cf$, $g'\leq dg$, a~tedy $f'+g' \le
cf+dg \le (c+d)(f+g)$.

\s{Cvièení:} Uka¾te, ¾e:
\itemize\ibull
\:$\O(f) \cdot \O(g)=\O(f \cdot g)$,
\:$\O(f+g)=\O(\max(f,g))$,
\:$\O(n^{2})+\O(n)=\O(n^{2}+n)=\O(n^{2})$.
\endlist

$\O$-notace popisuje horní odhad asymptotického chování funkce. Mnohdy v¹ak
potøebujeme také odhadnout funkci zespodu (chceme-li øíci, ¾e algoritmus
potøebuje {\I alespoò} nìjaké mno¾ství èasu nebo pamìti), pøípadnì z~obou stran:

\s{Definice:}

\itemize\ibull
\:$f=\Omega(g) \equiv \exists c>0:\forall^* n \in {\bb N}: f(n) \geq c\cdot
g(n)$.

$\Omega$-notace tedy øíká, ¾e hodnota funkce $f$ je v¾dy stejná nebo vy¹¹í ne¾
nìjaký $c$-násobek funkce $g$, a tedy $g=\O(f)$.
\:$f=\Theta(g) \equiv f=\O(g) \wedge f=\Omega(g)$

nebo výøeènìji:

$f=\Theta(g) \equiv \exists$ $c_{1},c_{2} > 0: \forall^* n \in {\bb
N}: c_{1}\cdot g(n) \leq f(n) \leq
c_{2}\cdot g(n)$ To znamená, ¾e existují nezáporné reálné konstanty
$c_{1},c_{2}$ takové, ¾e se funkce $f(n)$ dá ohranièit $c_{1}$- a
$c_{2}$-násobkem funkce $g(n)$.
\endlist

\>{\sl Poznámka:} Ona rovnost je dost zavádìjící. Není to toti¾ rovnost, není
to symetrické. Jiný, mo¾ná rozumnìj¹í pohled, je zavedení $\O(g)$ jako mno¾iny.
Pak by se dalo psát $f \in \O(g)$, nebo tøeba $\O(n) \subseteq \O(n^2)$.

\s{Porovnání rùstu funkcí:} (aneb jak moc máme algoritmy rádi podle jejich
chování od~nejlep¹ích k~nejhor¹ím)

\itemize\ibull
\:$\Theta(1) \ldots$ funkce zespoda i shora ohranièené konstantami
\:$\Theta(\log{( \log{n} )})$
\:$\Theta(\log{n})$ \dots\ logaritmická
\:$\Theta(n^{\varepsilon}), \varepsilon \in (0,1)$ \dots\ sublineární
\:$\Theta(n)$ \dots\ lineární
\:$\Theta(n^{2})$ \dots\ kvadratická
\:$\Theta(n^{k})$ \dots\ polynomiální
\:$\Theta(2^{n})$ \dots\ exponenciální pøi základu $2$
\:$\Theta(3^{n})$ \dots\ exponenciální pøi základu $3$
\:$\Theta(k^{n})$ \dots\  exponenciální pøi základu $k>1$
\:$\Theta(n!)$ \dots\ faktoriálová
\:$\Theta(n^{n})$
\:\dots\ nekoneènì mnoho dal¹ích tøíd (i mezi tìmi vý¹e uvedenými)
\endlist

\>{\sl Poznámka:} Pokud se v~odhadu slo¾itosti vyskytne logaritmus (jinde ne¾
v~exponentu), nezále¾í na tom, jaký má základ, proto¾e platí:
$$
\log_k{n}={{\log_c{n}}\over{\log_c{k}}}={{1}\over{\log_c{k}}}\cdot \log_c{n},
$$
kde $1/\log_c{k}$ je jen konstanta, tak¾e ji mù¾eme \uv{schovat do~$\O$}.

\s{Pøíklad:} Select sort (rozebraný vý¹e):
Kdy¾ jej pustíme na $n$ èísel, pak èasová slo¾itost je $T(n) = \Theta(n^2)$ a
prostorová $S(n) = \Theta(n)$.

\h{Úvod do grafových algoritmù}
Dal¹í dùle¾itou a zajímavou kapitolou jsou grafové algoritmy. Napøíklad
následující pøíklady lze (i kdy¾ to tak obèas na první pohled nevypadá) øe¹it
nìjakým grafovým algoritmem:
\itemize\ibull
\:Mám mapku silnièní sítì, v ní místa (vrcholy) oznaèená \uv{Doma} a \uv{©kola}.
Dostanu se do
¹koly (le¾í ve stejné komponentì souvislosti)? Dostanu se do ¹koly, kdy¾ v zimì
napadne hodnì snìhu a nìkteré cesty budou neprùjezdné? A jaký nejkrat¹í úsek
cest musí silnièáøi prohrnout, aby byla v¹echna místa na mapì dostupná?
\:Mìjme hlavolam \uv{Lloydova devítka} -- krabièku $3\times3$ se ètvereèky
oznaèenými èísly od jedné do osmi a jednou mezerou, ètvereèky jsou zamíchané a
na¹ím úkolem je správnì je seøadit pomocí pøesouvání ètvereèkù sousedících s
mezerou do této mezery. Jak to udìlat? Kolik nejménì krokù nám na
to staèí? Jde to vùbec se zadáním, které jsme dostali?
\:Jaké je nejkrat¹í (kladné, celé) èíslo v desítkové soustavì zapsané jen
èíslicemi 1, 0, které je dìlitelné tøinácti? Nakreslíme orientovaný graf s
vrcholy 0 a¾ 12
a hranami $(x,y),$ $y=10\cdot x \bmod 13$ a $y=(10\cdot x + 1) \bmod 13$
(z~ka¾dého vrcholu vychází jedna hrana za pøidání èíslice 1 a dal¹í za èíslici
0). Hledané èíslo existuje právì tehdy, kdy¾ graf obsahuje orientovaný sled
z~1~do~0. Jakým algoritmem takový sled najdeme?
\endlist
Podobné a dal¹í úlohy budeme øe¹it v následujících kapitolách.

\bye
