DESCRIEREA ALGORITMILOR
1.1 Algoritm, program, programare
Aparitia primelor calculatoare electronice a
constituit un salt urias in directia automatizarii activitatii umane. Nu
exista astazi domeniu de activitate in care calculatorul sa nu isi
arate utilitatea.
37138rdg26xfj3r
37138rdg26xfj3r
Calculatoarele pot fi folosite pentru a rezolva
probleme, numai daca pentru rezolvarea acestora se concep programe
corespunzatoare de rezolvare. Termenul de program (programare) a suferit
schimbari in scurta istorie a informaticii. Prin anii '60 problemele
rezolvate cu ajutorul calculatorului erau simple si se gaseau algoritmi
nu prea complicati pentru rezolvarea lor. Prin program se intelegea
rezultatul scrierii unui algoritm intr-un limbaj de programare. Din
cauza cresterii complexitatii problemelor, astazi pentru rezolvarea unei
probleme adesea vom concepe un sistem de mai multe programe.
Dar ce este un algoritm? O definitie matematica,
riguroasa, este greu de dat, chiar imposibila fara a introduce si alte
notiuni. Vom incerca in continuare o descriere a ceea ce se intelege
prin algoritm.
Ne vom familiariza cu aceasta notiune prezentand mai
multe exemple de algoritmi si observand ce au ei in comun. Cel mai
vechi exemplu este algoritmul lui Euclid, algoritm care determina cel
mai mare divizor comun a doua numere naturale. Evident, vom prezenta mai
multi algoritmi, cei mai multi fiind legati de probleme accesibile
absolventilor de liceu.
Vom constata ca un algoritm este un text finit, o
secventa finita de propozitii ale unui limbaj. Din cauza ca este
inventat special in acest scop, un astfel de limbaj este numit limbaj de descriere a algoritmilor.
Fiecare propozitie a limbajului precizeaza o anumita regula de calcul,
asa cum se va observa atunci cand vom prezenta limbajul Pseudocod.
df138r7326xffj
Oprindu-ne la semnificatia algoritmului, la efectul
executiei lui, vom observa ca fiecare algoritm defineste o functie
matematica. De asemenea, din toate sectiunile urmatoare va reiesi foarte
clar ca un algoritm este scris pentru rezolvarea unei probleme. Din mai
multe exemple se va observa insa ca, pentru rezolvarea aceleasi
probleme, exista mai multi algoritmi.
Pentru fiecare problema P exista date presupuse cunoscute (date initiale pentru algoritmul corespunzator, A)
si rezultate care se cer a fi gasite (date finale). Evident, problema
s-ar putea sa nu aiba sens pentru orice date initiale. Vom spune ca
datele pentru care problema P are sens fac parte din domeniul D al algoritmului A. Rezultatele obtinute fac parte dintr-un domeniu R, astfel ca executand algoritmul A cu datele de intrare xID vom obtine rezultatele rIR. Vom spune ca A(x)=r si astfel algoritmul A defineste o functie
A : D ---> R .
Algoritmii au urmatoarele caracteristici: generalitate, finitudine si unicitate.
Prin generalitate se intelege faptul ca un algoritm este aplicabil pentru orice date initiale xID. Deci un algoritm A nu rezolva problema P
cu niste date de intrare, ci o rezolva in general, oricare ar fi aceste
date. Astfel, algoritmul de rezolvare a unui sistem liniar de n ecuatii cu n necunoscute prin metoda lui Gauss, rezolva orice sistem liniar si nu un singur sistem concret.
Prin finitudine se intelege ca textul
algoritmului este finit, compus dintr-un numar finit de propozitii. Mai
mult, numarul transformarilor ce trebuie aplicate unei informatii
admisibile xID pentru a obtine rezultatul final corespunzator este finit.
Prin unicitate se intelege ca toate transformarile prin care trece informatia initiala pentru a obtine rezultatul rIR
sunt bine determinate de regulile algoritmului. Aceasta inseamna ca
fiecare pas din executia algoritmului da rezultate bine determinate si
precizeaza in mod unic pasul urmator. Altfel spus, ori de cate ori am
executa algoritmul, pornind de la aceeasi informatie admisibila xID, transformarile prin care se trece si rezultatele obtinute sunt aceleasi.
In descrierea algoritmilor se folosesc mai multe limbaje de descriere, dintre care cele mai des folosite sunt:
- limbajul schemelor logice;
- limbajul Pseudocod.
In continuare vom folosi pentru descrierea
algoritmilor limbajul Pseudocod care va fi definit in cele ce urmeaza.
In ultima vreme schemele logice sunt tot mai putin folosite in
descrierea algoritmilor si nu sunt deloc potrivite in cazul problemelor
complexe. Prezentam insa si schemele logice, care se mai folosesc in
manualele de liceu, intrucat cu ajutorul lor vom preciza in continuare
semantica propozitiilor Pseudocod.
1.2 Scheme logice
Schema logica este un mijloc de descriere a
algoritmilor prin reprezentare grafica. Regulile de calcul ale
algoritmului sunt descrise prin blocuri (figuri geometrice) reprezentand
operatiile (pasii) algoritmului, iar ordinea lor de aplicare
(succesiunea operatiilor) este indicata prin sageti. Fiecarui tip de
operatie ii este consacrata o figura geometrica (un bloc tip) in
interiorul careia se va inscrie operatia din pasul respectiv.
Prin executia unui algoritm descris printr-o
schema logica se intelege efectuarea tuturor operatiilor precizate prin
blocurile schemei logice, in ordinea indicata de sageti.
In descrierea unui algoritm, deci si intr-o schema
logica, intervin variabile care marcheaza atat datele cunoscute initial,
cat si rezultatele dorite, precum si alte rezultate intermediare
necesare in rezolvarea problemei. Intrucat variabila joaca un rol
central in programare este bine sa definim acest concept. Variabila
defineste o marime care isi poate schimba valoarea in timp. Ea are un
nume si, eventual, o valoare. Este posibil ca variabila inca sa nu fi
primit valoare, situatie in care vom spune ca ea este neinitializata.
Valorile pe care le poate lua variabila apartin unei multimi D pe care o
vom numi domeniul variabilei. In concluzie vom intelege prin variabila
tripletul
(nume, domeniul D, valoare)
unde valoare apartine multimii D È {nedefinit}.
Blocurile delimitatoare Start si Stop
(Fig.1.2.1.a si 1.2.1.b) vor marca inceputul respectiv sfarsitul unui
algoritm dat printr-o schema logica. Descrierea unui algoritm prin
schema logica va incepe cu un singur bloc Start si se va termina cu cel putin un bloc Stop.
Blocurile de intrare/iesire Citeste si Tipareste
(Fig. 1.2.1.c si d) indica introducerea unor Date de intrare respectiv
extragerea unor Rezultate finale. Ele permit precizarea datelor initiale
cunoscute in problema si tiparirea rezultatelor cerute de problema.
Blocul Citeste initializeaza variabilele din lista de intrare cu valori corespunzatoare, iar blocul Tipareste va preciza rezultatele obtinute (la executia pe calculator cere afisarea pe ecran a valorilor expresiilor din lista de iesire).
Blocurile de atribuire (calcul) se utilizeaza in descrierea operatiilor de atribuire (:=). Printr-o astfel de operatie, unei variabile var i se atribuie valoarea calculata a unei expresii expr (Fig.1.2.1.e).
Fig.1.2.1. Blocurile schemelor logice
Blocurile de decizie marcheaza punctele de ramificatie ale algoritmului in etapa de decizie. Ramificarea poate fi dubla (blocul logic, Fig.1.2.1.f) sau tripla (blocul aritmetic, Fig. 1.2.1.g). Blocul de decizie logic indica ramura pe care se va continua executia algoritmului in functie de indeplinirea (ramura Da) sau neindeplinirea (ramura Nu)
unei conditii. Conditia care se va inscrie in blocul de decizie logic
va fi o expresie logica a carei valoare poate fi una dintre valorile
"adevarat" sau "fals". Blocul de decizie aritmetic va hotari
ramura de continuare a algoritmului in functie de semnul valorii
expresiei aritmetice inscrise in acest bloc, care poate fi negativa,
nula sau pozitiva.
Blocurile de conectare marcheaza
intreruperile sagetilor de legatura dintre blocuri, daca din diverse
motive s-au efectuat astfel de intreruperi (Fig.1.2.1.h).
Pentru exemplificare vom da in continuare doua
scheme logice, corespunzatoare unor algoritmi pentru rezolvarea
problemelor P1.2.1 si P1.2.2.
P1.2.1. Sa se rezolve ecuatia de grad doi aX2+bX+c=0 (a,b,cIR _i a¹0).
Metoda de rezolvare a ecuatiei de gradul doi este
cunoscuta. Ecuatia poate avea radacini reale, respectiv complexe,
situatie recunoscuta dupa semnul discriminantului d = b2 - 4ac.
Algoritmul de rezolvare a problemei va citi mai intai datele problemei, marcate prin variabilele a, b si c. Va calcula apoi discriminantul d si va continua in functie de valoarea lui d, asa cum se poate vedea in fig.1.2.2.
Fig.1.2.2. Algoritm pentru rezolvarea ecuatiei de gradul doi.
P1.2.2. Sa se calculeze suma elementelor pozitive ale unui sir de numere reale dat.
Schema logica (data in Fig.1.2.3) va contine imediat
dupa blocul START un bloc de citire, care precizeaza datele cunoscute
in problema, apoi o parte care calculeaza suma ceruta si un bloc de
tiparire a sumei gasite, inaintea blocului STOP. Partea care calculeaza
suma S ceruta are un bloc pentru initializarea cu 0 a acestei sume, apoi blocuri pentru parcurgerea numerelor: x1, x2…xn si adunarea celor pozitive la suma S. Pentru aceasta parcurgere se foloseste o variabila contor i, care este initializata cu 1 si creste mereu cu 1 pentru a atinge valoarea n, indicele ultimului numar dat.
Fig.1.2.3. Algoritm pentru calculul unei sume.
Schemele logice dau o reprezentare grafica a
algoritmilor cu ajutorul unor blocuri de calcul. Executia urmeaza sensul
indicat de sageata, putand avea loc reveniri in orice punct din schema
logica. Din acest motiv se poate obtine o schema logica incalcita, greu
de urmarit. Rezulta importanta compunerii unor scheme logice structurate
(D-scheme, dupa Djikstra), care sa contina numai anumite structuri
standard de calcul si in care drumurile de la START la STOP sa fie usor
de urmarit.
1.3. Limbajul PSEUDOCOD
Limbajul Pseudocod este un limbaj inventat in scopul
proiectarii algoritmilor si este format din propozitii asemanatoare
propozitiilor limbii romane, care corespund structurilor de calcul
folosite in construirea algoritmilor. Acesta va fi limbajul folosit de
noi in proiectarea algoritmilor si va fi definit in cele ce urmeaza.
Tinand seama ca obtinerea unui algoritm pentru rezolvarea unei probleme
nu este intotdeauna o sarcina simpla, ca in acest scop sunt folosite
anumite metode pe care le vom descrie in capitolele urmatoare, in
etapele intermediare din obtinerea algoritmului vom folosi propozitii
curente din limba romana. Acestea sunt considerate elemente nefinisate
din algoritm, asupra carora trebuie sa se revina si le vom numi
propozitii nestandard. Deci limbajul Pseudocod are doua tipuri de
propozitii: propozitii standard, care vor fi prezentate fiecare cu sintaxa si semnificatia (semantica) ei si propozitii nestandard. Asa cum se va arata mai tarziu, propozitiile nestandard sunt texte care descriu parti ale algoritmului inca incomplet elaborate, nefinisate, asupra carora urmeaza sa se revina.
Pe langa aceste propozitii standard si nestandard, in textul algoritmului vom mai introduce propozitii explicative, numite comentarii.
Pentru a le distinge de celelalte propozitii, comentariile vor fi
inchise intre acolade. Rolul lor va fi explicat putin mai tarziu.
Propozitiile standard ale limbajului
Pseudocod folosite in aceasta lucrare, corespund structurilor de calcul
prezentate in figura 1.3.1 si vor fi prezentate in continuare. Fiecare
propozitie standard incepe cu un cuvant cheie, asa cum se va vedea in
cele ce urmeaza. Pentru a deosebi aceste cuvinte de celelalte denumiri,
construite de programator, in acest capitol vom scrie cuvintele cheie cu
litere mari. Mentionam ca si propozitiile simple se termina cu
caracterul ';' in timp ce propozitiile compuse, deci cele in interiorul
carora se afla alte propozitii, au un marcaj de sfarsit propriu. De
asemenea, mentionam ca propozitiile limbajului Pseudocod vor fi luate in
seama in ordinea intalnirii lor in text, asemenea oricarui text al
limbii romane.
Prin executia unui algoritm descris in Pseudocod se intelege efectuarea operatiilor precizate de propozitiile algoritmului, in ordinea citirii lor.
In figura 1.3.1, prin A, B s-au notat subscheme
logice, adica secvente de oricate structuri construite conform celor
trei reguli mentionate in continuare.
Structura secventiala (fig.1.3.1.a) este
redata prin concatenarea propozitiilor, simple sau compuse, ale
limbajului Pseudocod, care vor fi executate in ordinea intalnirii lor in
text. Propozitiile simple din limbajul Pseudocod sunt CITESTE,
TIPARESTE, FIE si apelul de subprogram. Propozitiile compuse corespund
structurilor alternative si repetitive.
Structura alternativa (fig.1.3.1.b) este redata in Pseudocod prin propozitia DACA, prezentata in sectiunea 1.3.2, iar structura repetitiva din fig.1.3.1.c este redata in Pseudocod prin propozitia CÂT TIMP, prezentata in sectiunea 1.3.3.
Bohm si Jacopini [Bohm66] au demonstrat ca orice algoritm poate fi descris folosind numai aceste trei structuri de calcul.
Propozitiile DATE si REZULTATE sunt folosite in faza de specificare a problemelor, adica enuntarea riguroasa a acestora.
4 5 6
a) structura b) structura c) structura
secventiala alternativa repetitiva Figura 1.3.1. Structurile elementare de calcul
Propozitia DATE se foloseste pentru
precizarea datelor initiale, deci a datelor considerate cunoscute in
problema (numite si date de intrare) si are sintaxa:
DATE lista ;
unde lista contine toate numele variabilelor a
caror valoare initiala este cunoscuta. In general, prin lista se
intelege o succesiune de elemente de acelasi fel despartite prin
virgula. Deci in propozitia DATE, in dreapta acestui cuvant se vor scrie acele variabile care marcheaza marimile cunoscute in problema.
Pentru precizarea rezultatelor dorite se foloseste propozitia standard
REZULTATE lista ;
in constructia "lista" ce urmeaza dupa cuvantul REZULTATE fiind trecute numele variabilelor care marcheaza (contin) rezultatele cerute in problema.
Acum putem preciza mai exact ce intelegem prin
cunoasterea completa a problemei de rezolvat. Evident, o problema este
cunoscuta atunci cand se stie care sunt datele cunoscute in problema si
ce rezultate trebuiesc obtinute. Deci pentru cunoasterea unei probleme
este necesara precizarea variabilelor care marcheaza date considerate
cunoscute in problema, care va fi reflectata printr-o propozitie DATE si cunoasterea exacta a cerintelor problemei, care se va reflecta prin propozitii REZULTATE.
Variabilele prezente in aceste propozitii au anumite semnificatii,
presupuse cunoscute. Cunoasterea acestora, scrierea lor explicita,
formeaza ceea ce vom numi in continuare specificarea problemei. Specificarea unei probleme este o activitate foarte importanta dar nu si simpla.
De exemplu, pentru rezolvarea ecuatiei de gradul al doilea, specificarea problemei, scrisa de un incepator, poate fi:
DATE a,b,c; { Coeficientii ecuatiei }
REZULTATE x1,x2; { Radacinile ecuatiei }
Aceasta specificatie este insa incompleta daca
ecuatia nu are radacini reale. In cazul in care radacinile sunt complexe
putem nota prin x1, x2 partea reala respectiv partea imaginara a
radacinilor. Sau pur si simplu, nu ne intereseaza valoarea radacinilor
in acest caz, ci doar faptul ca ecuatia nu are radacini reale. Cu alte
cuvinte avem nevoie de un mesaj care sa ne indice aceasta situatie (vezi
schema logica 1.2.2), sau de un indicator, fie el ind. Acest
indicator va lua valoarea 1 daca radacinile sunt reale si valoarea 0 in
caz contrar. Deci specificatia corecta a problemei va fi
DATE a,b,c; { Coeficientii ecuatiei }
REZULTATE ind, {Un indicator: 1=radacini reale, 0=complexe}
x1,x2; { Radacinile ecuatiei, in cazul ind=1,}
{respectiv partea reala si cea }
{imaginara in cazul ind=0}
Evident ca specificarea problemei este o etapa
importanta pentru gasirea unei metode de rezolvare si apoi in
proiectarea algoritmului corespunzator. Nu se poate rezolva o problema
daca aceasta nu este bine cunoscuta, adica nu avem scrisa specificarea
problemei. Cunoaste complet problema este prima regula ce trebuie respectata pentru a obtine cat mai repede un algoritm corect pentru rezolvarea ei.