Proprietatile algoritmilor

Proprietatile algoritmilor

Un algoritm trebuie sa aiba urmatoarele trei proprietati fundamentale, numite si proprietatile de baza ale algoritmilor:

1. Claritatea. Orice algoritm trebuie sa fie caracterizat printr-o descriere precisa, riguroasa, fara ambiguitati a tuturor actiunilor ce urmeaza a fi executate. Un algoritm, datorita caracterului sau de automatism, trebuie sa precizeze in mod univoc toate etapele de calcul pe care le va urma executantul algoritmului (omul sau masina). De aceea, aceasta proprietate este denumita uneori si unicitate.

2. Generalitatea. Un algoritm este util daca rezolva nu numai o problema particulara, concreta, ci o intreaga clasa de probleme asemanatoare. Aceasta inseamna ca un algoritm trebuie sa se aplice la o multime de sisteme de date initiale. Aceasta multime poarta numele de domeniu de aplicabilitate al algoritmului.

De exemplu, algoritmul lui Euclid se poate aplica la orice pereche de numere naturale strict pozitive. Vom spune deci ca domeniul de aplicabilitate al algoritmului lui Euclid este multimea perechilor de numere naturale, mai putin zero (N* x N*). Aceasta proprietate este cunoscuta si sub numele de universalitate.

3. Eficacitatea. Executarea unui algoritm urmareste intotdeauna obtinerea unui anumit rezultat.

Deoarece nu este suficient ca actiunile algoritmului sa fie bine determinate, ci trebuie ca pentru orice sistem de date initiale, numarul de actiuni (pasi)ce trebuie executate sa fie finit, aceasta proprietate poarta denumirea si de finitudine. La exemplele de algoritmi prezentate anterior s-a aratat ca numarul de pasi corespunzatori unui sistem oarecare de date initiale este finit.

Se poate spune, in concluzie, ca un algoritm reprezinta o secventa finita de operatii, ordonata si complet definita, care, pornind de la o anumita valoare sau o multime de valori ca date de intrare, produce o anumita valoare sau multime de valori ca date de iesire.

Exemplul 1.2

Sa consideram o problema simpla:

Un dreptunghi are baza de 2,75 si inaltimea de 1,4 unitati. Care sunt aria si perimetrul dreptunghiului?

Enuntul de mai sus furnizeaza persoanei care rezolva problema urmatoarele informatii:

se are in vedere un dreptunghi;

baza dreptunghiului este de 2,75 unitati;

inaltimea dreptunghiului este de 1,4 unitati;

se cer aria si perimetrul dreptunghiului.

Enuntul nu contine decat o descriere a problemei, nu si curs in care ea trebuie rezolvata. Remarcam ca persoana care rezolva aceasta problema trebuie sa aiba o serie de cunostinte: ce este un dreptunghi, ce sunt baza si inaltimea dreptunghiului, care sunt formulele de calcul pentru aria si perimetrul dreptunghiului, care sunt unitatile de masura si relatiile dintre ele. Pe baza acestor cunostinte, persoana respectiva deduce ca:

si 1,4 sunt de fapt masurile bazei si respectiv inaltimii dreptunghiului, exprimate in unitati dimensionale de lungime;

aria se poate calcula aplicand formula arie = baza * inaltime (unde '*' este operatorul de inmultire);

perimetrul se poate calcula cu formula perimetru = (baza +inaltime)*2;

Daca am dori ca si calculatorul sa rezolve aceasta problema la fel cum o face omul, ar trebui sa aiba aceleasi cunostinte, ceea ce se incearca acum sa se realizeze in cadrul sistemelor de inteligenta artificiala prin sisteme de programe adecvate acestui scop. Calculatorul in sine este insa o simpla 'masina', care poate executa fidel, rapid si bine niste comenzi, dar nu intelege ceea ce face.

Intreaga responsabilitate a rezolvarii problemei revine celui care intocmeste 'programul', care trebuie sa stabileasca succesiunea de instructiuni (comenzi) pe care trebuie sa le execute calculatorul pentru a rezolva problema. Sa vedem deci cum am putea concepe o succesiune de instructiuni, a carei executare de catre sistem (fie acesta un om sau o masina) sa conduca de la ce 'se da' la ce 'se cere' in problema de mai sus, fara a fi necesar ca sistemul sa cunoasca problema sau, cu atat mai mult, sa o inteleaga.

Vom considera ca sistemul care rezolva problema primeste pe un anumit 'suport de intrare' (de exemplu pe o hartie, in cazul omului, sau de la tastatura, in cazul calculatorului) doua numere reale, despre care noi stim ca sunt baza si inaltimea unui dreptunghi, dar el nu stie. Numim aceste numere date de intrare, deoarece ele sunt introduse de noi in sistem.

Vom considera, de asemenea, ca rezultatele obtinute vor trebui scrise de sistem pe un alt suport, care poate fi citit de catre om (de exemplu pe o hartie sau pe un ecran), si le vom numi date de iesire, deoarece ele sunt transmise de sistem catre exteriorul sau. Pentru a 'rezolva problema', sistemul trebuie sa preia datele de intrare (fara sa cunoasca semnificatia lor in problema), sa verifice daca sunt valabile si sa le inregistreze in memorie. Asupra lor trebuie sa aplice apoi niste operatii de calcul, pe baza carora sa obtina rezultatele cerute. Aceste rezultate vor fi si ele inregistrate in memorie, atunci cand sunt obtinute. In fine, rezultatele trebuie transmise in exterior sub forma de date de iesire.

