Subiecte teoretice IP (semestrul 2)

1. Arhitectura unui sistem grafic interactiv.

Prin sistem se intelege un ansamblu format din echip & progr specializate in tratarea si rep grafica a informatiei; dupa scopul prelucrarilor pe care le efectueaza avem: 1) sistem de sinteza a imaginii si 2) sistem de prelucrare si analiza a imaginilor. Calitatea unei imag pe suportul de iesire este caracterizat de 3 notiuniu: 1) dimensiunea punctului; 2) adresabilitatea; 3) rezolutia; Procesarea inf primare necesita un volum mare de calcule aritm efectuate asupra punctelor din care e constr imaginea; grafica este sustinuta de procesorul unic al sistemului; calc au in alcatuire si placa video care contine mem grafica, comp de serializare si conversie video, controlerul video care genereaza semnale de sincronizare a monitorului si extrage inf din memoria video. Arh unui sistem grafic se regaseste in structura echip numit statie grafica interactiva – o structulra posibila e urmatoarea: UCP, dispozitive periferice, magistrala sistemului, procesor grafic, memorie UCP, memorie proc grafic, memorie rasturi, controler video.

2. Elemente de geometrie (ec dreptei, cercului si elipsei)

Ecuatiile unei curbe sunt – forma explicita – y=f(x), forma implicita – f(x,y)=0, forma parametrica x=f(t) si y=f(t), forma polara R=f(teta); Notiunile de suprafata, curba si punct pot fi considerate ind de suportul lor material deoarce prin miscarea unui punct obtinem curba, prin miscarea unei curbe avem suprafata si prin miscarea unei suprafete avem volum. O transformare este o aplicatie bijectiva a planului, spatiului pe el insusi. Transformarile cele mai imp sunt izometriile – deplasari si antideplasari (oglindiri). Ecuatia dreptei – forma explicita y=mx+n; forma implicita ax+by+c=0; Ecuatia cercului – (x-x0)^2 + (y-y0)^2=R^2; Ecuatia elipsei – ecuatia carteziana (x-x0)^2/a^2 + (y-y0)^2/b^2=1; Ecuatia parabolei – ecuatia carteziana y^2=2px; ecuatia generala – y=ax^2+bx+c.

3. Transformarea de vizualizare 2D

Desenele realiz cu calc sunt descrise intr-un sistem de coordonate dif de acela la care sunt rap pe supr de afisare; vom numi sistemul de coordonate logice universale sau utilizator, sist in care sunt desenele descrise; si vom numi sistemul de coordonate fizice sau disp sistemul atasat suprafetei de afisare. Transf de vizualizare este o aplicatie dintr-un sistem de coordonate in altul care pune in corespondenta fiecare punct al unui desen cu fiecare punct al suprafetei de afisare; Supr de de disp in care vom facem desenul este de forma dreptunghiulara si o numim poarta; supr din spatiul real din care decumap fig de desenat este ferestra => transf de vizualizare se mai numeste transf fereastra – poarta. Fie F(xf, yf) un pct din fereastra si P(xp,yp) punctul corespunzator din poarta. Transf fer-poarta -> cond se formuleaza astfel:
Xp-Xpmin / Xpmax-Xpmin=Xf-Xfmin / Xfmax – Xfmin si Yp – Ypmin / Ypmax – Ypmin = Yf – Yfmin / Yfmax – Yfmin. Forma matematica a trans fer-poarta este Xp=Xf*sx+tx si Yp=Yf*sy+ty. Daca aplicam trans, atunci desenul din fereastra va aparea rasturnat – pentru a evita asta Yp=Ypmin + Yfmax – Yf * Sy + Ty.

4. Transformari 2D 

Translatie – rep prin ec x’=x+a si y’=y+a. Prod a doua translatii este tot o transaltie. Pb translatiei se rez cu o matrice [1 0 a \ 0 1 b \ 0 0 1]. Spunem ca rep. pozitie unui punct in plan printr-un vec cu 3 comp este o rep in coordonate omogene.
Scalarea – este controlata de matricea T = [ A 0 \ 0 D ] si avem (x,y)*T=(Ax,By) si x’=Ax si y’=Dy. Daca se doreste marirea sau micsorarea uniforma a patratului trebuie ca val lui A si D sa fie egale.
Simetrie – cazuri particulare ale matri care prod scalari in care A si / sau D sunt negative.
Deformarea (forfecarea) – controlata de matricea T = [ 1 0 \ B 1 ] pt o deformare in y sau in sensul axei oy; matricea T = [ 1 C \ 0 1 ] prod o deformare pe ox; T = [ 1 C \ B 1 ] prod o deformare in ambele axe.
Rotatie – formulele care dau rotatia punctului x’=xcos(teta)-ysin(teta) / y’=xsin(teta)+ycos(teta). Matricea care controleaza este T=[cos(teta) –sin(teta) \ sin(teta) cos(teta)]
Tb sa retinem ca rotatiile se efectueaza numai in jurul originiii, matr de rota este o comb de scalar si deformari care lasa neschimbate dim finale si o matr de rot are intotdeauna val det = 1;

5. Compunerea transformarilor 2D

Toate transf 2D au fost centrate in orig. axelor sau altfel spus O(o,o) este un invariant. Toate matr de trans sunt de forma T=[A C 0 \ B D 0 \ 0 0 1]. O rot in jurul unui pct auxiliar al unui plan va fi efect in felul urm: 1) se translateaza centrul de rotatie 2) se efect rotatia asteptata 3) se executa transaltia rez la centrul de rotatie initial; pentru o mai mare opt se compun cele 3 matri necesare in una singura. In final va fi necesar si indeajuns sa citim coordonatele (a,b) ale centrului de rotatie si val unghiului de rot teta si apoi aplicam aceste forumule:
x’=xcos(teta)-ysin(teta)-acos(teta)+bsin(teta)+a si y’=xsin(teta)+ycos(teta)-asin(teta)-bcos(teta)+b.
Ca o concluzie – matri are forma generala T= [ A C a \ B D b \ 1 1 E] unde A,B,C,D produc scalarile, rotatiile si deformarile; a,b – prod translatiile; E – prod schimbarea scalei generale;


6. Sisteme de coordonate carteziene, sferice, cilindrice

Avem conventia – axa de rotatie ox / y / z – dir de rot poz y catre z / z catre x / x catre y. Avem sist. Urm de coordonate matematice: a) sist de coord carteziene XoYoZ; b) sist de coord sferice XoYoZoPoP’ unde poz pct p se specifica in coord sferice prin raza R, unghiul gamma si teta. Avem o relatie de trecere de la a la b (v. curs) si de la b la a – x=Rcos(teta)*cos(gamma) y=Rsin(teta)cos(gamma) si z=Rsin(gamma); c) sist de coord cilindreice XoYoZoPoP’ unde P apare la cota z, raza R si unghiul teta; trecerea de la a la c se face astfel: R=radical din x^2+y^2 si z=z; trecerea de la c la a se face astfel: x=rcos(teta) y=rsin(teta) si z=z. Grafice v. curs.

7. Transformari 3D

Matricea de transf generalizata 4x4 pentru coord omogene 3d are forma T=[ a d g l \ b e h m \ c f i m \ p q r s ]. Semnificatia partilor este urmatoarea: [ a d g \ b e h \ c f i ] include trans de scalare locala, deformare, oglindire si rotatie. [l m n] rep transf de translatie iar [s] rep transf de sclare generala.
Scalare – [x y z 1] * [ A 0 0 0 \ 0 B 0 0 \ 0 0 C 0 \ 0 0 0 D] = [ Ax, By, Cz, 1] = [x’,y’,z’,1]. Daca A=B=C atunci scalarea este uniforma.
Simetrie (oglindire) – pentru a gasi in raport cu planul xoy este suficient sa schimbam semnul cotei z al tuturor punctelor obectului respectiv. Vom avea matricile de transformare Sxoy = [ 1000\0100\00-10\0001]; Sxoz = [1000\0-100\0010\0001]; Syoz = [-1000\0100\0010\0001]. Simetriile fata de axele ox, oy si oz sunt: Sox=[1000\0-100\00-10\0001]; Soy=[-1000\0100\00-10\0001]; Soz=[-1000\0-100\0010\0001]; Simetrie fata de origine So=[-1000\0-100\00-10\000]; Exista si alte timpuri de simetrii – fata de un plan oarecare se rezolva aplicand sist de ref translatia si rotatia ai un plan de coordonate sa se suprapuna peste planul dat si apoi efectuam simetria fata de acest plan; apoi se face translatia inversa;

8. Metoda Branch & Bound

