Domáce úlohy

Úloha: 1 | 2 | 3 | 4

Majme danú Janovovu schému S:

begin [y]:=[x]
1:     [y]:=[f(y)]
2:     if p(y) then goto 6
3:     [y]:=[f(y)]
4:     if p(y) then goto 6
5:     goto 2
6:     if q(y) then goto 8
7:     goto 4
8:     [y]:=[f(y)]
end    [z]:=[y]

Nájdite ku schéme S ekvivalentnú voľnú Janovovu schému S₁. Schému S₁ napíšte a nakreslite aj jej grafickú reprezentáciu (vývojový diagram). Stručne zdôvodnite, prečo je schéma S₁ voľná a ekvivalentná so schémou S.

(5 bodov)

Späť

Daná je štandardná schéma S:

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

Nájdite rekurzívnu schému, ktorá je ekvivalentná so štandardnou schémou S. Upravte schému tak, aby mala minimálny počet funkčných premennych.

(5 bodov)

Späť

Daný je štandardný program P:

begin [y1,y2]:=[1,1]
1:    if y2 ł x then goto end
2:    [y1,y2]:=[y1 + 1,(y1 + 1)2]
3:    goto 1
end   [z]:=[y1]
  

Floydovou metódou formálne dokážte správnosť programu P vhľadom na podmienky:

• vstupná podmienka p(x): x > 0
• výstupná podmienka q(x,z): (z - 1)² < x Ł z² (t.j. z = éÖxů)

(5 bodov)

Späť

Daný je štrukturovaný program P:

begin [y1,y2]:=[1,1]
  while y2 < x do
    [y1,y2]:=[y1 + 1,(y1 + 1)2]
  od
end [z]:=[y1]

Hoarovou metódou formálne dokážte správnosť programu P vhľadom na podmienky:

• vstupná podmienka p(x): x > 0
• výstupná podmienka q(x,z): (z - 1)² < x Ł z² (t.j. z = éÖxů)

(5 bodov)

Späť