Zk 2.2.2012

Jebi
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 19. 1. 2009 12:40
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Zk 2.2.2012

Příspěvek od Jebi »

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
Odpovědět

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