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": m9u9uo
"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.
4.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 R(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.
4.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 n1, respectiv n2 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.
4.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.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 4.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.
4.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,NUMEi, i=1,n, NOTEi,j, j=1,m, i=1,n; PENTRU
i:=1,n EXECUTA Acalculeaza media generala a elevului iS FIE S:=0; PENTRU j:=1,m
EXECUTA S:=S+NOTEi,j SFPENTRU FIE MEDIIi:=S/M SFPENTRU PENTRU j:=1,m EXECUTA
CHEAMA ORDINE(n,NOTEj,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.