Dinic: Preznaceni obrazku (s,t -> z,s)

[ads2.git] / 11-np / 11-np.tex

diff --git a/11-np/11-np.tex b/11-np/11-np.tex
index bbe61b8e68bc84b7cfebde58c4b360a4655ecc07..171e51d8d3124a444e3cffe4c356e5ad5e7078e0 100644 (file)
--- a/11-np/11-np.tex
+++ b/11-np/11-np.tex
@@ -5,7 +5,7 @@
 
 Dosud jsme zkoumali problémy, které se nás ptaly na to, jestli nìco existuje.
 Napøíklad jsme dostali formuli a problém splnitelnosti se nás ptal, zda
-existuje ohodnocení promìnných takové, ¾e formule platí. Nebo v~pøípade
+existuje ohodnocení promìnných takové, ¾e formule platí. Nebo v~pøípadì
 nezávislých mno¾in jsme dostali graf a èíslo $k$ a ptali jsme se, jestli
 v~grafu existuje nezávislá mno¾ina, která obsahuje alespoò~$k$ vrcholù.
 Tyto otázky mìly spoleèné to, ¾e kdy¾ nám nìkdo napovìdìl nìjaký objekt, umìli
@@ -85,7 +85,7 @@ d
 Napøíklad nezávislá mno¾ina, rùzné varianty SATu, klika v~grafu~\dots
 
 Jak taková tøída NP vypadá? Pøedstavme si v¹echny problémy tøídy NP, jakoby seøazené
-zhora dolu podle obtí¾nosti problémù (tedy navzdor gravitaci), kde porovnání dvou
+shora dolu podle obtí¾nosti problémù (tedy navzdor gravitaci), kde porovnání dvou
 problémù urèuje pøevoditelnost (viz obrázek).
 
 \figure{p-np.eps}{Struktura tøídy NP}{2.5cm}
@@ -257,7 +257,7 @@ vzhledem k~$n$.
 
 \s{Poznámka:}
 Pro dùkaz následující vìty si dovolíme drobnou úpravu v~definici tøídy NP.
-Budeme chtít, aby nápovìda byla
+Budeme chtít, aby nápovìda
 mìla pevnou velikost, závislou pouze na~velikosti vstupu (tedy: $\vert y \vert
 = g(\vert x \vert)$ namísto $\vert y \vert \le g(\vert x \vert)$). Proè je taková
 úprava BÚNO? Jistì si dovedete pøedstavit,