Scheme Logice

Scheme Logice

Pentru a putea defini notiunea de schema logica sau program sub forma de schema logica , vom prezenta sub forma formalizata instructiunile care pot aparea intr-o schema logica.

Exista doua clase de scheme logice:

Clasa 1. Scheme logice pe limbaj de programare

Clasa 2. Scheme logice propriu-zise

O schema logica face parte din prima clasa, daca urmareste descrierea p 343b14d roblemei in blocurile sale functionale sau de decizie, in functie de facilitatile limbajului de programare in care urmeaza a fi scris programul aferent; in acest caz fiecare bloc de functionare sau de decizie al schemei logice trebuie sa scrie informatia pe care o trateaza in asa natura incat, informatiei tratate in blocul respectiv, adaugandu-i cuvinte cheie potrivite, rezultatul sa devina o instructiune scrisa corect din punct de vedere al limbajului la care face referinta.

O schema logica face parte din a doua clasa, daca, in descrierea problemei, informatia inscrisa in blocurile sale sau decizie sa fie comuna fiecarui limbaj de programare. Aceasta inseamna ca unele facilitati transmise de informatia din blocurile de functionare sau decizie trebuie deduse in functie de limbajul de programare in care urmeaza a se lucra.

Instructiunile admise intr-o schema logica:

1. Instructiunea START este un arc etichetat cu cuvantul START (figura 4a) . Varfur initial al arcului nu este pus explicit in evidenta , deoarece in el nu pot sosi arce, iar executia ( derularea ) unui program incepe intotdeauna cu aceasta instructiune.
2. Instructiunea STOP este un arc etichetat cu cuvantul STOP (figura 4b) . Varful final al arcului nu este pus explicit in evidenta, deoarece din el nu pot pleca arce, efectul acestei instructiuni determina terminarea executiei programului.
3. Instructiunea de citire CITESTE , este un arc etichetat cu cuvantul CITESTE (figura 4c) care determina citirea a "n" valori de pe banda de intrare si inscrierea lor in locatiile de memorie rezervate pentru variabilele a , a .,a_n
4. Instructiunea de scriere, TIPARESTE, este un arc etichetat cu cuvantul TIPARESTE (fig 4d)

care determina inscrierea pe banda de iesire, a valorilor memorate in locatiile de memorie

rezervate pentru valorile a , a .,a_n

5. Instructiunea de atribuire  (figura 4e) este un arc in care " v" este o variabila iar "e" este o expresie de acelasi tip ( numeric, boolean) cu variabila "v". Efectul instructiunii consta in evaluarea expresiei " e" si in inscrierea rezultatului in locatia de memorie rezervata variabilei "v".
6. Instructiunea de ramificare (figura 4f) contine predicatele p p p_n care satisfac relatiile p₁v..vp_n=1

_{i j}=0

Care exprima faptul ca unul si numai unul dintre aceste predicate poate fi verificat

( adevarat). Efectul instructiunii consta in continuarea executiei pe arcul corespunzator acestui unic predicat.

Pentru cazul n=2 este utilizata si reprezentarea din figura 4g echivalenta cu cea din fig 4h.

j

Figura 4

Def 13: Se numeste schema logica sau program sub forma de schema logica un graf orientat in care:

1. Exista o unica instructiune START si o unica instructiune STOP
2. Oricare arc este etichetat cu una din urmatoarele informatii:

Ø      STOP

Ø      CITESTE sau TIPARESTE

Ø      O atribuire

Ø      Un predicat in care caz extremitatea initiala a arcului trebuie sa fie extremitatea initiala a unei instructiuni de ramificare

3. Pentru orice arc exista macar un drum care incepe cu instructiunea START, se termina cu instructiunea STOP si contine arcul considerat.

Aceasta ultima conditie exclude existenta intr-o schema logica a unui arc diferit de STOP din a carui extremitate finala nu pleaca un alt arc; de asemenea sunt excluse configuratii ca cele din figura 4i si 4j care reprezinta cicluri infinite.

Definitia adoptata mai sus nu poate elimina insa toate cazurile de nedeterminare a programelor, cum ar fi de exemplu o schema logica in care apare configuratia din figura 4k, nedeterminarea ecuatiei datorandu-se in acest caz formei particulare a etichetelor arcelor, preintampinarea acestor neajunsuri cade in sarcina celui care proiecteaza schema logica.

Fie V multimea valorilor care pot fi luate de variabilele din program si fie V^* multimea sirurilor de n 0 de astfel de valori.

In aceste conditii unei scheme logice S i se poate atasa o functie partial definita:

unde domeniul D_S pe care este definita functia f_S este formau din acele siruri x V^* aflate pe banda de intrare, pentru care programul de termina ( se ajunge la o instructiune STOP) pe banda de iesire obtinandu-se sirul f_S(x).

Def 14: Doua scheme logice S₁ si S₂ sunt echivalente daca:

D_S1= D_S2

D_S1 D_S2 f _S1( x) = f _S2( x)

Schemele logice pot lua forme foarte complicate astfel incat pentru proiectarea lor se folosesc anumite configuratii obtinandu-se astfel scheme logice bine structurate.

Def 15: Se numeste subschema logica un graf orientat in care:

Ø      Exista un singur varf initial ( varf in care nu sosesc arcele) si un singur varf final ( varf din care nu pleca arce).

Ø      Oricare arc este etichetat cu una din urmatoarele informatii:

STOP

CITESTE sau TIPARESTE

atribuire

Un predicat in care caz extremitatea initiala a arcului trebuie sa fie extremitatea initiala a unei instructiuni de ramificare

Daca subschema contine instructiunea START , atunci extremitatea initiala este tocmai varful initial; Iar daca contine instructiunea STOP, atunci extremitatea finala a acesteia este tocmai varful final.

Ø      Orice arc face parte din cel putin un drum ce uneste varful initial cu cel final

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

Def 16: O subschema logica bine structurata ( SLBS) se defineste recursiv astfel:

Ø      Instructiunile de intrare iesire, START, STOP si de atribuire sunt SLBS

Ø      Daca S₁ si S₂ sunt SLBS atunci si subschemele din figura 5 sunt SLBS cu respectarea conditiilor referitoare la START si STOP

Ø      Orice SLBS se obtine din 1 si aplicand de un numar finit de ori regula 2

O schema logica bine structurata este in aceste conditii o SLBS care este chiar o schema logica.

Teorema BǑHM, JACOPINI: Orice schema logica este echivalenta cu o schema logica bine

structurata.