Zk 15.1.2014

Zk 15.1.2014

Příspěvekod ch34 » 15. 1. 2014 15:07

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.
ch34
 

Re: Zk 15.1.2014

Příspěvekod J4rd4 » 20. 1. 2014 15:34

Zdravím,
věděl by někdo, jak na tu dvojku? Podrobně... :wink: Nějak v těch převodech plavu... Díky
J4rd4
Matfyz(ák|ačka) level I
 
Příspěvky: 10
Registrován: 14. 4. 2011 09:54
Typ studia: Informatika Mgr.
Login do SIS: kubatj

Re: Zk 15.1.2014

Příspěvekod ch34 » 21. 1. 2014 13:59

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: viewtopic.php?f=451&t=7421
Druhé (podrobné) je třeba na Wikipedii: http://en.wikipedia.org/wiki/Subset_sum_problem
ch34
 


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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník