Evaluarea corectitudinii algoritmilor

Evaluarea corectitudinii algoritmilor

Un program realizat trebuie sa fie corect, clar, sigur in functionare, usor de modificat, portabil, eficient, insotit de o documentatie corespunzatoare. Exista numeroase tehnici de verificare si validare a algoritmilor, adresate in general practicienilor, dar si usor accesibile unui incepator in programare.

Dintre acestea amintim:

testarea programelor si depanarea programelor

verificarea formalizata a programelor

cea mai slaba preconditie

cea mai tare postconditie

instructiuni generalizate

sintaxa expresiilor logice

Actiunea de testare a programelor se deosebeste de celelalte faze prin care trec acestea (proiectare, programare, documentatie, etc.) prin caracterul ei in aparenta "demolator". Astfel, in timp ce alte faze au o esenta constructiva, testarea are in aparenta un caracter distructiv, deoarece scopul ei este de a pune in evidenta proasta functionare a programului, de a gasi hibele aeestuia si nu partile sale bune. Din punct de vedere psihologic, programatorul insusi trebuie sa adopte in aceasta etapa 0 atitudine "dusmanoasa" fata de propriul program, pentru a putea gasi defectele acestuia,

Analizand problema mai atent, realizam de fapt ca scopul testarii este in realitate tot constructiv, acela de a pune in functiune un program care sa functioneze la parametri prevazuti.

Se stie ca, intr-un algoritm de calcul si deci, intr-un program, este oricand posibila prezenta unei/unor erori, oricat de precis si laborioasa ar fi metodologia de elaborare. Proeesul de detectare si apoi de eliminare a erorilor unui algoritm/program are doua componente, numite:

verificare

validare

Aceste dou aetivitati ar trebui sa earacterizeze practic toate etapele prin care trece un program, de la formularea cerintei de rezolvare a unei probleme, la analiza acesteia, la identificarea si apoi descrierea algoritmului de rezolvare a problemei, a codificarii datelor si validarea rezultatelor obtinute.

Aceasta deoarece tot mai multi specia1isti din diferite domenii arata ca aceasta activitate de testare si validare nu este specifica doar activittii de programare, ci se inta1neste pretutindeni, acolo unde se produce sau construieste ceva; exista in acest sens controale efectuate la nivelul fiecrei operatii sau grup de operatii, dupa cum exista si un control final, produsului finit, pentru realizarea receptiei lui finale.

In acest sens, activitatea de verificare si validare a unui produs program urmareste in principal, urmtoarele:

descoperirea defectelor programului
. certificarea faptului ca programul va functiona corect in conditii de exploatare curenta.

Testarea programului ramane metoda de baza pentru verificarea corectitudinii unui program, succesul ei fiind conditionat in primul rand de experienta programatorului, de complexitatea si completitudinea setului de date folosite in procesul testarii, de analiza riguroasa, atenta a rezultatelor obtinute in urma fiecarui test.

Prin testarea programului se intelege deci executarea programului respectiv cu scopul de a descoperi o anomalie sau eroare. Ea se bazeaza pe construirea unor esantioane de date de intrare care sa conduca la depistarea unor erori in functionarea programului, intr-un timp cat mai scurt si cu efort cat mai mic.

Practic, pornind de la niste date de test construite de el, programatorul asteapta sa obtina la final sau pe parcurs, anumite rezultate. Dac acestea sunt corecte, complete sau in formatul asteptat avem cel putin o eroare in executia programuiui. Putem spune ca succesul testarii depinde de "arta" programatorului de a-si construi setul de date de test.

Trebuie s precizam insa faptul ca relevanta testului depinde de numarul esantioane1or de date de test, dar mai ales de calitatea datelor alese. In acest sens, au aparut, in ultimul timp, o serie de metode de elaborare a datelor de test, care ajuta programatorul, oferindu-i posibilitatea de a aborda sistematic activitatea de testare a programelor, cu o probabilitate crescuta de depistare a erorilor.

Aceste metode pot fi denumite:

testarea functionala sau metoda cutiei negre, care presupune construirea datelor de test astfel incat sa permita testarea fiecarei functiuni a programului;

testarea structurala sau rnetoda cutiei transparente, care presupune construirea datelor de test astfel incat toate partile programului sa poata fi testate.

Succesul activitatii de testare consta deci in conceperea unor date de intrare prin prelucrarea carora defectele algoritmului si deci si a programului sa fie puse in evidenta prin observarea si analiza rezultatelor obtinute.

De aceea el este in mare masura dependent de experienta si indemanarea programatorului, de abilitatea lui de a-si construi datele de test cat mai complete, complexe, cuprinzatoare din punct de vedere al situatiilor sau valorilor de exceptie ce pot apare in executia curecta a programului.

Testarea unui program trebuie sa se finalizeze, pentru a fi utila, cu semnalarea erorii si localizarea ei. De aceea, testarea programului este urmata de depanarea lui.

Depanarea unui program consta in localizarea erorii, determinarea naturii sale si corectitudinea ei. Ea se poate face in mod:

sttic, dupa executarea programului

dinamic, in timpul executiei acestuia

Depanarea simbolica, o alta metoda de depanare, este mai usor de utilizat, deoarece ofera posibilitatea de a urmari executarea programului la nivel de limbaj sursa. Limbajele de programare ofera, in ultimile lor versiuni, un depanator simbolic integrat, care permite depanarea usoara, placuta si eficienta a programelor prin urmatoarele operatii:

executarea pas cu pas a programului (un pas inseamna de fapt o instructiune executabila);

observarea, in timpul executiei, a valorilor unor variabile sau expresii specificate de programator (care apar intr-o fereastr speciala - Watch Window);

specificarea unor puncte de suspendare a executiei programului;

modificarea valorilor unor variabile.

In activitatea de testare si depanare a programelor, erorile datorate variabilelor neinitializate sunt greu de semnalat si de localizat, mai ales atunci cand aparent totul functioneaza corect. In acest sens amintim variabila cu rol de indice (numarator) care asigura parcurgerea elementelor unui vector. Aceasta trebuie initializata cu pozitia primului element din sir care trebuie prelucrat si apoi testat si comparata valoarea ei cu cea finala. Deasemenea, expresia care stabileste daca un ciclu se executa sau nu trebuie astfel formulata sau initializata incat sa asigure sau nu prima executie, asa cum necesita algoritmul de prelucrare descris. In acest sens, trebuie sa facem precizarea c adeseori, suntem nevoiti sa facem noi, prin program, initializarea variabilei care controleaza executia ciclului, pentru a asigura executia lui pentru prima data. Este vorba de ciclul cu testarea initiala a conditiei, la care reluarea ulterioara va fi hotarata de valoarea pe care respectiva variabila o primeste, in timpul executiei programului, in cadrul ciclului. Deci, ciclul cu testarea initiala a conditiei trebuie sa fie bine analizat, verificat si testat din punctul de vedere al expresiei care-i controleaza reluarea.

Practica a dovedit, in timp, ca oricat de numeroase ar fi testele efectuate asupra unor programe foarte complexe, ele nu pot garanta functionarea corecta a acestora. Ele raman deosebit de utile pentru semnalarea multora dintre erori si deasemenea pentru familiarizarea programatorului cu algoritmul, cu modul sau de lucru.

Proprietatea P se numeste preconditie sau proprietate finala, iar proprietatea Q postconditie san proprietate finala.

Practica a dovedit c exista situatii cand pentru un algoritm A si o postconditie data, nu intereseaza o preconditie oarecare, ci se cauta " cea mai buna" preconditie care rezolva algoritmul dat.

Fie secventa de comenzi, care calculeaza factorialul unui numar >=2:

(n>=2)

f:=1;

i:

while i <n do

begin

i:=i+1;

f:=f*i

end

(f=n!)

Se poate observa factorialul este calculat corect si daca n porneste de la valoarea 1 (n>=1). Deci, preconditia n>=2 poate fi inlocuita cu n>=1 care se consider o     preconditie mai buna, care descrie o multime de date initiale mai cuprinzatoare, obtinuta prin adaugarea valorii 1.

O analiza mai atenta a algoritmului arata ca preconditia n>=1 poate fi inlocuita cu n>0 considerat o preconditie mai buna, care atesta capacitatea algoritmului de a calcula factorialul oricarui numar natural, multimea datelor initiale fiind din nou marita prin adaugarea valorii 0 (0!=1).