# [Zap] 10.1.2011

<{ForumPost(poster="Šlupka", timestamp=2011-01-10 14:24:35)}>
Podmínky jako loni, 3/4 příkladů měl mít člověk dobře, všechny zadání co jsem zahlédl byly v podobném stylu.  
  
1. Napište TS, který rozpoznává následující jazyk: $1^{x+1}01^{x^2+1}$  
  
2. Ukažte, že $f(x):=x!$ je PRF  
  
3. Ani jsem nečetl, něco s rekurzivní množinou  
  
4. Ukažte, že problém existence přípustného řešení 0-1 celočíselného lineárního programování je NP-úplný
<{/ForumPost}>

<{ForumPost(poster="Cabroušek", timestamp=2011-01-10 14:35:12)}>
3. Ukažte, že existuje $n$, pro které $W_n = \{ k \cdot n | k \in \mathbb{N} \}$. (Pokud použijete nějakou primitivně rekurzivní nebo částečně rekurzivní funkci, zdůvodněte, proč jde o primitivně nebo částečně rekurzivní funkci.)  
  
(Tohle je verze A, ještě byla verze B.)
<{/ForumPost}>

<{ForumPost(poster="kukmuk", timestamp=2011-01-10 20:38:54)}>
**Varianta B**  

*  Napište TS, který rozpoznává jazyk *1^(2^x), x >= 0*. Stačil popis/postup.
*  Ukažte, že *2^x, x>=0* je PRF. (odvození)
*  Ukažte, že existuje *n*, pro které *W_n={n^k | k z N}*.
*  Ukažte, že rozvrhování je NPC (přesné zadání už tu je na fóru v jiném příspěvku).

<{/ForumPost}>