Algoritmi

Conceptul de algoritm

Algoritmul este, în general, descrierea riguroasă a secvenței de acțiuni care trebuie executate pentru a atinge un anumit obiectiv.

In informatică 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 trăit in Persia și a scris în anul 825 îen (aproximativ), o carte care conținea reguli de aritmetică.
Algoritmul trebuie sa aibă urmatoarele caracteristici:

a. Caracter discret. Fiecare acțiune prevăzută în algoritm are un început și un sfârșit și durează un anumit interval finit de timp, fiind numită și pas al algoritmului;
b. Caracter finit. Rezultatul trebuie să se obțină după un număr finit de pași.
c. Caracter realizabil. Toate acțiunile prevăzute în algoritm trebuie să poată fi realizate în mediul de execuție pentru care a fost conceput algoritmul respectiv. În general, la elaborarea algoritmului se are în vedere o mulțime finită de acțiuni, realizabile în mediul de execuție considerat.
d. Caracter de generalitate. Algoritmul se aplică asupra anumitor date de intrare, pentru a se obține anumite date de ieșire. În general, la elaborarea algoritmului se are în vedere ca acesta să se aplice oricărui set de date de intrare dintr-o anumită mulțime de astfel de seturi de date avută în vedere.
e. Caracter de unicitate a soluției. De câte ori se aplică același algoritm asupra acelorași date, trebuie să se obțină același rezultat.

Ținând cont de caracteristicile menționate, algoritmul poate fi definit și astfel:

Algoritmul constă dintr-o mulțime ordonată de pași executabili, descriși fără echivoc, care definesc un proces finit.

Algoritmul este, deci, descrierea riguroasă a unui proces. În schimb, nu orice proces poate fi descris printr-un algoritm. De exemplu, în cazul unei aplicații interactive bazată pe programarea orientată pe evenimente, executarea fiecărei metode în parte este un proces descris algoritmic (prin însăși metoda respectivă). Dacă însă urmărim executarea întregii aplicații, în care participă atât calculatorul, cât și sursele de evenimente externe (de exemplu operatorul uman care interacționează cu interfața grafică), constatăm ca acest proces nu este întotdeauna algoritmizabil.

Complexitatea algoritmilor

Pentru rezolvarea aceleeași probleme se pot concepe mai mulți algoritmi. Este important să comparăm acești algoritmi din punct de vedere al numărului de operații elementare necesare pentru a obține rezultatul și din punct de vedere al memoriei ocupate. Cu cât numărul de operații elementare este mai mic, cu atât timpul de calcul necesar este mai mic și deci algoritmul respectiv este mai eficient.

Pentru același algoritm, numărul de operații elementare depinde, în general, de cantitatea de date prelucrată. De exemplu, în algoritmii pentru efectuarea anumitor operații asupra tablourilor, numărul de operații poate să depindă de numărul de componente ale tabloului. Sa notăm cu n numărul de date de intrare prelucrate de algoritmul respectiv și cu f(n) funcția care exprimă relația dintre numărul de operații și numărul de date de intrare. Prezintă interes ce se întâmplă cu numărul de operații f(n) atunci când n crește. În figura de mai jos sunt trasate pe intervalul [1, 3] graficele unor funcții, pentru a pune în evidență tendința de variație a fiecăreia.


Se observă că, în ordinea vitezei de creștere, funcțiile pot fi ordonate astfel: log(n), n, n*log(n), n2, en. Daca funcția este polinomială în n, pentru valori mari ale lui n viteza de creștere a funcției depinde numai de cea mai mare putere a acestuia. Viteza de creștere a funcției exponențiale este, la valori mari ale variabilei n, mai mare decât a oricărei funcții polinomiale.

Complexitatea algoritmului se notează cu O(f(n)), unde f(n) este funcția care indică rapiditatea de creștere a numărului de operații elementare în raport cu numărul de date de intrare. Înmulțirea cu coeficient constant sau adunarea cu o constantă nu sunt luate în considerație, întrucât nu interesează valoarea exactă a funcției ci numai tendința de creștere. Din acest punct de vedere distingem, în ordinea vitezei de creștere:

Complexitatea constantă și cea liniară sunt, evident, cazuri particulare ale celei polinomiale. Este evident că cei mai avantajoși algoritmi sunt cei de complexitate O(1), dar aceștia se întâlnesc rar. În general, se consideră acceptabili algoritmii cu complexități O(log(n)), O(n), O(n*log(n)), O(n2) și O(n3). Remarcăm că, totuși, acest raționament este valabil numai pentru valori mari ale lui n. La valori mici, este posibil ca un algoritm de complexitate exponențială sau polinomială de ordin superior să necesite timp de execuție mai mic decât unul de complexitate liniară. În cazul când mai mulți algoritmi se încadrează în aceeași categorie de complexitate, pentru a stabili gradul lor relativ de eficiență este necesară o analiză mai fină.

Studiul complexității este una din problemele fundamentale ale algoritmicii. Mai există și alte categorii de complexitate, dar cele enunțate aici sunt suficiente pentru acest curs.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați