SDA curs 1 I IS 2009/2010 1

Structuri de date si algoritmi

2h curs+ 1h laborator+ 1h proiect

Examen scris +

pe calculator

SDA curs 1 I IS 2009/2010 2

De ce SDA?

� Structuri de date : metode de organizare a unei mari cantitati de informatie

� Analiza algoritmilor : estimarea timpului de executie si a resurselor necesare

� Dezvoltarea tehnologiei=> calculatoare din ce in ce mai rapide

- nevoia de programe care sa poata procesa in timp util o mare catitate de intrare

- eficienta programelor, obiectiv stringent in special la cantitati mari de date de intrare

- analiza algoritmului permite o apreciere , o estimare a soluitie daca este eficienta, inca inainte de a scrie codul

Ex. 1 Problema de selectie. Se da un grup de N numere. Sa se determine elementul de pe pozitia k in ordinea descrescatoare a marimii.

SDA curs 1 I IS 2009/2010 3

Variante de solutii Ex.1

� a) a citi cele N elemente intr-un tablou, sortarea lor in ordine descrescatoare si returnarea elenetului de pe pozitia k

� b) a citi primele k elemente intr-un tablou si sortarea lor in ordine descrescatoare. Fiecare element este citit apoi unul cate unul. Daca este mai mic dacat al k –lea element este ignorat, altfel este pus in pozitia corecta, cel in plus fiind eliminat

Care varianta este mai buna ? Sunt destul de bune ambele ?

Set de intrare : 1 milion de elemente: k=500.000

Ex. 2 Se considera un tablou bidimensional de litere si o lista de cuvinte.

Obiectiv : gasirea de cuvinte in tablou

SDA curs 1 I IS 2009/2010 4

Variante de solutii Ex.2

a) Pentru fiecare cuvant din lista se verifica fiecare triplet ( rand, coloana, orientare); vor rezulta prin implementare foarte multe bucle imbricate

b) Pentru fiecare quadruplu ( rand, coloana, orientare, numar de caractere) se verifica daca cuvantul exista in lista

Dimensiune tablou:16x16; lungime cuvant :1-16: lista – intregul dictionar

SDA curs 1 I IS 2009/2010 5

Nevoia unei structuri

� Structura este prezenta atat in raport cu datele, cat si cu programul (codul) care implementeaza algoritmul.

� Cerinte asupra programelor : usor de urmarit, concise, usor de modificat

� Structurarea programului - permite descompunerea problemei de rezolvat, si implict a soluitiei, in parti mai simple, pana la cele direcct rezolvabile

� Structurarea datelor – conduce la operatii simple si eficiente, in cazul alegerii unei structuri de date potrivite

� Structura datelor si a programelor se afla intr- stransa corelare si ambele conduc la eficienta

Ex. 3 Parcurgerea traseului intre casele dintr-un oras ( N case )

Ex. 4 Cautarea unui nr de telefon in cartea de telefon cand se cunoaste numele.

Ex. 5 Cautarea unor infromatii pe hartile geografice

Structurarea clarifica, iar detaliile fara insemnatate pentru rezolvare ingreuneaza.

SDA curs 1 I IS 2009/2010 6

Structura programelor

� Ex. 6 Scrieti un program care tipareste toate numerele prime intre 2 si n.

Un algoritm asociat unei probleme specifica operatiile care trebuie efectuate pentru a se ajunge la un rezultat corect.

prime1 ( n)

1. Creeaza o multime ( colectie) numita candidati care cuprinde toti intregii intre 2 si n

2. Elimina toate numerele care nu sunt prime din candidati

3. Tipareste toti intregii ramasi in candidati

Variante de implementare : prime1_a( int n); prime1_b( int n)

SDA curs 1 I IS 2009/2010 7

� Utilizarea datelor abstracte si a modularizarii functionale usureaza intelegerea programului si a manierei de rezolvare, dat totodatasimplifica si mentenanta unui program

� Modificarea programului pentru a face ceva nou

� Modificarea programului pentru a nu mai face anumite operatii ( sarcini)

� Modificari pentru cresterea eficientei in implemetarea anumitor sarcini (task-uri)

� Alegerea implementarii pentru datele abstracte este un punct critic pentru cresterea eficientei programelor

Variante de implementare pentru candidati: tablou, intreg a carui valoare depinde de contributia fiecarui membru), lista, arbori, etc

