Algoritm

De la Wikipedia, enciclopedia liberă

Salt la: Navigare, căutare

Un algoritm (cuvântul are la origine numele matematicianului persan Al-Khwarizmi) înseamnă în matematică şi informatică o metodă sau o procedură de calcul, alcătuită din paşii elementari necesari pentru rezolvarea unei probleme sau categorii de probleme. De obicei algoritmii se implementează în mod concret prin programarea adecvată a unui calculator, sau chiar şi a mai multora. Din diverse motive există şi algoritmi încă neimplementaţi, teoretici.

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

Câteva exemple de algoritme:

  • algoritmul de construcţie a unui automobil (urmărind procedeele şi schiţele de fabricaţie);
  • algoritmul de folosire a unei maşini-unelte (citind manualul de folosire);
  • algoritmul de explorare a unui labirint în vederea găsirii unei ieşiri (una din soluţii: se ţine o mână pe perete şi se merge fără a o dezlipi de acesta).
  • algoritmul (ordinea operaţiilor, sau "check list ") la decolarea unui turbojet. Acest algoritm desigur nu ţine în mod direct de domeniul matematicii sau informaticii.

Cuprins

[modifică] Proprietăţi

Cele mai importante proprietăţi ale unui algoritm, îndeplinite de diverşii algoritmi într-o măsură mai mare sau mai mică, sunt următoarele:

    • Corectitudinea - este proprietatea algoritmului de a furniza o soluţie corectă a problemei date. În acest sens este de dorit ca algoritmii să se bazeze pe fapte şi relaţii matematice demonstrabile.
    • Caracterul univoc sau deterministic - plecând de la un set de date iniţial anume, rezultatul este unic, sau altfel spus, repetarea execuţiei algoritmului duce întotdeauna la aceleaşi rezultate.
    • Generalitatea - este proprietatea unui algoritm de a rezolva o clasă sau categorie de probleme, şi nu doar o singură problemă particulară. Spre exemplu, un algoritm care rezolvă doar ecuaţia x2 + 5x − 6 = 0 este mai puţin general decât unul care rezolvă ecuaţia ax2 + bx + c = 0, oricare ar fi valorile lui a,b,c.
    • Claritatea - proprietatea algoritmului de a descrie cu exactitate şi fără ambiguităţi paşii care trebuiesc parcurşi în rezolvarea problemei.
    • Verificabilitatea - acea proprietate a algoritmelor care permite ca fiecare pas să poată fi verificat într-un timp rezonabil de către om, folosind mijloace de validare de încredere.
    • Optimalitatea - 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, el s-ar termina abia în n paşi, şi deci nu ar fi optim.
    • 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 mărginit de paşi, dar aceştia se numesc "metode algoritmice".
    • Eficienţa - este proprietatea unui algoritm de a se termina nu numai într-un număr finit, ci şi "rezonabil" de paşi, chiar dacă acesta nu este cel mai mic posibil (nu este optim). Algorimul este ineficient şi dacă rezultatul se obţine într-un timp mai lung decât cel dorit sau permis.
    • Existenţa unei intrări (datele de prelucrat). Întrucât operatorii se aplică unui operand (sau şi mai multor operanzi deodată), este de neconceput un algoritm fără niciun operand. Intrările permise formează împreună un set (mulţime) specific de obiecte sau valori, care se numeşte "domeniul" algoritmului.
    • Existenţa unei ieşiri (rezultatele). Este de neconceput un algoritm care nu are nicio ieşire, deoarece în acest caz intră în discuţie însăşi utilitatea sa.

[modifică] Clasificări

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

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

[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
  • Doina Logofătu: Algoritmi fundamentali in C++. Aplicaţii, Ed. 1, Editura Polirom, Iaşi, 2007, ISBN 9734600939.
  • Doina Logofătu: Algoritmi fundamentali in Java. Aplicaţii, Ed. 1, Editura Polirom, Iaşi, 2007, ISBN 9734608157.

[modifică] Vezi şi

[modifică] Legături externe

Adus de la http://ro.wikipedia.org/wiki/Algoritm
Unelte personale