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

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)

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

Attachments:

• P1000246.jpg

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.

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.