Zk 4.2.2015

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zk 4.2.2015

Zk 4.2.2015

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

Nahoru