# Zk 2.2.2012

<{ForumPost(poster="Jebi", timestamp=2012-02-03 17:05:49)}>
Dnešní termín už byl trošku obsazenější než ten včerejší, v 9 písemka, byla následující  
  
1. S = {e | (exje x)fí_e(x) = 0} (množina G.Č. funkcí, které pro nějaký argument vrací nulu)  
Je S rekurzivní nebo alespoň rekurzivně spočetná?  
  
2. Operace + definovaná na množinách jako A+B = {2x | x z A}U{2x + 1 | x z B} (tedy disjunktní sjednocení množin A a B)  
a) ukažte, že A i B je m-převoditelná na A+B  
b) ukažte, že pokud A i B je m-převoditelná na C, je A+B m-převoditelná na C  
  
3. Problém: Nalezení kostry grafu, přičemž vrcholy kostry smí mít max stupeň k  
Dokázat NP-úplnost převedením z nějakého známého NP-úplného problému  
  
Návod k řešení:  
1. rekurzivní není kvůli Riceovi, je však rekurzivně spočetná - vyšel jsem z f(e) = μy\[fí_e(y) = 0] .. je třeba použít konečnou aproximaci, aby předikát v \[] byl rekurzivní, takže vznikne funkce g(e) = μ<y,s>\[fí_e,s(y) = 0], která je definovaná pro ta správná e, která potřebujeme, takže stačí zadefinovat S = dom g  
  
2. poměrně nenáročná úloha, zobrazující ORF byla f(x) = 2x při převádění z A a f(x) = 2x + 1 při převádění z B  
  
3. tu nevim, jestli někdo tušíte, tak napište, samotného by mě to taky zajímalo  
  
Po písemce vím jen o jednom člověku, co musel odejít, takže žádné velké síto to není.  
  
Ústní část:  
  
Vylosoval jsem si důkaz NP-úplnosti 3D párování ze SATu a Rekurzivně spočetnou množinu jako obor hodnot ORF či ČRF. Druhá otázka mi prošla bez dotazů, jsou to dvě věty, tak nějak jsem nastínil i důkazy, jen na pár řádek, zřejmě mu stačilo vidět myšlenku. Ta první otázka mi ale dala zabrat, pamatoval jsem si jen jak se přibližně konstruují množiny X, Y, W a M a tak jsem to nějak zkusil. No, bylo to špatně, přeházel jsem tam nějaký indexy, tak mě na tom chvíli dusil, ať mu to vysvětlim a pak mi řek, ať to spravim. Po chvíli jsem si svou chybu uvědomil a opravil to, společně jsme to pak nějak dovymysleli a to kupodivu stačilo, ani se neptal na nějakej důkaz, proč že to teda vlastně pak funguje a tak, prý že to mam určitě rozmyšlený (což nevím, jestli myslel vážně anebo viděl, že v tom dosti plavu, tak to nechtěl komplikovat :D ). Nakonec za 1.  
  
==> Myslím, že jde Kučerovi hlavně o myšlenku, když to máte dobře, tak se ani moc neptá, ale pokud se mu něco nezdá, bude vám do toho šťourat a šťourat, než vám ukáže, jak je to špatně, nebo mu to nevysvětlíte. Nakonec je ale při hodnocení velmi schovívavý. Také z toho plyne, že není třeba psát nějaké dlouhé eseje, když to napíšete moc složitě, stejně to nebude číst a požádá vás, ať mu to vysvětlíte vlastními slovy.  
  
Tedy hodně štěstí přeji
<{/ForumPost}>