From b705cb31095caeb2f087c73d01bb47d1e690b6f4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 4 Apr 2011 10:47:14 +0200 Subject: [PATCH] Uvod: Dalsi varka korektur --- 1-uvod/1-uvod.tex | 257 ++++++++++++++++++++++++++++------------------ 1 file changed, 156 insertions(+), 101 deletions(-) diff --git a/1-uvod/1-uvod.tex b/1-uvod/1-uvod.tex index aab035d..a8e0e4e 100644 --- a/1-uvod/1-uvod.tex +++ b/1-uvod/1-uvod.tex @@ -1,7 +1,6 @@ \input ../lecnotes.tex -\prednaska{1}{Úvodní pøíklady, definice RAM} -{} +\prednaska{1}{Úvodní pøíklady, definice RAM} {} \h{Pøíklad: {\sc Reportá¾}} @@ -9,8 +8,8 @@ Novin 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? @@ -18,165 +17,221 @@ nejdel {\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ý +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í, co¾ nám dává jednoduchý zpùsob jak je -generovat. +$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}$. +{\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)$. +funkce vrátí $m$. Na~zaèátek posloupnosti pøidáme $-\infty$ a zavoláme $f(0)$. %TODO sázet jako algoritmus + \algo -\:for $j = i_k + 1$ to $n$ -\::if $x_j > x_{i_k}$ -\:::$m |<-| \max (m, f(i_1, \dots, i_k), j + 1)$ -\:return $m$ + +\: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ù. -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)$. +Nejhor¹ím pøípadem je rostoucí posloupnost, na které na¹e funkce vykoná øádovì $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)$. + +{\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 Rekurze s blbenkou}: pøedchozí algoritmus poèítá mnohokrát tyté¾ vstupy, proto¾e -$f(i)$ bude nebo byla volána i pro v¹echny podposloupnosti zrovna zkoumané podposloupnosti. 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$~bunìk pamìti. +Cvièení: uka¾te, ¾e algoritmus vykoná øádovì $n^2$ operací a spotøebuje $n$~bunìk +pamìti. + +{\I Bez rekurze}: v¹imnìme si, ¾e spoèítat $f(n)$ je velmi snadné ($f(n)=0$). + +\algo + +\:$f(n)=0$ -{\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. +\:$k=n-1 \dots 0$ -{\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 \$(x, y)$ a dotaz \: -\($t$)~$:=~\max~\{y~\mid \exists x \geq t: (x, y)$ je ve struktuøe$\}$. +\::$f(k)=0$ -V jednom prùchodu zavoláme \$(x_j, f(j))$ a \($x_{k+1}$), obì trvají øádovì -$\log n$, struktura nám vrátí nejvìt¹í hodnotu $f(j)$ pro dané $x_{k+1}$. +\::$j=k+1 \dots n$ + +\:::Kdy¾ $x_j > x_k$ + +\::::$f(k)= \max (f(k), f(j)+1)$ + +\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. + +{\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 \$(x, y)$ a dotaz +\: \($t$)$ := \max \{y \mid \exists x \geq t: (x, y)$ je ve +struktuøe$\}$. + +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 \$(x_j, f(j))$ a +\($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í. -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. My budeme brát algoritmus jako program v -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á -vìta, spí¹ vyjadøuje, ¾e v¹echny rozumné definice algoritmu definují vpodstatì to -samé. - +\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). +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é. -\vskip 6pt -\line{{\bf Model RAM} \hfil {}} -\vskip 4pt +\vskip 6pt \line{{\bf Model RAM} \hfil {}} \vskip 4pt -Výpoèetních modelù je více, my vybereme jeden pomìrnì blízký skuteèným poèítaèùm: +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, dále jen {\I èísla} -- znaky, stringy a podobnì reprezentujeme -{\I èísly}, jejich posloupnostmi atd. Pamì» je tvoøena buòkami, které obsahují -{\I èísla}. Pamì»ové buòky jsou adresované takté¾ {\I èí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 + \:Datové 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|. -%\