REZOLVAREA PROBLEMELOR CU CALCULATORUL

REZOLVAREA PROBLEMELOR CU CALCULATORUL

1.1. Activitatea de programare

Aparitia primelor calculatoare electronice a constituit un salt urias in directia automatizarii activitatii umane. Cresterea performantelor calculatoarelor, raspandirea acestora si folosirea lor in cele mai diverse domenii de activitate a dus la cresterea complexitatii problemelor rezolvate cu calculatorul. Acesta a devenit un mijloc indispensabil multor activitati umane, iar unele dintre ele ar fi fost imposibil de rezolvat in absenta lui. In acelasi timp unele aplicatii trebuiesc realizate contra cronometru, ele trebuind sa fie terminate intr-un timp limitat, insuficient pentru a putea fi realizate de o singura persoana. Ca o consecinta, s-a observat o crestere continua a costului scrierii de programe in comparatie cu costul echipamentelor. Consideram ca cel mai important factor care a contribuit la aceasta situatie este cresterea complexitatii programelor elaborate pentru problemele tot mai complicate rezolvate astazi cu ajutorul calculatorului. Complexitatea problemelor si necesitatea urgentarii realizarii programelor au dus la munca in echipa.

Calculatoarele pot fi folosite pentru a rezolva probleme, numai daca pentru rezolvarea acestora se concep programe corespunzatoare. Termenul de program (programare) a suferit schimbari in scurta istorie a informaticii. Prin anii '60 problemele rezolvate cu ajutorul calculatorului erau simple si le corespundeau algoritmi nu prea complicati. Prin program se intelegea rezultatul scrierii unui algoritm intr‑un limbaj de programare. Din cauza cresterii complexitatii, astazi pentru rezolvarea unei probleme adesea vom concepe un sistem de mai multe programe.

Cresterea continua a costului scrierii de programe se datoreaza unor factori obiectivi. Asa cum deja am mentionat, cel mai important consideram ca este cresterea complexitatii programelor elaborate. Apoi, este necesara adaptarea programatorului la conditiile reale existente. Programele destinate supravegherii si/sau conducerii in timp real a unor procese industriale trebuie sa porneasca de la realitatea locului de munca respectiv cu care sunt obisnuiti muncitorii din acel loc si nu este permisa simplificarea conditiilor reale pentru a se ajunge la programe mai simple. Un al treilea factor ce contribuie la cresterea costului consta in schimbarea programului initial, schimbare datorata si ea unor factori obiectivi. Astfel, lumea reala se afla intr-o continua miscare, ducand la modificarea conditiilor in care s-a presupus ca lucreaza programul. Este necesar ca acesta sa se adapteze noilor conditii. Apoi exista dorinta fireasca a beneficiarului de a obtine mai multe rezultate cu ajutorul calculatorului si in consecinta este necesara modificarea programului initial pentru a satisface dorinta acestuia. De asemenea, schimbarea configuratiei hard poate duce la schimbari in program.

Astazi se simte nevoia elaborarii unor produse-program complexe, la care trebuie sa participe mai multi programatori. In [Vad85] produsele-program sunt clasificate in: simple (pana la 1000 de linii sursa, care pot fi realizate de un singur programator in cateva luni), de complexitate medie (pana la 10000 linii sursa si elaborate de 1-5 programatori, realizate in cel mult doi ani), complexe (pana la 100000 linii sursa si elaborate de 5-20 de programatori in 2-3 ani), foarte complexe (pana la 1 milion linii sursa, elaborate de 100-1000 programatori in cativa ani) si programe aproape imposibile (cateva milioane de instructiuni, elaborate de peste 1000 de programatori intr-un timp ce poate depasi 10 ani de zile).

Ca exemple de programe complexe cunoscute tuturor mentionam compilatoarele, sistemele de gestiune a bazelor de date si sistemele de operare in general.

Trecerea de la programarea individuala la programarea in echipa a necesitat schimbarea stilului de munca, respectarea unei discipline in programare, gasirea unor modalitati adecvate de comunicare intre programatori, precum si a unor modalitati adecvate de specificare a problemelor. Termenul programare este folosit aici in sens larg, intelegand prin el intreaga activitate depusa de la enuntul unei probleme pana la obtinerea unui program pentru rezolvarea ei. Asa cum vom vedea, aceasta activitate contine mai multe faze, una dintre ele fiind si programarea propriu-zisa, numita si implementare. Activitatea de programare implica urmatoarele subactivitati: specificarea, proiectarea, implementarea, documentarea si intretinerea produsului program. Despre ele vom vorbi in sectiunea care urmeaza.

Prima dintre metodele de programare utilizata a fost programarea modulara (vezi sectiunea 3.5). Odata cu aparitia limbajului FORTRAN in 1956, care avea posibilitatea folosirii subalgoritmilor in programare si compilarea separata, apare si programarea modulara. Tot compilarea separata a dus la aparitia bibliotecilor de subprograme. Programarea modulara consta in descompunerea unei probleme complexe in subprobleme, pentru fiecare subproblema elaborandu-se cate un subalgoritm. Algoritmul de rezolvare al intregii probleme va fi obtinut prin asamblarea acestor subalgoritmi (module).

Parintele programarii structurate este E.W. Dijkstra (sectiunea 3.7). El arata [Dah72] ca se pot obtine programe mai bune fara instructiunea GOTO: calitatea unui program este invers proportionala cu numarul de instructiuni GOTO pe care le contine.

Fundamentarea teoretica a programarii structurate se datoreste apoi lui Bohm si Jacopini [Boh66] care au demonstrat ca sunt suficiente trei structuri de calcul, secventa, selectia si iteratia, pentru descrierea oricarui algoritm.

In 1971 Wirth [Wir71] continua fundamentarea teoretica a metodelor de programare, definind procedeul detalierii algoritmilor in pasi succesivi (stepwise refinement), iar in 1972 H.D.Mills [Mil75] foloseste conceptul de functie pentru modelarea unui algoritm.

Exista astazi numeroase cercetari referitoare la demonstrarea corectitudinii programelor. Desi nu s-au obtinut rezultate care sa permita demonstrarea automata a corectitudinii unui produs-program complex, aceste cercetari au contribuit la instaurarea unei munci disciplinate in activitatea de programare.

Multi specialisti considera astazi ca limbajele viitorului vor fi limbaje de specificare a problemelor, urmand ca pe baza specificarii sa se realizeze o programare automata.

1.2. Fazele rezolvarii unei probleme cu calculatorul

Rezolvarea unei probleme cu ajutorul calculatorului presupune parcurgerea urmatoarelor faze:

- precizarea cerintelor beneficiarului;

- specificarea problemei;

- proiectarea algoritmului de rezolvare a problemei;

- programarea propriu-zisa, numita si implementare (sau codificare);

- testarea produsului obtinut;

- exploatarea si intretinerea programului;

- redactarea documentatiei fiecareia din fazele enumerate.

Aceste faze constituie ciclul de viata al programului.

De foarte multe ori, atunci cand beneficiarul discuta cu executantul despre problema care trebuie rezolvata, acesta da un enunt vag, incomplet, daca nu chiar inexact sau chiar contradictoriu, pentru problema de rezolvat. Urmeaza mai multe discutii, uneori intinse in timp, in urma carora se ajunge la un enunt relativ complet si exact al problemei. Executantul are sarcina de a obtine de la client enuntul cat mai exact al problemei, cat si conditiile in care se va executa programul, pe ce calculator, cu ce spatiu de memorie interna si externa, etc. Aceasta este prima faza din activitatea pe care o va depune executantul, faza numita definirea problemei si terminata cu mentionarea scrisa a cerintelor clientului.

