Etapele rezolvarii unei probleme

Rezolvarea unei probleme constituie un proces complex, care comporta mai multe etape.

1. Analiza problemei in scopul stabilirii datelor de intrare, precum si a rezultatelor pe care trebuie sa le obtinem prin rezolvarea problemei.

2. Elaborarea unui algoritm de rezolvare a problemei.

3. Implementarea algoritmului intr-un limbaj de programare.

4. Verificarea corectitudinii algoritmului propus. Un prim pas consta in testarea programului pe diverse seturi de date de test. Seturile de date de test trebuie elaborate cu atentie, astfel incat sa acopere, pe cat posibil, toate variantele de executie a algoritmului, inclusiv situatii de exceptie, si sa verifice daca fiecare subproblema a problemei date este rezolvata corect (daca este posibil, se va testa separat fiecare modul de program).

Testarea poate pune in evidenta, eventual, omisiuni sau erori de conceptie a algoritmilor, dar nu garanteaza corectitudinea algoritmului. Pentru aceasta ar trebui sa testam algoritmul pe toate seturile posibile de date de intrare, ceea ce este practic imposibil. Din acest motiv se impune utilizarea unor metode formale de demonstrare a corectitudinii algoritmului, etapa de obicei deosebit de laborioasa, necesitand un aparat matematic complex.

5. Analiza complexitatii algoritmului.

In general, exista mai multi algoritmi de rezolvare a unei probleme date. Pentru a alege cel mai bun algoritm, trebuie sa analizam acesti algoritmi in scopul determinarii eficientei lor si, pe cat posibil, a optimalitatii lor. Eficienta unui algoritm se evalueaza din doua puncte de vedere:

1. din punctul de vedere al spatiului de memorie necesar pentru memorarea valorilor variabilelor care intervin in algoritm;

2. din punctul de vedere al timpului de executie. Complexitatea spatiu o vom analiza cu precadere atunci cand vom transpune algoritmul intr-un limbaj de programare.

Pentru a estima complexitatea timp vom presupune ca se lucreaza pe un calculator «clasic », in sensul ca o singura instructiune este executata la un moment dat. Astfel, timpul necesar executiei programului depinde de numarul de operatii elementare efectuate de algoritm.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s