[Zap] 10.1.2011

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ý

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.)

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).