From 9579d75684b3f628f5e6f923eb3600a33ad4699d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 17 Mar 2011 19:49:03 +0100 Subject: [PATCH] Uvod od Karla --- 1-uvod/1-uvod.tex | 162 ++++++++++++++++++++++++++++++++++++++++++++++ 1-uvod/Makefile | 3 + 2 files changed, 165 insertions(+) create mode 100644 1-uvod/1-uvod.tex create mode 100644 1-uvod/Makefile diff --git a/1-uvod/1-uvod.tex b/1-uvod/1-uvod.tex new file mode 100644 index 0000000..abb1594 --- /dev/null +++ b/1-uvod/1-uvod.tex @@ -0,0 +1,162 @@ +\input ../lecnotes.tex + +\prednaska{1}{Úvodní pøíklady, definice RAM} +{(zapsal Karel Král)} +%Úvodní pøíklady, definice modelu RAM se nevlezlo na øádek + +\h{Pøíklad: {\sc 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. + +Ø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. + + +\> Jak mù¾eme takový problém øe¹it? +\numlist\ndotted +\:{\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. + +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)$. + +Nejhor¹ím pøípadem je rostoucí posloupnost na které na¹e funkce vykoná $2^n$ krokù. + +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 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 +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. + +\:{\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 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)$. + +Provedeme tedy øádovì $n\cdot log(n)$ krokù, co¾ je nejlep¹í známé øe¹ení. +\endlist + +\s{Definice:} 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. + +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é. + + + + +\vskip 6pt +\line{{\bf Model RAM} \hfil {(zapsal Martin Koutecký)}} +\vskip 4pt + +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 +koneèná posloupnost instrukcí (také opatøených adresami) následujících druhù: +\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| +%\