od Jebi » 3. 2. 2012 17:05
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
). 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
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