ALGORITMI SI METODE DE REPREZENTARE

ALGORITMI sI METODE DE REPREZENTARE

Algoritmi

Algoritmul este o regula de calcul (reteta) care permite ca pentru o anumita clasa de probleme sa se obtina solutia acestora, pornind de la datele initiate, prin intermediul unui sir ordonat de operatii efectuate cvasimecanic.

Cel care a utilizat primul aceasta definitie a algoritmului este matematicianul si filozoful german G. W. Leibnnitz (1646-1716).

Caracteristicile algoritmilor

Pentru a putea fi utilizat in programarea calculatoarelor, un algoritm trebuie sa indeplineasca trei conditii principale:

Generalitatea

Un algoritm este creat cu scopul de a rezolva o clasa de probleme, deci el trebuie sa raspunda adecvat unei multimi de date de intrare (initiale). De exemplu, un algoritm avand ca scop determinarea coordonatelor unui punct prin metoda intersectiei inainte trebuie sa poata rezolva problema indiferent de datele de intrare, adica indiferent de pozitia punctelor pe suprafata terestra.

Eficacitatea

Rezolvarea problemei din clasa pentru care a fost conceput trebuie sa se faca, indiferent de sistemul de date initiale, intr-un numar finit de operatii. Algoritmul trebuie sa "reactioneze" corespunzator in toate situatiile posibile (pentru exemplul dat, algoritmul trebuie sa rezolve si cazul cand diferensele dintre orientarile directiilor din punctele vechi catre punctul nou sunt apropiate de 0^g sau 200^g).

Claritatea

Toate operatiile ce urmeaza a fi efectuate pentru rezolvarea problemei date (inclusiv cazurile limita) trebuie sa fie descrise riguros, fara ambiguitati. Deci, un algoritm trebuie sa poata fi executat automat (mecanic), pornind de la precizarea univoca a etapelor de prelucrare implicate, fara ca cel care rezolva problema (masina sau om) sa cunoasca natura acesteia. Din acest punct de vedere, este necesar ca algoritmul sa includa tratarea corespunzatoare a tuturor situatiilor care s-ar putea ivi si sa nu lase pe seama calculatorului rezolvarea unor cazuri care aparent contrazic datele problemei sau logica. Pentru acelasi exemplu, algoritmul creat ar trebui sa includa o secventa de operatii prin care sa se verifice daca valorile efectiv introduse se incadreaza in multimea de valori posibile (directii unghiulare orizontal 636d34g e cuprinse in intervalul [0,400]). Cu alte cuvinte, inainte de efectuarea unei operatii matematice este necesar sa existe siguranta ca valorile implicate fac posibil calculul respectiv (impartire la zero sau la o valoare foarte apropiata de zero, radacina patrata dintr-un numar negativ, arctan dintr-o valoare foarte apropiata de 0, etc.).

Variabile in algoritmi

Pentru a se ajunge la rezultate cautate plecand de la datele initiate, un algoritm trebuie sa cantina o descriere detaliata a tuturor operatiilor si ordinea in care acestea trebuie sa fie efectuate. Indiferent de clasa de probleme pentru care a fost creat, algoritmul efectueaza operatii asupra datelor. O data are sens numai daca ea poate fi regasita. Acest lucru presupune ca data trebuie sa aiba asigurata o anumita durata de viata, cel putin intre momentul inregistrarii si momentul primei utilizari. Perenitatea datei implica existenta unui suport pentru stocarea ei. Deoarece algoritmii sunt elaborati in principal pentru a fi utilizati in prelucrarea datelor cu ajutorul calculatoarelor electronice, operatiile descrise in algoritmi se refera la continutul locatiilor de memorie in care sunt stocate datele (valorile de prelucrat). Referirea la o astfel de valoare se face prin specificarea locatiei de memorie in care aceasta este depozitata, pentru aceasta utilizandu-se niste nume simbolice.

Spre deosebire de algebra, unde variabila reprezinta o necunoscuta a carei valoare urmeaza a fi determinata prin intermediul unor operatii matematice ce se efectueaza asupra ei, in algoritm o variabila reprezinta denumirea unei zone de memorie, zona care contine intotdeauna o valoare (o succesiune de biti).

In algoritmi se pot intalni doua tipuri de variabile, functie de numarul de valori reprezentate: variabile simple (sau scalari) si variabile structurate.

