jevu $A$ poèítáme jako: $$\Pr[A]=\sum_{a\in A}P(a).$$
\s{Pøíklad:}
-Jaká je pravdìpodobnost slo¾eného jevu "na kostce padne sudé èíslo"? Oznaèíme
+Jaká je pravdìpodobnost slo¾eného jevu \uv{na kostce padne sudé èíslo}? Oznaèíme
$A=\{2,4,6\}\subseteq\Omega$. Hledanou pravdìpodobností je pak
$P(A)=1/6+1/6+1/6=1/2$.
\s{Prùmìrná slo¾itost algoritmu}
Prùmìrnou slo¾itost algoritmu mù¾eme poèítat pøes v¹echny vstupy nebo pøes náhodné
-volby vstupù. V prvním pøípadì je algoritmus pravdìpodobnostní ("hází mincí") a slo¾itost poèítáme jako prùmìr pøes v¹echny vstupy.
+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.
Ve druhém je zase algoritmus deterministický a zajímá nás pouze slo¾itost v nejhor¹ím pøípadì.
Pokud jde o koneèný výsledek, jsou oba uvedené zpùsoby ekvivalentní.
\s{Algoritmus:} ({\I Hledání l¾imediánu v mno¾inì $X$})
\algo
-\:Zvol náhodnì $x\in X$, pøèem¾ $\forall x,y\in X:\Pr[x]=\Pr[y]$.
+\:Zvol náhodnì $x\in X$ (v¹echna~$x$ se stejnou pravdìpodobností).
\:Spoèítej $A=\vert \{y\in X:y<x\} \vert$ a $B=\vert\{y\in X: y>x\}\vert$.
-\:Pokud $A\geq1/4$ a~zároveò $B\geq1/4$, vra» $x$, jinak skoè na~1.
+\:Pokud $A\geq \vert X\vert/4$ a~zároveò $B\geq \vert X\vert/4$, vra» $x$, jinak skoè na~1.
\endalgo
\s{Pozorování:}
\<Select> s~pivotem rovným prostøednímu prvku má v~prùmìru pøes permutace na vstupu èasovou slo¾itost $\Theta(n)$.
\proof
-Pøevodem na náhodnou volbu pivota. Pokud je na~vstupu náhodná permutace, pak v¹echny hodnoty~$p$
-jsou stejnì pravdìpodobné. Zbývá ukázat, ¾e dal¹í iterace algoritmu dostane na vstupu opìt náhodnou permutaci
-(s~rovnomìrným rozdìlením pravdìpodobností), tak¾e prùbìh celého algoritmu bude odpovídat
-algoritmu s~náhodnou volbou pivota, který jsme odhadli v~pøedchozí vìtì.
-
-K~tomu sestrojíme bijekci mezi $\pi_n$ (permutace na $1$ a¾ $n$) a mno¾inou ètveøic $(m, L, \pi_M, \pi_V)$, kde $m$ vezmeme jako prostøední prvek permutace $\pi_n$,
-$$m\in\{1,\dots,n\}\hbox{ na pozici } l=\lfloor {1+n\over 2} \rfloor$$
-Zbývá nám tedy obsadit v¹echny pozice pøed a za pozicí $l$ v permutaci $\pi_n$. K tomu nám dobøe poslou¾í
-$$L\in{{\{1,{\dots},l-1,l+1,{\dots},n\}} \choose {m-1}},$$
-z èeho jednoznaènì podle zvoleného $m$ dostaneme permutace
-$$\pi_M \hbox{ na } \{1{\dots}m-1\},\pi_V \hbox{ na } \{m+1{\dots}n\},$$
-které vyplòují zbylý prostor. Sestrojili sme tedy hledanou bijekci a podle pøedcházející vìty je èasová slo¾itost $\Theta(n)$.
+Uká¾eme, ¾e algoritmus s~pevnou volbou pivota se na~náhodném vstupu chová
+stejnì, jako algoritmus s~náhodnou volbou pivota na~pevném vstupu, jeho¾
+prùmìrnou slo¾itost odhaduje pøedchozí vìta.
+
+Pokud je na~vstupu náhodná permutace~$\pi$, jsou v¹echny hodnoty pivota~$p$ stejnì pravdìpodobné.
+Zbývá ukázat, ¾e dal¹í iterace algoritmu dostane na vstupu prvky vìt¹í nebo men¹í ne¾~$p$
+opìt v~náhodném poøadí (s~rovnomìrným rozdìlením pravdìpodobností).
+K~tomu sestrojíme bijekci mezi mno¾inou v¹ech permutací na~$\{1,\ldots,n\}$ a mno¾inou ètveøic $(m, L, \pi_M, \pi_V)$, kde:
+
+\itemize\ibull
+\:$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$,
+\:$L\in{{\{1,{\dots},l-1,l+1,{\dots},n\}} \choose {p-1}}$ je mno¾ina pozic, na~nich¾ jsou
+ umístìny prvky men¹í ne¾~$p$ (ty, které ná¹ algoritmus umístí do~mno¾iny~$M$),
+\:$\pi_M$ permutace na~$\{1,\ldots, p-1\}$ popisující poøadí men¹ích prvkù a
+\:$\pi_V$ permutace na~$\{p+1,\ldots, n\}$, tedy poøadí vìt¹ích prvkù.
+\endlist
+
+Jakmile zvolíme~$p$, jsou volby~$L$, $\pi_M$ a $\pi_V$ navzájem nezávislé. Ka¾dé volbì~$\pi_M$
+tedy odpovídá stejný poèet permutací~$\pi$, a~proto jsou v¹echny~$\pi_M$ stejnì pravdìpodobné.
+Analogicky pro~$\pi_V$.
+
\qed
\bye
projects / ads1.git / blobdiff