Algoritmi

Rezolvarea unei probleme cu ajutorul calculatorului implica parcurgerea urmatoarelor etape preliminare:

problema sa fie pusa sub forma matematica, iar datele de intrare sa fie puse sub forma numerica:

precizarea valorilor datelor de intrare si de iesire;

intocmirea schemei logice pentru a descrie grafic algoritmul ales. Sau descrierea algoritmului in limbaj pseudocod:

scrierea programului intr-un limbaj de programare, corectarea erorilor de sintaxa si verificarea corectitudinii rezultatului.

Un algoritm este compus dintr-o multime de pasi, fiecare necesitand una sau mai multe operatii. Operatiile care apar in cadrul unui algoritm sunt:

operatii de intrare-iesire:

datele de intrare se citesc (de la tastatura si /sau din fisiere) si ele reprezinta valorile initiale de la care se incepe rezolvarea problemei

datele de iesire reprezinta rezultatul problemei obtinut dupa parcurgerea algoritmului si se afiseaza (pe ecran si / sau in fisiere).

operatii de atribuire: reprezinta acele operatii in urma carora valoarea unei expresii (aritmetice, logice sau relationale) este pastrata intr-o variabila.

operatii de decizie: se determina valoarea de adevar a unei expresii logice si in functie de rezultatul obtinut se continua executia programului pe una din ramificatii.

Programarea structurata folosita in elaborarea algoritmilor presupune folosirea unui numar mic de structuri elementare avand fiecare o singura intrare si o singura iesire din structura. Astfel, orice algoritm apare ca o secventa liniara de structuri elementare. Structurile elementare sunt:

structura liniara: consta in executia neconditionata a unei secvente de instructiuni;

structura alternativa: ramifica executia programului in functie de valoarea de adevar a conditiei evaluate;

structura repetitiva: consta in executia repetata, dar finita, a unei secvente de instructiuni in functie de indeplinirea sau nu a unei conditii.

Proiectarea algoritmului consta in doua etape:

v    Descrierea algoritmului intr-un pseudo-limbaj. Algoritmii pot fi reprezentati prin mai multe metode: pseudocod, scheme logice, diagrame etc.

v    Demonstrarea corectitudinii rezultatelor in raport cu datele de intrare Dupa elaborarea si reprezentarea sa, un algoritm trebuie sa fie validat (sa i se verifice corectitudinea) pentru a ne asigura ca el functioneaza corect, indiferent in ce limbaj de programare va fi implementat.

Analiza algoritmului

Pentru o anumita problema pot fi elaborati mai multi algoritmi. Pentru a putea sa, decidem care dintre ei este cel mai bun, este nevoie sa definim un criteriu de apreciere a performantei unui algoritm. In general, acest criteriu se refera la timpul de calcul si la memoria necesara unui algoritm.

La analiza algoritmului trebuie avut in vedere modelul de implementare (serial vs. paralel) si arhitectura masinii de calcul (superscalar, multithread, multicore) respectiv daca aceasta permite sau nu executia speculativa a instructiunilor.

Complexitatea unui algoritm, exprimata prin notatii asimptotice (Q O W) in functie de dimensiunea datelor de intrare (n), are urmatoarele componente:

v    Complexitatea temporala (indicatorul principal al performantei unui algoritm) - numarul de operatii necesare pentru rezolvarea unei probleme. Poate fi determinat experimental prin masurarea timpului de executie sau prin analiza teoretica prin estimarea numarului de operatii primitive.

v    Complexitatea spatiala - spatiul de memorie utilizat.

Elaborarea programelor Un algoritm corect, de obicei, este implementat intr-un limbaj de programare, pentru a fi utilizat pe calculator

Testarea programelor Acest aspect consta din doua faze: depanare si trasare (in vederea optimizarii).

Depanarea (debugging) este procesul ce consta in executare a programului pe date de test si corectarea eventualelor erori. Prin depanare, asa cum afirma E. W. Dijkstra, putem evidentia doar prezenta erorilor dar nu si absenta lor. In schimb, demonstrarea faptului ca un program este corect este mult mai valoroasa decat o mie de teste deoarece prin demonstratie se poate garanta ca programul functioneaza corect in orice situatie.

Trasarea (profiling), este procesul de executie a unui program corect pe diferite date de test (bine alese) cu scopul de a determina timpul de calcul si memoria necesara (zonele de program care dureaza cel mai mult). Rezultatele obtinute in aceasta etapa se pot compara, dupa aceea, cu rezultatele obtinute in etapa de analiza a algoritmului.

Scheme logice

Schema logica este un mijloc de descriere a algoritmilor prin reprezentare grafica. Regulile de calcul ale algoritmului sunt descrise prin blocuri (figuri geometrice) reprezentand operatiile (pasii) algoritmului, iar ordinea lor de aplicare (succesiunea operatiilor) este indicata prin sageti. Fiecarui tip de operatie ii este consacrata o figura geometrica (un bloc tip) in interiorul careia se va inscrie operatia din pasul respectiv.

Prin executia unui algoritm descris printr-o schema logica se intelege efectuarea tuturor operatiilor precizate prin blocurile schemei logice, in ordinea indicata de sageti.

In descrierea unui algoritm, deci si intr-o schema logica, intervin variabile care marcheaza atat datele cunoscute initial, cat si rezultatele dorite, precum si alte rezultate intermediare necesare in rezolvarea problemei. Intrucat variabila joaca un rol central in programare este bine sa definim acest concept.

Variabila defineste o marime care isi poate schimba valoarea in timp.

are un nume si, eventual, o valoare. Este posibil ca variabila inca sa nu fi primit valoare, situatie in care vom spune ca ea este neinitializata. Valorile pe care le poate lua variabila apartin unei multimi D pe care o vom numi domeniul variabilei.

Blocurile delimitatoare Start si Stop vor marca inceputul respectiv sfarsitul unui algoritm dat printr-o schema logica. Descrierea unui algoritm prin schema logica va incepe cu un singur bloc Start si se va termina cu cel putin un bloc Stop.

Blocurile de intrare/iesire Citeste si Tipareste indica introducerea unor Date de intrare respectiv extragerea unor Rezultate finale. Blocul Citeste initializeaza variabilele din lista de intrare cu valori corespunzatoare, iar blocul Tipareste va preciza rezultatele obtinute.

Blocurile de atribuire (calcul) se utilizeaza in descrierea operatiilor de atribuire (:=). Printr-o astfel de operatie, unei variabile var i se atribuie valoarea calculata a unei expresii expr.

Blocurile schemelor logice

Blocurile de decizie marcheaza punctele de ramificatie ale algoritmului in etapa de decizie. Ramificarea poate fi dubla (blocul logic) sau tripla (blocul aritmetic). Blocul de decizie logic indica ramura pe care se va continua executia algoritmului in functie de indeplinirea (ramura Da) sau neindeplinirea (ramura Nu) unei conditii. Conditia care se va inscrie in blocul de decizie logic va fi o expresie logica a carei valoare poate fi una dintre valorile 'adevarat' sau 'fals'. Blocul de decizie aritmetic va hotari ramura de continuare a algoritmului in functie de semnul valorii expresiei aritmetice inscrise in acest bloc, care poate fi negativa, nula sau pozitiva.

Blocurile de conectare marcheaza intreruperile sagetilor de legatura dintre blocuri, daca din diverse motive s-au efectuat astfel de intreruperi.

P1. Sa se rezolve ecuatia de grad doi aX²+bX+c=0 (a,b,cIR si a

Algoritmul de rezolvare a problemei va citi mai intai datele problemei, marcate prin variabilele a, b si c. Se va calcula apoi discriminantul d (d = b² - 4ac) si va continua in functie de valoarea lui d.

Algoritm pentru rezolvarea ecuatiei de gradul doi

ALGORITMUL ECGRDOI ESTE:

CITESTE a,b,c;

FIE delta:=b*b‑4*a*c;

DACA delta<0 ATUNCI ind:=0;

r:=radical din (‑delta);

x1:=‑b/(a+a);

x2:=r/(a+a);

ALTFEL ind:=1;

r:=radical din delta;

x1:=(‑b‑r)/(a+a);

x2:=(‑b+r)/(a+a);

SFDACA

TIPARESTE ind, x1,x2;

SFALGORITM

P2. Sa se calculeze suma elementelor pozitive ale unui sir de numere reale dat.

Schema logica va contine imediat dupa blocul START un bloc de citire, care precizeaza datele cunoscute in problema, apoi o parte care calculeaza suma ceruta si un bloc de tiparire a sumei gasite, inaintea blocului STOP. Partea care calculeaza suma S ceruta are un bloc pentru initializarea cu 0 a acestei sume, apoi blocuri pentru parcurgerea numerelor: x₁, x_2.x_n si adunarea celor pozitive la suma S. Pentru aceasta parcurgere se foloseste o variabila contor i, care este initializata cu 1 si creste mereu cu 1 pentru a atinge valoarea n, indicele ultimului numar dat.

Algoritm pentru calculul unei sume.

ALGORITMUL MAXMIN ESTE:

CITESTE n,(x_i,i=1,n);

FIE valmin:=x₁; valmax:=x₁;

PENTRU i:=2,n EXECUTA

DACA x_i<valmin ATUNCI valmin:=x_i SFDACA

DACA x_i>valmax ATUNCI valmax:=x_i SFDACA

SFPENTRU

TIPARESTE valmin,valmax;

SFALGORITM