Algoritmi si modalitati de reprezentare a datelor

Algoritmi si modalitati de reprezentare a datelor

Prelucrarea automata a informatiilor este asigurata de catre calculatoarele electronice. Gestionarea resurselor hard (fizice) ale echipamentelor de calcul electronic se poate realiza prin intermediul a doua tipuri de soft: softul de baza (sisteme de operare, medii de lucru, programe utilitare) si softul de aplicatie.

Daca pana acum ne-am ocupat de modul in care putem realiza prelucrarea automata a datelor folosind facilitatile softului de baza, in acest capitol ne vom indrepta atentia asupra modului in care poate fi proiectat softul de aplicatie, adica programele utilizator.

Prelucrarea automata a datelor este realizata de catre calculator ca urmare a executiei unui program. Programele sunt forma concreta de reprezentare pe calculator a algoritmilor destinati rezolvarii diverselor probleme.

Notiunea de algoritm

Ori de cate ori ne propunem sa rezolvam o problema (indiferent de natura acesteia) este necesara o ordonare logica a operatiilor ce trebuie efectuate.

Succesiunea logica a operatiilor ce trebuie efectuate in scopul rezolvarii unei probleme de natura stiintifica, economica, sociala sau de orice alta natura poarta numele de algoritm.

Trebuie sa remarcam faptul ca nu orice insiruire de operatii destinate rezolvarii unei probleme poate primi numele de algoritm. Pentru aceasta trebuie ca o astfel de succesiune finita de operatii sa posede urmatoarele caracteristici:

(a1) CLARITATE, adica proprietatea de a descrie fara ambiguitati ordinea de executie a operatiilor

(a2) GENERALITATE, adica proprietatea de a descrie rezolvarea unei clase de probleme

(a3) FINITUDINE, adica proprietatea de a descrie rezolvarea problemei intr-un numar finit de pasi sau intr-o unitate finita de timp

(a4) CORECTITUDINE, adica proprietatea de a descrie rezolvarea problemei conducand la solutia corecta a acesteia.

Este evident faptul ca pentru rezolvarea unei probleme pot exista mai multe metode si deci mai multi algoritmi corecti asociati acesteia. Dintre acestia este ales pentru reprezentarea pe calculator acela care este optim din punct de vedere al resurselor spatio-temporare utilizate.

Un program (care reprezinta materializarea pe calculator a unui algoritm) va fi scris de catre programator urmarind optimizarea spatiului de memorie ocupat de catre acesta si datele asupra carora lucreaza, precum si a timpului de executie.

Astfel, marimea datelor de intrare determina dimensiunea problemei (spatiul de memorie ocupat) , iar timpul necesar executiei unui program (algoritm) este reflectat de complexitatea algoritmului.

Pentru edificare sa consideram urmatoarea problema: se considera un sir de n numere a₁,a₂, . ,a_n - ordonat (crescator sau descrescator). Se cere sa se determine pozitia din sir in care se gaseste o valoare data x (daca aceasta valoare exista in sirul dat).

Este evident o problema foarte simpla si prima tentatie a rezolvitorului este aceea de a folosi urmatorul algoritm: se parcurge sirul de numere, pozitie cu pozitie si se compara valoarea de pe pozitia la care am ajuns, cu cea cautata. Daca se gaseste o egalitate se afiseaza pozitia corespunzatoare si problema este rezolvata. Daca se parcurge intreg sirul fara succes, atunci valoarea cautata nu este in sir. Aceasta modalitate de rezolvare a problemei poate conduce insa la un timp destul de mare de executie (mai ales in situatia in care numarul elementelor sirului dat este mare, iar valoarea cautata, fie este situata pe ultimele pozitii, fie lipseste).

In aceasta situatie se recomanda optimizarea algoritmului de cautare prin utilizarea asa numitei metode de cautare binara. Aceasta fructifica faptul ca sirul de numere date este ordonat si micsoreaza numarul de cautari. Algoritmul ar putea fi descris, in cazul cautarii binare, astfel:

Pas 0 : li:=1; ls:=n;

Pas 1

daca li < ls

atunci

se determina pozitia de mijloc a sirului, m:=[(li+ls)/2], si se compara valoarea cautata x, cu cea aflata pe aceasta pozitia m

daca x < valoarea de pe pozita m

atunci

Ls:= m-1, se reia pasul 1

altfel

daca x > valoarea de pe pozitia m

atunci

Li: = m+1, se reia pasul 1

altfel

se trece la pasul 2

altfel

se trece la pasul 3.

Pas 2 : se afiseaza m (pozitia cautata) se trece la pasul 4.

Pas 3 : se afiseaza mesajul " valoare negasita".

Pas 4 : stop.

Comparativ cu prima varianta de rezolvare, algoritmul prezentat anterior determina micsorarea numarului cautarilor, si conduce mult mai rapid la solutia problemei. Timpul de executie nu depinde, in acest caz, de pozitia valorii de cautat in cadrul sirului.

In cazul de fata am folosit, ca mod de reprezentare a algoritmului, o modalitate mai putin pretentioasa: prin pasi.

Aceasta modalitate este de altfel destul de des utilizata. Dar este oare singura? Raspunsul la aceasta intrebare este evident negativ si-l vom gasi in paragraful urmator.

Modalitati de reprezentare a algoritmilor pot fi urmatoarele:

in pasi

in schema logica

in limbaj pseudocod

in limbaj de programare

Deoarece cele mai utilizate dintre aceste metode sunt ultimle trei, in continuare vom prezenta succint caracteristicile fiecarora dintre ele. Indiferent insa de metoda de reprezentare utilizata, logica conceperii algoritmilor se bazeaza in prezent pe teoria programarii structurate.De aceea, inainte de a prezenta cele trei modalitati de reprezentare amintite, sa facem cateva precizari referitoare la principiul programarii structurate.

Teorema de structura: orice algoritm se poate reprezenta doar cu ajutorul a trei structuri logice de baza:

structura secventiala

structura alternativa

structura repetitiva

Fiecare dintre aceste structuri au modalitati specifice de reprezentare.

Structura secventiala reprezinta o succesiune de operatii care se executa una dupa cealalta in ordinea aparitiei lor. În cazul structurii secventiale, ordinea fizica coincide cu ordinea logica.

Structura alternativa permite descrierea luarii de decizii pe parcursul rezolvarii unei probleme, functie de valorile de adevar ale unor propozitii (conditii).

Structura repetitiva permite descrierea repetarii de un anumit numar de ori, in numite conditii sau pana cand anumite conditii devin adevarate, a unui grup de operatii.