Zápočet 10. 1. 2011

Varianta A

• Napište TS, který rozpoznává následující jazyk: 1^{x+1}01^{x+2}

• Ukažte, že f(x):=x! je PRF

• Ukažte, že existuje n, pro které W_n=\{k*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.)

• Ukažte, že problém existence přípustného řešení 0-1 celočíselného lineárního programování je NP-úplný

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 \in\mathbb{N}\}.

• Ukažte, že rozvrhování je NPC.