From 0d98e8a74ced5c20ca8ca20e2836ffb4c1c96b93 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 24 Apr 2009 09:12:30 +0200 Subject: [PATCH] Zapisky o RAMu --- 2-ram/2-ram.tex | 238 ++++++++++++++++++++++++++++++++++++++++++++++++ 2-ram/Makefile | 3 + 2 files changed, 241 insertions(+) create mode 100644 2-ram/2-ram.tex create mode 100644 2-ram/Makefile diff --git a/2-ram/2-ram.tex b/2-ram/2-ram.tex new file mode 100644 index 0000000..ae78ad8 --- /dev/null +++ b/2-ram/2-ram.tex @@ -0,0 +1,238 @@ +\input ../lecnotes.tex + +\prednaska{2}{Slo¾itost, grafové algoritmy} +{(zapsal Martin Koutecký)} + +\h{Model {\sc Ram}} + +Pøi analýze algoritmu bychom chtìli nìjak popsat jeho slo¾itost. Abychom mohli + udìlat toto, potøebujeme nejprve definovat výpoèetní model. 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 ({\sc Ram}) + +{\sc Ram} poèítá jen s èí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. A program samotný je +koneèná posloupnost instrukcí následujících druhù: +\itemize\ibull +\:Aritmetické a logické: +$X \leftarrow Y \oplus Z, \oplus\in\{+, -, \times, \div,\mod, \&\&, \|, <<, +>>\}$ +\:Skoky: goto LABEL +\:Podmínky: pro libovolnou nepodmínìnou instrukci mù¾u pou¾ít +if~$X~<~Y~\Rightarrow$~instrukce +\:Øídící: goto, halt. +\endlist + +\s{Poznámka} (operandy): +\itemize\ibull +\:Konstanty (1,2,\dots) +\:Adresované pøímo - M[konst.] -- budeme pou¾ívat písmena A-Z jako aliasy pro +registry -1 a¾ -26 +(tedy A=M[-1]) +\:Adresované nepøímo -- M[M[konst.]] - budeme pou¾ívat zkratku [[konst.]] +\endlist + +Samotný výpoèet probíhá takto: +\algo +\:Do smluvených bunìk umístíme vstup, obsah zbylých pamì»ových bunìk není +definován. +\:Provádíme program postupnì po instrukcích, dokud nedojdeme k haltu nebo konci +programu. +\:Pokud se program nezacyklil, tedy pokud skonèil, ze smluvených bunìk pøeèteme +výstup. +\endalgo + + +\h{Slo¾itost} +Jak dobøe popsat slo¾itost? +\numlist\ndotted +\:{\sc Ram} s jednotkovou cenou: èas $\approx$ \#instrukcí, prostor $\approx$ +maximální èíslo buòky minus minimální èíslo buòky pou¾ité pøi výpoètu. +Toto není moc dobrý nápad, proto¾e není nijak penalizována napøíklad práce s +velmi dlouhými èísly -- poøád je to jedna instrukce, tak¾e cena je stejná, ale +poèítaèe se tak pøece nechovají. Velikost èísel ale omezit nesmíme, proto¾e +bychom omezili pamì» (èísly ji adresujeme). +\:{\sc Ram} s logaritmickou cenou: èas $\approx$ \#bitù zpracovávaných èísel, +prostor $\approx$ \# bitù v¹ech pou¾itých bunìk. To je teoreticky pøesné, ale +dost nepraktické (ve v¹ech slo¾itostech by byly logaritmy). +\:{\sc Ram} s omezenými èísly: jednotková cena instrukcí, ale èísla omezíme na +$\leq P(n)$, $P(n)$ je polynom. Tím zmizí paradoxy prvního modelu, ale mù¾eme +adresovat jen polynomiální prostor (to nám obvykle nevadí). +\endlist + +% Z minulých zápiskù. +\s{Definice:} +\itemize\ibull +\:{\I Èas bìhu algoritmu} $t(x)$ pro vstup~$x$ mìøíme jako poèet +elementárních operací, které program provedl pøi zpracování vstupu +$x$. +\:{\I Prostor bìhu algoritmu} $s(x)$ je analogicky poèet pamì»ových +bunìk spotøebovaných pøi výpoètu se vstupem~$x$. +\:{\I Èasová slo¾itost} (v~nejhor¹ím pøípadì) je: +$$T(n) := \max \{t(x) ; \hbox{$x$ je vstup délky $n$}\}.$$ +\:{\I Prostorová slo¾itost} (v~nejhor¹ím pøípadì) je: +$$S(n) := \max \{s(x) ; \hbox{$x$ je vstup délky $n$}\}.$$ +\endlist + +Nyní zkusíme zanalyzovat nìjaký konkrétní algoritmus. Vezmìme napøíklad øazení +pomocí pøímeho výbìru (selection sort). Na vstupu dostaneme v registru N poèet +èísel, v buòkách 1\dots n je nesetøídìná posloupnost èísel. Ty pak tøídíme +následujícím algoritmem zapsaném v pseudokódu: +\algo +\:Pro $i=1$ do $n$: +\::$j\leftarrow i$ +\::Pro $k=i$ do $n$: +\:::Je-li $[k]<[j]\Rightarrow j\leftarrow k$ +\::$[i]\leftrightarrow[j]$ +\endalgo + +Jak by takový algoritmus vypadal zapsaný v instrukcích {\sc Ram}? Budeme muset +pou¾ít návì¹tí a goto místo cyklù, jména registrù místo promìnných a +tøeba prohození musíme provést pøes tøetí promìnnou. Nìjak takto: + +%Tady vá¾nì nevím jak formátovat, aby to bylo hezké. Nejvíce by se mi líbil +% verbatim, ale jak v nìm udìlat rozumnì ¹ipeèky? Tøeba => a <- ? +\verbatim{ + I <- 1 +LOOP: J <- I + M <- I +MIN: IF [J]<[M] ==> M <- J + J <- J+1 + IF J<=N ==> GOTO MIN + X <- [I] + [I] <- [M] + [M] <- X + I <- I+1 + IF I<=N ==> GOTO LOOP +} + + +Pojïme se podívat, jaká je èasová slo¾itost jednotlivých èástí algoritmu. +Cyklus MIN provede $3\cdot (N-I+1)$ instrukcí. Mimo cyklu MIN je v LOOP je¹tì 7 +instrukcí, tedy celý LOOP provede $3\cdot (N-I+1)+7$ instrukcí. Celkovì se +dostáváme k souètu +$$1+3\cdot N+7+3\cdot (N-1)+7+3\cdot (N-2)+7+3\cdot (N-3)+\dots +3\cdot 1+7 =$$ +$$1+7\dots N+3\dots {{N(N+1)}\over{2}} = {{3}\over{2}}N^2 + 8,5N + 1$$ + +Na multiplikativních konstantách ale nezále¾í -- zaprvé se na reálných strojích +ceny jednotlivých (pro nás jednotkových) instrukcí stejnì li¹í, zadruhé +asymptoticky pomalej¹í funkce stejnì pro velké N v¾dy prohraje, tak¾e nemá cenu +(alespoò pøi prvním pøiblí¾ení k problému) multiplikativními konstantami se +zabývat. Tím pádem nezále¾í ani na èlenech ni¾¹í øádù: +$$1,5N^2 + 8,5N + 1 \leq 1,5N^2 + 8,5N^2 + N^2 = 11N^2\approx N^2$$ +Kdy¾ u¾ toto víme, mù¾eme zanedbávat konstanty prùbì¾nì: $N$ cyklù po +$\approx~N$~krocích $\Rightarrow~\approx~N^2$ krokù. To nás vede k zavedení tzv. +{\I asymptotické notace} + +\h{Asymptotická notace} +% Okopírováno z minulých zápiskù, lehké opravy, na konci ukazujeme select sort +% místo E.A. +\s{Definice:} Pro funkce $f,g: {\bb N} \rightarrow {\bb R}^+$ øekneme, +¾e $f$ je $\O(g)$ právì tehdy, kdy¾ $\exists c>0: \forall ^{*} n \in {\bb N}: +f(n) \leq c \cdot g(n)$. +Zde $\forall^* n \in {\bb N}$ je zkratka za \uv{$\exists n_0 \in {\bb N}: +\forall n \geq n_0$}, tedy +\uv{pro v¹echna~$n$ a¾ na~koneènì mnoho výjimek.} + +\s{Poznámka:} $\O$-notace tedy vyjadøuje, ¾e funkce~$f$ je skoro v¹ude men¹í +nebo nejvý¹e rovná nìjakému reálnému násobku funkce~$g$. Aèkoliv zápis vypadá +jako rovnost, rozhodnì není symetrický: napøíklad platí $\log n=\O(n)$, ale +neplatí $n=\O(\log n)$. Formálnì by bylo lep¹í pova¾ovat $\O(g)$ za tøídu +funkcí, pro které platí, ¾e se dají shora odhadnout kladným násobkem funkce~$g$, +a~psát tedy~$f\in\O(g)$, ale zvyk je bohu¾el ¾elezná ko¹ile. + +\s{Pøíklady:} $2.5n^{2} = \O(n^{2})$, $2.5n^{2}+30n = \O(n^{2})$. + +\>Také platí: +$$ +\O(f)+\O(g) \in \O(f+g), +$$ +èím¾ myslíme, ¾e pokud vezmeme libovolnou $f'=O(f)$ a $g'=O(g)$, bude +$f'+g'=O(f+g)$. +To platí, jeliko¾ skoro v¹ude je $f' \leq cf$, $g'\leq dg$, a~tedy $f'+g' \le +cf+dg \le (c+d)(f+g)$. + +\s{Cvièení:} Uka¾te, ¾e: +\itemize\ibull +\:$\O(f) \cdot \O(g)=\O(f \cdot g)$, +\:$\O(f+g)=\O(\max(f,g))$, +\:$\O(n^{2})+\O(n)=\O(n^{2}+n)=\O(n^{2})$. +\endlist + +$\O$-notace popisuje horní odhad asymptotického chování funkce. Mnohdy v¹ak +potøebujeme také odhadnout funkci zespodu (chceme-li øíci, ¾e algoritmus +potøebuje {\I alespoò} nìjaké mno¾ství èasu nebo pamìti), pøípadnì z~obou stran: + +\s{Definice:} + +\itemize\ibull +\:$f=\Omega(g) \equiv \exists c>0:\forall^* n \in {\bb N}: f(n) \geq c\cdot +g(n)$. + +$\Omega$-notace tedy øíká, ¾e hodnota funkce $f$ je v¾dy stejná nebo vy¹¹í ne¾ +nìjaký $c$-násobek funkce $g$, a tedy $g=\O(f)$. +\:$f=\Theta(g) \equiv f=O(g) \wedge f=\Omega(g)$ + +nebo výøeènìji: + +$f=\Theta(g) \equiv \exists$ $c_{1},c_{2} > 0: c_{1}\cdot g(n) \leq f(n) \leq +c_{2}\cdot g(n)$ To znamená, ¾e existují nezáporné reálné konstanty +$c_{1},c_{2}$ takové, ¾e se funkce $f(n)$ dá ohranièit $c_{1}$- a +$c_{2}$-násobkem funkce $g(n)$. +\endlist + +\s{Porovnání rùstu funkcí:} (aneb jak moc máme algoritmy rádi podle jejich +chování od~nejlep¹ích k~nejhor¹ím) + +\itemize\ibull +\:$\Theta(1) \ldots$ funkce zespoda i shora ohranièené konstantami +\:$\Theta(\log{( \log{n} )})$ +\:$\Theta(\log{n})$ \dots\ logaritmická +\:$\Theta(n^{\varepsilon}), \varepsilon \in (0,1)$ \dots\ sublineární +\:$\Theta(n)$ \dots\ lineární +\:$\Theta(n^{2})$ \dots\ kvadratická +\:$\Theta(n^{k})$ \dots\ polynomiální +\:$\Theta(2^{n})$ \dots\ exponenciální pøi základu $2$ +\:$\Theta(3^{n})$ \dots\ exponenciální pøi základu $3$ +\:$\Theta(k^{n})$ \dots\ exponenciální pøi základu $k>1$ +\:$\Theta(n!)$ \dots\ faktoriálová +\:$\Theta(n^{n})$ +\:\dots\ nekoneènì mnoho dal¹ích tøíd (i mezi tìmi vý¹e uvedenými) +\endlist + +\>{\sl Poznámka:} Pokud se v~odhadu slo¾itosti vyskytne logaritmus (jinde ne¾ +v~exponentu), nezále¾í na tom, jaký má základ, proto¾e platí: +$$ +\log_k{n}={{\log_c{n}}\over{\log_c{k}}}={{1}\over{\log_c{k}}}\cdot \log_c{n}, +$$ +kde $1/\log_c{k}$ je jen konstanta, tak¾e ji mù¾eme \uv{schovat do~$\O$.} + +\s{Pøíklad:} Select sort (rozebraný vý¹e): +Kdy¾ jej pustíme na $n$ èísel, pak èasová slo¾itost je $T(n) = \Theta(n^2)$ a +prostorová $S(n) = \Theta(n)$. + +\h{Úvod do grafových algoritmù} +Dal¹í dùle¾itou a zajímavou kapitolou jsou grafové algoritmy. Napøíklad +následující pøíklady lze (i kdy¾ to tak obèas na první pohled nevypadá) øe¹it +nìjakým grafovým algoritmem: +\itemize\ibull +\:Mám mapku silnièní sítì, v ní oznaèené \uv{Doma} a \uv{©kola}. Dostanu se do +¹koly (le¾í ve stejné komponentì souvislosti)? Dostanu se do ¹koly, kdy¾ v zimì +napadne hodnì snìhu a nìkteré cesty budou neprùjezdné? A jaký nejkrat¹í úsek +cest musí silnièáøi prohrnout, aby byla v¹echna místa na mapì dostupná? +\:Mìjme hlavolam \uv{Lloydova devítka} -- krabièku $3\times3$ s ètvereèky +oznaèenými èísly od jedné do osmi a jednou mezerou, ètvereèky jsou zamíchané a +na¹ím úkolem je správnì je seøadit. Jak to udìlat? Kolik nejménì krokù nám na +to staèí? Jde to vùbec se zadáním, které jsme dostali? +\:Jaké je nejkrat¹í (kladné, celé) èíslo v desítkové soustavì zapsané jen +èíslicemi 1, 0 dìlitelné tøemi? Nakreslíme orientovaný graf s vrcholy 1 a¾ 13 +a hranami $(x,y),$ $y=10\cdot x \mod 13$ a $y=(10\cdot x + 1) \mod 13$ (z +ka¾dého vrcholu vychází jedna hrana za pøidání èíslice 1 a dal¹í za èíslici 0). +Hledané èíslo existuje právì tehdy, kdy¾ graf obsahuje orientovaný sled z 0 do +1. Jakým algoritmem takový sled najdeme? +\endlist +Podobné a dal¹í úlohy budeme øe¹it v následujících kapitolách. + +\bye diff --git a/2-ram/Makefile b/2-ram/Makefile new file mode 100644 index 0000000..382372f --- /dev/null +++ b/2-ram/Makefile @@ -0,0 +1,3 @@ +P=2-ram + +include ../Makerules -- 2.39.2