1-uvod/1-uvod.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{1}{Úvodní pøíklady, definice RAM}
   4 {}
   5
   6 \h{Pøíklad: {\sc Reportá¾}}
   7
   8 Novináø má za úkol za rok napsat reportá¾ o pracovních podmínkách v jedné nejmenované
   9 firmì. Musí tedy vyzkou¹et co nejvíce pracovních pozic. Chce ale, aby se mu neustále
  10 zvy¹oval plat. Firma v rùzných èasech vypisuje pracovní místa.
  11
  12 Øeèeno matematicky, máme zadánu posloupnost $p_1,\, \dots, p_n$ reálných èísel a~hledáme
  13 nejdel¹í ostøe rostoucí vybranou podposloupnost.
  14
  15
  16 \> Jak mù¾eme takový problém øe¹it?
  17
  18
  19 {\I Podle definice}: budeme generovat v¹echny podposloupnosti a testovat, jestli jsou
  20 rostoucí. Podposloupnost mù¾eme popsat charakteristickým vektorem, co¾ je posloupnost
  21 nul a jednièek, kde na $i$-té pozici je $1$ právì kdy¾ podposloupnost obsahuje $i$-tý
  22 èlen pùvodní posloupnosti. Charakteristické vektory odpovídají binárním zápisùm èísel
  23 $1$ a¾ $2^n$ kde $n$ je poèet vypsaných prací, co¾ nám dává jednoduchý zpùsob jak je
  24 generovat.
  25
  26 Nyní nás bude zajímat kolik øádovì provedeme krokù. V¹ech charakteristických vektorù
  27 je $2^n$. Pro ka¾dý zkontrolujeme, jestli je podposloupnost rostoucí, co¾ zabere $n$
  28 krokù. Celkem tedy provedeme øádovì $2^n\cdot n$ krokù.
  29
  30 {\I Rekurzívnì}: funkce dostane zaèátek posloupnosti a najde v¹echna roz¹íøení na
  31 rostoucí podposloupnost
  32 $f(i_1, \, \dots, i_k) :=$ maximání délka rostoucí podposloupnosti navazující na $x_{i_1},
  33 \, \dots, x_{i_k}$.
  34 Probereme v¹echna $j$~od $i_k+1$ do $n$ a pro ka¾dé $j$ takové, ¾e $x_j > x_{i_k}$,
  35 nastavíme maximum $m \leftarrow \max(m, f(i_1, \, \dots, i_k, j) + 1)$. Jako výsledek
  36 funkce vrátí $m$. Na zaèátek posloupnosti pøidáme $-\infty$ a zavoláme $f(0)$.
  37 %TODO sázet jako algoritmus
  38 \algo
  39 \:for $j = i_k + 1$ to $n$
  40 \::if $x_j > x_{i_k}$
  41 \:::$m |<-| \max (m, f(i_1, \dots, i_k), j + 1)$
  42 \:return $m$
  43 \endalgo
  44
  45 Nejhor¹ím pøípadem je rostoucí posloupnost, na které na¹e funkce vykoná øádovì $2^n$ krokù.
  46
  47 Volání funkce mù¾eme zjednodu¹it, kdy¾ si uvìdomíme, ¾e prvních $k-1$ parametrù vùbec
  48 nepotøebujeme, tak¾e mù¾eme rovnou volat $f(i_k)$.
  49
  50 {\I Rekurze s blbenkou}: pøedchozí algoritmus poèítá mnohokrát tyté¾ vstupy, proto¾e
  51 $f(i)$ bude nebo byla volána i pro v¹echny podposloupnosti zrovna zkoumané podposloupnosti.
  52 V poli $X$ si pamatujeme výsledky funkce $f$ pro jednotlivá $i$, tedy
  53 pole $X$ obsahuje na pozici $i$ hodnotu $f(i)$.
  54
  55 Cvièení: uka¾te, ¾e algoritmus vykoná øádovì $n^2$ operací a spotøebuje $n$~bunìk pamìti.
  56
  57 {\I Pøevédst úlohu na grafovou} je standardní informatický trik.
  58 Vrcholy jsou èísla $V := \{1, \,\dots, n\}$,
  59 hrana $(i, j) \in E \equiv i < j\, \& \,x_i~<~x_j$. Cesty v tomto grafu odpovídají
  60 vybraným rostoucím posloupnostem a my hledáme nejdel¹í cestu v acyklickém grafu, co¾ umíme (budeme umìt)
  61 lineárnì s velikostí grafu. Hran mù¾e být a¾ $\vert E\vert  = {n \choose
  62 2} \approx~n^2$. Èím¾ jsme dostali dal¹í kvadratický algoritmus.
  63
  64 {\I Datová struktura}: bìhem semestru poznáme ¹ikovnou datovou strukturu, která obsahuje
  65 uspoøádané  dvojice reálných èísel $(x, y)$ kde $x$ je klíè a $y$ hodnota. Po~této
  66 struktuøe budeme chtít aby umìla vlo¾it dvojici \<Insert>$(x, y)$ a dotaz \<Query>:
  67 \<Query>($t$)~$:=~\max~\{y~\mid \exists x \geq t: (x, y)$ je ve struktuøe$\}$.
  68
  69 V jednom prùchodu zavoláme \<Insert>$(x_j, f(j))$ a \<Query>($x_{k+1}$), obì trvají øádovì
  70 $\log n$, struktura nám vrátí nejvìt¹í hodnotu $f(j)$ pro dané $x_{k+1}$.
  71 %TODO lépe vysvìtlit
  72
  73 Provedeme tedy øádovì $n\cdot \log n$ krokù, co¾ je nejlep¹í známé øe¹ení.
  74
  75 Na pøí¹tích pøedná¹kách budeme studovat algoritmy a jejich vlastnosti. Co~ale
  76 algoritmus doopravdy je? Jak ho definovat?
  77 ®ádná poøádná definice algoritmu neexistuje. My budeme brát algoritmus jako program v
  78 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á
  79 vìta, spí¹ vyjadøuje, ¾e v¹echny rozumné definice algoritmu definují vpodstatì to
  80 samé.
  81
  82
  83
  84
  85 \vskip 6pt
  86 \line{{\bf Model RAM} \hfil {}}
  87 \vskip 4pt
  88
  89 Výpoèetních modelù je více, my vybereme jeden pomìrnì blízký skuteèným poèítaèùm:
  90
  91 \s{Definice:} Random Access Machine (RAM)
  92
  93 RAM poèítá jen s celými èísly, dále jen {\I èísla} -- znaky, stringy a podobnì reprezentujeme
  94 {\I èísly}, jejich posloupnostmi atd. Pamì» je tvoøena buòkami, které obsahují
  95 {\I èísla}. Pamì»ové buòky jsou adresované takté¾ {\I èísly}. Program samotný je
  96 koneèná posloupnost instrukcí (také opatøených adresami) následujících druhù:
  97 \itemize\ibull
  98 \:Datové pøesuny $X$ |<-| $Y$
  99 \:Aritmetické a logické:
 100 $X$ |<-| $Y \oplus Z, \oplus\in\{|+|, |-|, |*|, |div|, |mod|, \&,
 101 {\tt\char124}, |<<|, |>>|\}$
 102 \:Øídící: skok |goto| $Z$, podmínìný skok |if |$X$ |<| $Y$ |goto| $Z$||,
 103 zastavení programu |halt|.
 104 %\<label>
 105 %\:Podmínky: pro libovolnou nepodmínìnou instrukci mù¾u pou¾ít \hfil \break
 106 %if~$X$~|<|~$Y$~|==>|~instrukce % Tady to prosím je¹tì zkontroluj. Myslím, ¾e
 107 % zápis je správný, ale sází se to divnì a vidím èerný obdélníèek na konci
 108 % øádku. Díky.
 109 \endlist
 110
 111 \s{Operandy}:
 112 \itemize\ibull
 113 \:Konstanty $(1, 2, \, \dots)$
 114 \:Adresované pøímo -- |[\<konst.>]| -- budeme pou¾ívat písmena {\tt A-Z} jako aliasy
 115 pro
 116 buòky pamìti $-1$ a¾ $-26$ (tedy A={\tt [-1]}), které nazýváme registry a budou nám slou¾it jako promìnné.
 117
 118 \:Adresované nepøímo -- {\tt [[\<konst.>]]}
 119
 120 Mù¾eme se chtít podívat na adresu, kterou máme ulo¾enou v nìjaké buòce (podobnì jako
 121 pointry v C).
 122 \endlist
 123
 124 \> Samotný výpoèet probíhá takto:
 125
 126 \algo
 127 \:Do smluvených bunìk umístíme vstup, obsah zbylých pamì»ových bunìk není
 128 definován.
 129 \:Provádíme program postupnì po instrukcích, dokud nedojdeme k haltu nebo konci
 130 programu.
 131 \:Pokud se program nezacyklil, tedy pokud skonèil, ze smluvených bunìk pøeèteme
 132 výstup.
 133 \endalgo
 134
 135
 136 \h{Míry slo¾itosti}
 137 \> Chceme zavést míru èasové a prostorové nároènosti programù, které budeme øíkat
 138 slo¾itost.
 139 \numlist\ndotted
 140 \:{\I RAM s jednotkovou cenou}: èas $=$ \# instrukcí pøi daném
 141 vstupu,\break prostor
 142 $=$
 143 \# bunìk do kterých algoritmus aspoò jednou zapsal bìhem výpoètu.
 144
 145 Toto není moc dobrý nápad, proto¾e není nijak penalizována napøíklad práce s
 146 velmi dlouhými {\I èísly} -- poøád je to jedna instrukce, tak¾e cena je stejná, ale
 147 poèítaèe se tak pøece nechovají. Velikost {\I èísel} ale konstantou (tøeba $32$ bitù) omezit nesmíme, proto¾e
 148 bychom omezili pamì» ({\I èísly} ji adresujeme) a co hùø i mo¾nou velikost vstupu.
 149 \:{\I RAM s logaritmickou cenou}: cena instrukce $=$ \# bitù
 150 zpracovávaných {\I èísel},
 151 prostor $=$ \# bitù v¹ech pou¾itých bunìk. To je teoreticky pøesné, ale
 152 dost nepraktické (ve v¹ech slo¾itostech by byly spousty logaritmù).
 153 \:{\I RAM s omezenými {\I èísly}}: jednotková cena instrukcí, ale {\I èísla} omezíme
 154 nìjakým polynomem $P(n)$, kde $n$ je velikost vstupu. Tím zmizí paradoxy prvního modelu, ale
 155 mù¾eme adresovat jen polynomiální prostor (to nám ov¹em obvykle nevadí).
 156 \endlist
 157
 158 Nadále budeme pøedpokládat tøetí zmínìný model.
 159
 160 % Z minulých zápiskù.
 161 \s{Definice:}
 162 \itemize\ibull
 163 \:{\I Èas bìhu algoritmu} $t(x)$ pro vstup~$x$ mìøíme jako sumu èasù
 164 instrukcí, které program provedl pøi zpracování vstupu
 165 $x$. Pokud se pro daný vstup program nezastaví berme $t(x)=+ \infty$.
 166 \:{\I Prostor bìhu algoritmu} $s(x)$ je analogicky poèet pamì»ových
 167 bunìk pou¾itých pøi výpoètu se vstupem~$x$.
 168 \endlist
 169
 170 Slo¾itost je maximum délky bìhu pøes v¹echny vstupy urèité délky.
 171
 172 \itemize\ibull
 173 \:{\I Mno¾ina mo¾ných vstupù} $X$
 174 \:{\I Délka vstupu} je funkce $l:X \rightarrow {\bb N}$
 175 \:{\I Èasová slo¾itost} (v~nejhor¹ím pøípadì) je:
 176 $$T(n) := \max \{t(x) \mid \hbox{$x$ je vstup délky $n$}\}.$$
 177 \:{\I Prostorová slo¾itost} (v~nejhor¹ím pøípadì) je:
 178 $$S(n) := \max \{s(x) \mid  \hbox{$x$ je vstup délky $n$}\}.$$
 179 \endlist
 180
 181 Podobnì mù¾eme zavést i slo¾itost v nejlep¹ím a prùmìrném pøípadì, ale ty budeme
 182 pou¾ívat jen zøídka.
 183
 184 \bye
 185