Metoda B&B, inrudita cu metoda backtracking, difera de aceasta prin ordinea de parcurgere a arborelui spatiului starilor S si prin modul in care se elimina subarbori care nu pot conduce la rezultat. Avem o stare intiala – So si o stare finala Sf – se trece de la o stare la alta prin luarea unei decizii. Deci trebuie sa determinam un sir de decizii pentru a trece din starea So in starea Sf.
Astfel, trebuie construit un graf ale carui noduri vor corespunde starilor iar muchiile / arcele reprezinta deciziile. Vom introduce restrictii ca un nod sa apar o singura data si atunci graful se transforma intr-un arbore. Exista doua modalitati de parcurgere a arborelui starilor.
1) Parcurgere DF (Deth First) – consta in pornirea din starea initiala So. Se apeleaza functia DF(So); se obtin nodurile fii ale nodului pentru care s-a apelat procedura; pentru fiecare nod rezultat se apeleaza din nou procedura DF; ne vom opri in momentul in care vizitam nodul care contine starea finala. Dezavantajul consta in faptul ca nu va furniza solutia cu numarul minim de decizii.
2) Parcurgerea BF (Breadth First) – consta in construirea unui sir de multimi de stari in care prima multime contine doar starea initiala iar a doua multime contine starile fii; la fiecare pas in multimea k se vor introduce starile fii ale starilor din multimea k-1; ne vom opri cand s-a generat multimea ce contine starea finala.
Se obtine intotdeauna solutia intr-un numar minim de decizii dar trebuie parcurse relativ multe stari pentru a ajunge la rezultatul final.
Astfel apare 3) Parcurgerea LC (Least Cost) – se introd o functie cost a unei stari care trebuie sa respecte doua conditii – costul starii finale trebuie sa fie minim; - costul starilor ce se afla pe un drum de lungime minima de la starea So la starea Sf trebuie sa fie in ordine descrescatoare. Se va lucra cu aproximari euristice ale costului (vor fi explorare si stari care nu conduc la solutie optima sau nu conduc la nici o solutie). Aceasta functie trebuie sa indeplineasca conditiile – distanta (A,A) <- 0; distanta (A, Sfinal) >= distanta (B, Sfinal) daca exista o decizie care trece de la A in B;
Relativ la cost – doua dintre euristicile cele mai des folosite sunt – cost <- nivelul curent + distanta dintre config curenta si config finala; cost <- costul starii parinte + distanta dintre config curenta si config finala;
Forma standard a problemei – se da o stare initiala, o stare finala si se cer deciziile. Folosim o lista in care un elem al liste are campurile: inf (retine o stare), cost (retine costul), urm si pred (legaturile).

9. Clasificarea programelor de grafica

Dupa domeniul de aplicare avem: 1) Progr de pictura (Paintbrush); 2) Progr de desenare orientate pe obiecte si prod ilustrate simple; 3) Progr pentru ilustrare dezvoltari ale celor de desen; 4) Progr pentru grafica de afaceri si de prezentare deseneaza grafice, histograme, etc.; 5) Progr de animatie; 6) Progr pentru desenarea, proiectarea asistata de calculator - CAD; 7) Progr pentru prelucrarea imaginii; 8) Progr de umbrire si iluminare; 9) Programe de trasare care sunt orientate pe puncte si sunt utulizare in proiectarea de circuite;

10. Elemente de teoria culorii

Dpdv fizic – culoarea este sinonima cu radiatiile electromagnetice cuprinse intre 375 si 76 nanometrii. Dpdv psiho-fizic, culoarea este aceea caracteristica a luminii care permite distingerea unul de alta a doua 2 corpuri de aceiasi forma, marime, structura din spectrul vizibil. Dpdv psiho-senzorial, orice senzatie luminoasa care se carcat prin luminozitate, tonalitate si saturatie. O culoare rezulta din suprapunerea componentelor sale def de 3 atribute – tenta, luminozitate, saturatie. In general toate culorile pot fi realiz pornind de la 3 surse monocrome diferite RGB.
Natura tridimensionala a culorii reiese din legile lui Grassman – sis vizual distinge 3 stimuli diferiti, 4 culori pot fi puse intotdeauna intr-o relatie liniara, spatiul 3d al culorilor este continuu. Informatica sintetizeaza sist de codificare numerica a culorilor – RGB, CMY, HSL, HSB, etc.

11. Fonturi si formate de reprezentare a informatiei grafice

Pentru rep seturilor de carcatere se pot folosi urmatoarele standarde de baza: 1) ASCII – se deseneaza un set de 128 / 256 carcatere; 2) ASCII extins – coduri de 128 / 256 caractere dar pentru taste apasate simultan. 3) setul IBM de carcatere grafice – a aparut odata cu monitoarele grafice. In mod concret, fonturile sunt fisiere care descriu setul de carcatere prin informatii referitoare la – dimens masurata in nr de puncte; tip; matricea de puncte; informatii de identificare a fisierului; informatii neutre;

12. Structuri de date statice

O structura este statica daca ocupa in memorie o zona de dimensiune constanta.
Tabloul – un tablou uni-dimensional este vector sau sir; daca dim este mai mare de 1 atunci tabloul poate fi considerat un tablou de vectori.
Articolul – o colectie formata dintr-un nr fix / variabil de componente numite campuri de regula avand tipuri diferite. Operatiile care actiuneaza asupra articolului sunt atribuirea, selectarea unei componente.
Multimea – este o structura statica prin care se poate reprezenta o colectie finita de elemente. Carcat finit permite indexarea elem. Operatii posibile – atribuirea, operatii cunoscute din teoria multimilor.

13. Structuri de date semistatice

Daca o structura ocupa o dimensiune constanta, dar elementele sale ocupa un loc variabil in timpul executiei, structura este semistatica.
Stiva – fie S spatiul alocat avand baza B si varful V ai B<=V. Operatii posibile – adugare, sterge element. Stiva poate fi privita ca o struc semistatica formata din perechi.
Coada – fie S o zona de memorie cu baza B si varful V ai B<V. Coada poate fi privita ca o struc ca tripletul. Operatii posibile – adaugare si eliminare.
Tabela de dispersie – fie S spatiu aloca stru avand baza B si varful V ai B<V impartit in n parti egale numerotate cu valori din multimea 0..n-1. Este o structura prin care se realiz partionarea multimii M in n clase disjuncte. Datele din partitiile tabelei in general sunt numerotate sub forma unei liste liniare.

