Zk 1.2.2012

Tooomy
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 16. 10. 2008 00:36
Typ studia: Informatika Mgr.
Bydliště: kolej 17.listopadu

Zk 1.2.2012

Příspěvek od Tooomy »

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
JK.
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 14. 2. 2008 16:55
Typ studia: Informatika Mgr.

Re: Zk 1.2.2012

Příspěvek od JK. »

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!
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“