od chucky » 27. 2. 2008 14:33
2) mame CRF f a jej obor hodnot range(f).
Chceme najst CRF h t.ž. dom(h) = range(f).
definujme h(y) = prva zlozka z min
<x,s>{f(x) konverguje za s krokov a je rovne y}
vysvetlenie:
- ak pre y neexistuje x, ze f(x)=y, tak program neskonci, co je ok, lebo y je mimo range(f) a teda mimo dom(h)
- ak pre y existuju nejake x, ze f(x)=y, tak nejake najdeme. Predpokladame, ze kody dvojic <x,s> su usporiadane tak, ze sa na kazdu dostane, teda nie napr. ze najskor preberiem <x,1> pre vs. x, potom <x,2> pre vs. x; ani nie najskor <0,s> pre vs. s, potom <1,s> pre vs. s; to by az na specialne pripady nikdy nekonvergovalo. Vhodne poradie preberania dvojic je napr. nasledovne:
Kód: Vybrat vše
s|
x | 0 1 2 3 4 ...
----------------------
1| 1 2 4 7 11 ...
2| 3 5 8 12 ...
3| 6 9 13 ...
4| 10 ...
...
Tak budeme verit, ze nase zvolene kodovanie dvojic usporiada dvojice v nejakom podobnom poradi
Poznamka: nemozeme definovat h jednoducho takto:
h(y) = min
x{f(x) = y}
Povedzme, ze najmensie x, ze f(x)=y je 1 a ze f(0) nie je definovane.
Skusame postupne x od 0 do nekonecna, ci f(x)=y. ale uz na f(0) program diverguje, takze sa ani nedostaneme k tomu, aby sme otestovali f(1). Takze min
x{f(x) = y} nedokazeme
efektivne vycislit a teda sa nam nepodari skonstruovat takuto h tak, aby bola CRF.
2) mame CRF f a jej obor hodnot range(f).
Chceme najst CRF h t.ž. dom(h) = range(f).
definujme h(y) = prva zlozka z min[sub]<x,s>[/sub]{f(x) konverguje za s krokov a je rovne y}
vysvetlenie:
[list]ak pre y neexistuje x, ze f(x)=y, tak program neskonci, co je ok, lebo y je mimo range(f) a teda mimo dom(h)[/list]
[list]ak pre y existuju nejake x, ze f(x)=y, tak nejake najdeme. Predpokladame, ze kody dvojic <x,s> su usporiadane tak, ze sa na kazdu dostane, teda nie napr. ze najskor preberiem <x,1> pre vs. x, potom <x,2> pre vs. x; ani nie najskor <0,s> pre vs. s, potom <1,s> pre vs. s; to by az na specialne pripady nikdy nekonvergovalo. Vhodne poradie preberania dvojic je napr. nasledovne:
[code]
s|
x | 0 1 2 3 4 ...
----------------------
1| 1 2 4 7 11 ...
2| 3 5 8 12 ...
3| 6 9 13 ...
4| 10 ...
...
[/code]
Tak budeme verit, ze nase zvolene kodovanie dvojic usporiada dvojice v nejakom podobnom poradi
[/list]
Poznamka: nemozeme definovat h jednoducho takto:
h(y) = min[sub]x[/sub]{f(x) = y}
Povedzme, ze najmensie x, ze f(x)=y je 1 a ze f(0) nie je definovane.
Skusame postupne x od 0 do nekonecna, ci f(x)=y. ale uz na f(0) program diverguje, takze sa ani nedostaneme k tomu, aby sme otestovali f(1). Takze min[sub]x[/sub]{f(x) = y} nedokazeme [i]efektivne vycislit[/i] 8) a teda sa nam nepodari skonstruovat takuto h tak, aby bola CRF.