Zk 3.2.2010

Kajinek
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 20. 12. 2007 22:24
Typ studia: Informatika Mgr.

Zk 3.2.2010

Příspěvek od Kajinek »

Na dnesni zkousku nas dorazilo celych 6 :) Na to, ze jeste pred 2 dny nebylo volne misto, to bylo ponekud prekvapive. Dostali jsme test (v priloze), na ktery jsou 2 hodiny. Oficialne musi byt alespon 2 otazky spravne a ja jsem zivoucim dukazem toho, ze nemusi...:)

Naznaky odpovedi:
1) Ma se vyjit z Riceovy vety, podle ktere tato mnozina rekurzivni samozrejme neni. Znat jeji dukaz, tak pomerne lehke. Mel jsem z casti.
2) Nemam tuseni, zatvrdl jsem na negaci te podminky v 1). Kdyz tak nekdo doplnte.
3) Prevod z KNF do DNF, tam se to roznasobi a nakonec z toho vyleze, ze vysledek muze byt "veliky" :). Nemel jsem.
4) Nejak pres silne souvisle komponenty. Najit je a pak s nimi chvili carovat. Vymyslel jsem kus.
5) Podle me nejlehci otazka - staci vzit HK a tu na to prevest. Za k vemte pocet vrcholu. Mel jsem cele.

Takze, mel jsem spravne vsehovsudy 1 otazku (+ 2 "na pul") a po kratke konzultaci jsem byl pripusten k ustni casti. Duvod byl asi ten, ze celkova uspesnost testu byla dost mizerna (nekdo odevzdaval skoro prazdny papir) a i pres dost tristni vysledek to relativne nebylo tak spatne.

Ustni byla, jak uz zde nekdo psal, porod. :)
Dostal jsem:
1) Pseudopolynomialni algoritmus pro batoh, silna NP-uplnost
2) Dokazat, ze mnozina je rekurzivni, je li oborem hodnot nejake rostouci usekove CRF

Algoritmus jsem vyplodil a o silne NP-uplnosti jsem si s Kucerou asi 15 min povidal. Chtel skutecne videt, jestli tomu rozumim, na vzorcich nikterak nebaziroval, probihalo to v pomerne pratelskem duchu, nesnazil se me potopit.
Dukaz jsem ramcove umel a rozumel jsem mu, takze jsme to jen prosli. Vse jsem popsal slovy, nechtel po me zadne "skutecne" odvozeni fce. Spise obcas prisla otazka "A proc tohle muzete udelat?". Po celem tomhle divadle se Kucera rozmyslel jestli 2 nebo 3 a tudiz mi (tenhle semestr uz potreti) byla polozena doplnujici otazka "obe definice NP". Prvni me napadla hned (sjednoceni NTIME(n^i)), ke druhe me musel trochu nakopnout a nasledovala smrst dalsich otazek ("mam SAT, ten je NP-uplny, jak na to aplikujete tu druhou definici?",...).
Nakonec 2. Kucera byl v pohode, snazil se pomahat. Jde mu skutecne o to, abyste tomu rozumeli a ne to jen meli nadrcene. Docela oceni, kdyz ten dukaz umite vymyslet (nebo alespon vsechno zduvodnit).
Přílohy
zkouskovy test
zkouskovy test
Odpovědět

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