# Zk 1.2.2012

<{ForumPost(poster="Tooomy", timestamp=2012-02-01 14:43:34)}>
Na zkoušce jsme se tentokrát sešli pouze jen 3. Zkouška probíhala jinak klasicky, tj celkem 3 příklady-1h na vypracování. Alespoň 1 celý správně =postup do další části.  
  
Zadání otázek (varianta C):  
1) Rozhodnout zda S={ W<sub>x</sub> je podmnožina množiny sudých čísel}   
  a) je rekurzivní  (NE - přes Riceovu větu)  
  b) pokud ne, tak zda je S (NENÍ) nebo doplněk S (TA UŽ ANO) rekurzivně spočetná  
  
2) Předpokládejte, že máte černou skříňku, co umí říct o formuli v KNF v konst. čase, zda je splnitelná. Napište algoritmus, který s pomocí této skříňky najde splňující ohodnocení proměnných (pokud existuje).  
  
3) Ukázat že DOMINUJÍCÍ MNOŽINA (DM) je NP-úplná,  
  
DM:  
-Instance:Graf G=(V,E), k>=0  
-Otázka: Existuje V´podmnožina V, |V´|<=k, že každý vrchol z V je spojen alespoň s 1 vrcholem z V´ ?  
  
(Myslím, že ideálně díky převodu z vrcholového pokrytí)  
  
Na ústní jsme postoupili všichni 3 celkem bez problémů (já měl od všeho něco, ale naštěstí jsem měl alespoň tu 2 správně úplně celou  :D )    
  
Na ústní jsem si pak vytáhl:  
a) Vyčíslitelnost - Alg.nerozhodnutelné problémy-diagonalizační jazyk, univerzální jazyk, problém zastavení  
b) Složitost - Důkaz NP-úplnosti 3-SAT za pomoci SAT  
  
PK byl opravdu hodný a příjemný a zkouška probíhala v poklidném tempu  :wink: Jinak je pravdou, že není problém dostat za 1, i když máte z první části jen 1 příklad správně (což byl mimochodem i můj případ )  
  
Hodně štěstí všem (na příklady i na otázky) :P
<{/ForumPost}>

<{ForumPost(poster="JK.", timestamp=2012-02-01 17:57:21)}>
Ahoj! Díky za info, mohl by mi někdo prosím poradit jak se řeší ta 1b)?  
  
Ze S R  <=> S RS a -S RS je jasný že alespoň jedna nebude, ale to mi asi moc nepomůže...  
  
Díky!
<{/ForumPost}>