Korektury vsech kapitol od Bohumira Zamecnika. Diky moc!

[ads2.git] / 12-apx / 12-apx.tex

diff --git a/12-apx/12-apx.tex b/12-apx/12-apx.tex
index 48dfa77829125626d8c9166cf5542dcf1f96621a..2635b3d875e56b86eaa63def143fb6c27d6dba23 100644 (file)
--- a/12-apx/12-apx.tex
+++ b/12-apx/12-apx.tex
@@ -22,7 +22,7 @@ podmno
 Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=\infty$ pro $c>0$. Pokud ji¾ známe
 $A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì
 pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili
-(a pak je $A_k(c)=A_{k-1}(c)$) nebo pou¾ili a tehdy bude $A_k(c) = A_{k-1}(c-c_k) + h_k$
+(a pak je $A_k(c)=A_{k-1}(c)$), nebo pou¾ili a tehdy bude $A_k(c) = A_{k-1}(c-c_k) + h_k$
 (to samozøejmì jen pokud $c\ge c_k$). Z~tìchto dvou mo¾ností si vybereme tu,
 která dává mno¾inu s~men¹í hmotností. Tedy:
 $$
@@ -47,9 +47,9 @@ Takov
 
 \s{Verze bez cen:} Na verzi s~cenami rovnými hmotnostem se dá pou¾ít
 i jiný algoritmus zalo¾ený na~dynamickém programování: poèítáme mno¾iny
-$Z_k$, obsahující v¹echny hmotnosti men¹í ne¾~$H$, kterých nabývá
+$Z_k$ obsahující v¹echny hmotnosti men¹í ne¾~$H$, kterých nabývá
 nìjaká podmno¾ina prvních~$k$ prvkù. Pøitom $Z_0=\{0\}$, $Z_k$
-spoèteme z~$Z_{k-1}$ a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny
+spoèteme ze~$Z_{k-1}$ a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny
 mají nejvý¹e $H$ prvkù, tak¾e celková èasová slo¾itost algoritmu je~$\O(nH)$.
 
 \h{Aproximaèní schéma pro problém batohu}
@@ -125,7 +125,7 @@ kvantovan
 které nemù¾e být lep¹í. Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$:
 $$
 \eqalign{
-ALG &\ge \biggl( { OPT \cdot M\over c_{max}} - n\biggr) \cdot {c_{max}\over M} \g
+ALG &\ge \biggl( { OPT \cdot M\over c_{max}} - n\biggr) \cdot {c_{max}\over M} \ge
 OPT - {n\cdot c_{max}\over n / \varepsilon} \ge OPT - \varepsilon c_{max} \ge \cr
 &\ge OPT - \varepsilon OPT = (1-\varepsilon)\cdot OPT.
 }