Algoritm
De la Wikipedia, enciclopedia liberă
![]() |
Acest articol are nevoie de ajutorul dumneavoastră! Puteţi contribui la dezvoltarea şi îmbunătăţirea lui apăsând butonul "modifică pagina". |
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 (mâna dreaptă/stângă pe perete şi mergi fără să o dezlipeşti de perete).
[modifică] Proprietăţi
Cele mai importante proprietăţi ale algorimtului sunt următoarele:
-
- finititudinea 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 rezolvare 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ă neclarităţi, 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.
[modifică] Clasificări
În funcţie de modul de implementare, un algoritm poate fi:
- recursiv sau iterativ
- serial sau paralel
- deterministic sau aleator
- 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
[modifică] Bibliografie
- Donald E. Knuth - Arta Programării Calculatoarelor (ed. 2), Volumul 1: Algoritmi Fundamentali
- en Herbert S. Wilf - Algorithms and Complexity (PDF Document)
- en Martin Davis - The Undecidable: Basic Papers On Undecidable Propostions, Unsolvable Problems and Computable Functions, Raven Press, New York, 1965