Dialogul client-executant trebuie sa se termine cu un enunt clar al cerintelor clientului. O situatie frecvent intalnita consta in interpretarea diferita data aceleasi propozitii de catre cele doua tabere. Desi au fost de acord cu enuntul problemei, pot exista in acest enunt propozitii care pentru executant inseamna ceva iar pentru beneficiar inseamna altceva. Este necesar ca in urma acestui dialog fiecare propozitie sa reprezinte acelasi lucru pentru ambele tabere, neexistand ambiguitati in formularea si interpretarea ei. Acest dialog trebuie sa se finalizeze printr-un document scris, in care este enuntata problema in cele mai mici detalii.

Urmeaza faza a doua, specificarea problemei, in care cerintele clientului sunt analizate atent si retinute sub forma unui document care precizeaza cat mai exact ce trebuie sa faca programul cerut. Este foarte important ca aceasta faza sa se termine cu specificatia corecta a problemei. Se recomanda verificarea atenta a acestei specificatii astfel ca eventualele contradictii sa fie inlaturate inca din aceasta faza.

Si aceasta faza trebuie sa se incheie cu un document (scris) de specificare. El trebuie sa reflecte exact sarcinile produsului ce se va realiza, care sunt datele de intrare si care sunt rezultatele cerute; de asemenea, la ce restrictii este supus programul. Se recomanda ca specificatia facuta unei probleme sa fie analizata atent cel putin de catre o persoana diferita de autorul specificatiei. La verificarea specificarii unei probleme complexe se recomanda sa lucreze o echipa din care vor face parte reprezentanti atat din partea executantului cat si din partea beneficiarului.

Dupa stabilirea specificatiilor, urmeaza modelarea matematica si cautarea unei metode de rezolvare a problemei. Uneori sunt posibile mai multe moduri de rezolvare, caz in care se va alege metoda considerata cea mai potrivita scopului urmarit. Modelarea matematica si alegerea unei metode de rezolvare se imbina aproape intotdeauna cu conceperea algoritmului, fiind greu sa se separe una de cealalta. Activitatile de mai sus constituie ceea ce numim proiectarea programului. In aceasta etapa echipa de proiectare va defini structura produsului ce trebuie realizat (componentele, modulele), structurile de date si algoritmii folositi. Vor fi definite toate modulele si interfetele dintre ele si se va da specificatia fiecarui modul in parte.

Pe toata durata proiectarii trebuiesc mentionate in scris toate deciziile luate, intrucat este posibil ca ulterior sa fie necesara o reproiectare si deci, sa se revina asupra acestor decizii. Documentatia realizata este necesara in primul rand pentru urmatoarea faza a ciclului de viata al programului, implementarea. De asemenea, in faza de intretinere a programului este posibila modificarea unor module, modificare in care sunt necesare sa fie cunoscute si aceste decizii. E bine ca proiectarea sa fie astfel facuta incat sa permita o intretinere cat mai usoara. O anume schimbare nu trebuie sa provoace schimbarea tuturor modulelor ci doar cateva module sa fie afectate. Eventual pot fi necesare cateva module noi, dar majoritatea modulelor sa fie folosite fara nici o modificare.

Faza a patra, implementarea sau codificarea, consta in traducerea algoritmului intr-un limbaj de programare. Evident, prima decizie ce trebuie luata consta in alegerea limbajului de programare in care va fi scris programul. De multe ori se vor folosi mai multe limbaje pentru aceasta activitate. De exemplu, pot exista unele module a caror scriere se poate face numai in limbajul de asamblare.

Urmeaza faza a cincia, testarea programului elaborat. Testarea 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. Sunt rezultatele obtinute in timp util? Uneori testarea pune in evidenta erori grave de programare, erori care au dus in unele situatii la refacerea (partiala sau integrala) a activitatilor anterioare. Sigur ca este de dorit sa nu se ajunga la astfel de situatii si, daca proiectarea si implementarea au fost facute corect, in faza de testare nu ar trebui sa intalnim erori.

In [Sch90] testarea nu este considerata o faza separata, dupa scrierea programului, ci o activitate continua pe toata durata proiectarii, implementarii si intretinerii programului respectiv, activitate numita verificarea programului. Suntem de acord cu acest punct de vedere. Mai mult, consideram ca testarea clasica a programelor este deja inlocuita cu activitatea de verificare a programelor, activitate extinsa la intreg ciclul de viata al acestora. Ea imbina metodele traditionale de testare a programelor cu metodele matematice de demonstrare a corectitudinii unor parti din program. Verificarea programelor va fi prezentata mai pe larg in capitolul sase.

O faza care lipseste ca faza distincta in cele mai multe carti de programare este validarea programelor. Notiunile de verificare si validare sunt adesea confundate si de multe ori neclar prezentate in anumite materiale. In aceasta carte consideram ca exista o diferenta clara intre cele doua notiuni, chiar daca ele constau din aceleasi activitati si au scopuri similare. Validarea este activitatea de verificare a programului facuta de catre beneficiar la primirea acestuia, verificarea fiind activitatea facuta de firma care a realizat produsul. Chiar daca au scopuri similare si ar trebui sa constea din aceleasi activitati, enumerate mai sus, ele sunt diferite prin modul in care sunt realizate, prin ponderea acordata activitatilor enumerate si prin persoanele care fac verificarea. Astfel, la validarea programului de catre beneficiar, acesta este mai putin (adeseori chiar deloc) interesat in analiza specificatiei, sau in generarea unor date de test conform unor criterii. El va testa programul cu date reale si va urmari in primul rand daca obtine rezultatele dorite si daca forma sub care le obtine il satisfac. Verificarea facuta de catre firma soft care realizeaza produsul are acelasi scop principal, acela ca produsul realizat sa-l satisfaca pe beneficiar, dar si scopuri colaterale, care constau in marirea productivitatii, marirea certitudinii ca produsul va fi realizat la timp, conform bugetului si a sigurantei ca el va fi corect.

Urmatoarea faza din viata programului consta in exploatarea propriu-zisa a acestuia, faza in care executia se face cu date reale. Aceasta activitate se intinde in timp si cere adeseori schimbari in program, motiv pentru care este cunoscuta sub numele de intretinerea programului. Este faza cea mai costisitoare si cea mai importanta din viata produsului. Toata activitatea de realizare a programului trebuie sa tina seama de acest fapt si sa fie astfel gandita incat sa se permita modificari in ceea ce face programul cu un numar minim de modificari in textul acestuia. Intretinerea presupune si actualizarea documentatiei prin precizarea tuturor modificarilor facute.

Documentarea programului presupune elaborarea unor materiale scrise in care se precizeaza toate informatiile utile despre programul realizat. Exista doua aspecte importante care trebuie avute in vedere: explicarea modului in care a fost conceput programul si explicarea modului de functionare a acestuia. Vom avea deci o documentatie de realizare si o documentatie de exploatare. Documentatia de realizare a programului este scrisa si actualizata in fiecare faza din ciclul de viata al acestuia. Deci in fiecare faza din ciclul de viata al unui program vom avea o documentatie corespunzatoare fazei respective.

Evident, produsul program este el insusi o autodocumentare a sa, prin textul sursa disponibil. Din pacate, foarte frecvent este si singura documentatie existenta. Mai multe despre documentarea programelor se vor prezenta in sectiunea 6.2.

In sfarsit, ultima faza din existenta unui program este pensionarea (sau moartea) programului. Dupa un numar de ani de folosire, de obicei cu multe imbunatatiri facute in timp, programul a ajuns sa nu mai corespunda noilor cerinte ale beneficiarului. Motivele pot fi multiple: schimbarea conditiilor in care lucreaza beneficiarul, prin achizitionarea unui calculator nou pentru care este necesar un nou program, sau schimbarile ce ar trebui facute programului ar costa mai mult decat realizarea unui nou produs.

