Pridana druha prednaska, nulta verze.

[ads1.git] / 2-rozdel / 2-rozdel.tex

\input ../lecnotes.tex

\prednaska{2}{Rozdìl a panuj}{(zapsali J. Záloha a P. Ba¹ista)}

\s{O èem bude dne¹ní pøedná¹ka?} Pøevá¾nì o metodì Rozdìl a panuj (\>{\sl Divide et Impera})

\noindent
Pro porovnávání algoritmù si musíme zavést nìjaké kritérium. Vìt¹inou se zajímáme o èas a pamìt, které spotøebují pro svùj bìh. Proto, abychom v¹ak mohli takto algoritmy porovnávat bez ohledu na prostøedí, stroj a podobné vìci, zavádíme takzvanou $O$ notaci.

\s{Definice:} Pøedpokládejme, ¾e funkce, které porovnávame jsou dle následujícího pøedpisu:

$f:{N} \rightarrow {R}^{+}$

\noindent
Potom øekneme, ¾e$ f(n) $ je $ O(g(n))$ právì tehdy kdy¾ existuje nìjaké $c>0: \forall ^{*} n \in {N}: f(n) \leq c.g(n)$

\>{\sl Poznámka:} $ \forall ^{*} n$ znamená $\exists n_{0}: \forall n \geq n_{0} :$. Nebo je¹tì jinak: výrok platí pro v¹echna $n$ a¾ na koneèný poèet vyjímek. Tato definice tedy øíká, ¾e funkci $f(n)$ je mo¾né ohranièit shora nìjakým reálným násobkem funkce $g(n)$ pro $\forall n \in N$. Èasto zapisujeme $f(n)=O(g(n))$ - jedná se o za¾itou vìc, ale uvìdomme si v¹ak, ¾e tento zápis neoznaèuje rovnost! (proto¾e platí napøíklad $\log{n}=O(n)$ ale neplatí $n=O(\log{n})$ To znamená, ¾e neplatí symetrie, odtud vyplývá, ¾e nemù¾e jít o rovnost). Ale: "Je to èuòaèina." Formálnì jde o nìjakou mno¾inu nebo tøídu funkcí $f(n)$, pro které platí, ¾e se dají shora ohranièit kladným reálným násobkem funkce $g(n)$. A potom pí¹eme $f \in O(g)$.

napøíklad:

$$
2,5n^{2} \dots O(n^{2})
$$
$$
2,5n^{2}+30n \dots O(n^{2})
$$

Platí:

$$
O(f)+O(g)=O(f+g)
$$

proto¾e:

$$
f^{\prime} \leq c.f
$$
$$
g^{\prime} \leq d.g
$$
$$
f^{\prime} + g^{\prime} \leq c.f+d.g \leq (c+d).(f+g)
$$

\noindent
A zde vidíme, ¾e $(c+d)$ se schová do $O$. Naprosto stejnì se doká¾e odobný vztah také pro násobení:

$$
O(f).O(g)=O(f.g)
$$

Rovnì¾ platí:

$$
O(f+g)=O(max(f,g))
$$

\noindent
nebot libovolný $n$-násobek funkce s exponentem $k$ je v¾dy asymmptoticky men¹í ne¾ $n$ násobek funkce s exponentem $l>k$.
To nám umo¾nuje zanedbávat pomaleji rostoucí èleny:

$$
O(n^{2})+O(n)=O(n^{2}+n)=O(n^{2})
$$

\noindent
$O$ notace v¹ak popisuje nejhor¹í pøípad. U nìkterých algoritmù nejhor¹í, nejlep¹í a tudí¾ i prùmìrný pøípad splývají. Je ale mnoho algoritmù, které se v tìchto parametrech diametrálnì li¹í, proto zavádíme dal¹í notace.


\s{Definice:}