Iata succesiunea de instructiuni care trebuie executate de catre sistem pentru a rezolva problema data:

1. Citeste de pe suportul de intrare un numar real si inregistreaza-l in memorie ca valoare a variabilei b.

2. Citeste de pe suportul de intrare un numar real si inregistreaza-l in memorie ca valoare a variabilei i.

3. Daca valoarea b este nula sau negativa sau daca valoarea i este nula sau negativa, atunci scrie pe suportul de iesire textul 'datele de intrare sunt gresite' si opreste executarea programului; altfel, treci la pasul urmator.

4. Inmulteste valoarea b cu valoarea i si inregistreaza in memorie ca valoare a variabilei A.

5. Aduna valoarea b cu valoarea i si inregistreaza rezultatul ca valoare a variabilei d.

6. Inmulteste valoarea d cu 2 si inregistreaza rezultatul ca valoare a variabilei p.

7. Scrie pe suportul de iesire textul 'aria dreptunghiului este' urmat de valoarea variabilei A.

8. Scrie pe suportul de iesire textul 'perimetrul dreptunghiului este ' urmat de valoarea variabilei p.

9. Opreste executarea programului.

Se observa imediat ca, pentru a executa aceste instructiuni, sistemul nu trebuie sa cunoasca problema, ci doar sa 'stie' modul in care se realizeaza fiecare operatie cuprinsa in ele: citire de pe suportul de intrare, scriere pe suportul de iesire, comparatie, memorare (inregistrare in memorie), inmultire, adunare, oprirea executiei.

Remarcam, de asemenea, ca in aceste instructiuni se opereaza cu niste numere sau texte care nu au pentru sistem nici o alta semnificatie. Astfel de 'materiale supuse prelucrarii' care nu au pentru sistem nici o alta semnificatie se numesc date, iar ansamblul tuturor instructiunilor (comenzilor) care trebuie executate astfel incat, pornind de la datele de intrare, sa se obtina datele de iesire, se numeste algoritm.

Daca algoritmul se executa de catre un calculator, fiecare data (de intrare, de iesire sau rezultat intermediar) este inregistrata in memoria interna a acestuia la o anumita adresa care este un numar. In consecinta, instructiunea 1, de exemplu, ar fi trebuit scrisa astfel:Citeste de pe suportul de intrare un numar real si inregistreaza-l in memorie la adresa 1724.

La fel ar fi trebuit sa procedam si cu celelalte date, fie ele de intrare, de iesire sau auxiliare. Evident ca, pentru om, o astfel de notatie este foarte incomoda. Din aceasta cauza, in algoritmi si in programe se prefera sa se foloseasca pentru indicarea locului in care se gasesc datele in memorie niste nume simbolice, numite variabile. Conversia acestor nume de variabile in adrese de memorie este una din sarcinile care revin compilatorului, atunci cand genereaza programul binar. Este deci bine sa retinem ca, din punctul de vedere al compilatorului, variabilele sunt nume date adreselor de memorie la care sunt plasate anumite date.

Se obisnuieste, de asemenea, ca instructiunile cuprinse in algoritm sa fie scrise intr-o forma mai compacta, retinand numai cuvintele cheie si numele variabilelor si eliminand cuvintele de prisos. Se obisnuieste, de asemenea, ca operatiile aritmetice sa fie scrise sub forma de formule matematice si nu prin cuvinte. Procedand astfel, algoritmul de mai sus poate fi scris sub forma:

Citeste b

Citeste i

Daca b<=0, atunci Scrie 'datele de intrare sunt gresite';

Stop

Calculeaza A= b*i

Calculeaza d=b+i

Calculeaza p=d*

Scrie 'aria dreptunghiului este ' A;

Scrie 'perimetrul dreptunghiului este ' p;

Stop

Este evident ca citirea se face de pe suportul de intrare si ca datele citite se inregistreaza in memorie. Prin simbolul '<=' s-a notat operatia de comparatie 'mai mic sau egal'. Prin simbolul '=' s-a notat operatia de atribuire, prin care variabilei din partea stanga i se atribuie (i se da) valoarea din partea dreapta, iar prin simbolul '*' s-a notat operatia de inmultire.

O observatie importanta este ca algoritmul prezentat aici poate fi folosit oricand este necesar sa se calculeze aria si perimetrul unui dreptunghi, avand ca date de intrare baza dreptunghiului si inaltimea acestuia. Setul de date de intrare este constituit, in acest caz, din doua numere reale pozitive. Caracterul universal al algoritmului consta in faptul ca el poate fi aplicat oricarui astfel de set de date.

Test de autoevaluare 1.2

Completati spatiile libere din urmatoarele intrebari. Fiecare intrebare valoreaza 20 de puncte.

1. Proprietatea unui algoritm de a rezolva o intreaga clasa de probleme asemanatoare se numeste  ......

2. Proprietatea algoritmului numita claritate mai este cunoscuta si cu denumirea.

3. Un algoritm trebuie sa precizeze in mod .........toate etapele de calcul ce vor fi executate.

4. Multimea sistemelor de date initiale se numeste ..

5. Numarul de pasi ce trebuie sa fie executati intr-un algoritm trebuie sa fie , iar aceasta proprietate poarta denumirea de ..