Zk 13.2.2013

Uživatelský avatar
kolage
Matfyz(ák|ačka) level I
Příspěvky: 32
Registrován: 27. 1. 2011 18:10
Typ studia: Informatika Mgr.

Zk 13.2.2013

Příspěvek od kolage »

Nejake poznamky:

1. Chce to nejak prevest z halting problemu / z K1 na tuto mnozinu S a dokazat tak, ze neni rekurzivni. Pak dokazat, ze -S je R.S. (-S = {<x,y> | Wx prunik Wy je neprazdny} ... f ~ existuje z: z in Wx & z in Wy - zhruba takto - to je RSP)
2. Jednoduse pres SMN vetu - klasika
3. Asi nejsnadneji z vrcholoveho pokryti (k se zanecha a, ale s mnozinou R se pak nejak machruje ?!)
Přílohy
ZSV-130213.png
Odpovědět

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