\itemize\ibull
\:$f(n)$ je $\Omega(g(n)) \Longleftrightarrow \exists c>0: \forall ^{*} n \in {N}: f(n) \geq c.g(n)$
$\Omega$ notace øíká, ¾e algoritmus se v¾dy chová stejnì èi lépe ne¾ nìjaký $c$-násobek funkce $g$.
\:$f(n)$ je $\Theta(g(n)) \Longleftrightarrow f(n)$ je $O(g(n)) \wedge f(n) $ je $ \Omega(g(n))$

nebo:

$f(n)$ je $\Theta(g(n)) \Longleftrightarrow \exists c_{1},c_{2}: c_{1}.g(n) \leq f(n) \leq c_{2}.g(n)$
existují-li nezáporné konstanty $c_{1},c_{2}$ takové, ¾e se funkce $f(n)$ dá ohranicit $c_{1}$ a $c_{2}$ násobky funkce $g(n)$
\endlist

\noindent
$\Theta$ notace tedy vyjadøuje, ¾e nejlep¹í a nejhor¹í pøípad chování algoritmu jsou stejné tøídy, li¹í se nanejvý¹ multiplikativní konstantou.

\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})$
\: $\Theta(n^{\varepsilon}), \varepsilon \in (0,1)$
\: $\Theta(n)$
\: $\Theta(n^{2})$

$\vdots$

\: $\Theta(n^{k}), k \in {N}$

$\vdots$

\: $\Theta(2^{n})$
\: $\Theta(3^{n})$

$\vdots$

\: $\Theta(k^{n}), k \in {R}^{+}, k > 1$

$\vdots$

\: $\Theta(n!)$

$\vdots$

\: $\Theta(n^{n})$
\endlist

\>{\sl Poznámka:} Pøi logaritmech a odhadech slo¾itosti se dá v¾dy hovoøit o logaritmu s libovolným základem, proto¾e platí:
$$
\log_k{n}={{\log_c{n}}\over{\log_c{k}}}={{1}\over{\log_c{k}}}.\log_c{n}
$$
kde ${1}\over{\log_c{k}}$ je jen konstanta, tak¾e ji mù¾eme zanedbat.

\>{\sl Pøíklady:}

\s{Eukleidùv algoritmus:} Pokd jej pustím na 2 èísla o $n$ bitech, potom poèet iterací bude $O(n)$, ka¾dá iterace trvá $O(n^{2})$ krokù. Tak¾e celkovì má tento algoritmus èasovou slo¾itost: $O(n^{3})$

\s{Rozdìl a panuj:} A nyní pøestaòme chodit okolo horké ka¹e a øekòeme si, co to ono vý¹e zmiòované ``rozdìl a panuj'' znamená. Mìjme nìjaký problém, který má tu vlastnost, ¾e kdy¾ jej rozdìlím na nìjaké podproblémy, které mají stejný charakter a ty  vyøe¹ím, tak slo¾ením jejich øe¹ení získám øe¹ení pùvodního problému. Ten po¾adavek na stejný charakter je podstatný, nebot nám umo¾ní se podívat na tyto podproblémy pod stejným úhlem a opìt je rozdìlit na ``podpodproblémy'' a tak dále, a¾ se dostanu na úroveò, kterou je mo¾né vyøe¹it triviálnì, popøípadì jiným ménì nároèným zpùsobem, teï je provedeno rozdìlení. Po jejich vyøe¹ení se zaènu vynoøovat z logické rekurze a na jednotlivých hladinách skládám øe¹ení, a¾ se octnu na hladinì pùvodního problému, tu slo¾ím a u¾ mohu panovat.

\s{Odboèka:} \>{\sl (Mergesort)} Pøi prùbìhu algoritmu mergesort nejprve rozdìlujeme vstup na dvì ``stejnì'' (v hor¹ím pøípadì a¾ na jednotku) velká pole. To nám zabere na ka¾dé hladinì konstantní práci: 
$T(1) \dots O(1)$. 

\noindent
Kdy¾ se v¹ak vynoøujeme z logické rekurze, musíme na ka¾dé hladinì strávit linárnì èasu sluèováním: 
$T(n)=2.T({{n}\over{2}})+O(n)$

