Zk 15.1.2014

ch34

Zk 15.1.2014

Příspěvek od ch34 »

Zkouška v 9:00 písemka, hodina času, pak 6 lidí ústně rovnou, zbytek v 13:00. Ústní klasika, tahaly se papírky, podle bodů z písemky byla možnost si vybrat jinou jinou kartičku. Oproti loňsku ubyla jedna otázka (NP-úplnost 3DM).

Obrázek

1. Rekurzivní není podle Riceovy věty (pozor, S není třída funkcí, ale množina čísel, třídu je potřeba nějak zadefinovat). Doplněk S je r.s., lze ukázat třeba přes konečné aproximace. S není r.s.
2. Dynamickým programováním, podobně jako batoh, ale není to batoh a nejde to uplně jednoduše převést na batoh.
3. Stačí hrany nahradit dvojcyklem (hranou tam a zpět), k zůstane stejné. Úplně všichni ale měli špatně důkaz, že daný problém je v NP, protože nestačilo napsat, že certifikát je množina S a že to lze ověřit polynomiálně. Protože kdybysme zkoušeli projít všechny cykly, tak těch může být exponenciálně mnoho. Řešení je, že certifikát se ověří tak, že se z grafu všechny vrcholy z S odstraní a pak se zkontroluje, jestli tam ještě je cyklus. Nicméně to nebylo považováno za chybu a dával se celý bod i když to člověk neměl.
J4rd4
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 14. 4. 2011 10:54
Typ studia: Informatika Mgr.

Re: Zk 15.1.2014

Příspěvek od J4rd4 »

Zdravím,
věděl by někdo, jak na tu dvojku? Podrobně... :wink: Nějak v těch převodech plavu... Díky
ch34

Re: Zk 15.1.2014

Příspěvek od ch34 »

J4rd4 píše:věděl by někdo, jak na tu dvojku? Podrobně... :wink: Nějak v těch převodech plavu... Díky
Jedno řešení je popsáno tady: http://forum.matfyz.info/viewtopic.php?f=451&t=7421
Druhé (podrobné) je třeba na Wikipedii: http://en.wikipedia.org/wiki/Subset_sum_problem
Odpovědět

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