Zk 23.1.2013

muck
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 12. 1. 2011 12:33
Typ studia: Informatika Mgr.

Zk 23.1.2013

Příspěvek od muck »

Zk_23.1.2013.PNG
1) S neni rekurzivni podle Riceovy vety (mame tridu CRF, ktere se zastavi na alespon jednom sudem cisle a ta neni urcite prazdna ani neobsahuje vsechny CRF). Mnozina S je rekurzivne spocetna, protoze ji muzu zapsat pomoci existencnich kvantifikatoru a rekurzivni podminky - v ni se pouziva konecna aproximace. No a kdyz S neni rekurzivni a je rekurzivne spocetna, tak podle Postovy vety doplnek S neni rekurzivne spocetna mnozina.

2)
(a)
- f1(x) = 2x
- f2(x) = 2x + 1
(b) Existuje ORF f3 prevadejici A na C, stejne tak i ORF f4 prevadejici B na C. Funkce f5 se bude chovat takto:
- kdyz vstup je sudy, vydeli ho dvema (tim ziska prvek z A) a pusti funkci f3
- kdyz vstup je lichy, odecte od nej 1, vydeli dvema (tim ziska prvek z B) a pusti funkci f4
Takto zadefinovane funkce f1, f2 i f5 jsou ORF, takze m-prevadi podle zadani.


Trojku nevim a co jsem si vytahl na ustni nemusim rikat. Je to o nahode a kazdy muze dostat cokoliv ze seznamu co ma pan Kucera na strankach. Tak hodne stesti vsem, koho to jeste ceka.
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: Zk 23.1.2013

Příspěvek od blabla »

skusil som si dat dohromady tu funkciu f5, tak ked tak to niekto skontrolujte:
f_5(x) = ((x + 1) MOD 2) * f_3(x DIV 2) + (x MOD 2) * f_4((x - 1) DIV 2)
muck
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 12. 1. 2011 12:33
Typ studia: Informatika Mgr.

Re: Zk 23.1.2013

Příspěvek od muck »

Vypada to spravne :) .
strky
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 1. 2006 15:15
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Zk 23.1.2013

Příspěvek od strky »

Ja mam otazku este k tej jednotke. Ako sa tam pouziva konecna aproximace?
Nestaci to prepisat na: S = {x | Wx obsahuje cele cislo} = {x| (ex.y)Fi_x(y) div 2 = 0} a povedat, ze operacie div a = su rekurzivne spocetne a ex. kvantifikator tu rekurzivnu spocetnost tiez nepokazi a teda cela S je rekurzivne spocetna?
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: Zk 23.1.2013

Příspěvek od blabla »

S = {x | Wx obsahuje cele cislo} = {x| (ex.y)Fi_x(y) div 2 = 0}
predpokladam, ze co si chcel napisat je:
S = \{x | W_x\ obsahuje\ sude\ cislo\} = \{x | (\exists y)[\varphi_x(y) \mod 2 = 0]\}

to je ale cele zle, lebo \varphi_x(y) nemusi byt definovane a tak sa ti ten predikat "zasekne" hned na prvom testovanom y. aj keby vsak definovany bol, tak ty nechces modulit funkcnu hodnotu, ale samotne y.

konecna aproximacia sa pouzije tak, ze:
S = \{x | (\exists <y, s>)[y \in W_{x, s} \wedge (y \mod 2 = 0)]\}
muck
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 12. 1. 2011 12:33
Typ studia: Informatika Mgr.

Re: Zk 23.1.2013

Příspěvek od muck »

\varphi_x(y) nemusi byt definovane a tak sa ti ten predikat "zasekne" hned na prvom testovanom y.
Jen na upresneni - predikat se muze "zaseknout" (a neskoncit) prave kvuli tomu, ze se nepouzije konecna aproximace.

Blabla to pise dobre. Tento zapis mnoziny S by taky mel byt v poradku:
S = \{x | (\exists y)(\exists s)[\varphi_x_,_s(2y)\downarrow]\}
Odpovědět

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