1.2.1 Specificarea problemei

Specificarea problemei este a doua faza din viata unui program, i-am putea spune actul de nastere al programului. Ea cere elaborarea unui document care arata ce trebuie sa faca programul. Acest document, care trebuie sa reflecte exact cerintele beneficiarului si sa nu contina ambiguitati sau afirmatii contradictorii, este cunoscut sub numele de specificatie.

Pentru a intelege complexitatea si importanta acestei faze vom da un exemplu din literatura de specialitate. Astfel, Naur [Nau66] enunta urmatoarea problema (tradusa din limba engleza):

'Dandu-se un text format din cuvinte separate printr-un caracter spatiu sau sfarsit de linie, sa se converteasca intr-o secventa de mai multe linii dupa urmatoarele reguli:

1) Fiecare linie contine o parte din text ce se termina cu un cuvant;

2) Fiecare linie contine cat mai multe cuvinte din text;

3) O linie are cel mult MAX caractere.'

Cu toate ca problema este enuntata de un specialist in domeniu, ea nu este corecta. Erorile din enuntul lui Naur au fost observate de mai multi autori. O prima eroare a fost semnalata in recenzia facuta de Leavenworth [Lea70], iar London [Lon71] semnaleaza alte trei erori. Goodenough si Gerhart [Goo75] au scris specificatia problemei intr-un text de patru ori mai lung decat al lui Naur. Evident au facut-o cu multa atentie si cu dorinta de a inlatura orice eroare. Cu toate acestea Meyer [Mey85] a gasit in specificatia acestora alte 12 greseli si a dat o noua specificatie intr-un limbaj matematic.

Deci pentru o problema relativ mica, specificatia scrisa de specialisti in domeniu a continut destule erori. Ce se intampla pentru o problema mult mai complexa la care lucreaza o echipa de programatori obisnuiti?

Specificarea unei probleme poate fi facuta atat in limbaj natural cat si in limbaj matematic. Specificatia scrisa intr-un limbaj natural are sansa mai mare de a contine contradictii, omisiuni sau ambiguitati, in timp ce specificatia in limbaj formalizat este mai greu de urmarit.

Evident ca nu putem scrie programe fara a avea un enunt clar al problemei pe care dorim sa o rezolvam. De aceea inca din primul capitol vom vorbi despre specificarea problemelor. Vom continua apoi in capitolul patru, in care definim notiunea de corectitudine. Aceasta notiune cere o specificare mult mai riguroasa, facuta cu ajutorul limbajului logicii matematice.

1.2.2. Proiectarea programului

Scopul acestei faze este de a preciza cum sunt realizate cerintele beneficiarului, care sunt algoritmii folositi si structurile de date cu care se lucreaza. Deosebim:

- proiectarea de ansamblu, a intregului program;

- proiectarea detaliata a fiecarui modul.

Rezultatul acestei etape este numit proiect (de ansamblu si de detaliu).

In proiectarea de ansamblu se decide structura produsului pornind de la specificatii. In general un produs se compune din module. In proiectarea de ansamblu se precizeaza scopul fiecarui modul si interfata dintre module. Interfata dintre module precizeaza datele care sunt transferate intre module, asa cum va reiesi din descrierea subalgoritmilor. Proiectarea de detaliu se refera la fiecare subalgoritm (modul) in parte.

In descrierea algoritmilor se folosesc mai multe limbaje de descriere, dintre care cele mai des folosite sunt:

- limbajul schemelor logice;

- un limbaj pseudocod.

Acestea sunt prezentate in capitolul doi al acestei carti, iar proiectarea va fi scopul principal al paginilor care urmeaza.

1.2.3. Implementarea

Implementarea (codificarea, sau programarea propriu-zisa) este procesul traducerii algoritmului obtinut in urma proiectarii intr-un limbaj de programare existent in sistemul de calcul in care se va folosi produsul. Ea este realizata fie de un singur programator, fie de o echipa de programatori. Este bine ca implementarea sa fie facuta de o singura persoana, lucru posibil pentru produse mai putin complexe. Dar nu putem astepta 20 de ani ca un singur programator sa termine un produs complex. In acest caz munca in echipa devine obligatorie.

Alegerea limbajului, sau a limbajelor de programare este prima etapa din implementare. Ea se impune numai daca pe calculatorul pe care se va folosi produsul realizat sunt disponibile mai multe limbaje de programare (adica sistemul lor de operare contine programe translatoare pentru respectivele limbaje) si daca aceasta alegere nu a fost deja stabilita printr-o dorinta expresa a beneficiarului. In aceasta carte limbajul ales este Pascal, introdus de Wirth [Wirth71] special pentru invatarea programarii. Desi accentul acestei carti nu este pe implementare, avem nevoie de un limbaj de programare pentru a ne putea testa algoritmii si pentru a intelege activitatea de programare in ansamblul ei. Limbajul Pascal este prezentat in capitolul patru.

La prima vedere implementarea nu ridica probleme deosebite, ea insemnand doar traducerea algoritmului in limbajul de programare ales. Evident, cel care face aceasta traducere trebuie sa cunoasca foarte bine limbajul de programare, dar si limbajul de descriere a algoritmului. Exista insa anumite decizii pe care programatorul trebuie sa le ia, sunt anumite parti pentru care traducerea in limbajul de programare utilizat nu este banala.

Exista mijloace soft care ajuta programatorii in implementare. Dintre acestea enumeram editoarele de texte, compilatoarele, depanatoarele si mediile de programare in general (in Anexa B se prezinta pe scurt depanatorul Turbo-Pascal).

1.2.4 Intretinerea programelor

Intretinerea programelor consta din toate schimbarile facute dupa ce beneficiarul a acceptat produsul comandat. Motivele acestor schimbari pot fi multiple.

In primul rand ne astepam la corectarea erorilor descoperite dupa acceptare, care constituie intretinerea corectiva.

Exista insa si o intretinere perfectiva care consta din schimbarile facute cu scopul de a imbunatati programul, a-i mari eficienta si, cel mai des, a-i adauga functii noi dorite, de beneficiar si utile acestuia.

In sfarsit, putem vorbi si de o intretinere adaptiva, care consta din schimbari necesare adaptarii programului la mediul aflat intr-o continua schimbare. Ca exemplu, daca printre informatiile cu care opera programul se aflau si numerele de telefon ale unor persoane, in urma schimbarii sistemului de numerotare din 1992 sunt necesare schimbari in program prin care toate numerele de telefon din Municipiul Cluj-Napoca se extind la sase cifre, primind cifra 1 in fata numarului vechi.

Ponderea acestor activitati in totalul activitatii de intretinere (dupa [Sch90]) reprezinta:

- intretinerea corectiva 17%;

- intretinerea perfectiva 60%;

- intretinerea adaptiva 18%;

- alte activitati de intretinere 5%.

Se apreciaza ca in ciclul de viata al unui program intretinerea costa peste 50% din costul total al programului (dupa Meyer [Mey88] chiar 70%). In acelasi timp intretinerea este considerata activitatea cea mai dificila dintre toate celelalte faze.

Orice schimbare poate produce erori. Ca orice program nou si programul obtinut in urma intretinerii trebuie testat. Aceasta testare trebuie sa verifice daca modulele schimbate functioneaza corect si daca schimbarile facute nu au efect negativ asupra celorlalte parti ale programului.

Evident ca pentru a reusi sa facem schimbari intr-un program sunt necesare cat mai multe informatii despre acest program. Deci este foarte utila documentatia programului pe toata durata intretinerii. In acelasi timp intretinerea trebuie sa actualizeze documentatia cu toate modificarile facute si cauzele acestor modificari.

Pe timpul intretinerii unui program se obtin mai multe versiuni succesive. Se recomanda pastrarea tuturor versiunilor.