14. Structuri de date dinamice

In cazul in care str ocupa in mem interna o zona care se aloca in timpul exec pragului fara a avea o dim structura este dinamica.
Lista liniara – daca M e mult prin lista lin se intelege o secventa vida de elem din M. Pt reprez sunt necesari – referinta la primul element din lista (cap), inlantuirea elem lista intre ele, ultimul element din lista. Le sunt carcateristice operatiile – inserarea si eliminarea unui element, crearea str prin inserarea in lista initial vida, traversarea listei, cautarea unui elemn, concatenarea listei.
Arborele – fiind data o multime M de elem numite noduri sau fii vom numi arbore un set finit de noduri ai exista un nod cu distanta speciala numit radacina, celelalte noduri sunt repartizare in m>=0 seturi disjuncte, fiecare set constituind la randul sau un arbore.
Arbori binari – acesta este fie vid, fie orintat in fiecare varf avand cel mult doi descendenti – stang si drept. Ierahizarea nodurilor se poate concretiza prin diferite tipuri de referinte sau leg, in general folosindu-se referinte descendente dar putand folosi si ascendente. Daca nu exista o ierarhizare a nodurilo pe niveluri, arborele e neorientat.
Reteaua – daca nodurile unei multimi M nu se mai organizeaza pe niveluri, dandu-se posibilitatea existentei de legaturi intre oricare dintre ele, atuni vom aveam o struct de tip retea.
Fisierul – este o colectie de date memorate de obicei pe un suport magnetic.
Baze de date – colectie de fisiere care pot avea structuri identice sau diferite care se prelucreaza in cadrul unei aplicatii.

15. Arbori binari, descriere recursiva, repr cu vectori si reprezentarea liniara.

O struct arborescenta e o struct de date care permite o descriere recursiva. In limbaje de tip Pascal descrierea se realiz in felul urmator:
Type ref=^varf; varf=record info: T; stang,drept: ref; end;
In cazul altor limbaje se foloseste reprezentarea cu vectori de inregistrai. Campurile contin informatia propriu-zisa si referintele la fiul stang si / sau cel drept. Alta reprezentare este cea liniara – se reprezinta doar informatiile propriu-zise atasate nodurilor, legaturile dintre noduri fiind implicite. Se utilizeaza de regula in implementarea acelor algoritmi care nu presupun inserari, stergeri, etc.

16. Arbori oarecare. Reprezentarea prin arbori binari echivalenti

Pentru arbori oarecare avem urmatoarele tipuri de reprezentari.
1) Rep cu referinte descendente – fiecare nod contine pe langa informatia propriu-zisa un vector cu referinte catre fii si un contor care arata nr de astfel de referinte.
2) Rep prin arbore binar echivalent – arborele binar se obtine pastrand primul descendent ca fiu stang iar al doilea ca fiu drept al fiului stang, samd  - adica referinta stanga corespunde unei legaturi tata – fiu iar cea dreapta unei legaturi de tip frate – frate.
3) Reprezentarea prin referinte ascendente – in finecare nod pe langa info propriu-zisa se pastreaza o singura referinta si anume aceea catre tatal nodului respectiv.

17. Reprezentarea arborilor pe suportul de iesire (monitor)

Sunt trei forme de reprezentare prinicipale – preordine, inordine, postordine. Arborele se mai poate vizualiza si prin expresii cu paranteze in care lista nodurilor apare intr-o anumita ordine, relatia de subordonare fiind data de paranteze. O varianta este cea prefixata, in care se reprezinta (radacina subarbore stang subarbore drept). Pentru simplificare nu mai punem paranteze daca nodul este terminal. Ex – (A(B D(E H I))(C F (G J K))). Se poate folosi si varianta infixata (subarbore stang radacina subarbore drept) dar nu se poate utiliza pentru arbori oarecare.

18. Traversarea arborilor in adancime si latime

Traversarea in adancime. Alg pntru preordine – se viziteaza rad, se traverseaza sub-arborele stang si dupa aceea se traverseaza sub-arborele drept. Avem procedura traversare cu arg – nod_travers si rad care realiz trav arb binar in toate cele trei moduri.
Afisarea se face cu procedura afisare – procedure afisare (nod, nivel) while nivel>0 write ‘ ‘ nive <- nivel -1; endwhile; write nod^.cod; return;
Procedure Travers (modt, rad, nivel) if rad <> nil then if modt=preordine then afisare (rad, nivel); travers (modt, rad^.st, nivel +1); if modt=inordine then afisare(rad,nivel); travers (modt, rad^.dr, nivel+1); if modt=postordine then afisare(rad,nivel); return;
Procedure traversare (mod_travers, rad) travers(mod_travers, rad, 0); return;