SDA curs 1 I IS 2009/2010 8

prime2 ( n)

1. Pune x1, x2, …, xn pe 0.

2. Pune k pe 2

3. Daca xk este 1, executa pasul 7.

4. Tipareste k.

5. Pune m ca parte intreaga a lui n/k

6. Pune xk,x2k,…,xmk pe1.

7. Pune k pe k++.

8. Daca k <=radical(n) executa pasul 3

9. Daca xk este 0, tipareste k

10. Pune k pe k+1

11. Daca k<=n, executa pasul 9

SDA curs 1 I IS 2009/2010 9

Obiectivele cursului

� 1. Cunoasterea conceptelor de baza referitoare la marea varietate de structri de date utilizate in activitatea de programare si cunoasterea celor mai semnificative aplicatii care le utilizeaza

� 2 Conceperea si implementarea unor algoritmi specifici in contextul unor structuri de date, cu aprecierea eficientei si a performantelor acestora, atat din punctul de vedere al vitezei de excutie , cat si a spatiului de memorie necesar.

� 3. Dezvoltarea si insusirea unui mod de lucru ingineresc, integrat, referitor la abordarea, dezvoltarea si implementarea unor produse software eficiente.

SDA curs 1 I IS 2009/2010 10

Structura cursului

� Cap.1 Structuri de date fundamentale

� Cap.2 Notiuni despre algoritmi. Analiza algoritmilor.

� Cap.3 Algoritmi de sortare

� Cap. 4 Tipul de date abstract sir

� Cap. 5 Recusivitate. Algoritmi recursivi

� Cap. 6 Liste si structuri derivate din liste

� Cap. 7 Arbori

SDA curs 1 I IS 2009/2010 11

Bibliografie

� Vladimir Cretu – Structuri de date si algoritmi, Orizonturi Universitare, 2000

� Mark Allen Weiss- Data Structures and Algorithm Analysis in C, 2nd ed, Addison Wesley, 1997

� R. Sedgewick – Algorithms in C, Addison Wesley, 1998

� James Korsh, Leonard Garett – data Structures, Algorithms and Program Style using C, PWS – Kent Publishing Company, 1988

SDA curs 1 I IS 2009/2010 12

Cap. 1 Structuri de date fundamentale1.1 Preliminarii

� Caracteristici ale sistemele de calcul:

- viteza de lucru -faciliteaza si accelereaza executia unor calcule complexe;

- capacitatea de memorare;

- posibiltatile de acces la infromatiile memorate

Cantitatea mare de informatii prelucrata de un sistem de calcul reprezinta o abstractizare a lumii reale, concretizata intr-o multime de date, selectate astfel incat sa fie reprezentatice pentru problema de rezolvat.

Constituirea informatiilor furnizate unui program comporta doua etape, care adeseori se interpatrund:

1. Stabilirea abstractizarii valabile pentru rezolvarea problemei, in urma careia rezulta un set de date initial

2. Stabilirea modului de reprezentare in sistem a acestor date.

SDA curs 1 I IS 2009/2010 13

� Alegerea reprezentarii datelor se poate realiza la randul ei la diferite nivele de abstractizare, in functie de scopul urmarit si de limbajul de programare utilizat. Reprezentarea este determinata de facilitatile hard si soft pe care le pune la dispozitie sistemul de caclcul.

� Un limbaj de programare poate fi privit drept un “calculator abstract”, capabil sa intelega termenii definiti in limbaj. Termenii limbajului incorporeaza deja un anumit nivel de abstractizare a obiectelor utilizate de masina reala, functie de nivelul limbajului ( cobort, ridicat). Sarcina tranformarii notiunilor abstracte ale limbajului in termenii sistemelor ( masinilor) de calcul revine altor programe : compilatoare, interpretoare, asambloare (translatoare)

� Cu cat nivelul de abstractizare al limbajului este mai strans legat de sistemul de calcul, cu atat este mai simplu pentru cel care realizeaza implementarea sa aleaga o reprezentare mai eficienta, dedicata problemei.

� Limbajul C se situeaza intre limbajele orientate spre masina si cele cu inalt nivel de abstractizare.

SDA curs 1 I IS 2009/2010 14

1.2 Tipuri de date1.2.1 Conceptul de tip de data

� In procesul de prelucrare a datelor numerice sa face o distinctie clara intre numerele reale, intregi, complexe.

