From daa50f2c79ec7b1fdbb0bfff8f00656df11095e5 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 23 May 2011 14:18:07 +0200
Subject: [PATCH] RAM: Revidovana verze od Moskyta

---
 {2009/2-ram => 2-ram}/2-ram.tex | 49 +++++++++++++++++++++------------
 {2009/2-ram => 2-ram}/Makefile  |  0
 2 files changed, 31 insertions(+), 18 deletions(-)
 rename {2009/2-ram => 2-ram}/2-ram.tex (88%)
 rename {2009/2-ram => 2-ram}/Makefile (100%)

diff --git a/2009/2-ram/2-ram.tex b/2-ram/2-ram.tex
similarity index 88%
rename from 2009/2-ram/2-ram.tex
rename to 2-ram/2-ram.tex
index 71c3a25..f9a8f9f 100644
--- a/2009/2-ram/2-ram.tex
+++ b/2-ram/2-ram.tex
@@ -102,8 +102,9 @@ t
 \verbatim{	I <- 1
 LOOP:	J <- I
 	M <- I
-MIN:	IF [J]<[M] ==> M <- J
-	J <- J+1
+MIN:	IF [J]>=[M] ==> GOTO NEXT
+	M <- J
+NEXT:	J <- J+1
 	IF J<=N ==> GOTO MIN
 	X <- [I]
 	[I] <- [M]
@@ -113,23 +114,31 @@ MIN:	IF [J]<[M] ==> M <- J
 }
 
 Pojïme se podívat, jaká je èasová slo¾itost jednotlivých èástí algoritmu.
-Cyklus |MIN| provede $3\cdot (N-I+1)$ instrukcí. Mimo cyklu |MIN| je v |LOOP|
-je¹tì 7 instrukcí, tedy celý |LOOP| provede $3\cdot (N-I+1)+7$ instrukcí.
-Celkovì se dostáváme k souètu
-$$1+3\cdot N+7+3\cdot (N-1)+7+3\cdot (N-2)+7+3\cdot (N-3)+\dots +3\cdot 1+7 =$$
-$$1+7\cdot N+3\cdot {{N(N+1)}\over{2}} = {{3}\over{2}}N^2 + 8{,}5N + 1$$
-
-Na multiplikativních konstantách ale nezále¾í -- zaprvé se na reálných strojích
-ceny jednotlivých (pro nás jednotkových) instrukcí stejnì li¹í, zadruhé
-asymptoticky pomalej¹í funkce nakonec pro velké $N$ v¾dy prohraje, tak¾e nemá
-cenu
-(alespoò pøi prvním pøiblí¾ení k problému) multiplikativními konstantami se
-zabývat. Tím pádem nezále¾í ani na èlenech ni¾¹í øádù:
-$$1{,}5N^2 + 8{,}5N + 1 \leq 1{,}5N^2 + 8{,}5N^2 + N^2 = 11N^2\approx N^2$$
+Cyklus |MIN| provede za prùchod 3 nebo 4 instrukce, ale zajímá nás nejhor¹í
+pøípad, tak¾e 4. Zavolá se $(N-I+1)$-krát, tedy celkem provede $4\cdot (N-I+1)$
+instrukcí.
+
+Mimo cyklu |MIN| je v |LOOP| je¹tì 7 instrukcí, tedy celý |LOOP| provede
+$4\cdot (N-I+1)+7 = 4(N-1) + 11$ instrukcí.
+
+Celkovì se dostáváme k souètu $$1+(\sum_{I=1}^{N} 4(N-I) + 11) = 1 + 11N +
+4\cdot{N(N-1)\over 2} = 2N^2+9N + 1.$$
+
+Na multiplikativních konstantách ale nezále¾í -- Na reálných strojích se
+ceny jednotlivých (pro nás jednotkových) instrukcí stejnì li¹í, tak¾e
+nemá cenu se multiplikativními konstantami zabývat (alespoò pøi prvním
+pøiblí¾ení k problému).
+
+$$2N^2 + 9N + 1 \approx N^2 + N$$
+
+Navíc asymptoticky pomalej¹í funkce nakonec pro velké $N$ v¾dy prohraje. Tím
+pádem nezále¾í ani na èlenech ni¾¹ích øádù:
+
+$$N^2 + N \approx N^2$$
+
 Kdy¾ u¾ toto víme, mù¾eme zanedbávat konstanty prùbì¾nì: $N$ cyklù po
-${}\approx~N$~krocích $\Rightarrow~\approx~N^2$ krokù. To nás vede k zavedení
-tzv.
-{\I asymptotické notace:}
+$\approx\nobreak N$~krocích $\Rightarrow~\approx N^2$ krokù. To nás vede k zavedení
+tzv.  {\I asymptotické notace:}
 
 \h{Asymptotická notace}
 \s{Definice:} Pro funkce $f,g: {\bb N} \rightarrow {\bb R}^+$ øekneme,
@@ -187,6 +196,10 @@ $c_{1},c_{2}$ takov
 $c_{2}$-násobkem funkce $g(n)$.
 \endlist
 
+\>{\sl Poznámka:} Ona rovnost je dost zavádìjící. Není to toti¾ rovnost, není
+to symetrické. Jiný, mo¾ná rozumnìj¹í pohled, je zavedení $\O(g)$ jako mno¾iny.
+Pak by se dalo psát $f \in \O(g)$, nebo tøeba $\O(n) \subseteq \O(n^2)$.
+
 \s{Porovnání rùstu funkcí:} (aneb jak moc máme algoritmy rádi podle jejich
 chování od~nejlep¹ích k~nejhor¹ím)
 
diff --git a/2009/2-ram/Makefile b/2-ram/Makefile
similarity index 100%
rename from 2009/2-ram/Makefile
rename to 2-ram/Makefile
-- 
2.39.2