19. Traversarea nerecursiva a arborilor

Pentru a elimina recursivitatea folosim de exemplu o stiva. In procedura travers_nerec, arb este consid ca fiind repr prin refer ascendente, cat si prin cele descendente si in plus, in fiecare nod se pastreaza un contor ce numara de cate ori s-a trecut prin nodul respectiv in decursul traversarii. Codificarea este urmatoarea: type tipref=0..2 ref=^varf; varf=record cod:integer; refs: array[tipref] of ref; indice: 0..3; end; trav=0..2.
Aceasta codificare semnifica referinta tata-stanga-dreapta iar cea din trav arata tipul traversarii (pre, in, postordine). Vectorul refs contine 3 referinte – catre nodul tata, catre fiu. In traversarea arb trecerea de la un nod la altul este dirijata de val contorului indicelui nodului curent, care in afara de rolul mentionat va fi si indice de referinta in vectorul refs.
Proc traver_nerec se va apela cu valori diferite ale lui nod_traver si anume – 0 pentru preordine, 1 pentru inordine si 2 pentru postordine;
Procedure Travers_nerec (mod_travers, rad)
p<-rad; q<-nil; while p<> nil repeat if p^.indice=3 then p^.refs[0]=q; q<-p; q^.indice=0; endif; if p^.indice=mod_travers then write(p^.cod); endif; p ^.indice<-(p^.indice+1) mod 3; if p^.indice=0 then q<-p^.refs[0]; gasit<-true; else gasit<-p^.refs[p^.indice]<>nil; endif; until gasit; p<-p^.refs[p^.indice]; endwhile; return;
Alte variante pentru traversarea nerecursiva – 1) se foloseste o structura de lista liniara suprapusa peste structura de arbore; 2) traversarea se va face cu refacerea legaturilor pe cale de revenire; 

20. Arbori de cautare: definire si clasificare

Struct arb sunt folosite pentru mem si regasirea rapida a unor informatii. Inf memorate pot fi inreg oricat de complexe dar ele contin un camp numit cheie care serveste la identificarea inreg. O clasif a arb de cautare este urmatoarea: 1) Arb de cautare numerica – structurii tree; 2) Arb bazati pe ord cheilor – a) arb optimali; b) arb echilibrati; c) arb splay; b1)arb echil dupa inaltime (echil AVL si arb a-b – care pot fi B arbori si arbori rosu si negru); b2) dupa greutate – BB[alfa], WB[alfa]; b3) dupa pondere – aproape optimali;
Arb bazati pe ord cheilor pot fi – binari (o sg cheie asoc fiecarui nod) si multi cai (mai multe chei pentru fiecare nod);

21. Structura de tip HEAP (rezultate bune ca timp de executie)

Un heap este un vector care poate fi considerat un arbore binar. Aceasta structura poate fi folosita foarte bine pt alg de sortare si cautare. Pentru ca un arb binar sa poata fi considerat un heap nodurile acestuia trebuie sa fie complete, cu exceptia ultimelor (se completeaza incepand cu nodul ce mai din stanga). Intaltimea unui heap este inaltimea arb binar corespunzator. Cea mai imp a heap e aceea ca val oricarui nod nu poate fi mai mare decat val nodului tata. Prop foarte importanta pentru operatiile de cautare (mai ales in structuri mari).
Operatiile posibile cu aceasta structura sunt – determinarea max val dintr-un heap, creearea unui heap dintr-un vector oarecare, eliminare element, inserare element, sortare, cautarea unui element.
Implementarea  - in mem sub forma de arb sau forma vectoriala. Typedef int heap[max]. Deoarece dimens struct poate fi destul de mare, e recomandabil ca aceasta sa nu e transmisa ca parametru pentru anumite functii.
1) det maximului – deoarece primul elem e cel mai mare – avem o functie foarte simpla – int max() { return h[1]; }
2) crearea unu heap dintr-un vector oarecare – daca avem cumva un nod care nu respecta prop de heap el trebuie coborat in arbore. Alg de reconstituire a prop de heap va cobora in arbore nodul care nu se afla pe o pozitie corecta pana in momentul in care nu mai avem fii sau prop de heap este respectata. Pentru a cobora nodul in arb, in vom interschimba cu fiul care are rad max. Aceasta operatie poarta numele de scufundare. O sa avem o functie void scufundare (int n, int k) { codul nostru }. Mai avem o functie – void construiesteheap (int n) { for int i = (n>>1); i ; scufunda (n, i--);}
3) eliminarea unui element – aici avem nevoie de o alta operatie – reconstituirea structurii heap – atunci cand un nod care nu respecta prop de heap. Vom interschimba acest nod cu tatal sau. Totusi s-ar putea ca dupa interschimbare nodul sa aiba un tata cu o val mai mica – mai trebuie din nou aplicate modificari. Procedeul va continua pana cand avem o structura heap. Aceasta op se cheama ridicare. Avem urmatoarea functie – void ridica (int n, int k) { int nod = h[k]; while (k >1  && nod > h[k]>>1) h[k]=h[k>>1]; h[k]=rad;}

22. Modalitati de reprezentarea a grafurilor

Exista 3 moduri de reprezentare a grafurilor.
1) Reprezentarea prin matrice de adiacenta – element a(i,j)=1 daca muchia exista si a(i,j)=0 daca nu exista muchea. Daca este vorba de un graf foarte mare metoda nu este eficienta din cauta memoriei care nu este folosita eficient.
2) Reprezentarea prin liste de adiacenta – se va atasa fiecarui nod i o lista de varfuri adiacente lui (pt graf orientate e necesar ca muchea sa plece din i). Aceasta reprezentare este recomandata dpdv al folosirii memoriei cand nr de muchii e mic. Cautarea este insa anevoiasa.
3) Reprezentarea prin lista de muchii (sau arce) – perechi (i,j) – eficienta cand se vor examinate toate muchiile grafului.

23. Parcurgerea grafurilor

Parcgraf (i) vizit<-i; prelucr inf din i; neexplor<-vizit; cat timp neexplor<>0 alege un nod din neexplor, gaseste perechea (v,w) arc neexplor; daca (v,w) nu exista atunci sterge v din neexplor altfel data w nu apartine vizit atunci adauga w la vizit; prelucreaza info din vizit; adauga w la neexplor;
Operatia de parcurgere a grafurilor se realizeaza prin una din urmatoarele 3 metode:
1) Algoritmul DF (depth first) – se porneste de la un nivel initial v. Nodul curent este x. Cautarea continua cu muchea (x,y) care e incidenta in x si y si nodul y devine nodul curent. Dupa epuizarea tuturor drumurilor care pleaca din y revenim in nodul x, parcurgand urmatoarea muche. Numele alg provine de la faptul ca parcurgerea s-a efectuat avand ca directie prioritara adancimea grafului.
Procedure DF (i); vizit(i)<-i; prelucr nodul i; reurn – orice nod j vecin cu i; daca vizit(j)=0 atunci DF(j); end;
Pentru parcurgerea intregului graf avem secventa urmatoare: pentru i:1,n daca vizit(i)=0 atunci df(i)
2) Algoritmul BF (breadth first) – porneste din nodul initial v si il noteaza ca vizitat. Apoi toate nodurile adiacente lui v. Dupa aceea se alege un descendent al lui v. Parcurgerea se executa pe latime.
Procedure BF(i); initializeaza coada executa push(i); vizt(i)<-1; prelucreaza nodul i; cat timp coada nu e vida j<-pop; pentru toti k ai lui j daca vizt(k)=0 atunci executa push(k); vizit(k)<-1; prelucram nod k;
Alg se termina cand coada e vida.
3) Algoritmul D (depth) spre deosebire de BF acesta prelucreaza mereu numai ultimul elem la care s-a ajuns. Lista nu mai este coada ci stiva.

24. Interpretarea instructiunilor de atribuire

Fie v apartine lui e, unde se evalueaza mai intai expresia e iar valoare astfel obtinuta se atribuie variabilei v. Ac succesiune,in timp, se poate retranscrie astfel:
V(t+1)=e(t),e(t)=e(….,v(t),…);v(t) poate lipsi,figurand alte variabile.
Fie sirul de atribuiri simultane:
Vi=e(v1,…,vk,c1,…,cp)  (1) vj,j=1..k,cj,j=1..p
Tinandu-se seama de momentul executiei,sirul de atribuiri se poate scrie:
Vi(t+1)=ei(v1(t),..vl(t),c1,…,cp)	(2)
Cand se poate elimina t din relatiile (2) atunci vorbim de una sau mai ulte relatii intre variabilele v1,interpretate ca relatii functionale intre ele. Este posibila expriarea unora dintre variabilele v1,v2,..vk in functie de celelalte si atunci sistemul 2, impreuna cu vi e pot inlocui prin
Wi=fi(vq+1,…vk,c1,…,cp,w10,….wk0) (3) cu i=1..q, incare wi sunt cele q variabile ce au fost exprimate in functie de celalte,w10,…wk0 sunt valori intiale pt w1,..wk
Trecerea de la (1) la (3) pp parcurgerea cel putin o data a sist (1). Relatiile (3) au loc la sfarsitul oricarei executii ce contine sirul 1.Deci sunt 2 moduri de calcul al variabilelor vi care constau din:1)reluarea succesiva a sirului 1 atata timp cat sunt satisfacute conditiile pt reluarea ciclului;2)determinarea valorilor variabilelor vi cu ajutorul (3),folosind conditia de intrerupere a ciclului.
Ex:secv(x,y);z<-0,u<-y,while z<-z+x;u<-u-1;write z;instructiunil de atribuire din ciclul while se pot scrie astfel:z(t+1)=z(t)+x;u(t+1)=u(t)-1 cu solutia z(t)=z(t0)+x(t-t0);u(t)=u(t0)-(t-t0) in care t0 este mom inecperii ciclului. Elim. T-t0=>z(t)=z(t0)+x(u(t0)-u(t));not z(t)=z,u(t)=u;z(t0)=z0;u(t0)=u0=>z=z0+x(u0-u)(5).expr (5) este un invariant ak sitemului, deoarece e valabila pt orice t=>t0.cand u(t)=0, la incheierea parcurgerii ciclului z0=0,u0=y din (5)=>z=x*y.secventa data calculeaza produsul xy si e echivalenta cu read(x,y),z<-x*y,write z.concluzie:s-a verificat faptul ca prg initial calc intr-adevar prod xy;s-a transformat prg initial intr-unul mai concret(mai putin instructiuni).acest lucru a fost posibil deoarece s-a putut calcula invariantul dat de realtia (5).

