\input ../lecnotes.tex
-\prednaska{1}{Úvodní pøíklady, definice RAM}
-{(zapsal Karel Král)}
-%Úvodní pøíklady, definice modelu RAM se nevlezlo na øádek
+\prednaska{1}{Úvodní pøíklady, definice RAM} {}
-\h{Pøíklad: {\sc Reportá¾}}
+\h{Pøíklad: {\csc Reportá¾}}
-Novináø má za úkol za jeden rok vyzkou¹et co nejvíc pracovních pozic v urèité firmì a
-napsat o této firmì reportá¾. Chce ale aby se mu neustále zvy¹oval plat. Firma v
-rùzných èasech vypisuje pracovní místa.
+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
-nejdel¹í ostøe rostoucí vybranou podposloupnost.
+Ø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?
-\numlist\ndotted
-\:{\I Podle definice}: budeme generovat v¹echny podposloupnosti a testovat jestli jsou
+
+
+{\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.
+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ì}: funkce dostane zaèátek posloupnosti a najde v¹echna roz¹íøení na
-rostoucí podposloupnost
-$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)$.
+{\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ù.
-Nejhor¹ím pøípadem je rostoucí posloupnost na které na¹e funkce vykoná $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)$.
-Volání funkce mù¾eme zjednodu¹it, kdy¾ si uvìdomíme, ¾e prvních $k-1$ parametrù vùbec
-nepotøebujeme, tak¾e mù¾eme rovnou 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$.
-\:{\I 2. s blbenkou}: efektivitu algoritmu mù¾eme zvý¹it tím, ¾e ho nenecháme poèítat
-to samé dokola. V poli $X$ si pamatujeme výsledky funkce $f$ pro jednotlivá $i$, tedy
+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$~pamìti.
+Cvièení: uka¾te, ¾e algoritmus vykoná øádovì $n^2$ operací a spotøebuje $n$~bunìk
+pamìti.
-\:{\I Pøevédst úlohu na grafovou} je standartní informatický trik.
-Vrcholy jsou èísla $V := \{1, \,\dots, n\}$,
-hrana $(i, j) \in E \equiv i \le j\, \& \,x_i~\le~x_j$. Cesty v tomto grafu jsou vybrané
-posloupnosti 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¾ ${\tt\char124}E{\tt\char124} = {n \choose
-2} \approx n^2$. Èím¾ jsme dostali dal¹í kvadratický algoritmus.
+{\I Bez rekurze}: v¹imnìme si, ¾e spoèítat $f(n)$ je velmi snadné ($f(n)=0$).
-\:{\I Datová struktura}: vytvoøí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(t) :=
-max\{y {\tt\char124} \exists x \geq t: (x, y)$ je ve struktuøe$\}$.
-V jednom prùchodu zavoláme $Insert(x_j, f(j))$ a $Query(x_{k+1})$, obì trvají øádovì
-$log(n)$.
+\algo
-Provedeme tedy øádovì $n\cdot log(n)$ krokù, co¾ je nejlep¹í známé øe¹ení.
-\endlist
+\:$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)$
-\s{Definice:} Algoritmus
+\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.
-®ádná poøádná definice algoritmu neexistuje. My budeme brát algoritmus jako program v
-nìjakém jazyce na nìjakém výpoèetním stroji.
+{\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$\}$.
-Churchova teze: v¹echny definice algoritmù jsou ekvivalentní. Toto není opravdová
-vìta, spí¹ vyjadøuje, ¾e v¹echny rozumné definice algoritmu definují vpodstatì to
-samé.
+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).
-\vskip 6pt
-\line{{\bf Model RAM} \hfil {(zapsal Martin Koutecký)}}
-\vskip 4pt
+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é.
-Výpoèetních modelù je více, my vybereme jeden pomìrnì blízký skuteèným poèítaèùm:
+\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 -- 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
+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
-\:Pøesuny $X$ |<-| $Y$
-\:Aritmetické a logické:
-$X$ |<-| $Y \oplus Z, \oplus\in\{|+|, |-|, |*|, |div|, |mod|, \&,
-{\tt\char124}, |<<|, |>>|\}$
-\:Øídící: skok |goto| $Z$, podmínìný skok |if [|$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.
+
+\: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{Poznámka} (operandy):
+\s{Operandy}:
+
\itemize\ibull
+
\:Konstanty $(1, 2, \, \dots)$
-\:Adresované pøímo -- |[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 [-1]})
-\:Adresované nepøímo -- {\tt [[konst.]]}
+
+\: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:
+
+\>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.
+
+\: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{Slo¾itost}
-\> Jak dobøe popsat slo¾itost?
+\h{Míry slo¾itosti}
+
\numlist\ndotted
-\:{\I Ram s jednotkovou cenou}: èas $\approx$ \#instrukcí pøi daném
-vstupu,\break prostor
-$\approx$
-\#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í. Navíc bychom jakýkoliv problém mohli vyøe¹it v
-konstantním èase. Velikost èísel ale omezit nesmíme, proto¾e
-bychom omezili pamì» (èísly ji adresujeme).
-\:{\I 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 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.
+\:{\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ù 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$}\}.$$
+
+\:{\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
projects / ads1.git / blobdiff