\input ../lecnotes.tex

\prednaska{1}{Úvodní pøíklady, definice RAM} {}

\h{Pøíklad: {\sc Reportá¾}}

Novináø má za úkol za rok napsat reportá¾ o pracovních podmínkách v jedné nejmenované
firmì. Musí tedy vyzkou¹et co nejvíce pracovních pozic. Chce ale, aby se mu neustále
zvy¹oval plat. Firma v rùzných èasech vypisuje pracovní místa.

Øeèeno matematicky, máme zadánu posloupnost $p_1,\, \dots, p_n$ reálných èísel
a~hledáme v ní nejdel¹í ostøe rostoucí vybranou podposloupnost.


\> Jak mù¾eme takový problém øe¹it?


{\I Podle definice}: budeme generovat v¹echny podposloupnosti a testovat, jestli jsou
rostoucí. Podposloupnost mù¾eme popsat charakteristickým vektorem, co¾ je posloupnost
nul a jednièek, kde na $i$-té pozici je $1$, právì kdy¾ podposloupnost obsahuje $i$-tý
èlen pùvodní posloupnosti. Charakteristické vektory odpovídají binárním zápisùm èísel
$1$ a¾ $2^n$ kde $n$ je poèet vypsaných prací.

Charakteristické vektory mù¾eme generovat napøíklad tak, ¾e si cifry binárního èísla
budeme udr¾ovat v poli a budeme pøièítat $1$. Po hlub¹ích úvahách (zvídaví hledejte
pojem amortizovaná èasová slo¾itost) zjistíme, ¾e na jedno pøiètení jednièky
potøebujeme prùmìrnì konstantnì mnoho operací.

Nyní nás bude zajímat kolik øádovì provedeme krokù. V¹ech charakteristických vektorù
je $2^n$. Pro ka¾dý zkontrolujeme, jestli je podposloupnost rostoucí, co¾ zabere $n$
krokù. Celkem tedy provedeme øádovì $2^n\cdot n$ krokù.

{\I Rekurzívnì}: vytvoøme funkci, která dostane zaèátek posloupnosti a najde v¹echna
roz¹íøení na rostoucí podposloupnost. Zajímá nás ale jen nejdel¹í podposloupnost,
polo¾me tedy $f(i_1, \, \dots, i_k) :=$ maximání délka rostoucí podposloupnosti
navazující na $x_{i_1}, \, \dots, x_{i_k}$.

Probereme v¹echna $j$~od $i_k+1$ do $n$ a pro ka¾dé $j$ takové, ¾e $x_j > x_{i_k}$,
nastavíme maximum $m \leftarrow \max(m, f(i_1, \, \dots, i_k, j) + 1)$. Jako výsledek
funkce vrátí $m$. Na~zaèátek posloupnosti pøidáme $-\infty$ a zavoláme $f(0)$.
%TODO sázet jako algoritmus

\algo

\:Pro $j = i_k + 1$ to $n$

\::Kdy¾ $x_j > x_{i_k}$

\:::$m \leftarrow \max (m, f(i_1, \dots, i_k, j) + 1)$

\:Vra» $m$

\endalgo


Nejhor¹ím pøípadem je rostoucí posloupnost, na které na¹e funkce vykoná øádovì $2^n$
krokù.

Zamysleme se, jestli potøebujeme prvních $k-1$ parametrù. Pokraèování podposloupnosti
mù¾e ovlivnit poze poslední parametr funkce $f$. Zjednodu¹íme tedy volání funkce a
místo $f(i_1, \dots, i_k)$ budeme volat $f(i_k)$.

{\I Rekurze s blbenkou}: $f(i)$ bude volána mnohokrát pro stejné $i$. Nejlépe je to
vidìt na pøíkladu rostoucí posloupnosti, kde je $f(i)$ volána po ka¾dém zavolání
$f(j)$ kde $j < i$.

V poli $X$ si pamatujeme výsledky funkce $f$ pro jednotlivá $i$, tedy
pole $X$ obsahuje na pozici $i$ hodnotu $f(i)$.

Cvièení: uka¾te, ¾e algoritmus vykoná øádovì $n^2$ operací a spotøebuje $n$~bunìk
pamìti.

{\I Bez rekurze}: v¹imnìme si, ¾e spoèítat $f(n)$ je velmi snadné ($f(n)=0$).

\algo

\:$f(n)=0$

\:$k=n-1 \dots 0$

\::$f(k)=0$

\::$j=k+1 \dots n$

\:::Kdy¾ $x_j > x_k$

\::::$f(k)= \max (f(k), f(j)+1)$

\endalgo


Rychlost jsme nezvý¹ili, dokonce ani pamì» jsme neu¹etøili, ale zbavili jsme se
rekurze.

{\I Pøevédst úlohu na grafovou} je standardní informatický trik. Vrcholy jsou èísla $V
:= \{1, \,\dots, n\}$, hrana $(i, j) \in E \equiv i < j$ \& $x_i < x_j$. Cesty v tomto
grafu odpovídají vybraným rostoucím posloupnostem a my hledáme nejdel¹í cestu v
acyklickém grafu, co¾ umíme (budeme umìt) lineárnì s velikostí grafu. Hran mù¾e být a¾
$\vert E\vert  = {n \choose 2} \approx~n^2$. Èím¾ jsme dostali dal¹í kvadratický
algoritmus.

{\I Datová struktura}: bìhem semestru poznáme ¹ikovnou datovou strukturu, která
obsahuje uspoøádané  dvojice reálných èísel $(x, y)$, kde $x$ je klíè a $y$ hodnota.
Po~této struktuøe budeme chtít aby umìla vlo¾it dvojici \<Insert>$(x, y)$ a dotaz
\<Query>: \<Query>($t$)$ := \max \{y \mid \exists x \geq t: (x, y)$ je ve
struktuøe$\}$.