\s{Strom volání: }

\figure{figure1.eps}{Strom volání}{2in}

\noindent
Souèet práce pøes jednu hladinu stromu je $O(n)$. A jedodu¹e odvodíme, ¾e celkový poèet hladin je $O(\log{n})$, tudí¾ jsme si ukázali slo¾itost $O(n\log(n))$.

\s{Rychlej¹í algoritmus pro násobení:} \>{\sl (rychlej¹í ne¾ $O(n^{2})$)} Pokud násobíme dvì èísla zpùsobem, který nás uèili na základní ¹kole, dostaneme se na èasovou slo¾itost $O(n^2)$. Proto¾e se jedná o dost èastou operaci, zamyslíme se, jestli by ne¹la zjednodu¹it. Nasmìrujme na¹e úvahy na postup ``rozdìl a panuj''. Rozdìlíme ka¾dého èinitele na dvì stejnì dlouhé èásti a pro jednoduchost pøedpokládejme, ¾e dìlení probìhne v¾dy bez zbytku:

$$
X=A.10^{{n}\over{2}}+B
$$
$$
Y=C.10^{{n}\over{2}}+D
$$

\noindent
Potom získáme výsledek pùvodního výrazu jako:

\noindent
$X.Y=(A.10^{{n}\over{2}}+B).(C.10^{{n}\over{2}}+D)=A.C.10^{n}+A.D.10^{{n}\over{2}}+B.C.10^{{n}\over{2}}+B.D=A.C.10^{n}+(A.D+B.C).10^{{n}\over{2}}+B.D$

\noindent
Nyní, jak vidíme, staèí spoèítat souèin ètyø ${n}\over{2}$ ciferných císel. Spoèítejme, jak se tím zmìní celková èasová slo¾itost:

\noindent
$T(n)=4.T({{n}\over{2}})+O(n)=4.T({{n}\over{2}})+c.n=4.(4.T({{n}\over{4}})+c.{{n}\over{2}})+c.n=4^{2}.T({{n}\over{4}})+2.c.n+c.n=4^{2}.T({{n}\over{4}})+3.c.n=4^{2}.(4.T({{n}\over{8}})+c.{{n}\over{4}})+3.c.n=4^{3}.T({{n}\over{8}})+4.c.n+3.c.n=4^{3}.T({{n}\over{8}})+7.c.n=\ldots$

\noindent
takto bychom mohli pokraèovat dále, a¾ bychom se dostali na:

$$
T(n)=4^{4}.T({{n}\over{16}})+15.c.n
$$
$$
T(n)=4^{5}.T({{n}\over{32}})+31.c.n
$$
$$
\vdots
$$
Odtud mù¾eme vypozorovat, ¾e se vztah pro $T(n)$ vyvíjí zøejmì podle vzorce:
$$
T(n)=4^{k}.T({{n}\over{2^{k}}})+2^{k-1}.c.n+2^{k-2}.c.n+2^{k-3}.c.n+2^{k-4}.c.n+\ldots+2^{0}.c.n
$$
$$
T(n)=4^{k}.T({{n}\over{2^{k}}})+(2^{k}-1).c.n
$$
kde k je poèet vìtvení a n je velikost úlohy. Kdy¾ uvá¾íme, ¾e se strom volaní v¾dy vìtví pravidelnì na dva podstromy, tak platí: $k \approx \log{n}$. Kdy¾ dosadíme:
$$
T(n)=4^{\log{n}}.T({{n}\over{2^{\log{n}}}})+(2^{\log{n}}-1).c.n
$$
$$
T(n)=2^{\log{n}}.2^{\log{n}}.T({{n}\over{2^{\log{n}}}})+(2^{\log{n}}-1).c.n
$$
$$
T(n)=n.n.T({{n}\over{n}})+(n-1).c.n
$$
$$
T(n)=n^{2}.T(1)+(n-1).n.c
$$
$$
T(n) \doteq n^{2}.(T(1)+c)
$$
Pokud $T(1)$ a $c$ jsou konstanty, mù¾eme psát: $T(n)$ je $O(n^{2})$. Tak¾e jsme si pøíli¹ nepomohli, proto¾e i klasický algoritmus na násobení má kvadratickou èasovou slo¾itost. Podívejme se v¹ak, jako vypadá tabulka vìtvení pro daný algoritmus:

