Pisomna praca zo ZTP, 14. marca 2001

Uloha 1. (10 bodov) Najdite ekvivalentnu volnu schemu k nasledujucej
standardnej scheme. Zakreslite ju graficky (vyvojovym diagramom).

begin [y1,y2] := [f(a),a]
1: if p(y1) then goto end
2: if q(y2) then goto 7
3: [y1,y2] := [f(y1),g(y2)]
4: if p(y2) then goto 2
5: [y2] := [g(y2)]
6: goto end
7: if q(y2) then goto 11
8: [y1] := [f(y1)]
9: if q(y2) then goto 4
10: goto 7
11: [y1,y2] := [g(y1),f(y2)]
12: if p(y1) then [y1] := [f(y1)]
end [z] := [h(y1,y2)]


Uloha 2. (10 bodov) Uvazujme triedu dosiahnutelnych schem D. Je
prislusnost k trede D rozhodnutelny (resp. ciastocne rozhodnutelny)
problem? Svoje tvrdenie zdovodnite.

Uloha 3. (10 bodov) Najdite ekvivalentnu rekurzivnu schemu s minimalnym
poctom rekurzivych definici k nasledujucej standardnej scheme.

begin [y1,y2] := [x,x]
1: [y1,y2] := [f(y1),g(y2)]
2: if p(y1) then goto 4
3: goto 1
4: [y2] := [f(y1)]
5: if p(y2) then [y1] := [f(y2)]
6: if q(y1,y2) then goto end
7: goto 4
end [z] := [y2]

Uloha 4. (10 bodov) Uvazujme triedu priechodnych schem P a triedu
volnych schem V. Sformulujte a zdovodnite vztahy medzi triedami P a V
pomocou relacii podtrieda, prelozitelna trieda a efektivne prelozitelna
trieda.