1-uvod/1-uvod.tex

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