Zk 1.2.2012

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zk 1.2.2012

Re: Zk 1.2.2012

od JK. » 1. 2. 2012 17:57

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!

Zk 1.2.2012

od Tooomy » 1. 2. 2012 14:43

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={ Wx 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

Nahoru