[Zap] 10.1.2011

Šlupka
Matfyz(ák|ačka) level I
Příspěvky: 39
Registrován: 7. 11. 2007 22:12
Typ studia: Informatika Bc.

[Zap] 10.1.2011

Příspěvek od Šlupka »

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ý
Uživatelský avatar
Cabroušek
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 24. 1. 2008 23:16
Typ studia: Informatika Mgr.
Bydliště: Kladno
Kontaktovat uživatele:

Re: [Zap] 10.1.2011

Příspěvek od Cabroušek »

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.)
kukmuk
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 2. 2. 2009 20:20
Typ studia: Informatika Bc.

Re: [Zap] 10.1.2011

Příspěvek od kukmuk »

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).
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“