Algoritmi

ETAPELE REZOLVARII UNEI PROBLEME

ALGORITMUL – reprezintă o succesiune finită şi ordonată de operaţii univoc determinate, efectuate mecanic, care aplicate datelor iniţiale ale unei probleme dintr-o clasă dată, asigură obţinerea soluţiei acelei probleme. Cu alte cuvinte un algoritm este orice procedură de calcul bine definită care primeşte o anumită valoare sau o mulţime de valori ca date de intrare şi produce o anumită valoare sau mulţime de valori ca date de ieşire. Comportarea unui algoritm poate fi diferită în funcţie de datele de intrare.

Etimologia noţiunii de algoritm – provine din latinizarea numelui savantului Al-Khwarizmi (Algoritmi) – matematician, geograf, astronom persan (780-845), considerat şi părintele algebrei.

PROPRIETĂŢILE ALGORITMILOR sunt:

- Claritatea – operaţiile algoritmului şi succesiunea executării lor trebuie să fie descrise clar, precis, fără ambiguităţi, astfel încât să permită o executare mecanică, automată a acţiunilor algoritmului

- Generalitatea – un algoritm permite, nu rezolvarea unei singure probleme particulare, ci a unei întregi clase de probleme.

- Finitudinea – executarea algoritmului trebuie să cuprindă un număr finit de operaţii, chiar dacă numărul lor este foarte mare. Această proprietate diferenţiază metoda de calcul de algoritm.

- Eficienţa – dintre algoritmii care rezolvă o anumită problemă, prezintă interes numai algoritmii performanţi pentru care numărul operaţiilor care se execută este cel mai mic.

Provocari:

o La momentul actual sunt realizate cercetări serioase asupra algoritmilor care vizează nu numai o îmbunătăţire a performanţei ci şi o reducere a puterii consumate, vitală mai ales la nivelul dispozitivelor de calcul de tip “handheld” şi al sistemelor dedicate.

o Într-o era a sistemelor multicore (mai multe procesoare pe acelasi cip) s-ar putea ca algoritmii populari de programare, din era secvenţiala să scadă în popularitate. => Necesitatea scrierii algoritmilor in vederea paralelizarii executiei (fire de executie din cadrul aceluiasi program care sa opereze in paralel). Algoritmii de tip divide et impera pot fi paralelizati mai uşor. Exemplu: Quicksort – după partiţionare cele două liste obţinute pot fi uşor sortate în paralel. Avantajul consta in faptul că nu e nevoie de sincronizări (cu excepţia celei finale, când firele se reunesc). Un nou fir poate fi pornit imediat ce avem la dispoziţie o sublistă de sortat şi acesta nu are nevoie să comunice cu celelalte fire. Când toate firele au terminat, sortarea este completă.