Algoritmi și Programare

În anul 1642, matematicianul si fizicianul Blaise Pascal (1623-1662) a inventat prima masina

mecanica, cu roCi dinCate, capabila sa realizeze operaCii de adunare si scadere a numerelor naturale. Totusi,

de-abia dupa apariCia masinilor electromecanice, în 1944, John von Neumann a formulat principiul

programului înregistrat si a sugerat constructorilor de calculatoare trei principii care trebuie avute în vedere

pentru realizarea unui calculator:

• programele si datele trebuie sa fie codificate sub forma binara;

• programele si datele trebuie stocate într-o memorie a masinii de calcul;

• trebuie sa existe o componenta (unitate centrala de prelucrare, procesor) speciala care stie atât sa

execute operaCii de calcul, cât si sa extraga, sa decodifice si sa execute instrucCiunile programului.

Astfel, aproape toate tipurile de sisteme de calcul ce au aparut mai târziu sunt calculatoare de tip von

Neumann.

ApariCia sistemelor de calcul a dus la apariCia si dezvoltarea unei noi stiinCe: informatica

(Informatique, Informatics, Informatik în Europa, respectiv Computer Science în SUA). Informatica

reprezinta un complex de discipline prin care se asigura prelucrarea informaCiilor cu ajutorul sistemelor de

calcul. Astazi, informatica este prezenta în industrie, banci, ferme, arta, medicina, stiinCe sociale etc. si este

structurata în mai multe domenii precum:

• arhitectura sistemelor de calcul: studiaza modul de organizare a sistemului fizic (hardware) pentru a

se obCine o mai mare eficienta, siguranCa si utilitate.

• sisteme de operare: studiaza modalitaCile de gestiune eficienta a resurselor fizice si a programelor.

• algoritmi si structuri de date: studiaza metodele de rezolvare a problemelor si modurile de

organizare a datelor pentru a obCine programe eficiente.

• limbaje de programare: studiaza modalitaCile prin care algoritmii si structurile de date sunt

prezentate calculatorului pentru a fi prelucrate.

• ingineria programarii: studiaza metodele de automatizare a proceselor de proiectare, analiza, testare

si reutilizare a programelor.

• calcule numerice si simbolice: studiaza modalitaCile de reprezentare a informaCiei numerice pentru

implementarea unor algoritmi numerici robusti, eficienCi si de mare precizie.

• sisteme de gestiune a bazelor de date: studiaza modalitaCile de structurare si organizare eficienta a

colecCiilor mari de date ce vor fi supuse diverselor prelucrari.

• inteligenCa artificiala: studiaza modalitaCile de reprezentare si manipulare a cunostinCelor în vederea

obCinerii de noi cunostinCe.

• animaCia si robotica: studiaza modalitaCile de reprezentare, prelucrare si analiza a informaCiei audio-

vizuale.

În sfera sa de preocupari, informatica a atras si dezvoltat o mare varietate de discipline precum: logica

matematica, teoria automatelor, limbaje formale, cercetari operaCionale, teoria grafurilor si reCelelor, calcul numeric,

teoria fiabilitaCii, geometrie computaCionala, teoria calculabilitaCii, baze de date, baze de cunostinCe, sisteme expert .

I.2. Ce este un program? NoCiunea de algoritm

SoluCia unei probleme, din punct de vedere informatic, este data printr-o mulCime de comenzi

(instrucCiuni) explicite si neambigue, exprimate într-un limbaj de programare. Aceasta mulCime de

instrucCiuni prezentata conform anumitor reguli sintactice formeaza un program. Un program poate fi privit

si ca un algoritm exprimat într-un limbaj de programare. Totusi, un algoritm descrie soluCia problemei

independent de limbajul de programare în care este redactat programul.

Exista mai multe definiCii ale noCiunii de algoritm. A. A. Markov, a considerat algoritmul ca fiind o

noCiune matematica primara si a descris-o astfel: Un algoritm este o reCeta care descrie precis si clar un

proces de calcul. El a descris un mecanism formal pentru a specifica o clasa larga de activitaCi si anume:

216

algoritmii normali. Alte modalitaCi de descriere a algoritmilor ce au mai fost propuse sunt: masina Turing,

sistemele Post, funcCiile recursive etc. În aceasta lucrare, prin algoritm vom înCelege o secvenCa finita de

comenzi explicite si neambigue care, executate pentru o mulCime de date (ce satisfac anumite condiCii

iniCiale), conduce în timp finit la rezultatul corespunzator. Observam ca se face distincCie între algoritm (care

se termina în timp) si procedura (care poate continua nedefinit).

Conform lui D. Knuth (The art of computer programming, Vol. I, 1997) un algoritm poseda cinci

caracteristici importante:

• Un algoritm are caracter finit. El este descris printr-o secvenCa finita de etape si trebuie ca, ori de

câte ori sunt parcurse etapele algoritmului pentru anumite date, procesul sa se încheie în timp finit.

• Un algoritm are caracter determinist. AcCiunile specificate de pasii algoritmului sunt clare, fiind

riguros prezentate.

• Un algoritm are date de intrare. Se poate admite ca întotdeauna un algoritm lucreaza asupra unor

date de intrare. Acestea pot fi evidenCiate din contextul în care este formulata problema a carei

soluCie o reprezinta algoritmul.

• Un algoritm furnizeaza cel puCin o valoare de iesire ce se afla într-o relaCie specifica cu datele de

intrare.

• Un algoritm este eficace.

Trebuie spus ca nu orice problema admite soluCie descrisa algoritmic. Problemele pentru care exista

un algoritm de rezolvare se numesc probleme decidabile. Problemele pentru care s-a demonstrat (matematic)

ca nu admit un algoritm de rezolvare se numesc probleme nedecidabile. Nu este suficient ca o anumita

problema (clasa de probleme) sa admita soluCii (chiar si o singura soluCie). Din punctul de vedere al

informaticii, intereseaza daca exista soluCie ce poate fi descrisa algoritmic, deci daca soluCia problemei poate

fi construita efectiv. De asemenea, pentru rezolvarea anumitor probleme pot exista mai mulCi algoritmi.

Stabilirea celui mai bun dintre acestia se realizeaza în urma unui proces de analiza prin care se determina

performantele fiecaruia dintre algoritmi.

Am vazut ca algoritmii accepta date de intrare si furnizeaza rezultate (date de iesire). Introducerea

unei valori sau a unui sir de valori se va descrie folosind verbul citeste. Afisarea unei valori sau a unui sir de

valori va fi descrisa prin verbul scrie. Vom conveni sa numerotam pasii (etapele) unui algoritm. Aceasta

numerotare va fi utilizata eventual în alCi pasi. Acest mod de prezentare a algoritmilor se numeste descriere

în limbaj convenCional. În unele lucrari, limbajul convenCional mai este numit si limbaj pseudocod.