O variabila simpla desemneaza o zona de memorie in care, la un moment dat, poate fi stocata (pastrata) o singura valoare,

O variabila structurata desemneaza o zona de memorie in care se pot stoca simultan, sub un nume comun, mai multe valori.

Dintre variabilele structurate, o utilizare frecventa in algoritmii matematici o au tablourile. Un tablou poate avea una sau mai multe dimensiuni. Astfel, un tablou cu o dimensiune (unidimensional) poate fi asimilat unui vector sau unei liste cu o singura coloana, iar un tablou cu doua dimensiuni (bidimensiona) poate fi asimilat unei matrice. In principiu, pot fi utilizate tablouri cu oricate dimensiuni, daca prin aceasta se asigura cresterea eficacitatii si a gradului de genetalitate, sub rezerva ca unele limbaje de programare sau compilatoare nu accepta decat un numar limitat (3...7 dimensiuni).

Referirea la un element al unui tablou se face prin specificarea numelui tabloului (a zonei de memorie unde sunt stocate valorile variabilei structurate) urmat de un numar de indici egal cu numarul de dimensiuni. Daca ne referim la un element al unui tablou bidimensional (matrice) numit(a) A situat pe linia i coloana j, exista urmatoarele posibilitati de scriere:

A_i,j sau A(i,j) sau A[i,j]

Tipuri de operatii in algoritmi

Rezolvarea unei probleme prin intermediul unui algoritm se face, dupa cum s-a mai specificat, prin parcurgerea cvasimecanica a unui sir ordonat de pasi sau operatii. Operatiile care compun un algoritm se pot imparti in trei categorii principale:

Operatii de intrare / iesire

Aceste operatii se refera la transferul de date intre memoria principala si mediul exterior acesteia. Dupa cum rezulta si din denumire, doua sunt rezultatele acestor operatii: introducerea datelor initiate ale problemei si extragerea rezultatelor (rapoartelor).

Prin operatia de intrare, variabilele (locatiile de memorie) specificate in lista descrisa la pasul respectiv primesc valori dintr-un mediu exterior memoriei principale. Se poate spune ca "se citesc" valori de la un echipament de intrare.

In urma procesului de prelucrare sunt determinate valori care sunt pastrate in diverse locatii de memorie. Pentru a fi utile ele trebuie sa fie transmise, prin intermediul unor echipamente adecvate) mediului exterior memoriei principale. Cu alte cuvinte, prin operatia de iesire, "se scriu" valorile continute in locatiile de memorie specificate in lista variabilelor prezentata la pasul respectiv.

Operatii de calcul (sau de prelucrare)

In algoritm, aceasta operatie este descrisa prin precizarea expresiei simbolice care se evalueaza (se calculeaza) si a variabilei in care se depune valoarea expresiei respective. Un exemplu de operatie de calcul este si acesta:

Executarea acestei operatii de catre calculator consta in adunarea valorii din locatia de memorie (variabila) numita „B” cu valoarea din locatia numita „C”. Rezultatul obtinut este stocat in alta locatie de memorie (variabila) numita „A”. In cazul prezentat, semnul „=” nu are semnificatia cunoscuta din algebra, de egalitate, ci de atribuire.

Aceasta inseamna ca, in algoritmi, o operatie de calcul descrisa sub forma

este absolut corecta, desi relatia este absurda din punct de vedere algebric. La intalnirea acestei operatii, calculatorul va aduna „1” la valoarea din locatia „N” si va stoca numarul astfel obtinut in aceeasi locatie „N”, valoarea anterioara care exista aici fiind pierduta. Astfel, daca „N” contine numarul „0”, dupa efectuarea operatiei de mai sus va contine numarul „1”.

Operatii de decizie

Aceste operatii constau in evaluarea unor expresii logice care au ca rezultat doua valori posibile: „adevarat” sau „fals”. Functie de rezultatul evaluarii, algoritmul se „ramifica”, adica fluxul operatiilor este dirijat pe o cale sau pe alta.

Elaborarea algoritmilor

Se elaboreaza un algoritm care sa rezolve problemele dintr-o anumita clasa, si anume pentru impartirea intreaga a doua numere naturale.

Pentru inceput, trebuie sa se stabileasca "ce se da" si "ce se cere", adica sa se specifice care sunt datele de intrare, ce operatii trebuie sa se efectueze pentru rezolvarea problemei si care sunt rezultatele asteptate.

Algoritmul impartirii intregi (varianta 1)

