From 696765011d4dc15ceca2f6c6d408e92ae5037645 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 16 Jan 2012 00:27:50 +0100
Subject: [PATCH] Prevody: Pridana cviceni

---
 8-prevody/8-prevody.tex | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

diff --git a/8-prevody/8-prevody.tex b/8-prevody/8-prevody.tex
index 960ffcc..f351b1d 100644
--- a/8-prevody/8-prevody.tex
+++ b/8-prevody/8-prevody.tex
@@ -707,4 +707,32 @@ booleovsk
 v~CNF. Zavádíme sice nové promìnné, ale nová formule je splnitelná právì
 tehdy, kdy ta pùvodní.
 
+\exercises
+
+\ex{Vrcholové pokrytí grafu je mno¾ina vrcholù, která obsahuje alespoò jeden
+vrchol z~ka¾dé hrany. (Chceme na køi¾ovatky rozmístit strá¾níky tak, aby ka¾dou
+ulici alespoò jeden hlídal.) Uka¾te vzájemné pøevody mezi problém nezávislé
+mno¾iny a problémem \uv{Existuje vrcholové pokrytí velikosti nejvý¹e~$k$?}.}
+
+\ex{Zesilte ná¹ pøevod SATu na nezávislou mno¾inu tak, aby vytváøel grafy
+s~maximálním stupnìm~4.}
+
+\ex{Doka¾te \NP-úplnost problému $\bf Ax=b$ z~katalogu.}
+
+\exx{Doka¾te \NP-úplnost problému barvení grafu z~katalogu.}
+
+\ex{Uka¾te, ¾e barvení grafu jednou nebo dvìma barvami je snadné.}
+
+\ex{Pøeveïte batoh na dva loupe¾níky a opaènì.}
+
+\ex{Doka¾te \NP-úplnost problému batohu.}
+
+\ex{Pokud bychom definovali \P-úplnost analogicky k~\NP-úplnosti, které
+problémy z~\P{} by byly \P-úplné?}
+
+\exx{Doka¾te lemma o~vztahu mezi problémy z~\P{} a hradlovými sítìmi
+pomocí výpoèetního modelu RAM.}
+
+\endexercises
+
 \bye
-- 
2.39.2