25. Traiectoria asociata calculelor

Se considera un prg P in care apar variabilele vi,i=1..n si fie Di,i=1..n multimile in care pot lua val aceste var.var vi le putem asocia unui spatiu S=d1*..*Dn in care pct reprez coord celor n variabile.unui calcul concret efectuat in P ii corespunde o traiect T sau o mult de traiect.cunoasterea prop acestor trj ne poate ajuta sa fz inf imp pt corectitud calculelor.
Ex:x,y,w,v in N si prg de calcul al catului v si restului w din impartirea nr x>=0 si y>0
Procedure div(x,y,v,w);integer x,y,v,w;read x,y;v=0;w=x;while w>=y w=w-y;v=v+1;return;end. Variabilele v,w definesc un plan de coordonate (fig).pt x,y date se obs ca w scade succesiv cu val y,iar v creste succ cu 1.pct acestei trj sunt situate pe dreapta x=vy+w(8) – invariantul asociat calcului.din x>=0=>ultimei parcurgeri ii corespunde un pct F cu ord wF si abscisa vF. Cond:procedura div fz rez corecte, iar calc se termina intr-un nr finit de pasi. Pt a arata ca (8) este un invariant ,cele 2 atrib din ciclul while se vor transcrie sub forma:w(t+1)=w(t)-y;v(t+1)=v(t)+1.interpretate ca ec cu duferente vom avea:w(t)=w(t0)-y(t-t0);v(t)=v(t0)+(t-t0).Dc elim t-t0,w=x si v=0 la t0=>w(t)=x-v(t)y.dc facem abstractie de not se obt (8).Pt analiza unui prg sunt esentiale numai var care-si schimba val inproc efectuarii calculelor impreuna cu valorile lor initiale.fct de tip Manna:f(x)=x-1,x>=10 sau f(f(x+2)),x<10.Scrierea unui prg cu stiva pt a calcula val fct in orice pct este:proc manna(x,f)integer x,f;stacks;n=1;s(1)=x;do while s(n)<10;n=n+1;s(n)=s[n-1]+2;endwhile f=s[n]-1 if n==1 then return else n=n-1;s[n]=f;endif;enddo.dinintializari si ciclul wh se deduce ca pt x<10 s[n]=x+2(n-1)(9).relatia 9 este valabila pt prima parcurgere a cicllui.similar,dc urm parcurgeri au loc se va obt s[n]=s[n0]+2(n-n0).grafic trj sau pct respective vor urma un desen on zig-zag.pt x=2,f=9,dupa care secv if,dc n=1 atunci f=1,iar s[n]=f,in caz contrart n scade cu 1,iar s[n]=f=9.trj trece printr-o serie de pct A9n,s) si se incheie in pct final de coord (1,10)cu f(2)=9.in mod similar pt orice x<10=>dc x<10 f=9.
Metoda de analiza bazat pe reprez grafica are dezanvatajul ca atunci cand nr de variabile este >2,reprez gf devine greu de efectuat.in astfel de situatii se vor cauta alte metod ce utilizeaza th de corectitudine partiala sau totala ale uni prg.

26. Semnificatia logica a programelor

