ALGORITMI. CARACTERISTICILE ALGORITMILOR.

REPREZENTAREA ALGORITMILOR PRIN SCHEME LOGICE SI

PRIN PSEUDOCOD

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.

Unicitatea – transformările şi ordinea în care ele se aplică sunt univoc determinate de

regulile algoritmului. Ori de câte ori se aplică acelaşi algoritm asupra aceluiaşi set de date

iniţiale se obţin aceleaşi rezultate.

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.

Determinism – proprietatea algoritmilor prin care se cunoaşte cu exactitate următoarea

operaţie de executat.

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 eră 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 paralelizării execuției (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ă.

void *child(void *arg){

Quick_sort(params[0],params[1],v);

pthread_exit(NULL);

}

int main(int argc, char** argv) {

...

pivot = Partition(0, N, v);

params[0] = pivot;

params[1] = N;

pthread_create(&t, NULL, child, NULL);

Quick_sort(0, pivot-1, v);

pthread_join(t,NULL);

}

int Partitie(float *A,int p,int r){ int x=A[p]; int i=p-1; int j=r+1; while (1) { do j=j-1; while (A[j]>x); do i=i+1; while (A[i]<x); if (i<j)

{ int t=A[i]; A[i]=A[j]; A[j]=t; } else return j;

}}

void Quick(float *A,int p,int r)

{if (p<r) {

int q=Partitie(A,p,r);Quick(A,p,q);Quick(A,q+1,r);

}}