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