From ddc4835e1211cb6176200d732868254b9f3b8db4 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 25 Apr 2007 20:07:52 +0200
Subject: [PATCH] Pokus o lepsi dukaz.

---
 4-avg/4-avg.tex | 41 +++++++++++++++++++++++++----------------
 1 file changed, 25 insertions(+), 16 deletions(-)

diff --git a/4-avg/4-avg.tex b/4-avg/4-avg.tex
index 82a48c4..5509dea 100644
--- a/4-avg/4-avg.tex
+++ b/4-avg/4-avg.tex
@@ -18,7 +18,7 @@ Hodnot
 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$.
 
@@ -73,7 +73,7 @@ Uveden
 \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í.
 
@@ -84,9 +84,9 @@ bude spou
 
 \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í:}
@@ -126,18 +126,27 @@ Tedy $\E{}T=\E{}T_1+\E{}T_2+{\dots}=\Theta(n)$, kde $\E{}T_i$ ozna
 \<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
-- 
2.39.2