[NTIN090] Základy složitosti a vyč. - Zk 28.1.2010

Vinc
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 4. 11. 2006 22:29
Typ studia: Informatika Mgr.

[NTIN090] Základy složitosti a vyč. - Zk 28.1.2010

Příspěvek od Vinc »

Skuskovy test, 28/01/2010

(1) Ukazte, ze mnozina P = {p | p je prvocislo} ma primitivne rekurzivnu charakteristicku funkciu. Pri odvodzovani mozete vyuzit toho, ze scitanie, odcitanie, nasobenie, delenie, <, >, = su PRF a PRP

(2) Dokazte, ze existuje n, pre ktore plati, ze W_{n} = \{p_{n}^{k} | k >= 0\}

(3) Rozhodnete, zda nasledujici verze halting problemu je algoritmicky rozhodnutelna. Je dan kod programu a ptame se, zda se tento program zastavi na pocitaci, ktery mame na stole.

(4) Ukazte, ze nasledujuci problem je NP-uplny:
i: Mnozina X, |X| = 3q a mnozina trojic C z X x X x X
p: Existuje C' z C taka, ze kazdy prvok z X sa vyskytuje v prave jedne trojici z C'?

(5) Popiste polynomialny algoritmus pre 2SAT (Formula v KNF, kde kazda klauzula ma prave 2 literaly)
Uživatelský avatar
Lada
Donátor
Donátor
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Typ studia: Informatika Bc.
Bydliště: Slaný / zácpa na Evropské

Re: [NTIN090] Základy složitosti a vyč. - Zk 28.1.2010

Příspěvek od Lada »

sakra, nekdo me predbehl:)

tak pridam jen poznamky:
3. byl chytak - odpoved je ze halting problem JE zastavitelny (nas stolni PC ma omezenou pamet, disk, registry atd -> E jen konecne mnozstvi jeho ruznych konfiguraci -> lze detekovat zacykleni)
5. lze udajne najit nekde na webu v minulych pisemkach ze Slozitosti

jinak na ustni prevod CRF -> TS a 3 SAT je NP uplny -
celkova uspesnost byla podle me docela vysoka, videl jsem 2x 4, hodne jednicek, semtam 2 nebo 3...

Hodne stesti ostatnim
Lada
Přílohy
fotka zadani...
fotka zadani...
Hail to you, champion:o)
...mathew...
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 21. 12. 2007 19:56
Typ studia: Informatika Bc.

Re: [NTIN090] Základy složitosti a vyč. - Zk 28.1.2010

Příspěvek od ...mathew... »

ja len dodam, ze ten 2SAT nevyriesil nik, tak ho ani nepocital, na ustnej som dostal dokaz Riceovej vety pomocou 1 prevoditelnosti a dokaz vety 17.8 ... skusal na chodbe, dost vela casu stravil v kancelarii.
elgriton
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 21. 11. 2007 20:18
Typ studia: Informatika Mgr.

Re: [NTIN090] Základy složitosti a vyč. - Zk 28.1.2010

Příspěvek od elgriton »

Ahoj, nevíte někdo, jak řešit příklad (2). Zkoušel jsem větu o rekurzi, pak i její verzi s parametrem, ale zatím se mi nepodařilo dospět k výsledku. Myslím si, že přes tu větu o rekurzi to nějak musí jít. Mám problém s tím číslem k. To $W_x = \{p_x^k|k \ge 0\}$ vypadá jako sjednocení množin $\{p_x^k\}$ přes všechna k. Ale nekonečné sjednocení asi nebude obecně rekurzivní. Díky. Pokud se mi podaří to vyřešit, řešení pošlu.
Odpovědět

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