# Zk 15.1.2014

<{ForumPost(poster="ch34", timestamp=2014-01-15 15:07:15)}>
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).  
  
[http://i.imgur.com/GnnCb0J.jpg](http://i.imgur.com/GnnCb0J.jpg)  
  
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.
<{/ForumPost}>

<{ForumPost(poster="J4rd4", timestamp=2014-01-20 15:34:09)}>
Zdravím,  
věděl by někdo, jak na tu dvojku? Podrobně...  :wink: Nějak v těch převodech plavu... Díky
<{/ForumPost}>

<{ForumPost(poster="ch34", timestamp=2014-01-21 13:59:56)}>

 > J4rd4 wrote: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](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](http://en.wikipedia.org/wiki/Subset_sum_problem)
<{/ForumPost}>