Algoritmul

Algoritm (noţiunea are la origine numele matematicianului persan Al-Khwarizmi), în matematică şi informatica teoretică, reprezintă o metodă univocă prin care se descriu, pe rând, paşii necesari pentru rezolvarea unei probleme.

Algoritmul este noţiunea fundamentală a informaticii. Totul este construit în jurul algoritmilor (şi al structurilor de date, cum ar fi listele sau grafurile). Putem vorbi despre:

* algoritmul de construcţie a unui maşini (urmărind schiţele);
* algoritmul de folosire a unei maşini (citind manualul de folosire);
* algoritmul de explorare a unui labirint în vederea găsirii unei ieşiri (în principal, se ţine mâna dreaptă/stângă pe perete şi se merge fără a o dezlipi de acesta).

Proprietăţi

Cele mai importante proprietăţi ale unui algoritm sunt următoarele:

* finitudinea este proprietatea algoritmului de a se termina într-un număr finit de paşi. Există şi 'algoritmi' care nu se termină într-un număr finit de paşi, dar aceştia se numesc metode algoritmice.
* corectitudinea este proprietatea algoritmului de a furniza o soluţie corectă a problemei date.
* generalitatea este proprietatea unui algoritm de a rezolva o clasă de probleme, şi nu doar o problemă particulară. Spre exemplu, un algoritm care rezolvă ecuaţia x2 + 5x − 6 = 0 este mai puţin general decât unul care rezolvă ecuaţia ax2 + bx + c = 0.
* claritatea este proprietatea algoritmului de a descrie cu exactitate paşii pe care îi parcurge în rezolvarea problemei, fără ambiguităţi.
* optimalitatea este proprietatea unui algoritm de a se termina după un număr minim de paşi. Spre exemplu, dacă se cere să se calculeze suma primelor n numere naturale, putem aplica formula de calcul, şi astfel algoritmul se termină într-un singur pas, pe când, dacă am aduna toate numerele de la 1 la n, s-ar termina în n paşi.

Clasificări

În funcţie de modul de implementare, un algoritm poate fi:

* recursiv sau iterativ
* serial sau paralel
* deterministic sau aleator (probabilistic)
* poate furniza rezultatul exact sau doar o aproximare a acestuia

În funcţie de paradigma utilizată pot fi:

* algoritmi backtracking
* algoritmi divide et impera
* algoritmi de programare dinamică
* algoritmi greedy
* algoritmi probabilişti, algoritmi genetici, algoritmi euristici