Algoritmi - 1

Introducere

Un algoritm este o metoda de rezolvare a unei probleme printr-un numar finit de pasi. Printr-un pas se întelege o operatie executabila de catre un operator. Putem spune ca un algoritm seamana cu un proces de calcul (un complex de operatii), cu o reteta. Nu orice proces de calcul este un algoritm.

Un program de calculator este un complex de instructiuni scrise într-un anumit limbaj numit limbaj de programare ce transcriu operatiile dintr-un algoritm pentru operator. Instructiunile unui limbaj de programare trebui sa fie înteles atât pentru programator cât si pentru operator.

Proprietatile algoritmilor

- generalitatea (pentru rezolvarea mai multor probleme din aceeasi sfera)

- finitudinea

- determinismul (sa cuprinda toate cazurile posibile)

- unicitatea (la aceleasi intrari sa obtina aceleasi iesiri dar prelucrarea sa fie unica)

- claritatea/precizia (la orice operatie executata sa se stie ce operatie urmeaza)

Din punct de vedere structural un algoritm cuprinde urm. etape:

- initializarea

- prelucrarea

- furnizarea rezultatelor

Un algoritm are 0 sau mai multe date de intrare. Aceste date se mai numesc si date initiale.

Operatori logici: AND, OR, NOT, >, <, <>

Algoritmii, în principal cei pentru prelucrarea datelor, pot fi exprimati în diferite modalitati: text liber, pseudocod, schema logica, limbaj de programare. Algoritmii sunt în special pentru prelucrare automata a datelor.

- constante

- variabile

Prezentarea unui algoritm:

- text

- schema logica

- pseudocod

- limbaj de programare

Structuri de date

Organizare datelor este un proces cu urm. activitati:

- identificarea datelor

- clasificarea si descrierea proprietatilor sau caracteristicile datelor

- gruparea datelor în colectii de date destinate prelucrarii

- reprezentarea externa pe suportul tehnic al datelor

- identificarea, definirea si descrierea procedurilor de preluare si stocare a datelor

În calculator datele sunt memorate pe suporti de memorie externa sub forma unor colectii de date uniform structurate, numite fisiere. Organizarea uniforma se face prin înregistrari. De regula toate înregistrarile dintr-un fisier în aceeasi zona: gasim acelasi tip de data. Modalitatea structurarii înregistrarilor o stie doar programatorul în cazul unui fisier. Tabela este un fisier care contine colectii de date dar si structura înregistrarilor.

În functie de obiectele pe care le reprezinta datele se clasifica:

- date elementare sau scalare (entitati indivizibile)

- colectii de date (multime de date elementare între care se definesc si se descriu anumit relatii)

I. Datele elementare pot fi tratate sub 2 aspecte:

Nivelul fizic ce corespunde modului de organizare si reprezentare interna a datelor. O data elementara se memoreaza într-o zona de memorie situata la o anumita adresa. Ea poate contine date numerice, alfanumerice sau de un tip declarat fiind reprezentate în cod binar. În acest caz cea mai mica unitate de adresare fiind bitul.

Nivelul logic ce corespunde modului de organizare si prelucrare a datelor de catre utilizatori. Pentru identificarea unica a datelor utilizatorul va specifica pentru fiecare urm. elemente:

- identificatorul de data sau numele asociat datei.

- multimea valorilor pe care le poate lua data respectiva în procesul prelucrarii.

- verificarea încadrarii în domeniul de valori (modelele de validare)

- atribute: tipul datei (numerica, simpla, vector,...), precizia de reprezentare interna a datei (pentru numere reale exista reprezentare cu simpla sau dubla precizie), alte caracteristici (alinierea, modalitatea de alocare a memoriei asociate datei,...)

II. Se numeste structura de date o colectie de date pentru s-a definit un mecanism de selectare si identificare a componentelor. Pe baza acestor mecanisme sau în ele se pot introduce relatii care sa asigure ordonarea datelor dupa criteriile dorite si sa faciliteze în acest mod prelucrarea lor. Între date exista relatii ce se pot grupa în 2 categorii:

- Apartenenta datelor la entitate.

- Legaturile dintre entitatile de acelasi tip sau de tipuri diferite

Din alt punct de vedere o structura de date poate fi:

- Secventiala (localizarea unei componente se face prin parcurgerea tuturor componentelor care se afla înaintea sa în ordinea existenta)

- Cu acces direct (daca o componenta din structura poate fi localizata fara a tine cont de celelalte componente)

Componentele unei structuri date pot fi:

- Date elementare

- Structuri de date

Dupa tipul componentelor structurile se pot grupa în:

- structuri de date omogene (contin componente de acelasi tip)

- structuri de date eterogene (cu componente de tipuri diferite)

La fel ca si datele elementare structuri de date pot fi reprezentate atât în memoria interna cât si în memoria externa: