Analiza algoritmilor

ANALIZA ALGORITMILOR

O anumita problema poate fi rezolvata cu ajutorul calculatorului numai daca se gaseste un algoritm pentru rezolvarea ei, care este dat calculatorului sub forma unui program. Intrucat toate problemele practice pe care le intalnim se pot rezolva cu ajutorul calculatorului, s-ar putea crede ca orice problema este rezolvabila. Aceasta afirmatie este insa falsa. Se stie ca nu exista un program care sa rezolve 'problema terminarii programelor':

'Scrieti un program care sa decida daca un algoritm oarecare, dat, intra sau nu intr-un ciclu infinit'.

Chiar si problemele pentru care exista algoritmi corespunzatori nu sunt neaparat rezolvabile cu calculatorul. Este posibil ca timpul necesar executiei acestor algoritmi, sau cantitatea de memorie necesara, sa nu permita folosirea lor in practica.

Evident, daca spatiul de memorie necesar programului este mai mare decat cantitatea de memorie disponibila, programul nu poate fi executat. De asemenea, daca numarul calculelor ce trebuie efectuat este foarte mare, programul poate fi inutil. Iar asta se poate intampla destul de usor in cazul problemelor ce trebuiesc rezolvate in timp real (adica solutia trebuie obtinuta inaintea unui timp critic).

Iata cateva motive pentru care este necesar sa analizam algoritmii pe care-i concepem pentru rezolvarea unei probleme.

Ne intereseaza sa analizam un program din mai multe puncte de vedere:

1) Corectitudine;

2) Eficienta;

3) Posibilitate de imbunatatire;

4) Alte calitati pe care le are.

1 Corectitudinea programelor

Un program este corect daca el satisface specificatiile problemei. Nu ne intereseaza cata memorie foloseste acest program, din cate instructiuni este compus, sau cat timp de executie necesita. Cu alte cuvinte, un program este corect daca pentru acele date de intrare care satisfac specificatiile problemei rezultatele obtinute in urma executiei sunt corecte.

Pentru orice program P deosebim trei tipuri de variabile, pe care le vom grupa in trei vectori X, Y si Z. Componentele vectorului X desemneaza variabilele de intrare, deci datele presupuse cunoscute in problema rezolvata prin programul P. Componentele vectorului Z sunt variabilele care reprezinta rezultatele cerute de problema. In sfarsit, componentele vectorului Y sunt variabilele de lucru, care noteaza diferitele rezultate intermediare necesare in program.

O problema nu are sens pentru orice date de intrare. Vom folosi predicatul Ř(X) pentru a preciza datele pentru care problema are sens. R(X) se numeste predicat de intrare sau preconditie. Pentru acele valori ale lui X pentru care predicatul este adevarat problema are sens, pentru celelalte nu are sens sa executam programul P.

Intre rezultatele Z ale problemei si datele initiale X (cunoscute in problema) exista anumite relatii. Vom reda aceste relatii prin predicatul de iesire R(X,Z), numit si postconditie. Acesta este corect pentru acele valori a si b ale vectorilor X si Z pentru care rezultatele problemei sunt b in cazul cand datele initiale sunt a si este fals in caz contrar. Deci, daca executand programul cu datele initiale a obtinem rezultatele b' si R(a,b') este fals, acest fapt este un indiciu ca rezultatele obtinute in program nu sunt corecte. Apare o alta regula : fiecare variabila sa aiba semnificatia ei si sa nu fie folosita in scopuri diferite.

2 Testarea si depanarea programelor

Testarea programelor este activitatea prin care programatorul observa comportarea programului in urma executiei lui cu date de test. Evident, primul lucru urmarit este corectitudinea rezultatelor obtinute in urma executiei programului cu datele de test folosite. Dar se va urmari si daca programul are alte caracteristici ca: utilitate, siguranta in functionare, robustete, performanta. Este beneficiarul multumit de rezultatele care se obtin si de forma sub care sunt prezentate? Sunt ele obtinute in timp util?

Datele de test sunt date de intrare alese pentru variabilele de intrare pentru care se cunosc rezultatele, sau avem unele informatii despre rezultate. Executand programul cu aceste date ar trebui sa ajungem la rezultatele cunoscute.

Corectitudinea rezultatelor in aceste executii nu demonstreaza corectitudinea programului in general. Testarea insa pune adeseori in evidenta erori facute in diferite faze ale programarii. In privinta aceasta dam un citat din Dijkstra: Testarea programelor poate fi un mijloc eficient de a indica prezenta erorilor, dar din pacate, nu si un mijloc de a demonstra absenta lor.

Cu toate ca ea nu demonstreaza corectitudinea programului, testarea mareste certitudinea corectitudinii lui si este deocamdata singura metoda practica de certificare a programului. Ar fi de dorit demonstrarea apriori a corectitudinii programului, dar rezultatele cunoscute in prezent in aceasta directie nu sunt aplicabile programelor complexe.

Scopul testarii programelor este depistarea si eliminarea erorilor. Acest lucru este facut prin executia programului cu date de test pentru care se cunosc dinainte rezultatele (sau cel putin se stie ceva despre ele) si se observa rezultatele obtinute in urma executiei. In cazul in care rezultatele obtinute in urma executiei nu sunt cele asteptate se vor cauta si elimina erorile. Activitatea care urmareste descoperirea cauzelor erorilor si inlaturarea lor se numeste depanare.

Se pune problema alegerii datelor de test si a numarului de executii ce trebuie facute pentru a putea considera ca programul nu are erori. Numarul tuturor seturilor de date de intrare posibile este teoretic infinit chiar si pentru probleme simple. Deci nu poate fi vorba de o testare exhaustiva. Stabilirea datelor de test se poate face cel putin pe doua cai:

- tinand seama de specificatia problemei;

- tinand seama de textul programului.

Asa cum va rezulta din cele ce urmeaza, cea mai buna cale este una mixta, in care sunt combinate aceste doua posibilitati.

La testarea dupa specificatia problemei, stabilirea datelor de test se face analizand specificatia problemei. Se recomanda stabilirea datelor de test tinand seama de specificatia asupra datelor de intrare si de specificatia asupra datelor de iesire. Aceasta metoda de testare este adecvata problemelor simple. In cazul unei probleme complexe aplicarea ei este imposibila datorita numarului foarte mare de cazuri posibile, care ar trebui testate. Insa problema noastra a fost descompusa in subprobleme mai mici, invizibile in specificatie si a caror testare este mai simpla. Privind programul ca o cutie neagra nu vom mai tine seama de aceste subprobleme. Totusi, testarea dupa specificatia problemei ramane o metoda utila in testarea modulelor.

Testarea dupa textul programului tine seama, pentru a stabili datele de test, de instructiunile care trebuiesc executate. Considerand ca algoritmul este descris printr-o schema logica, o executie a programului inseamna parcurgerea unui drum de la START la STOP in aceasta schema. Daca la aceasta executie rezultatele obtinute sunt corecte probabil ca textul algoritmului pe acest drum este corect. Ar trebui sa verificam toate blocurile schemei logice si mai ales toate drumurile de la START la STOP posibile. Cu observatia ca in cazul a doua drumuri ce difera doar prin faptul ca o anumita bucla se executa de n₁, respectiv n₂ ori le vom considera echivalente intre ele. Dintre toate drumurile echivalente intre ele vom testa un singur drum, altfel am avea o infinitate de drumuri de testat.

In concluzie vom alege pentru fiecare drum un set de date de test, numarul executiilor fiind egal cu numarul acestor drumuri. Daca toate executiile au dat rezultate corecte programul se considera testat. Daca insa la o singura executie am depistat erori, corectarea lor a modificat textul algoritmului si testarea trebuie reluata pe toate drumurile afectate de aceasta schimbare.

Pentru un program complex, deci pentru o schema logica cu un numar foarte mare de drumuri START-STOP, testarea ar fi o activitate complexa, constand dintr-un numar foarte mare de executii. Inca un motiv pentru a practica programarea modulara, caz in care testarea se face asupra unor module mai mici si asupra interfetei dintre ele, asa cum se va mentiona mai jos.

Stabilirea datelor de test dupa textul programului are si unele dezavantaje. In primul rand, programul poate fi incomplet si sa nu corespunda specificatiilor. Pe drumurile existente el este corect, dar lipsesc drumuri care, conform specificatiilor, ar trebui sa existe. Lipsa acestor drumuri este o greseala grava care nu va fi descoperita de datele de test care ne duc doar pe drumurile existente. Din aceasta cauza se recomanda o testare mixta.

In textul unui program exista si drumuri moarte, pe care nu se poate merge oricare ar fi datele de intrare, deci nu putem gasi date de test corespunzatoare acestor drumuri. Adeseori aceste drumuri scot in evidenta erori prin simpla analiza a textului. Astfel, in succesiunea de propozitii Pseudocod

DACa n<2 ATUNCI

. . .

DACa n>3 ATUNCI A SFDACa

. . .

SFDACa

grupul A este inaccesibil oricare ar fi valoarea lui n. Este insa foarte frecventa eroarea de omisiune a unui caracter; in cazul nostru tastarea numarului 2 in loc de 20, ceea ce schimba complet sensul textului Pseudocod de mai sus.

Adesea este imposibil sa se execute programul cu toate datele de test stabilite. In acest caz apare problema alegerii acelei submultimi din aceste date care sa aiba sansa maxima de a depista erorile prezente in program. Testarea minima care trebuie facuta consta intr-un numar de executii a programului care sa ne asigure ca fiecare instructiune din program a fost executata cel putin odata. Ea inseamna mult mai putine executii decat toate drumurile START-STOP.

Exista date de test care ne duc pe un anumit drum fara a depista erori existente in instructiunile intalnite si alte date de test care depisteaza aceste erori. Inca un motiv pentru care se recomanda o testare mixta.

Ca ordine de folosire a datelor de test in timpul testarii, se recomanda mai intai testarea dupa specificatii si apoi testarea dupa textul programului.

Este necesara si testarea robustetei programului, care inseamna buna lui comportare la date de intrare intentionat gresite, pentru care problema nu are sens. Unele programe intra in aceste conditii in ciclu infinit, altele se termina cu erori de executie. Un program robust nu trebuie sa fie afectat de datele de intrare eronate. Comportarea cea mai normala in astfel de situatii ar fi semnalarea unor mesaje de eroare corespunzatoare.

La un produs program complex testarea este o activitate mult mai complicata. Este necesara o testare separata a fiecarui modul in parte, o testare a interfetei dintre module si o testare a produsului in ansamblu (testarea de integrare).

Testarea de integrare se refera la functionarea programului realizat in ansamblu. Dupa ce fiecare modul in parte a fost testat si corectat, deci in ipoteza ca fiecare modul in parte este corect, e necesar sa se verifice comportarea globala a programului. In aceasta etapa gasirea erorilor, inlaturarea cauzelor care le-a generat si corectarea lor, poate fi

foarte dificila, mai ales atunci cand ele provin dintr-o proiectare gresita.

Executia unui program se poate termina anormal datorita aparitiei unor erori ca:

- impartiri la zero;

- alte erori ce provoaca depasiri;

- neconcordanta intre parametri actuali si formali;

- depasirea dimensiunii tablourilor.

Dar chiar si la executia normala a programului putem avea erori, unele foarte grave, obtinand rezultate gresite. In ambele situatii urmeaza depanarea programului, adica descoperirea cauzei erorilor si inlaturarea lor.

O metoda utila in depanarea programelor, in special pentru incepatori, este inserarea in program a unor tipariri auxiliare. Mai ales in locurile vecine cu instructiunile care au provocat eroarea si pentru variabilele implicate in producerea ei. Observarea valorilor unei variabile, a schimbarilor facute in timpul executiei, pot dezvalui programatorului cauza erorii. Cu siguranta ii va arata ca o anumita variabila ia alte valori decat cele la care se asteapta el. De altfel, pe timpul testarii unui program, sunt utile semnalarile oricaror semne de eroare. Recomandam verificarea valorilor variabilelor imediat dupa obtinerea acestora.

3 Complexitatea algoritmilor

In aceasta sectiune ne va interesa eficienta unui algoritm. Mai exact, ne intereseaza sa comparam intre ei mai multi algoritmi care rezolva aceeasi problema. Care dintre ei este mai bun? Evident, vom compara numai algoritmi despre care stim ca sunt corecti.

Putem compara doi algoritmi in raport cu:

- cantitatea de memorie necesara;

- viteza de lucru, deci timpul necesar rezolvarii problemei.

Daca in urma cu doua decenii volumul de memorie necesar rezolvarii unei probleme era un factor important din cauza memoriei reduse existente la calculatoarele din acel timp, astazi acest factor a devenit mai putin important. Calculatoarele actuale au memorie suficient de mare pentru marea majoritate a algoritmilor intalniti.

Timpul necesar executiei unui program depinde de numarul operatiilor ce trebuiesc executate. Iar numarul operatiilor efectuate depinde de datele de intrare, deci se schimba de la o executie la alta.

Exista insa un cel mai rau caz, pentru acele date de intrare pentru care numarul operatiilor efectuate este maxim. In acest caz vorbim de complexitate in cel mai rau caz.

De asemenea, putem vorbi de numarul mediu de operatii efectuate intr-o executie. Daca numarul executiilor posibile este finit atunci acest numar mediu este egal cu numarul operatiilor efectuate in toate executiile, impartit la numarul executiilor. Sunt insa foarte putine programe cu aceasta proprietate. Pentru aproape toate programele, cel putin teoretic, numarul executiilor posibile este infinit.

4 Documentarea programelor

In paralel cu elaborarea programului trebuie elaborata si o documentatie. Aceasta va contine toate deciziile luate in crearea programului. Documentarea este activitatea de prezentare a programului celor care vor fi interesati sa obtina informatii despre el. Acestia sunt in primul rand persoanele care au realizat programul, apoi persoanele care-l vor folosi si persoanele solicitate sa faca intretinerea acestuia.

Adeseori se intalnesc programe fara nici o alta documentatie in afara textului propriu-zis al programului. In graba de a termina cat mai repede, programul nu este insotit de nici o documentatie si frecvent nu sunt folosite nici comentarii in textul programului.

Sigur ca insasi textul programului constituie o autodocumentare. Iar comentariile prezente in program dau explicatii suplimentare despre program. Este insa necesara o documentatie completa, scrisa, care va contine:

- enuntul initial al problemei;

- specificatia (vezi sectiunea 1);

- documentatia de proiectare (metoda de rezolvare aleasa si proiectarea algoritmilor folositi. Pentru fiecare algoritm va fi prezentata subproblema corespunzatoare, cu specificatia ei si rolul fiecarei variabile);

- documentatia de programare, care va include textul programului;

- datele de test folosite;

- documentatie privind exploatarea programului;

- modificari facute in timpul intretinerii programului.

Mentionam ca cele mai recente produse realizate de firmele consacrate au, pe langa documentatia scrisa, si o autodocumentatie (functii HELP).

Referitor la autodocumentare, folosirea comentariilor, alegerea cu grija a denumirii variabilelor, cat si claritatea textului, obtinuta prin indentare si grija asupra structurii programului, este utila nu numai pe timpul elaborarii programului, dar mai ales pe timpul intretinerii si modificarilor ulterioare.

Denumirea variabilei sa fie astfel aleasa incat sa redea cat mai bine semnificatia ei.

Cei care au dorit sa refoloseasca programe scrise cu cateva luni in urma inteleg foarte bine diferenta dintre un program insotit de comentarii explicative si un program fara nici o explicatie. Uitarea actioneaza asupra oricarei persoane si, chiar daca este posibila, descifrarea unui program cere timp si nu este o sarcina prea usoara. Comentariile sunt recomandate, fiind un mijloc de autodocumentare a programului sursa.

Sigur ca prima documentatie a oricarui program este textul sursa propriu-zis. Este bine ca acest text sa poata fi citit cat mai usor, iar programarea structurata duce la un program mai usor de citit decat unul lipsit de orice structura.

Este insa nevoie si de o documentatie insotitoare scrisa, care constituie documentarea propriu-zisa a programului. Aceasta trebuie sa redea toate deciziile facute in timpul proiectarii, sa prezinte diagrama de structura a intregului produs si fiecare parte separat. Pentru fiecare modul documentatia va contine:

- numele acestuia;

- datele de intrare;

- datele de iesire;

- functia realizata de modulul respectiv;

- variabilele folosite si semnificatia lor;

- algoritmul propriu-zis.

Este necesar ca aceste informatii sa se afle si sub forma unor comentarii in textul programului. De asemenea, documentatia va contine si textul final al programului.

Este necesara si o documentatie de folosire a produsului realizat. Beneficiarul nu este interesat de modul in care a fost realizat programul ci de modul in care il poate folosi.

O documentare completa a unui program poate fi utila nu numai pentru folosirea si intretinerea programului. Componente ale unui produs existent pot fi utile si in realizarea altor produse. Este insa necesar sa se inteleaga cat mai usor ce functii realizeaza aceste componente si cu ce performante. Folosirea acestor componente existente, testate si documentate, duce evident la cresterea productivitatii in realizarea noului produs.

5 Stil in programare

Fiecare programator are stilul sa propriu de concepere si redactare a unui program. Este bine ca el sa respecte anumite reguli generale de programare, astfel incat programele elaborate sa aiba anumite calitati.

Calitatile pe care le poate avea un program sunt urmatoarele:

Corectitudine = proprietatea programului de a respecta specificatiile si a da rezultate corecte;

Extensibilitate = posibilitatea adaptarii programului la unele schimbari in specificatie;

Robustete = abilitatea de a recunoaste situatiile in care problema ce se rezolva nu are sens si de a se comporta in consecinta (de exemplu, prin mesaje de eroare corespunzatoare);

Reutilizabilitate = posibilitatea reutilizarii intregului program sau a unor parti din el in alte aplicatii;

Compatibilitate = usurinta de combinare cu alte produse program;

Portabilitate = posibilitatea de folosire a produsului program pe alte sisteme de calcul, diferite de cel pe care a fost conceput;

Eficienta = masura in care sunt bine folosite resursele sistemului de calcul;

Claritate = usurinta citirii si intelegerii textului programului, a structurilor din care este compus si a rolului denumirilor si partilor sale.

Un produs program este considerat de calitate daca are calitatile de mai sus, daca lansat in executie da rezultate corecte, daca textul lui se poate citi si intelege, daca poate fi usor intretinut si daca este terminat la data fixata.

Stilul unui programator este dat de masura in care programul sau are aceste calitati si de vizibilitatea lor. Evident, pe langa aceste calitati, vizibile si in text, stilul de programare este dat si de corectitudinea si robustetea produselor realizate. Programul trebuie sa functioneze si la introducerea unor date gresite (pentru care problema nu are sens), recunoscand aceasta situatie si semnaland-o. In acelasi timp rezultatele obtinute pentru date pentru care problema are sens trebuie sa fie corecte. Iar corectitudinea sau incorectitudinea programului este o consecinta a modului in care programatorul a respectat regulile de programare (vezi capitolul 8) si a experientei obtinute in activitatea de programare.

Privind claritatea algoritmului trebuie sa observam ca indentarea (paragrafarea) este un alt mijloc de a mari claritatea scrierii. Textul unui algoritm poate fi scris cuvant dupa cuvant, completand tot randul asemeni textului unui roman. Claritatea lui este mica, dupa cum urmeaza:

PROGRAMUL CLASAMENT ESTE: DATE m,n,NUME_i, i=1,n, NOTE_i,j, j=1,m, i=1,n; PENTRU i:=1,n EXECUTA FIE S:=0; PENTRU j:=1,m EXECUTA S:=S+NOTE_i,j SFPENTRU FIE MEDII_i:=S/M SFPENTRU PENTRU j:=1,m EXECUTA CHEAMA ORDINE(n,NOTE_j,O); CHEAMA TIPAR(n, NUME, O) SFPENTRU CHEAMA ORDINE(n,MEDII,O); CHEAMA TIPAR(n,NUME,O) SFALGORITM

Consideram ca fiecare programator trebuie sa respecte anumite reguli de scriere a programelor, cu gandul la claritatea textului. In unele carti sunt date mai multe reguli de indentare. Astfel, Gries sugereaza urmatoarele reguli:

- instructiunile unei secvente se vor scrie aliniate, incepand toate in aceeasi coloana;

- instructiunile unei structuri de calcul (instructiuni compuse) se vor scrie incepand toate din aceeasi coloana, aflata cu 2-4 caractere la dreapta fata de inceputul instructiunii compuse;

- pe o linie pot fi scrise mai multe instructiuni, cu conditia ca ele sa aiba ceva comun. Astfel, 2-4 instructiuni scurte de atribuire pot fi scrise pe acelasi rand. Acest lucru se recomanda in vederea unei scrieri compacte a programului. E bine ca un program ce se poate scrie pe o pagina, cu respectarea structurii lui, sa nu fie intins pe doua pagini !

Consideram ca nu exista reguli de scriere obligatorii pentru toata lumea! Dar fiecare programator trebuie sa aiba propriile lui reguli de scriere.

Tot privind claritatea scrierii programului, se recomanda ca denumirile variabilelor sa fie astfel alese incat sa reflecte semnificatia acestor variabile.

Un alt mijloc de a mari claritatea textului unui program consta in inserarea comentariilor in text. Comentariile sunt texte explicative inchise intre acolade. Ele au rolul de a explica cititorului anumite parti din program. Am spus deja ca in proiectarea algoritmilor folosim si propozitii nestandard care vor fi pe parcurs inlocuite cu propozitii standard. E bine ca aceste propozitii sa ramana in text sub forma de comentarii.

Comentariile vor fi prezente:

in capul programului, pentru a prezenta titlul si scopul programului, perioada realizarii lui si numele programatorului;

- in definitii, pentru a descrie semnificatia notatiilor folosite (a variabilelor, constantelor, subalgoritmilor etc);

- in dreapta unor instructiuni, pentru a descrie rolul acestora, sau cazul in care se atinge    acea instructiune;

- intre partile unui modul mai lung, pentru a explica rolul fiecarei parti.

Speram ca prin exemplele date in acest material am prezentat un stil propriu de programare si am convins cititorul de necesitatea formarii propriului sau stil.