Programgraf. Valódi program, strukturalt program fogalma. Strukturalt és nemstrukturalt alapformak. Böhm-Jacopini tétele.

Programgráf. Valódi program, strukturált program fogalma. Strukturált és nemstrukturált alapformák. Böhm-Jacopini tétele.

Valódi program: olyan gyengén öf. irányított gráf, amely:

véges számú nem zérus bemenõ éllel és kijövõ éllel rendelkezik

csp.-jai prédikátum csp.-ok és fv.csp.-ok és gyûjtõ csp.-ok.

csp.-on át vezet legalább egy bemenõ éllel kezdõdõ és kijövõ éllel végzõdõ út

Példa Nem valódi pr.:

Azt a pr.-ot, melynek gráfja lebontható az önmagában álló ir. élre, struktúrált pr.-nak nevezzük.

Struktúrált programozás

1., if p then f else g  - I-T-E (p,f,g)

g

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     ha p akkor f

p ¯                     545f59f                      545f59f                      545f59f                      545f59f            kül. g

                     545f59f                      545f59f                      545f59f             p                     545f59f                      545f59f       ha vége

f

f g                     545f59f         

2., while p do f  - W-D(p,f)

                     545f59f     p                     545f59f                      545f59f       p                     545f59f                      545f59f       ciklus amíg p

f

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                      545f59f             f

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     ciklus vége

                     545f59f     f                     545f59f                      545f59f                      545f59f           

3., begin f g end  - B(f,g)

	f		f		g

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     f

g

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     g

Definíció: Egy pr. gráf lebontása az az eljárás, melynek során a fenti 3 alapszerkezet valamelyikét egy fv.csp.-tal helyettesítjük, és ezt addig folytatjuk, amíg lehetséges.

Egy fv.csp.-ot tartalmazó gráf önmagában álló ir. él.

Példa

                     545f59f                 p₂

f2

p₁

W-D(p2, f2)

p₁

I-T-E(p1, f1, W-D(p2, f2))

Definíció: Azt a pr.-ot, melynek gráfja lebontható az önmagában álló ir. élre, struktúrált pr.-nak nevezzük.

Megjegyzés: Lehet a do f while p - DU(p,f) formát is struktúrált alapformának tekinteni.

	f

f

                     545f59f                      545f59f         p

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f         p

f

                     545f59f                 ciklus

                     545f59f                 f

                     545f59f                 amíg p

Példa

h

h

                     545f59f     nem strukt.                     545f59f                      545f59f               strukt.

                     545f59f                 q                     545f59f                      545f59f                      545f59f           q

                     545f59f     p                     545f59f                      545f59f                      545f59f           p

			f		g

Nem strukturáltság jellemzõi

Tétel: Egy pr. nem struktúrált Û részgráfjaként elõfordul nem struktúrált alapforma.

Tétel: A nem struktúrált pr. a nem struktúrált alapformák közül legalább 2-t tartalmaz.

Nem struktúrált alapformák:

több kilépõ élû ciklus                     545f59f                      545f59f          több belépõ élû ciklus

több kilépõ élû döntés                     545f59f                      545f59f                     több belépõ élû döntés

(Böhm-Jacopini)

valódi pr.-hoz  vele ekvivalens struktúrált program.

Bizonyítás: (vázlat)

1. Lemma: Adott egy pr. gráf:

élek száma:     n

pred.csp.:        p

gyûjtõ csp.:     g

fv.csp.:            j

Ekkor: n = 3p j + 1 és p g

Ui.: Csp.-ba mutató élek száma:

fv.csp.-ba: j                     545f59f   Összesen:

pred.csp.-ba:   p                     545f59f   j p + 2g +1 = n

gyûjtõ csp.-ba:2g                     545f59f                      545f59f     kimenõ él

Csoportból kimutató élek:

fv.csp.-ba: j                     545f59f   Összesen:

pred.csp.-ba:   2p j p g +1 = n

gyûjtõ csp.-ba: g                     545f59f                      545f59f      bemenõ él

Þ j p + 2g j p g

                     545f59f     g = p                     545f59f                      545f59f         n=3p j

2. Lemma: Egy pr. struktúrált Û felírható B(g,h) , vagy I-T-E(p,g,h) , vagy W-D(p,g) alakban, ahol p predikátum, g,h struktúrált pr., vagy fv., vagy üres pr.

Ui.: Egyszerû meggondolással látható a pr. lebontásánál mutatott módszerrel.

Bizonyítás: (tétel) Konstruktív

Belátjuk: valódi pr. felírható B(g,h), I-T-E(p,g,h), W-D(p,g) alakban, ahol g,h valódi pr.-ok és gráfjukban az élek száma kisebb, mint ez eredeti pr. éleinek száma.