Programe structurate

Programe structurate

In practica, programele sub forma de schema logica pot lua forme foarte complicate. De aceea, in constructia programelor sub forma de schema logica se folosesc numai anumite structuri numite structuri fundamentale. Exista trei tipuri de structuri fundamentale: structuri liniare, structuri alternative, structuri repetitive.

Structura liniara este un subprogram care se construieste conform regulilor:

Instructiunile START, de citire, de atribuire, de apel de subprograme, de scriere, STOP sunt structuri liniare.

Daca SL1, SL2 sunt structuri liniare atunci structura

este o structura liniara.

Orice structura liniara se construieste plecand de la structurile liniare prezentate in regula 1 si aplicand de un numar finit de ori regula 2.

Structura alternativa este un subprogram care se construieste conform regulilor:

Instructiunea de decizie este o structura alternativa.

Daca SF1,., SFn sunt structuri fundamentale atunci structura

este o structura alternativa. Predicate p₁,.,p_n trebuie sa satisfaca conditiile prezentate la instructiunea de decizie.

Observatia 2.5

In cazul n = 2 este folosita reprezentarea

Daca una din structurile SF1, SF2 este vida, atunci arcul respectiv nu este etichetat.

Structurile repetitive sunt subprograme care descriu cicluri. In cazul ciclurilor cu un numar necunoscut de repetari, evaluarea predicatului p pentru iesirea din ciclu se poate face inainte sau dupa executia ciclului.

Daca evaluarea predicatului p se face inainte de executia ciclului, atunci structura repetitiva este de una din formele:

Daca evaluarea predicatului p se face dupa executia ciclului, atunci structura repetitiva este de forma:

Structura repetitiva care descrie cicluri cu un numar cunoscut de repetari este de forma:

unde

v     reprezinta o variabila numita variabila contor;

vi reprezinta valoarea initiala a variabilei v;

vc reprezinta valoarea de crestere a variabilei v;

vf reprezinta valoarea finala a variabilei v.

Observatia 2.6

Exista situatii cand evaluarea predicatului p se face in interiorul ciclului. In acest caz structura repetitiva este de forma:

Definitia 2.7

Se numeste subprogram bine structurat un subprogram construit conform regulilor:

instructiunile START, de citire, de atribuire, de apel de subprograme, de scriere, STOP sunt subprograme bine structurate;

structurile liniara, alternativa in cazul n = 2 si repetitiva in cazul evaluarii predicatului p inaintea executiei ciclului (prima forma) sunt subprograme bine structurate;

concatenarea a doua subprograme bine structurate este un subprogram bine structurat;

orice subprogram bine structurat se obtine aplicand regulile precedente de un numar finit de ori.

Definitia 2.8

Se numeste program bine structurat un subprogram bine structurat care este un program.

Observatia 2.7

Conform definitiilor prezentate un program bine structurat este un caz particular de subprogram bine structurat in care nodul initial este extremitatea initiala a instructiunii START, iar nodul final este extremitatea finala a instructiunii STOP.

Fie V multimea valorilor care pot fi luate de variabilele din program. Fie V_n multimea sirurilor de n 0 astfel de valori. Atunci unui program sub forma de schema logica i se poate atasa o functie partial definita

s : V_n V_n

unde domeniul D_s pe care este definita functia s este format din acele siruri x I V_n aflate pe banda de intrare pentru care programul se termina (se ajunge la instructiunea STOP), pe banda de iesire obtinandu-se sirul s(x).

Definitia 2.9

Doua programe sub forma de schema logica P₁ si P₂ care au asociate functiile s₁ si s₂ se numesc echivalente daca:

D_s1 = D_s2 .

Pentru orice x I D_s1 = D_s2 avem s₁(x) = s₂(x).

Teorema 2.1

(Bhm, Jacopini) Orice program sub forma de schema logica este echivalent cu un program sub forma de schema logica bine structurata.

Demonstratie

Vezi [13].

Observatia 2.8

In practica curenta in constructia programelor sub forma de schema logica sunt utilizate si celelalte structuri fundamentale care nu intervin in constructia unui program bine structurat.