\medskip

\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr
poèet vìtvení & poèet úloh & velikost podúlohy\cr
\noalign{\medskip\hrule\bigskip}
0 & $4^{0}$ & ${n}\over{2^{0}}$\cr
1 & $4^{1}$ & ${n}\over{2^{1}}$\cr
2& $4^{2}$ & ${n}\over{2^{2}}$\cr
3 & $4^{3}$ & ${n}\over{2^{3}}$\cr
\vdots & \vdots & \vdots\cr
k & $4^{k}$ & ${n}\over{2^{k}}$\cr}}

\medskip

\noindent
Naskýtá se otázka, jestli bychom nemohli, kdy¾ se pozornì zamyslíme, èasovou nároènost zlep¹it. Existuje nìkolik mo¾ností:
- zlep¹it èlen $O(n) \ldots c.n$, to znamená zlep¹it èas spojování podúloh $\rightarrow$ to v¹ak rychleji nejde (pokud ètenáø nevìøí, mù¾e si dokázat)
- sní¾it poèet vìtvení $\rightarrow$ nech» se algoritmus nevìtví na $4$ vìtve, ale na ménì. To, ale jak dále uvidíme u¾ mo¾né je\vdots Staèí si uvìdomit, ¾e vlastnì potøebujeme spoèítat:
$$
X.Y=A.C.10^{n}+(A.D+B.C).10^{{n}\over{2}}+B.D
$$
Pøièem¾ ale nepotøebujeme znát souèiny $A.D$ ani $B.C$ samostatnì, nebo» nám staèí zjistit èlen $A.D+B.C$. Jako kdybychom poèítali $A.C$, $B.D$ a potom $(A+B).(C+D)=A.C+A.D+B.C+B.D$, tak odèítáním $(A.D+B.C)$ od $A.C+A.D+B.C+B.D$ dostaneme hledaný prostøední èlen: $A.D+B.C$, který potøebujeme, abychom spoèetli $X.Y$. Nyní nám ji¾ staèí jen tøi násobení, jedno sèítání a jedno odèítání navíc.Otázka je, zda-li to bude výhodné. Sèítání i odèítání nám zaberou nanejvý¹e lineární èas, tak¾e to skuteènì je výhodná úprava. Jak se tím zmìní výsledný èas? Podívejme se opìt na tabulku vìtvení:

\medskip

\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr
poèet vìtvení & poèet úloh & velikost podúlohy\cr
\noalign{\medskip\hrule\bigskip}
0 & $3^{0}$ & ${n}\over{2^{0}}$\cr
1 & $3^{1}$ & ${n}\over{2^{1}}$\cr
2& $3^{2}$ & ${n}\over{2^{2}}$\cr
3 & $3^{3}$ & ${n}\over{2^{3}}$\cr
\vdots & \vdots & \vdots\cr
k & $3^{k}$ & ${n}\over{2^{k}}$\cr}}

\medskip

