4-avg/4-avg.tex

   1 \input ../lecnotes.tex
   2
   3 \def\E{{\bb E}}
   4
   5 \prednaska{4}{Prùmìrná èasová slo¾itost}{(zapsali R. Cinkais a R. Barczi)}
   6
   7 \h{První pomoc z~teorie pravdìpodobnosti}
   8
   9 \s{Definice:} {\I Diskrétní pravdìpodobnostní prostor} je uspoøádaná dvojice
  10 $(\Omega,P)$, kde $\Omega$ je nejvý¹e spoèetná mno¾ina {\I elementárních jevù}
  11 a $P:\Omega\rightarrow[0,1]$ je funkce, pro kterou platí:
  12 $$\sum_{x\in\Omega}P(x)=1.$$
  13 Hodnotám $P(x)$ budeme øíkat {\I pravdìpodobnosti} jednotlivých elementárních jevù.
  14
  15 \s{Pøíklad:} Mno¾ina elementárních jevù pøi vrhu kostkou je $\Omega=\{1,2,3,4,5,6\}$ a pokud je kostka spravedlivá, platí $\forall x\in\Omega:P(x)=1/6$.
  16
  17 \s{Definice:} {\I Jevem} $A$ rozumíme libovolnou mno¾inu $A\subseteq\Omega$. {\I Pravdìpodobnost}
  18 jevu $A$ poèítáme jako: $$\Pr[A]=\sum_{a\in A}P(a).$$
  19
  20 \s{Pøíklad:}
  21 Jaká je pravdìpodobnost slo¾eného jevu \uv{na kostce padne sudé èíslo}? Oznaèíme
  22 $A=\{2,4,6\}\subseteq\Omega$. Hledanou pravdìpodobností je pak
  23 $P(A)=1/6+1/6+1/6=1/2$.
  24
  25 \s{Definice:} {\I Náhodná promìnná} $X$ je funkce $X:\Omega\rightarrow{\bb
  26 R}$. {\I Støední hodnotou} náhodné promìnné $X$ rozumíme výraz
  27 $$\E{}X=\sum_{x\in\Omega}P(x)\cdot X(x).$$
  28
  29 \s{Pøíklad:} Nech» $H$ je náhodná promìnná pøiøazující vrhu kostkou dosa¾enou
  30 hodnotu, tedy $\forall x\in\Omega:H(x)=x$. Støední (oèekávanou) hodnotou této
  31 promìnné je $\E{}H= 1/6\cdot1 +1/6\cdot2 +1/6\cdot3 +1/6\cdot4 +1/6\cdot5
  32 +1/6\cdot6=7/2$.
  33
  34 \s{Vìta:} ({\I Linearita støední hodnoty})
  35 Nech» $A,B:\Omega\rightarrow\bb R$ jsou náhodné promìnné a $\alpha\in\bb R$ je libovolná konstanta. Potom:
  36 \numlist\ndotted
  37 \:$\E{}(A+B)=\E{}(A)+\E{}(B)$,
  38 \:$\E{}(\alpha\cdot A)=\alpha\cdot\E{}(A)$.
  39 \endlist
  40
  41 \proof
  42 \numlist\ndotted
  43 \:Podle definice støední hodnoty je:
  44 $$\eqalign{
  45 \E{}(A+B)&=\sum_{x\in\Omega}(A(x)+B(x))\cdot P(x)=\sum_{x\in\Omega}(A(x)\cdot P(x)+B(x)\cdot P(x))=\cr
  46          &=\sum_{x\in\Omega}A(x)\cdot P(x)+\sum_{x\in\Omega}B(x)\cdot P(x)=\E{}A+ \E{}B.
  47 }$$
  48 \:Opìt pøímo z definice støední hodnoty:
  49 $$\E{}(\alpha\cdot A)=\sum_{x\in\Omega}\alpha\cdot A(x)\cdot P(x)=\alpha\cdot \sum_{x\in\Omega}A(x)\cdot P(x)=\alpha\cdot\E{}A.$$
  50 \endlist
  51 \qed
  52
  53 \s{Pøíklad:}
  54 Házíme dvìmi odli¹nými hracími kostkami. Uva¾ovaný prostor elementárních jevù
  55 je proto $\Omega=\{(1,1),(1,2),\dots, (6,5),(6,6)\}$ a $\forall
  56 (a,b)\in\Omega:P((a,b))=1/36$. Mìjme náhodnou promìnnou $S$ pøiøazující vrhu
  57 kostkami souèet dosa¾ených hodnot, tedy $\forall (a,b)\in\Omega:S((a,b))=a+b$.
  58 Chceme urèit $\E{}S$.
  59
  60 Oznaème $A$ náhodnou promìnnou, která pøi vrhu kostkami vrací hodnotu na první
  61 kostce, tedy $\forall (a,b)\in\Omega:A((a,b))=a$. Podobnì oznaème $B$ náhodnou
  62 promìnnou, která vrací hodnotu na druhé kostce, tedy $\forall
  63 (a,b)\in\Omega:B((a,b))=b$. V~pøedcházejícím pøíkladì jsme si ukázali, ¾e
  64 $\E{}A=\E{}B=7/2$. Proto¾e $S((a,b))=a+b=A((a,b))+B((a,b))$, pou¾itím vìty
  65 o linearitì støední hodnoty dostáváme $\E{}S=\E{}(A+B)=\E{}A+\E{}B=7/2+7/2=7$.
  66
  67 \s{Poznámka:}
  68 Pro ka¾dou náhodnou promìnnou $Y$ platí: $$\E{}Y=\sum_{x\in{\bb R}}x\cdot\Pr[Y=x].$$
  69 \proof
  70 Uvedený vztah plyne okam¾itì z definice støední hodnoty, slouèíme-li dohromady v¹echny èleny $x\in\Omega$ se stejnou hodnotou $Y(x)$.
  71 \qed
  72
  73 \s{Prùmìrná slo¾itost algoritmu}
  74
  75 Prùmìrnou slo¾itost algoritmu mù¾eme poèítat pøes v¹echny vstupy nebo pøes náhodné
  76 volby vstupù. V prvním pøípadì je algoritmus pravdìpodobnostní (\uv{hází mincí}) a slo¾itost poèítáme jako prùmìr pøes v¹echny vstupy.
  77 Ve druhém je zase algoritmus deterministický a zajímá nás pouze slo¾itost v nejhor¹ím pøípadì.
  78 Pokud jde o koneèný výsledek, jsou oba uvedené zpùsoby ekvivalentní.
  79
  80 Na¹im cílem bude odvodit prùmìrnou slo¾itost algoritmu $\<Select>(k,X)$ z~minulé pøedná¹ky.
  81 K~tomu si uká¾eme algoritmus slou¾ící k výbìru pivota pro $\<Select>(k,X)$ ($\<Select>(k,X)$ jej pøi svém bìhu
  82 bude spou¹tìt jako podprogram). Bez újmy na~obecnosti pøedpokládejme,
  83 ¾e v¹echny prvky mno¾iny $X$ jsou navzájem rùzné.
  84
  85 \s{Algoritmus:} ({\I Hledání l¾imediánu v mno¾inì $X$})
  86 \algo
  87 \:Zvol náhodnì $x\in X$ (v¹echna~$x$ se stejnou pravdìpodobností).
  88 \:Spoèítej $A=\vert \{y\in X:y<x\} \vert$ a $B=\vert\{y\in X: y>x\}\vert$.
  89 \:Pokud $A\geq \vert X\vert/4$ a~zároveò $B\geq \vert X\vert/4$, vra» $x$, jinak skoè na~1.
  90 \endalgo
  91
  92 \s{Pozorování:}
  93 Uva¾ujme, ¾e házíme spravedlivou mincí. Aby nedo¹lo k ¾ádnému mezinárodnímu sporu, oznaème strany mince jako tuèòák ($T$) a ryba ($R$). Tedy pravdìpodobnost pádu na nìjakou stranu je $1/2$.
  94 Budeme zkoumat, jaká je støední hodnota èekání na pád tuèòáka $\E{}T$. Mno¾inu v¹ech jevù (posloupností vrhù), které mohou nastat, oznaème jako $\Omega=\{T,RT,RRT,\dots,RRR\dots\}$. Platí:
  95 $$\Pr[T]={1\over 2}, \Pr[RT]={1\over 4}, \Pr[R^{k}T]={1\over 2^{k+1}}, \Pr[RRR\dots]=\lim_{k\rightarrow\infty}{1\over 2^k}=0.$$
  96 Podle pozorování máme: $$\E{}T=\sum_{k=1}^{\infty}k\cdot\underbrace{\Pr[T=k]}_{1\over 2^k}=\sum_{k=1}^{\infty}{k\over 2^k}.$$
  97 Tuto sumu je v¹ak trochu obtí¾né spoèítat (kdo chce si to mù¾e zkusit), proto provedeme následující trik:
  98 $$\E{}T=1+{1\over 2}\cdot0+{1\over 2}\cdot\E{}T,$$
  99 to znamená, ¾e po jednom tahu jsme s polovièní pravdìpodobností vyhráli
 100 a s polovièní pravdìpodobností se situace nezmìnila. Jednoduchou úpravou tedy
 101 zjistíme, ¾e: $$\E{}T=2.$$
 102
 103 \s{Lemma:}
 104 Èekání na jev, který nastane s pravdìpodobností $p$, trvá prùmìrnì $1/p$.
 105
 106 \proof
 107 $\E{}T=1+(1-p)\E{}T$, tedy $\E{}T=1/p$.
 108 \qed
 109
 110 Pøi hledání l¾imediánu máme polovièní ¹anci, ¾e se trefíme pøi náhodném výbìru
 111 do prostøedních dvou ètvrtin -- prùmìrnì tedy vykonáme dva prùchody cyklem, pøièem¾
 112 jeden prùchod trvá $\Theta(n)$. Celkem bude tedy hledání l¾imediánu trvat prùmìrnì
 113 $\Theta(n)$.
 114
 115 \s{Vìta:}
 116 \<Select> s~náhodnou volbou pivota má v prùmìru èasovou slo¾itost $\Theta(n)$.
 117
 118 \proof
 119 Rozdìlíme algoritmus na {\I fáze} $\equiv$ posloupnosti iterací konèící dobrou
 120 volbou pivota (jako l¾imedián). V¹imneme si, ¾e jedna fáze zmen¹í vstup na nejvý¹e ${3\over 4}\cdot n$
 121 a~trvá v~prùmìru $\Theta(n)$ (prùmìrnì 2~iterace po $\Theta(n)$).
 122 Tedy $\E{}T=\E{}T_1+\E{}T_2+{\dots}=\Theta(n)$, kde $\E{}T_i$ oznaèuje $i$-tou fázi.
 123 \qed
 124
 125 \s{Vìta:}
 126 \<Select> s~pivotem rovným prostøednímu prvku má v~prùmìru pøes permutace na vstupu èasovou slo¾itost $\Theta(n)$.
 127
 128 \proof
 129 Uká¾eme, ¾e algoritmus s~pevnou volbou pivota se na~náhodném vstupu chová
 130 stejnì, jako algoritmus s~náhodnou volbou pivota na~pevném vstupu, jeho¾
 131 prùmìrnou slo¾itost odhaduje pøedchozí vìta.
 132
 133 Pokud je na~vstupu náhodná permutace~$\pi$, jsou v¹echny hodnoty pivota~$p$ stejnì pravdìpodobné.
 134 Zbývá ukázat, ¾e dal¹í iterace algoritmu dostane na vstupu prvky vìt¹í nebo men¹í ne¾~$p$
 135 opìt v~náhodném poøadí (s~rovnomìrným rozdìlením pravdìpodobností).
 136 K~tomu sestrojíme bijekci mezi mno¾inou v¹ech permutací na~$\{1,\ldots,n\}$ a mno¾inou ètveøic $(p, L, \pi_M, \pi_V)$, kde:
 137
 138 \itemize\ibull
 139 \:$p\in\{1,\ldots,n\}$ je prostøední prvek permutace~$\pi$ (pivot), tedy $\pi[l]$ le¾ící na~pozici $l=\lfloor {(1+n)/2} \rfloor$,
 140 \:$L\in{{\{1,{\dots},l-1,l+1,{\dots},n\}} \choose {p-1}}$ je mno¾ina pozic, na~nich¾ jsou
 141   umístìny prvky men¹í ne¾~$p$ (ty, které ná¹ algoritmus umístí do~mno¾iny~$M$),
 142 \:$\pi_M$ permutace na~$\{1,\ldots, p-1\}$ popisující poøadí men¹ích prvkù a
 143 \:$\pi_V$ permutace na~$\{p+1,\ldots, n\}$, tedy poøadí vìt¹ích prvkù.
 144 \endlist
 145
 146 Jakmile zvolíme~$p$, jsou volby~$L$, $\pi_M$ a $\pi_V$ navzájem nezávislé. Ka¾dé volbì~$\pi_M$
 147 tedy odpovídá stejný poèet permutací~$\pi$, a~proto jsou v¹echny~$\pi_M$ stejnì pravdìpodobné.
 148 Analogicky pro~$\pi_V$.
 149
 150 \qed
 151
 152 \bye