Zk 23.1.2013

Zk 23.1.2013

Příspěvekod muck » 26. 1. 2013 18:24

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.
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ěvekod blabla » 31. 1. 2013 02:27

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)
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ěvekod muck » 31. 1. 2013 13:31

Vypada to spravne :) .
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ěvekod strky » 31. 1. 2013 21:02

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?
strky
Matfyz(ák|ačka) level I
 
Příspěvky: 13
Registrován: 24. 1. 2006 15:15

Re: Zk 23.1.2013

Příspěvekod blabla » 31. 1. 2013 23:31

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)]\}
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ěvekod muck » 1. 2. 2013 19:29

\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]\}
muck
Matfyz(ák|ačka) level I
 
Příspěvky: 3
Registrován: 12. 1. 2011 12:33
Typ studia: Informatika Mgr.


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