Zk 4.2.2015

Zk 4.2.2015

Příspěvekod někdo » 5. 2. 2015 01:24

Verze F

1.
Rozhodněte, zda množina
S={x| fíx je konstantní ČRF, tj. (existuje c) (pro každé y) [fíx(y) ↓ implikuje fíx(y) rovnáse s vlnovkou c]}
je rekurzivní, rekurzivně spočetná, doplněk rekurzivně spočetné množiny, nebo nepatří do žádné z těchto kategorií. Svá rozhodnutí zdůvodněte.
Speciálně funkce, která není definovaná pro žádný vstup, podle této definice konstantní je.

2.
Dokažte následující tvrzení. Predikát P(x) je obecně rekurzivní právě tehdy, když existují primitivně rekurzivní predikáty Q1(x,y) a Q2(x,y) a platí:
P(x) právě tehdy, když (existuje y) [Q1(x,y)] právě tehdy, když (pro každé y) [Q2(x,y)]

3.
S pomocí některého problému probíraného na přednášce (tj, KACHL, SAT, 3SAT, Vrcholové pokrytí, Trojrozměrné párování, Hamiltonovská kružnice, Obchodní cestující nebo Loupežníci) ukažte, že následující problém je NP-úplný:
Množinové pokrytí
Instance: Systém množin C konečné množiny prvků, tj C je částí P(S), přirozené číslo k.
Otázka: Je možné vybrat C', C' je částí C, která obsahuje nejvýš k množin a přitom sjednocení přes C' je S?

↓ je šipka dolů, omlouvám se za to, že neumím latex.
Další termín bude v létě, říkal mi to. Výjimku dá těm, co by chtěli ke státnicím předtím.
někdo
 

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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník