Metode de construire a algoritmilor

          In functie de procesul de calcul necesar pentru rezolvarea unei probleme, exista urmatoarele clase de probleme:

- Probleme de enumerare prin care se gasesc toate solutiile posibile                   

- Probleme de decizie prin care se precizeaza daca exista sau nu cel putin o solutie.

- Probleme de optimizare prin care se identifica solutia optima din multimea de solutii posibile.

          Generarea tuturor permutarilor unei multimi de numere este o problema de enumerare, cauta­rea unei valori precizate intr-un sir de numere este o problema de decizie, iar gasirea modalitatii de plata a unei sume s cu un numar minim de bancnote de valori date este o problema de optimizare.

          Pentru rezolvarea aceleiasi probleme se pot folosi mai multe metode de construire a algoritmilor. Am invatat deja ca pentru rezolvarea aceleiasi probleme  putem folosi un algoritm iterative sau un algoritm recursiv.

          Solutiile recursive sunt mult mai clare, mai scurte si mai usor de urmarit. Alegerea algoritmului recursiv in locul celui iterativ este mai avantajoasa in cazul in care solutiile problemei sunt definite recursiv sau daca cerintele problemei sunt formulate recursiv.

               O(1) pentru n=0

    T(n) =   

               O(1)+T(n-1) pentru n<>0

          Timpul de executie a unui algoritm recursiv este dat de o formula recursiva De exemplu, pentru algoritmul de calculare a sumei primelor n numere naturale, functia pentru timpul de executie este prezentata mai sus, unde O(1) reprezinta timpul de executie a unei operatii elementare de atribuire a unei valori sumei. Rezulta ca T(n)=(n+1)xO(1), iar ordinul de complexitate a algoritmului este O(n) la fel ca si cel al algoritmului iterativ. In cazul implementarii recursive, fiecare apel al unul subprogram recurent inseamna inca o zona de memorie rezervata pentru executia sub­programului (variabilele locale si instructiunile). Din aceasta cauza, in alegerea intre un algoritm iterativ si un algoritm recursiv trebuie tinut cont nu numai de ordinul de complexi­tate, dar si de faptul ca, pentru o adincime mare a recursivitatii, algoritmii recursivi nu mai sunt eficienti, deoarece timpul de executie creste, din cauza timpilor necesari pentru mecanismul de apel si pentru administrarea stivei de sistem.

          Mult timp, elaborarea unui nou algoritm pentru rezolvarea unei probleme a constituit o formă de manifestare a inteligenţei, o exprimare a capacităţii de sinteză şi analiză, a bagajului de cunoştinţe şi experienţă ale celui care îl elabora punându-se în evidenţă caracterul de creativitate, de artă chiar a acestei activităţi. Reuşitei standardizării reprezentării algoritmilor i s-a alăturat dorinţa de standardizare a elaborării algoritmilor. Cu toate succesele obţinute în acest sens, activitatea de elaborare a algoritmilor beneficiază încă de o doză substanţială de libertate de exprimare a experienţei şi creativităţii. Primele metode de elaborare a algoritmilor au avut perioade mai lungi sau mai scurte de priză la mase, dar o analiză atentă a eficienţei (complexităţii) algoritmilor elaboraţi au etalat avantaje şi neajunsuri, care au condus la o ierarhizare a acestor metode. În cele ce urmează, vom prezenta succint cele mai uzitate metode de elaborare a algoritmilor.

          Vom invata noi metode de construire a algoritmilor - care ofera avantajul ca prezinta fiecare o metoda generala de rezolvare care se poate aplica unei clase de probleme:

- metoda backtracking;

- metoda divide et impera;

- metoda greedy;

- metoda programarii dinamice.

          Fiecare dintre aceste metode de construire a algoritmilor se poate folosi pentru anumite clase de probleme, iar in cazul in care - pentru aceeasi clasa de probleme - se pot folosi mai multe metode de construire a algoritmilor, criteriul de alegere va fi eficienta algoritmului.