Domáce úlohy

Úloha: 1 | 2 | 3 | 4 | 5 | 6 | 7

Majme danú štandardnú schému:

begin	 [y1,y2,y3]:=[f1(x1,x2),a,c]
1:			if p1(y2,x2) then goto 4
2:			[y1,y2]:=[f1(f2(y1,b),x2),f3(y2)]
3:			goto 1
4:			if p2(y1) then [y3]:=[d]
end		 [z]:=[y3]

Nájdite takú interpretáciu schémy, aby x1 a x2 boli celé kladné čisla a program počítal, či podiel x1/x2 má konečný desatinný rozvoj (program vráti hodnotu 1, ak áno a hodnotu 2, ak nie). Stručne zdovôdnite, že pri vašej interpretácii bude program pracovať správne. Program má teda vrátiť áno (hodnotu 1) napríklad pre dvojice (x1=1, x2=2); (x1=3, x2=15); (x1=9090, x2=3). Na druhej strane program má vrátiť nie (hodnotu 2) napríklad pre dvojice (x1=1, x2=7); (x1=2, x2=15); a pod.

(2 body)

Späť

Majme danú Janovovu schému S:

begin [y]:=[x]
1:		 if p1(y) then goto 9
2:		 if p2(y) then goto 8
3:		 if p1(y) then goto 6
4:		 [y]:=[f5(y)]
5:		 goto end
6:		 [y]:=[f4(y)]
7:		 goto end
8:		 goto 8
9:		 if p2(y) then goto 14
10:	 [y]:=[f2(y)]
11:	 if p1(y) then goto end
12:	 [y]:=[f3(y)]
13:	 goto end
14:	 if p1(y) then goto 14
15:	 [y]:=[f1(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 (diagram). Stručne zdôvodnite, prečo je schéma S₁ voľná a ekvivalentná so schémou S.

(3 body)

Späť

Daná je štandardná schéma S:

begin [y]:=[x]
1:		 if p(y) then goto end
2:		 [y]:=[f(y)]
3:		 if q(y) then [y]:=[g(y)]
4:		 if p(y) then goto 3
5:		 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. Stručne zdôvodnite, že vami nájdena schéma je ekvivalentná so schémou S.

(3 body)

Späť

Napíšte program, ktorý vyhovuje nasledujúcej špecifikácii.

• vstupná podmienka p(x): xł0
• výstupná podmienka q(x,z): z=x!

(3 body)

Späť

Napíšte program, ktorý vyhovuje nasledujúcej špecifikácii.

• vstupná podmienka p(x): xł0
• výstupná podmienka q(x,z): z=x!

(3 body)

Späť

Metódou konštrukcie správnych programpov nájdite program, ktorý dostane na vstupe dve celé čísla x₁ a x₂, a ktorý vyhovuje nasledujúcej špecifikácii.

• vstupná podmienka p(x₁,x₂): x₂ł0
• výstupná podmienka q(x₁,x₂,z): z = x₁^x2, (čítaj: x₁ na x₂)

(3 body)

Späť

1. Dokážte, že každá konečná čiastočne usoriadaná množina s najmenším prvkom je cpo!
2. Jednoargumentová (t.j. unárna) funkcia nad diskrétnym cpo je monotónna práve vtedy, keď je striktná alebo konštantná. Dokážte!

(3 body)