Algoritmi

1 Notiunea de algoritm

^In termeni generali un algoritm este o metoda de rezolvare pas cu pas a problemelor. O problema se

considera a constituita din date de intrare si un enunt care specica relatia existenta ^ntre datele

de intrare si solutia problemei. ^In cadrul algoritmului sunt descrise prelucrarile necesare pentru a

obtine solutia problemei pornind de la datele de intrare. ^In continuare consideram ca

Un algoritm este o succesiune bine precizata de prelucrari care aplicate asupra datelor

de intrare ale unei probleme permit obtinerea ^n timp nit a solutiei acesteia.

Termenul de algoritm provine de la numele unui matematician persan, al-Khowarizmi (al-

Kwarizmi), ce a trait ^n secolul al IX-lea si care a scris o lucrare despre efectuarea calculelor

numerice ^ntr-o maniera algebrica. Primul algoritm se considera a algoritmul lui Euclid (utilizat

pentru determinarea celui mai mare divizor comun a doua numere naturale).

Termenul de algoritm poate ^nteles ^n sens larg neind neaparat legat de rezolvarea unei

probleme cu caracter stiintic, ci doar pentru a descrie ^ntr-o maniera ordonata activitati care

constau ^n parcurgerea unei succesiuni de pasi (cum este de exemplu utilizarea unui telefon public

sau a unui bancomat). ^In matematica exista o serie de algoritmi: cel al rezolvarii ecuatiei de

gradul doi, algoritmul lui Eratostene (pentru generarea numerelor prime mai mici dec^at o anumita

valoare), schema lui Horner (pentru determinarea c^atului si restului ^mpartirii unui polinom la un

binom) etc.

Solutia problemei se obtine prin executia algoritmului. Algoritmul poate executat pe o masina

formala (^n faza de proiectare si analiza) sau pe o masina zica (calculator) dupa ce a fost codi-

cat ^ntr-un limbaj de programare. Spre deosebire de un program, care depinde de un limbaj de

programare, un algoritm este o entitate matematica, descrisa folosind un limbaj specic, care este

independenta de masina pe care va executat.

2 Obiectul disciplinei

Obiectul disciplinei de "Algoritmica" ^l reprezinta studiul algoritmilor din perspectiva elaborarii si

analizei lor. Descoperirea, selectia, adaptarea si analiza algoritmilor reprezinta un element cheie in

dezvoltarea produselor software.

Dezvoltarea unui algoritm pornind de la problema de rezolvat presupune parcurgerea urmatoarelor

etape:

1. Formularea clara, completa si neambigua a problemei, eventual prin utilizarea unor specicatii

formale.

2. Identicarea clasei din care face parte problema.

3. Identicarea unui algoritm care permite constructia solutiei pornind de la specicatiile problemei.

4. Analiza corectitudinii algoritmului (are ca scop sa verice daca algoritmul corespunde specicatiilor

problemei).

5. Analiza ecientei algoritmului (are ca scop sa verice daca solutia poate obtinuta prin

utilizarea unui volum rezonabil de resurse).

Elaborarea unui algoritm necesita: cunostinte specice domeniului de unde provine problema

de rezolvat (necesare pentru o mai buna ^ntelegere a problemei), cunoasterea unor tehnici generale

de rezolvare a problemelor (utile pentru a identica algoritmul adecvat unui problemei de rezolvat)

intuitie si g^andire algoritmica (acestea se dob^andesc si se dezvolta prin experienta).

Indiferent de complexitatea unei aplicatii informatice, la bazele ei stau algoritmi destinati rezolv

arii problemelor fundamentale ale aplicatiei. Oric^at de sosticata ar tehnologia software

utilizata (interfete, structurare globala a aplicatiei) ecienta aplicatiei este ^n mod esential determinat

a de ecienta algoritmilor implicati. Un algoritm prost conceput nu poate "reparat" prin

articii de programare. Din acest motiv dob^andirea unor cunostinte solide privind elaborarea si

analiza algoritmilor este o conditie necesara ^n formarea unui bun programator.

3 Proprietati ale algoritmilor

Un algoritm trebuie sa posede urmatoarele proprietati:

Generalitate. Un algoritm destinat rezolvarii unei probleme trebuie sa permita obtinerea rezultatului

pentru orice date de intrare nu numai pentru valori particulare ale acestora.

Finitudine. Un algoritm trebuie sa admita o descriere nita si ecare dintre prelucrarile pe care

le contine trebuie sa poate executata ^n timp nit. Prin intermediul algoritmilor nu pot

prelucrate structuri innite.

Rigurozitate. Prelucrarile algoritmului trebuie specicate riguros, fara ambiguitati. ^In orice etapa

a executiei algoritmului trebuie sa se stie exact care este urmatoarea etapa ce va executata.

Ecienta. Algoritmii pot efectiv utilizati doar daca folosesc resurse de calcul ^n volum acceptabil.

Resursele de calcul se refera la spatiul de memorie necesar pentru stocarea datelor si timpul

necesar pentru executie.