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
x 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
)
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
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)
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