In informatica algoritmul este un concept fundamental, deoarece descrie
procesul de calcul (de prelucrare a datelor).
Denumirea de algoritm provine de la numele matematicianului Abu Ja'far Mohammed ibn Mûsâ al-Khowârizmî, care a trait in Persia si a scris in anul 825 ien (aproximativ), o carte care continea reguli de aritmetica. |
Algoritmul trebuie sa aiba urmatoarele caracteristici:
a. Caracter discret. Fiecare actiune prevazuta in algoritm are
un inceput si un sfarsit si dureaza un anumit interval de timp, fiind numita
si pas al algoritmului;
Tinand cont de caracteristicile mentionate, algoritmul poate fi definit si astfel: Algoritmul consta dintr-o multime ordonata de pasi executabili, descrisi fara echivoc, care definesc un proces finit. Algoritmul este, deci, descrierea riguroasa a unui proces. In schimb, nu orice proces poate fi descris printr-un algoritm. De exemplu, in cazul unei aplicatii interactive bazata pe programarea orientata pe evenimente, executarea fiecarei metode in parte este un proces descris algoritmic (prin insasi metoda respectiva). Daca insa urmarim executarea intregii aplicatii, in care participa atat calculatorul, cat si sursele de evenimente externe (de exemplu operatorul uman care interactioneaza cu interfata grafica), constatam ca acest proces nu este intotdeauna algoritmizabil. |
Pentru acelasi algoritm, numarul de operatii elementare depinde, in general, de cantitatea de date prelucrata. De exemplu, in algoritmii pentru efectuarea anumitor operatii asupra tablourilor, numarul de operatii poate sa depinda de numarul de componente ale tabloului. Sa notam cu n numarul de date de intrare prelucrate de algoritmul respectiv si cu f(n) functia care exprima relatia dintre numarul de operatii si numarul de date de intrare. Prezinta interes ce se intampla cu numarul de operatii f(n) atunci cand n creste. In appletul de mai jos sunt trasate pe intervalul [1, 3] graficele unor functii, pentru a pune in evidenta tendinta de variatie a fiecareia.
Se observa ca, in ordinea vitezei de crestere, functiile pot fi ordonate astfel: log(n), n, n*log(n), n2, en. Daca functia este polinomiala in n, pentru valori mari ale lui n viteza de crestere a functiei depinde numai de cea mai mare putere a acestuia. Viteza de crestere a functiei exponentiale este, la valori mari ale variabilei n, mai mare decat a oricarei functii polinomiale.
Complexitatea algoritmului se noteaza cu O(f(n)), unde f(n) este functia care indica rapiditatea de crestere a numarului de operatii elementare in raport cu numarul de date de intrare. Inmultirea cu coeficient constant sau adunarea cu o constanta nu sunt luate in consideratie, intrucat nu intereseaza valoarea exacta a functiei ci numai tendinta de crestere. Din acest punct de vedere distingem, in ordinea vitezei de crestere:
Studiul complexitatii este una din problemele fundamentale ale algoritmicii. Mai exista si alte categorii de complexitate, dar cele enuntate aici sunt suficiente pentru acest curs.