Algoritmi

Conceptul de algoritm

Algoritmul este, in general, descrierea riguroasa a secventei de actiuni care trebuie executate pentru a atinge un anumit obiectiv.

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;
b. Caracter finit. Rezultatul trebuie sa se obtina dupa un numar finit de pasi. 
c. Caracter realizabil. Toate actiunile prevazute in algoritm trebuie sa poata fi realizate in mediul de executie pentru care a fost conceput algoritmul respectiv. In general, la elaborarea algoritmului se are in vedere o multime finita de actiuni, realizabile in mediul de executie considerat. 
d. Caracter de generalitate. Algoritmul se aplica asupra anumitor date de intrare, pentru a se obtine anumite date de iesire. In general, la elaborarea algoritmului se are in vedere ca acesta sa se aplice oricarui set de date de intrare dintr-o anumita multime de astfel de seturi de date avuta in vedere.
e. Caracter de unicitate a solutiei. De cate ori se aplica acelasi algoritm asupra acelorasi date, trebuie sa se obtina acelasi rezultat. 

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.

Complexitatea algoritmilor

Pentru rezolvarea aceleeasi probleme se pot concepe mai multi algoritmi. Din punct de vedere al aplicarii lor pe calculator, este important sa comparam acesti algoritmi din punct de vedere al numarului de operatii elementare necesare pentru a obtine rezultatul si din punct de vedere al memoriei ocupate. Cu cat numarul de operatii elementare este mai mic, cu atat timpul de calcul necesar este mai mic si deci algoritmul respectiv este mai eficient.

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.

Grafice functii 

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:

Complexitatea constanta si cea liniara sunt, evident, cazuri particulare ale celei polinomiale. Este evident ca cei mai avantajosi algoritmi sunt cei de complexitate O(1), dar acestia se intalnesc rar. In general, se considera acceptabili algoritmii cu complexitati O(log(n)), O(n), O(n*log(n)), O(n2) si O(n3). Remarcam ca, totusi, acest rationament este valabil numai pentru valori mari ale lui n. La valori mici, este posibil ca un algoritm de complexitate exponentiala sau polinomiala de ordin superior sa necesite timp de executie mai mic decat unul de complexitate liniara. In cazul cand mai multi algoritmi se incadreaza in aceeasi categorie de complexitate, pentru a stabili gradul lor relativ de eficienta este necesara o analiza mai fina.

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati