From 7d6712568e6846b6ec35c92de7b809dc44f44232 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 26 Apr 2007 09:23:09 +0200 Subject: [PATCH] Opraven preklep v dukazu posledni vety. --- 4-avg/4-avg.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/4-avg/4-avg.tex b/4-avg/4-avg.tex index 5509dea..8309b7b 100644 --- a/4-avg/4-avg.tex +++ b/4-avg/4-avg.tex @@ -133,7 +133,7 @@ pr 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: +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: \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$, -- 2.39.2