Pp urmatoarele:1)pp ca prg sunt bine structurate in enunturi if-then-else,while si atribuiri.2)prg e impartit in blocuri sau secvente de instructiuni.3)la incep si sf prg,in pct de concatenare a bloc avem specificatii prin expresii logice care sunt satisfacute de variabilele prg.4)bloc le not cu litera cursiva urmata eventual de indici. 
Cu ac pp dem th de corectit partiala.consta in a arata ca dc propr specificate la incep prg sunt adev,atunci sunt adev toate prop specificate in pct de concatenare a blocurilor cat si cele de la sf de prg.EX:procedure suma(x0,y0,y){x,y naturale}x=x0;y=y0{x+y=x0+y0}while x<>0 x=x-1;y=y+! endwhile {y=x0+y0} return. Prima specificatie mentioneaza explicit ca val x,y sunt naturale.a doua specificatie este adev deoarece sunt indeplinite prop de adunare in multimea nr nat si tinand cont si de atrib precedente. Specific tb interpretata si ca invariant pt ciclul while:cat timp x<>0, fapt ce rezulta imediat obs ca:x+y=(x-1)+(y+1)=x0+y0.ult specifcatie arata ca in mom incheierii ciclului cand x=0,val lui y este y=x0+y0 adica tocmai suma nr x0 si y. Ac dem este neformala si corect ei poate fi pusa la indoiala;de aceea vom cauta sa fol reg de deducere sau inferenta similare cu cele din logica matematica. Metodologia es bazeaza pe analiza instructiune cu instructiune a txt prg.este vorba de atrib de deicizie if si iterativa while,repeat, for. O secv de instruct A va fi precedata de un comentariu P care descrie propr datelor de intrare si va fi urmata de un comentariu Q ce descrie propr datelor de iesire.Ac prop P va fi numita prop initial sau precondiie iar Q propr final sau postconditie. {P}A{Q} – formula de corect totala.

27. Corectitudinea instructiunilor repetitive

In pascal avem o structura de genul {P} A while c do s {Q} cu semnificatia urmatoare – daca inainte de executia lui A date din program satisfac proprietatea descrisa in campul P atunci urm afirmatii sunt adevarate – la terminarea instr while datele prof satisfac propr descrisa in Q si instr din A se termina intr-un interval finit de timp. In aceasta situatie se spune ca instr de mai sus sunt corecte iar fiecare executie a lor se numeste iteratie. Pentru dem corectitudinii se va utiliza regula de dem a corect instr while.
Regula de corectitudine se enunta – fie o prop i si o fct t cu valori intregi. Se considera ipotezele:
0) i adev atunci c e bine def; 1) {P}A{I} corecta; 2) din i si not c => Q adica Q poate fi dedusa; 3) {I and c}S{I} corecta adica I este invarianta la efectuarea unei iteratii; 4) Dc I, c adv => t>=1 adica se mai face o iteratie => t este o marg superioara a nr de iteratii ce se vor efectua; 5) valuarea lui t descreste cel putin cu o unitate la fiecare iteratie.
Daca cele 6 sunt adevarate atunci {P} A while c do s {Q} sunt corecte.

28. Terminarea programelor

Daca un program P se incheie dupa un anumit numar de pasi este evident ca traiectoriile corespunzatoare T din spatiul S asociat prg P sunt constituite din succesiuni finite de puncte. Pt dem terminarii lui P folosim multimea bine aleasa – care este o multime partial ordonata in care orice sir descrescator al ei este finit. Dupa ce gasim multimea trebuie sa gasim functia t: S->M care sa aplice punctele traiectoriilor T din S in siruri descrescatoare din M. Daca nu gasim t putem pune pb dem faptului ca programul nu se va incheia – pt asta tb sa aratam ca prg contine cel putin un bloc while a carui parcurgere nu se incheie. Pt dem terminarii unui progr se poate folosi si metoda grafica.

29. Transformarea programelor

Identif functie calculate de un program este facilitate de cunoasterea invarianilor asociati diferitelor blocuri din program. Ca atare, un program poate fi inlocuit prin altul ce furnizeaza acelasi rezultat dar are un cod mai clar si / sau concentrat. Consideram functia Manna f(x)=x-1 pt x>=10 si f(x)=f(f(x+2) pentru x<10. Pornim de la n=1 si gamma(1)<-x. Urmarind bucla unde x este mai mic ca 10 se deduce ca pentru x<10 valoareea lui gamma(n)=x+2(n-1) care este invariantul asociat blocului while.
Pentru x par si x<10 la parasirea buclei avem gamma(n)=10 deci n=6-x/2>=2. Rezulta dupa mai multe parcurgeri ale ambelor bucle ca pentru x<10 par valoarea functiei este f(x)=9.
Pentru x impar si x<10 o sa avem f(x)=9.
Pentru orice x>=10 se obtine usor ca f(x)=x-1.
In concluzie functia f(x) calculata are valoareea x-1 pt x>=10 si 9 pentru x<10.
Totusi nu orice functie data initial se poate transforma intr-una care sa contina numai expresii elementare.

30. Utilizarea invariatiilor

Cunoasterea invariantilor rep un avantaj in verif si transf prog. Exemplu – programul care face impartirea – x=q*y+r si relatia echivalenta x=(q+1)y+r-y. Avem qy+r=x un invariant. Mai exact daca q si r sunt functii de tip t de forma q=q0+t si r=r0-yt atunci avem qy+r=q0y+r0=x. Rezulta ca valorile lui q si r se pot calcula astfel – incepand cu q=0 si r=a se creste succesiv q cu 1 si se scade y din r pana cand r devine mai mic decat y. Secv de program va fi q<-0; r<-x; while r>=y q<-q+1, r<-r-y endwhile iar invariantul blocului while este qy+r=x.