Algoritmul impartirii intregi a doua numere naturale este urmatorul:

aDatele de intrare sunt constituite din doua numere naturale primul numit deimpartit, al doilea impartitor.

aOperatiile aritmetice si logice care trebuie sa fie efectuate pentru a se ajunge la rezultatele scontate constau in scaderea repetata a impartitorului din deimpartit. Operatia de scadere se efectueaza pana cand rezultatul este (intr-o prima varianta) negativ ceea ce inseamna ca dupa fiecare operatie de scadere trebuie sa se verifice daca s-a obtinut o valoare negativa.

aIn urma efectuarii operatiilor descrise mai sus se obtin alte doua valori, numite cat si rest, ambele numere intregi. Catul este dat de numarul operatiilor de scadere efectuate pana la atingerea valorii negative iar pentru a gasi restul se va anula ultima scadere, prin efectuarea unei adunari intre rezultat si deimpartit.

Algoritmul prezentat nu este unica modalitate de rezolvare corecta a problemei, o alta varianta in care decizia de efectuare a operatiei de scadere se ia inainte ca aceasta sa fie executata, restul obtinandu-se chiar in locaiia de memorie „A”, fara a mai fi necesara adunarea din pasul 7.

Algoritmul impartirii intregi (varianta 2)

Este, posibil sa existe si alte variante de rezolvare a problemei date. Presupunand ca toate variantele sunt corecte, se pune problema alegerii variantei optime. Pentru aceasta trebuie avute in vedere doua criterii principale, uneori contradictorii: economia de memorie (cat mai putine locatii ocupate) si viteza de calcul (cat mai putine operatii de efectuat). In cazul de fata, ambele criterii dau castig variantei 2.

Testarea algoritmului impartirii intregi

Dupa elaborarea algoritmului acesta trebuie testat pentru a se verifica corectitudinea rezolvarii si daca au fost tratate corespunzator toate situatiile care pot aparea la utilizarea practica a algoritmului respectiv. Practic este suficient sa se verifice daca algoritmul raspunde corect la diferite seturi de date alese din toata gama posibila. Unele observatii se pot face chiar inainte de testare. Astfel, la algoritmul in discutie, se poate observa ca nu functioneaza corect daca sunt introduse valori negative sau daca impartitorul este nul. Cu toate ca algoritmul a fast realizat pentru lucrul cu numere naturale, ar fi trebuit totusi sa se introduca secvente prin care datele de intraare sa fie verificate inainte de introducerea lor in calcule. Aceasta operatie, numita validare, trebuie sa opreasca prelucrarea atunci cand datele de intrare sunt necorespunzatoare.

Pentru prima varianta a algoritmului impartirii intregi, se prezinta, cu scop didactic, o posibilitate de testare utilizand un set concret de date initiale, valorile 23 si 5.

Avand in vedere ca o locatie de memorie contine intotdeauna o valoare, pentru a indica faptul ca, la un moment dat, nu se cunoaste continutul respectivei locatii s-a utilizat semnul de intrebare. Aceasta situatie justifica si necesitatea operatiei de initializare din pasul 2.

Reprezentarea algoritmilor

Pentru reprezentarea algoritmilor pot fi utilizate mai multe metode, fiecare avand avantajele si dezavantajele sale.

r Utilizarea unui limbaj natural

Este cea mai simpla metoda de reprezentare (utilizata in exemplele prezentate), dezavantajele sale principale fiind urmatoarele:

urmarirea dificila, mai ales in cazul unor probleme complexe;

o anumita neclaritate si ambiguitate, datorate nestandardizarii modului de exprimare;

lipsa de concizie;

dificultatea intelegerii de catre persoanele care nu vorbesc limba respectiva.

r Utilizarea unui limbaj algoritmic sau pseudocod

In cadrul acestei metode sunt utilizate expresii alcatuite cu ajutorul unui vocabular care contine un numar minim de cuvinte standard (de exemplu: begin, read, write, if...then, do, end, etc.), respectand regulile de scriere care constituie sintaxa limbajului respectiv.

r Reprezentarea grafica

Reprezentarea algoritmilor prin aceasta metoda presupune utilizarea unor simboluri grafice numite blocuri. Reprezentarea grafica a unui algoritm se numeste si schema logica (flowchart).