� In acest sens este necesar ca fiecare constanta, variabila, expresie sau functie sa se incadreze unui anumit tip de data.

� Un tip de date se caracterizeaza prin:

- multimea valorilor

- grad ( nivel) de structurare

- set de operatori specifici

Precizarea tipurilor de date se realizeaza prin declaratii explicite, care preced textual utilizarea obiectelor incadrate in acele tipuri. Unele tipuri sunt recunoscute implicit prin reprezentare.

SDA curs 1 I IS 2009/2010 15

Caracteristicile conceptului de tip de data :

� 1. Un tip de data determina in mod univoc multimea valorilor pe care le poate asuma un elemnt incadrat in tipul respectiv ( constante, variabile sau valori generate de un operator sau o functie)

� 2. Tipul unui element sintactic poate fi dedus din forma sa de prezentare sau din declaratia sa explicita, fara a fi necesara executia unor procese de calcul suplimentare.

� 3. Fiecare operator sau functie definita accepta argumente de un tip precizat si furnizeaza rezultate de asemenea de un tip precizat. Daca apar abateri de la acesata regula generala , ele sunt rezolvate de reguli specifice limbajelor

� 4. Presupune un anumit grad de structurare a informatiei, grad care e evidentiat de nivelul de organizare asociat tipului de data.

Respectarea caracteristicilor de mai sus permite compilatoarelor sa verifice compatibilitatea si legalitatea unor constructii de limbaj, inca in faza de compilare, fara a fi necesara executia. Acest tip de redundanta din textul programelor sursa constituie un prim avanyaj major al limbajelor de nivel superior, fata de limbajul de asamblare.

SDA curs 1 I IS 2009/2010 16

Metode de structurare

� In fiecare limbaj de programare se precizeaza anumite metode de constructie a tipurilor de date structurate

� Metode de structurare de baza:

a) Prin agregare : definirea unor tipuri de date noi prin agregare (conglomerare), pornind de la tipuri existente ( anterior definite).Valorile tipurilor rezultate sunt conglomerate de valori ale tipurilor constitutive. Daca exista un singur tip constitutiv , acesta se numeste tip de baza.

b) Prin incuibare: definirea unor tipuri de date in interiorul altor tipuri

Cele doua metode pot fi combinate rezultand astfel un anumit nivel de structurare, bazat pe o ierarhie de astfel de structuri. Tipurile de la baza structurarii trebuie sa fie tipuri primitive ( atomi)

SDA curs 1 I IS 2009/2010 17

� Limbajele de programare pun la dispozitie tipuri primitive nestructurate(fundamentale):

a) Definite de programator prin enumerarea tipurilor constitutive ale tipului

b) Tipuri standard, numite si predefinite, care au de regula corespondenta cu reprezentari asociate arhitecturii hardware a sistemului de calcul

Daca intre valorile individuale ale tipului exista o relatie de ordonare, atunci tipul de data este ordonat sau scalar . Majoritatea tipurilor primitive sunt scalare.

Metodele de structurare de baza genereaza tipuri de date structurate:

- statice

- dinamice

- definite de utilizator

SDA curs 1 I IS 2009/2010 18

Operatori

� Variabilele si constantele sunt utilizate in calculele implementate prin program.In acest scop, limbajele de programare definesc operatori asociati tipurilor de date.

� Operatorii de baza : atribuire si comparatie

Executia acestor operatori presupune un volum cu ata mai sporit de calcul, cu cat gardul de structurare al tipului de data este mai ridicat.

� O alta clasa fundamentala de operatori : operatorii de transfer, utilizati in construirea tipurilor structurate

- constructori

- selectori

� Operatorii de transfer pot fi : impliciti sau expliciti

� Operatorii pot fi : omogeni sau mixti

� D.p. d. v. al rezultatului furnizat: interni sau externi

SDA curs 1 I IS 2009/2010 19

Bibliografie

� Vladimir Cretu – Structuri de date si algoritmi, Orizonturi Universitare, 2000

� Mark Allen Weiss- Data Structures and Algorithm Analysis in C, 2nd ed, Addison Wesley, 1997

� R. Sedgewick – Algorithms in C, Addison Wesley, 1998

� James Korsh, Leonard Garett – data Structures, Algorithms and Program Style using C, PWS – Kent Publishing Company, 1988

SDA curs 1 I IS 2009/2010 20