Zk 13.2.2013

Zk 13.2.2013

Příspěvekod kolage » 13. 2. 2013 15:04

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
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.
Login do SIS: 54683711

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