Programarea structurată

Blocurile unei scheme logice se pot imparti in doua categorii mari:

- blocuri functionale de forma: ce reprezinta operatiile elementare asupra elementului x: blocuri de intrare/iesire si de prelucrare.

- blocuri predicative de forma :

care decid asupra urmatoarelor operatii ce trebuie executate in functie de valoarea predicatului x.

Consideram urmatoarele trei structuri de baza in programarea structurata:

- secventa notata ?(a,b) si are forma:

- selectia notata ?(?,a,b) si are forma:

si se numeste IF...THEN...ELSE

- iteratia notata ?(?,a) (WHILE...DO) cu forma:

do...until si if...then se pot exprima in functie de aceste blocuri sub forma:

?(?,a)= = =?(a,?(?,a))

?(?,a)= = = ?(?,a,?(?,a))

Analog, for= = ? (v?vi, ? (vf | v,? (a,v?v+h)

?(C,d) = ?(c1, a?1, ? (c2, a2, ?(.....?(cn, an, mesaj))....)

Definitie: Spunem ca schema logica ? admite descompunere tare ?? se poate exprima numai in functie de structurile de baza ?, ?, ?. Exemple de scheme ce admit descompuneri tare: do...until, if...then, case, for.

Exista si scheme logice care nu admit descompunere tare, asa cum ar fi urmatoarea:

n?2

Observam ca pentru n=1, aceasta schema este ?(?1, a1) care este descompunere tare.

Pentru a exprima si scheme de tipul celei de mai sus cu ajutorul structurilor ?, ?, ?, vom mai introduce trei blocuri functionale T, F, k si un bloc predicativ ? definite astfel:

- T este un bloc ce transforma elementul x in perechea (t,x), unde t=true, T(x)=(t,x).

- F transforma elementul x in perechea (f,x) unde f=false, F(x)=(f,x)

- k este un bloc optional ce alege dintr-o pereche ordonata a doua sa componenta: k(v,x)=x, v?{t,f)

- ? este dat prin ?(v,t)=t ?v=t.

Definitie: Spunem ca schema logica ? are forma normala ? ? se poate exprima prin blocurile ?, ?, ?, T, F, k, ?, adica ?=???????,T,F,k,?).

Teorema de structura a lui Bohm-Jacopini

Orice schema logica se poate duce la forma normala (se poate normaliza).

Demonstratie:

Pentru demonstratie vom observa mai intai ca orice schema logica poate fi una din urmatoarele trei tipuri:

Tip I

Tip 2 Tip 3

A, B, C sunt parti de schema logica construite in mod arbitrar. 1 si 2 pot sa nu fie intotdeauna prezente, dar din A, B, sau C trebuie sa porneasca cel putin o sageata.

Se mai observa ca schema de tip 3 poate fi pusa sub forma:

unde C ' este o parte a lui C accesibila de la partea superioara a lui C si C " este o parte a lui C acesibila de la partea inferioara, C = C ' ? C ''.

Fie A= si B=

in care una din ramurile 1 sau 2 poate sa nu existe.

Cu aceasta relatie, schemele 1 si 2 se normalizeaza astfel:

1 =??T?? ? ? ??,? ?k?? ?a?????? k).

2

= ???T?? ?? ??? ? ?k?????????????k?

Presupunand acum, printr-un rationament asemanator inductiei ca A si B se pot reprezenta prin structurile ???????? T, F, K, ? din normalizarile anterioare, rezulta ca schemele 1,2,3 se pot reprezenta prin aceste blocuri, deoarece am vazut mai sus ca structura ? se exprima prin ? si ?. Astfel, orice schema logica se poate normaliza.