Deoarece aceasta ultima metoda de reprezentare a algoritmilor este considerata a fi cea mai sugestiva, pentru ca necesita minimum de efort pentru insusire si nu este legata de nici un limbaj, ea a fost aleasa pentru reprezentarea majoritatii algoritmilor.

Observatii privind realizarea schemelor logice

Lista variabilelor (notata, in blocurile de mai sus, lista var. sau l.v.)

In blocurile de intrare (blocurile prin care se specifica ce date se introduc) se trece lista variabilelor care urmeaza sa primeasca valori. De exemplu, blocul de mai jos

reprezinta o operatie de preluare date de la tastatura: se introduc doua valori, prima dintre acestea fiind stocata in locatia de memorie cu numele n iar a doua in locatia de memorie cu numele alfa.

In blocurile de iesire (blocurile prin care se specifica ce date se extrag) lista include deriumirile locatiilor de memorie al caror continut urmeaza a fi "scris" pe un mediu oarecare. Daca acest mediu poate fi perceput direct de catre om (textul afisat pe ecranul monitorului sau tiparit la imprimanta, etc.), atunci lista de iesire poate include si texte care urmeaza a fi reproduse ca atare. Aceste texte explicative se incadreaza intre apostrofuri („”) pentru a le distinge de numele variabilelor. De exemplu, blocul de mai jos reprezinta o operatie de "scriere" pe ecranul monitorului si consta din "afisarea textului "Dist. =", urmata de afisarea valorii din locatia de memorie cu numele d, urmata de afisarea textului"m". Daca in d

s-ar gasi valoarea 273.141, atunci, in urma efectuarii operatiei descrise prin blocul de mai sus, pe ecran s-ar afisa textul: Dist.=273.141 m

In scopul urmaririi cat mai usoare a schemei logice, pe langa preocuparea pentru estetica formei grafice, este necesar sa fie respectate cateva reguli de constructie, ca:

~ Exista blocuri, blocurile terminale, care au fie o iesire (blocul START, de exemplu), fie o intrare (blocul STOP, de exemplu);

~ Blocurile de decizie sunt singurele care au o intrare si doua iesiri;

~ Toate celelalte blocuri au o intrare si o iesire;

~ Intrarea si iesirea, in si dintr-un bloc, se indica prin cate o sageata verticala indreptata in jos si trecand aproximativ prin centrul de greutate al figurii care reprezinta blocu;

~ Blocurile succesive ale unei structuri liniare (care nu include o decizie) se vor plasa pe aceeasi verticala.

Conectorii soot utilizati pentru a evita intersectarea liniilor de legatura intre blocurile unei scheme logice, ca si incarcarea desenului cu linii prea lungi. Intre doi conectori care contin acelasi caracter se considera ca exista o linie (legatura directa) care nu a mai fost desenata. De asemenea, se utilizeaza conectori (de o forma diferita) pentru a marca referirea la un bloc aflat pe alta pagina.

Subprograme

In practica elaborarii algoritmilor (ca si a programelor de aplicatii) apar frecvent situatii in care anumite operatii se repeta. De exemplu, operatia prin care se aduna elementele (valori numerice) ale unui tablou unidimensional (vector) si apoi media acestor elemente poate fi necesara pentru: algoritmul determinarii centrului de greutate al unei retele geodezice planimetrice; algoritmul determinarii unghiului mediu de orientare a unei statii de teodolit; algoritmul determinarii mediei notelor unui student dintr-un anumit an de studiu.

In aceste situatii, evident, este normal sa se creeze o singura data secventele de calcul prin care sa rezolve problema propusa (adunarea unui numar de elemente si calculul mediei), secventa care sa fie utilizata de toti algoritmii care au nevoie de aceste calcule. Integrarea intr-un algoritm sau altul se face prin intermediul blocului de apel subprogram.

Asemenea secvente de calcul se numesc subprograme sau rutine. Cu toate ca atat un program cat si un subprogram rezolva o anumita problema bine determinata, intre ele exista unele diferente, cele mai semnificative fiind prezentate in tabelul de mai jos:

Exista doua tipuri principale de subprograme:

Functii

Acestea transmit programului apelant o singura valoare reprezentata chiar prin numele subprogramului, de exemplu sin(alfa), unde sin este numele functiei apelate, iar alfa este parametrul actual, adica numele variabilei in care se gaseste valoarea pentru care se va calcula functia respectiva;

Proceduri (sau subrutine)