Postupujeme podobnì jako v algoritmu {\I Bez rekurze} s tím rozdílem, ¾e kroky $4$~a¾
$6$ za nás udìlá datová struktura. Pro ka¾dé $k$ zavoláme \<Insert>$(x_j, f(j))$ a
\<Query>($x_{k+1}$). Obì trvají øádovì $\log n$, struktura nám vrátí nejvìt¹í hodnotu
$f(j)$ pro dané $x_{k+1}$.
%TODO lépe vysvìtlit

Provedeme tedy øádovì $n\cdot \log n$ krokù, co¾ je nejlep¹í známé øe¹ení.

\h{Algoritmus}

Na pøí¹tích pøedná¹kách budeme studovat algoritmy a jejich vlastnosti. Co~ale
algoritmus doopravdy je? Jak ho definovat? ®ádná poøádná definice algoritmu
neexistuje. Pro nás bude algoritmus program v nìjakém jazyce na nìjakém výpoèetním
stroji (viz definice RAM).

Churchova teze: v¹echny definice algoritmù jsou
ekvivalentní. Toto není opravdová vìta, spí¹ vyjadøuje, ¾e v¹echny rozumné definice
algoritmu definují v podstatì to samé.

\vskip 6pt \line{{\bf Model RAM} \hfil {}} \vskip 4pt

V pøedchozí èásti jsme mluvili o výpoèetním modelu, pojïme tedy nìjaký nadefinovat.
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 (RAM)

RAM poèítá jen s celými èísly (dále jen {\I èísla}). 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. Program samotný je
koneèná posloupnost instrukcí (také opatøených adresami) následujících druhù:

\>(kde $X, Y$ jsou nìjaké operandy)

\itemize\ibull

\:Datové pøesuny $X$ |<-| $Y$

\:Aritmetické, logické a bitové: $X$ |<-| $Y \oplus Z$

$\oplus\in\{|+|, |-|, |*|, |div|, |mod|, \&, \mid, |<<|, |>>|\}$ kde $\&, \mid$
znamenají logické and a or, $|<<|, |>>|$ znamenají bitový posun vlevo a vpravo.

\:Øídící: skok |goto| $Z$, podmínìný skok |Kdy¾ |$X$ |<| $Y$ |goto| $Z$||, zastavení
programu |halt|.
%\<label> \: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{Operandy}:

\itemize\ibull

\:Konstanty $(1, 2, \, \dots)$

\:Adresované pøímo -- {\tt [\<konst.>]} -- budeme pou¾ívat písmena {\tt A-Z} jako
aliasy pro buòky pamìti $-1$ a¾ $-26$ (tedy A={\tt [-1]}), které nazýváme {\it
registry} a budou nám slou¾it jako promìnné (samozøejmnì nejen ony).

\:Adresované nepøímo -- {\tt [[\<konst.>]]}

Mù¾eme se chtít podívat na adresu, kterou máme ulo¾enou v nìjaké buòce, podobnì jako
pointery v C.

\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 po instrukcích, dokud nedojdeme k {\tt halt}u nebo
konci programu.

\:Pokud se program nezacyklil, tedy pokud skonèil, ze smluvených bunìk
pøeèteme výstup.

\endalgo


\h{Míry slo¾itosti}

\numlist\ndotted

\:{\I RAM s jednotkovou cenou}: èas $=$ \# instrukcí pøi daném vstupu,\break prostor
$=$ \# bunìk do kterých algoritmus aspoò jednou zapsal bìhem 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 konstantou (tøeba $32$ bitù) omezit nesmíme,
proto¾e bychom omezili pamì» (èísly ji adresujeme) a co hùø i mo¾nou velikost vstupu.

\:{\I RAM s logaritmickou cenou}: cena instrukce $=$ \# bitù zpracovávaných èísel,
prostor $=$ \# bitù v¹ech pou¾itých bunìk. To je teoreticky pøesné, ale dost
nepraktické (ve v¹ech slo¾itostech by byly spousty logaritmù).

\:{\I RAM s omezenými èísly}: jednotková cena instrukcí, ale èísla omezíme nìjakým
polynomem $P(n)$, kde $n$ je velikost vstupu. 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 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ù instrukcí, které program provedl pøi zpracování vstupu $x$. Pokud se
pro daný vstup program nezastaví berme $t(x)=+ \infty$.

\:{\I Prostor bìhu algoritmu}
$s(x)$ je analogicky poèet pamì»ových bunìk pou¾itých pøi výpoètu se vstupem~$x$.

\endlist

\>Chceme zavést míru èasové a prostorové nároènosti programù zvanou slo¾itost.
Slo¾itost je maximum délky bìhu pøes v¹echny vstupy urèité délky.

\itemize\ibull \:{\I Mno¾ina mo¾ných vstupù} $X$ \:{\I Délka vstupu} je funkce $l:X
\rightarrow {\bb N}$ \:{\I Èasová slo¾itost} (v~nejhor¹ím pøípadì) je: $$T(n) := \max
\{t(x) \mid \hbox{$x$ je vstup délky $n$}\}.$$ \:{\I Prostorová slo¾itost}
(v~nejhor¹ím pøípadì) je: $$S(n) := \max \{s(x) \mid  \hbox{$x$ je vstup délky
$n$}\}.$$ \endlist

Podobnì mù¾eme zavést i slo¾itost v nejlep¹ím a prùmìrném pøípadì, ale ty budeme
pou¾ívat jen zøídka.

\bye

