1-uvod/1-uvod.tex

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