Reprezentarea algoritmilor cu ajutorul schemelor logice

Reprezentarea algoritmilor cu ajutorul schemelor logice

Prin schema logica sau program sub forma de schema    logica se realizeaza o reprezentare grafica a modului in care se succed operatiile prevazute de algoritm. Schema logica este formata din instructiuni care descriu operatiile algoritmului reprezentat.

Presupunem ca datele de intrare se afla pe o banda de intrare,    iar datele de iesire sunt inregistrate pe o banda de iesire. Modul de organizare si acces pentru mediile de intrare si iesire este cel secvential. Instructiunile care alcatuiesc un program sub forma de schema logica sunt reprezentate prin arce etichetate. Sunt admise urmatoarele instructiuni:

Instructiunea START are forma:

Efectul instructiunii consta in pornirea procesului de calcul, deci    desemneaza operatia de pornire a procesului de calcul.

Instructiunea de citire are forma:

Efectul instructiunii consta in citirea, in ordine, a n valori de pe banda de intrare si inscrierea lor in locatiile de memorie rezervate pentru variabilele v₁, . . . ,v_n, deci desemneaza operatia de introducere a datelor.

Instructiunea de atribuire are forma:

Efectul instructiunii consta in evaluarea expresiei ex si inscrierea rezultatului in locatia de memorie rezervata variabilei v, deci desemneaza operatia de atribuire.

Instructiunea de decizie are forma:

unde p₁ , p₂ , . , p_n sunt predicate satisfacand relatiile :

p₁ p₂ p_n = 1

p_i p_j = 0, i j

care exprima faptul ca unul si numai unul dintre aceste predicate poate fi satisfacut. Efectul instructiunii consta in continuarea operatiilor mergand pe arcul corespunzator acestui unic predicat satisfacut. Pentru cazul n = 2 este folosita reprezentarea :

Deci, aceasta instructiune desemneaza o operatie de decizie.

Instructiunea de scriere are forma:

unde v_{1,    .,} v_n sunt variabile sau mesaje. Efectul instructiunii consta in scrierea, in ordine, a n valori pe banda de iesire memorate in locatiile de memorie rezervate pentru variabilele v₁, . ,v_n sau in scrierea succesiunii de caractere din care este alcatuit mesajul, deci desemneaza operatia de extragere a datelor.

Instructiunea STOP are forma:

Efectul instructiunii consta in oprirea procesului de calcul, deci desemneaza operatia de oprire a procesului de calcul.

Observatia 2.2

Punctele marcheaza extremitatile arcelor etichetate care reprezinta instructiuni.

Extremitatea initiala a arcului care reprezinta instructiunea START nu este pusa explicit in evidenta deoarece in aceasta extremitate nu pot sosi arce.

Extremitatea finala a arcului care reprezinta instructiunea STOP nu este pusa explicit in evidenta deoarece din aceasta extremitate nu pot pleca arce.

Definitia 2.5

Se numeste schema logica sau program sub forma de schema logica un graf orientat cu proprietatile:

Orice arc este un arc etichetat conform instructiunilor prezentate mai sus; in cazul cand arcul este etichetat cu un predicat, extremitatea initiala a arcului trebuie sa fie extremitatea initiala a unei instructiuni de decizie.

Exista o unica instructiune START si o unica instructiune STOP.

Orice arc apartine cel putin unui drum de la instructiunea START la instructiunea STOP.

Observatia 2.3

Din definitie rezulta ca intr-un program sub forma de schema logica este exclusa existenta unui arc diferit de instructiunea STOP din a carui extremitate finala sa nu plece vreun alt arc.

De asemenea, din definitie rezulta ca un program sub forma de schema logica nu poate contine configuratii de forma:

care reprezinta cicluri inerent infinite. Insa definitia nu poate elimina toate cazurile de nedeterminare a programelor. Preintampinarea unor astfel de situatii cade in sarcina programatorului.

Deoarece intr-o schema logica delimitarea instructiunilor este clara, se omit punctele prin care sunt marcate extremitatile lor.

Definitia 2.6

Se numeste subschema logica sau subprogram sub forma de schema logica un graf orientat cu proprietatile:

Orice arc este un arc etichetat conform instructiunilor prezentate mai sus; in cazul cand arcul este etichetat cu un predicat, extremitatea initiala a arcului trebuie sa fie extremitatea initiala a unei instructiuni de decizie.

Exista un singur nod initial (in care nu sosesc arce) si un singur nod final (din care nu pleaca arce).

Orice arc apartine cel putin unui drum de la nodul initial la nodul final.

Observatia 2.4

Daca subschema logica contine instructiunea START, atunci extremitatea initiala a acesteia este tocmai nodul initial, iar daca contine instructiunea STOP, atunci extremitatea finala a acesteia este tocmai nodul final.

O schema logica este, in particular, o subschema logica in care nodul initial este extremitatea initiala a instructiunii START, iar nodul final este extremitatea finala a instructiunii STOP.

Intr-un program sub forma de schema logica se poate utiliza si instructiunea de apel de subprogram care este sub forma

unde SP este numele subprogramului, iar v₁, .. , v_n sunt variabile de intrare si iesire. Daca in interiorul blocului se scrie numai SP atunci arcul etichetat astfel reprezinta instructiunea subprogram.