\noindent
Spoèítejme si práci,která se musí udìlat na jedné hladinì. Pøedpokládejme, ¾e $k \approx \log{n}$. Dostávame:
$$\sum_{k=0}^{n}3^{k}.{{n}\over{2^{k}}}=\sum_{k=0}^{n} \left( {{3}\over{2}} \right) ^{k}.n=n.\sum_{k=0}^{n} \left( {{3}\over{2}} \right) ^{k}=n.{{ \left( {{3}\over{2}} \right) ^{k+1}-1}\over{{{3}\over{2}}-1}}=
$$
$$
=n{{ \left( {3}\over{2} \right) ^{\log{n}+1}-1}\over{{{1}\over{2}}}}=2.n. \left[ \left( {{3}\over{2}} \right) ^{\log{n}+1}-1 \right] \approx O \left( n. \left( {{3}\over{2}} \right) ^{\log{n}} \right) =
$$
$$
=O \left( n.{{3^{\log{n}}}\over{2^{\log{n}}}} \right)=O \left( n.{{3^{\log{n}}}\over{n}} \right)=O \left( 3^{\log_2{n}} \right)=O \left( (2^{\log_2{3}})^{\log_2{n}} \right)=
$$
$$
=O \left( 2^{\log_2{n}.\log_2{3}} \right)=O \left( (2^{\log_2{n}})^{\log_2{3}} \right)=O \left( n^{\log_2{3}} \right) \doteq O \left( n^{1,585} \right)
$$
Z toho vyplývá, ¾e jsme na¹li algoritmus s èasovou slo¾itostí men¹í ne¾ $O(n^{2})$. "Rozumné" implementace tohoto algoritmu jsou v¹ak trochu modifikované, a to tak, ¾e se rekuzivnì nevolají a¾ na jednociferná èísla, ale asi na 50 ciferná, a ty u¾ násobí standardním zpùsobem, nebo» re¾ie algoritmu není nulová a takto se dosahuje nejlep¹ích výsledkù.

\noindent
Pro násobení èísel existuje je¹tì efektívnìj¹í algoritmus, který má èasovou slo¾itost $O(n.\log{n})$, av¹ak tento u¾ vyu¾ívá rùzné pokroèilé techniky jako diskrétní Fourierova transformáce a podobnì, tak¾e jej zde nebudeme rozebírat.

\s{Vìta:} \>{\sl (Master Theorem)}

\noindent
Pokud $T(1)=O(1)$ a $T(n)=a.T(\lceil {{n}\over{b}} \rceil)+O(n^d)$, kde $a \geq 1$, $b>1$ a $d \geq 0$, potom $T(n)$ je:
\halign{#&#\cr
$O(n^d)$ & kdy¾ $a<b^d$\cr
$O(n^d.\log{n})$ & kdy¾ $a=b^d$\cr
$O(n^{\log_a{b}})$ & kdy¾ $a>b^d$\cr}


\proof \>{\sl 1. pøípad: }Pøedpokládejme nejdøíve, ¾e $n=b^x, x \in {N}$, aby platilo $\lceil {{n}\over{b}} \rceil = {n}\over{b}$. Uká¾eme si "dùkaz stromem":

\figure{figure2.eps}{Dùkaz stromem}{4in}

\noindent
Jak vidíme, strom sa v¾dy vìtví na stejný poèet vìtví - oznaème si jejich poèet $a$ a sestavme si tabulku vìtvení:

\medskip

\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr
poèet vìtvení & velikost podúlohy & èas potøebný na vyøe¹ení v¹ech podúloh\cr
\noalign{\medskip\hrule\bigskip}
$1$ & $n$ & $O(n^d)$\cr
$a$ & ${n}\over{b^1}$ & $O(({{n}\over{b^1}})^d).a^1$\cr
$a^2$ & ${n}\over{b^2}$ & $O(({{n}\over{b^2}})^d).a^2$\cr
$a^3$ & ${n}\over{b^3}$ & $O(({{n}\over{b^3}})^d).a^3$\cr
\vdots & \vdots & \vdots\cr
$a^k$ & ${n}\over{b^k}$ & $O(({{n}\over{b^k}})^d).a^k$\cr}}

\medskip