Acestea pot sa nu transmita nici o valoare (de exemplu, un subprogram pentru tiparirea unui cap de tabel), sau pot sa transmita programului apelant mai multe valori. De regula, intre programul apelant si subprogramul apelat valorile sunt transmise prin intermediul listei de parametri.

Structuri de baza in algoritmi

Experienta acumulata in elaborarea algoritmilor sau in programarea calculatoarelor, a demonstrat ca eficienta acestor activitati poate creste prin adoptarea unei metode specifice de lucru.

Una dintre cele mai apreciate si utilizate metode utilizate pentru dezvoltarea unor limbaje de programare (Pascal, C) este metoda programarii structurale, in cadrul acestei metode fiind definita notiunea de structura.

Structurile sunt secvente specifice, ce reprezinta o anumita etapa de prelucrare, in care se poate descompune orice algoritm.

De regula, o structura reprezinta o unitate independenta, in sensul ca poate fi dezvoltata si testata ca algoritm de sine statator (de exemplu, "introducerea coordonatelor punctelor vechi", "introducerea directiilor masurate", "orientarea statiilor", "calculul coordonatelor provizorii", etc.).

Exista trei tipuri principale de structuri:

Structura liniara (figura a).

O astfel de structura presupune executarea in succesiune a doua secvente distincte;

Structura alternativa (figura b).

In cadrul acestei structuri se va evalua o expresie logica c, in urma careia doua sunt raspunsurile (rezultatele) posibile: adevarat sau fals. Functie de acest rezultat se ia decizia parcurgerii uneia dintre secventele X sau Y. Aceasta structura se numeste IF-THEN-ELSE. Cu notatiile din figura, se poate scrie IF c THEN X ELSE Y sau "daca c este adevarata, atunci executa secventa X, altfel executa secventa Y".

Este posibil ca una dintre alternative, de exemplu Y, sa fie vida (figura c), situatie in care structura se numeste IF-THEN ("daca c este adevarata, atunci executa secventa X");

Structura repetitiva.

Acest tip de structura este numita si bucla sau ciclu (loop) si consta in efectuarea repetata a unei anumite secvente de prelucrare. Tipurile posibile de structuri repetitive sunt urmatoarele:

Structura WHILE-DO (figura d). La aceasta structura, secventa de prelucrare este executata repetat atata timp cat este indeplinita o anumita conditie. Din figura prezentata, structura se scrie WHILE c DO X, ceea ce ar insemna: "atata timp cat expresia logica c are valoarea adevarat executa secventa X". Practic, succesiunea operatiilor este urmatoarea: verifica expresia logica c si, daca este adevarata, executa secventa de instructiuni X dupa care reia ciclul cu verificarea expresiei c; daca c nu este adevarata atunci treci la secventa urmatoare, fara a mai executa X. Se poate observa ca secventa X poate sa nu fie executata deloc, daca in urma evaluarii expresiei logice rezultatul este fals. De asemenea, daca la prima evaluare a expresiei logice c rezultatul este adevarat, atunci, pentru ca secventa X sa nu se execute la infinit, trebuie ca ea sa cuprinda una sau mai multe operatii prin care valorile implicate in expresia c sa se modifice astfel incat aceasta sa poata deveni si falsa.

Structura DO-UNTIL (figura e). In cadrul acestei structuri, secventa de instructiuni (operatii) se repeta pana cand o anumita propozitie devine adevarata. Folosind notatiile din figura, aceasta structura respectiva se poate scrie

DO X UNTIL c adica "executa secventa X pana cand expresia logica c are valoarea adevarat". Se poate observa ca la aceasta structura, indiferent de rezultatul primei evaluari a expresiei logice, secventa X se executa cel putin o data. Ca si in cazul structurii anterioare, secventa de operatii ce trebuie executate trebuie sa cantina instructiuni care sa modifice valorile variabilelor implicate in expresia logica (conditie) astfel incat aceasta sa poata fi si adevarata.

Structura DO-FOR (figura f). Structura consta in repetarea unei secvente de un anumit numar de ori a unei secvente date. Numarul de reluari este egal cu numarul de valori posibile ale variabilei i, numita variabila de control a buclei. Valoarea initiala a variabilei i este l1. Dupa fiecare parcurgere a secventei X din interiorul buclei, variabila i este incrementata cu pasul p (care poate fi si un numar negativ), pana se atinge sau se depaseste limita l2. Daca pasul p nu este specificat, se subintelege ca are valoarea implicita 1.