zapocet 27.10

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: zapocet 27.10

Re: zapocet 27.10

od Pakluc » 8. 1. 2012 22:26

Ahoj,

k tej 3 ulohe, to je zrejme uloha na smn vetu, je toto validne riesenie?

Nech e je Godelove cislo take ze $\varphi_e^{(4)} (x,y,a,b) \simeq \varphi_x(a).\varphi_y(b)$
potom podla smn plati $\varphi_e^{(4)} (x,y,a,b) = \varphi_{f(x,y)}^{(2)}(a,b)$
kde $f(x,y)=s(e,x,y)$

zapocet 27.10

od Návštěvník » 27. 1. 2011 10:42

1. Popiste TS ktory pocita funkci \lceil \log _2 \left x \right \rceil

2. Ukazte, ze funkce x mod y je PRF, pri odvozovani mozete predpokladat, ze scitanie, odcitanie, nasobenie, sign a konstanta su PRF

3. Ukazte, ze existuje PRF f(x,y), pre ktoru plati, ze

\varphi _{f(x,y)}(a,b) = \varphi _x (a) . \varphi _y (b)

4. Ukazte ze KLIKA je NP uplny problem pomocou problemu ktoreho tazkost bola ukazana na prednaske.

Nahoru