SCHEMELE LOGICE - Structuri fundamentale ale algoritmilor

Structuri fundamentale ale algoritmilor

Structura secventiala sau liniara desemneaza una sau mai multe operatii ce se executa una dupa cealalta, in mod liniar (secvential).

Structura alternativadesemneaza executia unei secvente de operatii S₁ sau a alteia S₂, in functie de indeplinirea sau nu a unei conditii.

Structurile alternative sunt de mai multe tipuri:

Structura IF - THEN - ELSE, selecteaza succesiunea operatiilor ce urmeaza a fi executate, functie de valoarea logica de ,,adevar" sau ,,fals" pe care o are in momentul respectiv conditia specificata. Daca este adevarata conditia se urmeaza calea specificata de ramura DA, altfel se urmeaza calea NU.

Blocul are deci o intrare si doua iesiri, corespunzatoare celor doua valori logice posibile pentru o expresie logica (Adevarat si fals, Da si Nu)

Structura IF - THEN numita si selectia simpla, este practic o forma particulara a selectiei IF - THEN - ELSE, in care blocul de pe ramura Nu este vid.

In mod asemanator se poate construi si selectia IF - ELSE, cu precizarea ca in acest caz blocul vid va fi cel de pe ramura Da.

Practic, in ambele forme particulare, se testeaza conditia logica si se specifica doar succesiunea de operatii ce trebuie efectuate pe una dintre ramuri. Pe ramura cu bloc vid nu se executa nimic.

Structura CASE - OF selecteazauna dintre mai multe ramuri, in functie de valoarea unui selector. De aceea structura de acest tip se mai numeste selectie multipla.

Structura repetitiva sau iteratia indica repetarea unei operatii sau secvente de operatii S, atata timp cat este indeplinita o anumita conditie.

In functie de momentul in care se face testarea conditiei specificate, structurile repetitive sunt de mai multe tipuri:

Conditia poate fi testata anterior executiei secventei de comenzi S si atunci avem o structura de tip WHILE - DO

Conditia se testeaza posterior executiei secventei de comenzi S si atunci avem o structura de tip DO - UNTIL

Structura repetitiva mai poate fi analizata si din punct de vedere al numarului de reluari. Din acest punct de vedere, o structura poate fi:

fara numarator, caci nu se cunoaste de la inceput numarul de reluari. Asa este cazul structurii de tip WHILE, indiferent de tipul ei.

cu numarator, atunci cand se stie sau se poate calcula automat numarul de reluari. Asa e cazul structurii repetitive de tip DO - FOR

Pentru a evita ciclarea la infinit a structurilor repetitive, programatorul trebuie sa aigure negarea conditiei pentru a permite iesirea din structurile WHILE - DO si DO - UNTIL.

Se observa ca diferenta esentiala intre cele doua structuri consta in faptul ca DO - UNTIL executa S cel putin o data, in timp ce WHILE - DO poate sa nu-l execute pe S deloc, daca la intrarea in structura conditia este deja falsa.

Programarea structurata beneficiaza si de un puternic suport teoretic constand intr-o construcsie de principii, termeni si teoreme matematice specifice.

Teorema de structura Bohm si Jacopini spune:

Orice schema logica este echivalenta cu o schema logica structurata

Daca o organigrama cuprinde o multime F de actiuni si o multime P de predicate, astfel incat organigrama sa fie structurata si sa fie echivalenta cu cea initiala.

Corolarul ,,de sus in jos": Un program structurat este echivalent cu un program scris sub una din urmatoarele forme:

P=Secvential(f,g)

P=Alternativ(p,f,g)

P=Repetitiv(p,f)

Unde p este un predicat al lui P, iar f si g sunt secvente structuratesau functii ale programului.

Teorema de corectitudine:

Corectitudinea unui program structurat poate fi verificata prin examinarea fiecarui nod din arborescenta sa. Daca fiecare nod se verifica local, se spune ca programul structurat este corect.