Zk 15.1.2014

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 15.1.2014

Re: Zk 15.1.2014

od 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: 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

Re: Zk 15.1.2014

od 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

Zk 15.1.2014

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

Nahoru