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

<{ForumPost(poster="Vinc", timestamp=2010-01-28 15:00:14)}>
**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)
<{/ForumPost}>

<{ForumPost(poster="Lada", timestamp=2010-01-28 18:43:57)}>
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](/Forum%20archiv/Attachments/100_928dbddda77679cf13c619384668280a)*

<{/ForumPost}>

<{ForumPost(poster="...mathew...", timestamp=2010-01-29 01:30:07)}>
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.
<{/ForumPost}>

<{ForumPost(poster="elgriton", timestamp=2010-02-15 22:50:10)}>
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.
<{/ForumPost}>