\noindent
Zkoumejme èas potøebný na vyøe¹ení v¹ech podúloh na jedné hladinì: 
$$
O \left(  \left( {{n}\over{b^k}} \right) ^d \right) .a^k=O \left( a^k.n^d \left( {{1}\over{b^k}} \right) ^d \right)=O \left( a^k.n^d \left( {{1}\over{b^d}} \right) ^k \right)=O \left( n^d \left( {{a}\over{b^d}} \right) ^k \right)
$$
Celkem je tedy èas potøebný na vyøe¹ení v¹ech podúloh na v¹ech hladinách (to znamená celé úlohy):
$$
T(n)=\sum_{k=0}^{\log_b{n}}O \left( n^d \left( {{a}\over{b^d}} \right) ^k \right)=O \left( n^d \sum_{k=0}^{\log_b{n}} \left( {{a}\over{b^d}} \right) ^k \right)
$$
V¹imnìme si výrazu ${a}\over{b^d}$. Na jeho hodnotì závisí hodnota výsledné sumy, proto¾e se vlastnì jedná o kvocient geometrické posloupnosti. Proto rozli¹me následující pøípady:

\>{\I 1} ${a}\over{b^d}<1$ jinými slovy, práce na jednotlivých hladinách exponenciálnì ubývá a souèet sumy se dá omezit nìjakou konstantou, která se schvá do $O$, a tak mù¾eme psát $T(n)=O(n^d)$.

\>{\I 2} ${a}\over{b^d}=1$ práce na jednotlivých hladinách je stejnì, to znamená, ¾e ¾e souèet sumy je právì $\log(n)$ a to nás opravòuje psát: $T(n)=O(n^d \cdot \log(n))$.

\>{\I 3} ${a}\over{b^d}>1$ to znamená, ¾e práce na jednotlivých hladinách pøibývá a potom musíme psát:$ T(n)=O(n^d.({{a}\over{b^d}})^{\log_b{n}})$ To sice vypadá jako slo¾itý výraz, ale mù¾eme je dále upravit:
$O(n^d.({{a}\over{b^d}})^{\log_b{n}})=O(n^d.a^{\log_b{n}}({{1}\over{b^d}})^{\log_b{n}})=O((b^{\log_b{a}})^{\log_b{n}}.n^d.{{1}\over{(b^d)^{\log_b{n}}}})=O((b^{\log_b{n}})^{\log_b{a}}.n^d.{{1}\over{(b^{\log_b{n}})^d}})=O(n^{\log_b{a}}.n^d.{{1}\over{n^d}})=O(n^{\log_b{a}})$

\noindent
A nyní vidíme, ¾e vìta je správná a zároveò rozdìlení pøípadù je naprosto oprávnìné.

\>{\sl 2. pøípad: }Vratme se k mo¾nosti $n \neq b^x, x \in {N}$. Potom ale platí: $b^k<n<b^{k+1} \ldots$ v tomto pøípadì zaokrouhleme $n$ a poèítejme s $n'=b^{k+1}$. Pokud platí $b^{k+1}=b.b^k<b.n$, je odtud hned vidìt, ¾e platí $n'<b.n$ a odtud vyplývá, ¾e vstup se nám zvìt¹í pøinejhor¹ím konstanta-krát, co je z asymtotického hlediska, které nás zajímá nejvíce nezajímavé, a tak tuto konstantu "schováme" do $O$ a máme algoritmus stejné slo¾itosti.
\qed

\noindent
Porovnejme si nìkteré známé algoritmy a jejich èasovou slo¾itost pomocí \>{\sl Master Theorem}:

\medskip

\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & #\cr
algoritmus & a & b & d & èasová slo¾itost\cr
\noalign{\medskip\hrule\bigskip}
Mergesort & 2 & 2 & 1 & $O(n.\log{n})$\cr
Násobení I. & 4 & 2 & 1 & $O(n^2)$\cr
Násobení II. & 3 & 2 & 1 & $O(n^{\log_2{3}})$\cr
Binární vyhledávání & 1 & 2 & 0 & $O(\log{n})$\cr}}

\medskip

\s{Domácí úkol nakonec: } Vymyslete algoritmus, který by z $n$ zadaných bodù v rovinì (prostoru) na¹el takové dva, které jsou od sebe nejménì vzdálené (zde existuje takový algoritmus s èasovou slo¾itostí $O(n.\log{n})$).

\bye