sda.txt

STRUCTURI DE DATE SI ALGORITMI

                      STRUCTURI DE DATE SI ALGORITMI
BIBLIOGRAFIE

1. E. Horowitz, S. Sahni  "Fundamentals of Computer Algorithms" - 1985

2. E. Horowitz, S. Sahni  "Fundamentals of Data Structurs"

3. Livovschi Georgescu  "Sinteza si analiza algoritmilor"

4. U. Mandber  "Introduction to Algorithms"

5. S. Baase  "Computer Algorithms"

6. M. Shapiro  "Algorithms from P to NP"

7. N. Wirth  "Data Structurs + Algorithms = Programs"

                                   Curs 1

Structuri de date

Structurile de date erau definite 宯 limbajul C drept organizarea datelor 
primare.In limbajul C++, acestea reprezinta o colectie de date 宮preuna cu 
operatiile lor (data obiect).
De exemplu, prin multimea N a numerelor naturale se va 宯telege si elementele
multimii N, dar si operatiile ce se pot efectua cu acestea: 1, 2, 3, ..., +, -,
*, /. Sau prin multimea numerelor complexe:
C: {z = a + bi/a si bR, i = sqrt(-1)}, -, +, *, /, etc.
  Algoritmul se defineste ca o metoda de rezolvare a unei probleme 宯tr-un 
numar de pasi, metoda efectiva (pas cu pas), finita (are un numar finit de 
pasi) si cu o intrare si o iesire (I/O).
  Un algoritm poate avea un limbaj natural (o specificatie), un limbaj 
matematic (alta specificatie), un limbaj de programare (alta specificatie),
s.a.m.d.Intre limbajul natural si cel 宯 C++, de exemplu, vom folosi 
un pseudolimbaj (de trecere).

Modele de calcul
 Masina este un model de calcul care se constituie din Unitate Centrala (U.C.),
Memorie (M), I/O.
Exemple de modele de calcul:
 Masina Von Newman - presupune executia pe baza modelului de calcul cu:

Programarea este 宯 acest caz programare imperativa procedurala.
Masina RAM (Random Acces Memory) cu:

	model bazat pe algebra booleana;
	programarea este imperativa procedurala;
	evolutia se face prin set redus de instruciuni;
	viteza foarte mare de executie.
Masina TURNING
1. MODELUL functional - bazat pe teoria lambda - calcul.
Limbajele 宯 acest model sunt LISP, ML, MIRANDA, etc. iar programarea este 
宯 acest caz programare functionala.
2. MODELUL logic - bazat pe predicate de ordin I.
Un exemplu de limbaj 宯 acest model este PROLOG.Iar programarea se numeste
programare logica.
In cele ce urmeaza ne vom limita la modelul Von Newman.
 Asadar limbajul C++ se constituie din:
   variabile;
   identificatori;
   constante;
   operatori numerici obisnuiti;
   operatori relationali;
   structuri de control a executiei: if/else, while, do/while, for, etc.

Analiza performantelor algoritmului
Analiza performantelor (estimarea algoritmului) se impune 宯ca 宯ainte de 
scrierea programelor.
Etapele de realizare a unui produs software (software engineering)
Aceasta stiinta pune 宯 evidenta metodologii clare pentru modele.
Modelul initial:waterfall (cascada):

Etapele de realizare ale unui produs software:
 O prima faza:
  se pleaca de la cerinte;
  se obtin specificatii;
  se face analiza specificatiilor;
 A doua faza (DESIGN):
  proiectare de ansamblu (se sparge modulul 宯 submodule, etc);
  proiectarea structurilor de date;
  proiectarea algoritmilor;
  analiza performantelor;
  codarea (scrierea programului);
 A treia faza:
  testarea;
 Ultima faza:
  implementarea.
Programul rezultat se compara cu cerintele, si daca nu corespunde, se reia 
ciclul ori de c僼e ori este nevoie.
Analiza performantelor presupune  renunt僴d la acuratete  estimarea timpului 
de lucru si a spatiului de stocare, nestiind 宯ca limbajul care va fi folosit
si calitatea programului ce se va obtine.
Presupun僴d ca modelul RAM de masina pe care lucram executa instructiuni 
pseudocod, si ca fiecare instructiune pseudocod consuma acelasi timp de 
executie,rezulta ca timpul estimat pentru executia unui algoritm este 
proportional cu numarul instructiunilor executate de acel algoritm.

 Timpul de executie al algoritmului depinde de:
  dimensiunea datelor de intrare
  spatiul de memorie suplimentar ocupat

Dimensiunea datelor de intrare este o functie f(n) care calculeaza, pentru 
un n dat, numarul de instructiuni al algoritmului respectiv.

Estimarea se face p僴a la o constanta c.

Spatiul de memorare suplimentar
Definitie: Date doua functii f, g : N  N cu f = O(g) sau f(n) = O(g(n)),
f este ordinul de complexitate a lui g daca  N  N si const. c > 0
astfel incat .


                               Curs 2

Structuri de date elementare

O structura de date presupune un mod de organizare a datelor (宯 tablouri,
structuri, etc), si definirea operatiilor acceptate. Deci, o structura de date
reprezinta o colectie organizata de date si un set de operatii definite.
Si notiunea de tip de date presupune:
                 |--- reprezentare
                 |--- operatii acceptate

De exemplu, pentru tipul int:
                 |--- reprezentare: pe doi octeti: cod complementar
                 |---operatii acceptate: +, -, *, /, &, |, etc.

Daca pentru un tip de date nu intereseaza reprezentarea, ci doar operatiile 
acceptate,宯seamna ca tipul de date este abstract.

Structuri de date
  Tablouri
Tabloul este o colectie de date 宯 care fiecare element poate fi identificat
pe baza unui index, colectia asigur僴d timp de acces constant pentru fiecare
element. Prin reprezentarea tabloului se intelege plasarea elementelor 宯 
locatii succesive de memorie:


Locatiile de memorie pot fi numerotate, put僴d accesa direct orice element.
Timpul de accesare al elementului numar, de exemplu, fiind acelasi cu timpul
de accesare al elementului n.

  Liste
O lista este o multime de obiecte, numite atomi, pentru care este definita o 
ordine:

Operatiile principale care se pot se face 宯 cadrul listei:
  inserare: introducerea unui nou element 宯tr-o anumita pozitie;
  stergere: scoaterea unui element dintr-o anumita pozitie;
  consultare: accesul asupra fiecarui element din lista;
  parcurgere.
 Tipuri speciale de liste

   Stive
O stiva este o lista 宯 care operatiile de inserare, stergere si consultare se
efectueaza asupra unui capat al listei. Stiva se poate asemana cu un recipient
宯 care se pun si se pot scoate diferite obiecte. Operatia care pune obiectele
宯 stiva se numeste push, iar cea care scoate obiecte din stiva se numeste pop.
Capatul accesibil pentru stiva se numeste v價ful stivei:
 Asadar:
  push  insereaza un element 宯 v價ful stivei;
  pop  sterge un element din v價ful stivei;
  top  consulta (citeste) elementul din v價ful stivei;
  top(S)  citeste v價ful stivei.

 Cozi
O coada este o lista 宯 care inserarea se face la un capat (la sf價sit),
iar stergerea se face de la celalalt capat al cozii (de la 宯ceput). Partea
din fata a cozii (a primului element) se numeste front, iar partea din spate
(a ultimului element) se numeste end.
 Operatia de inserare 宯 coada  add (put)
 Operatia de stergere din coada  del (get)

 Implementari de liste
O lista poate fi realizata ca:  lista ordonata sau
                                lista 宯lantuita
Lista ordonata tine cont de o ordine a pozitiilor elementelor listei, nu de
continutul elementelor.
 Inserarea 宯tr-o lista de forma:

se face cu deplasare de o pozitie la st僴ga din punctul 宯 care dorim sa
inseram (pentru a face acest loc noului element).
Deplasarea se face 宯spre zona de memorie libera (cea hasurata)  presupunem
ca dorim sa inseram pe a 宯 pozitia i):

Presupun僴d acum hasurat corpul de elemente din lista si nehasurata zona de
memorie libera, inserarea s-ar putea figura astfel:

Stergerea: deplasarea cu o pozitie la st僴ga din acel punct.

  Liste 宯lantuite
Intr-o lista 宯lantuita, ordinea din memorie nu mai corespunde cu ordinea din
lista. Fiecare element al listei 宯lantuite va avea urmatoarea structura:
(a(i) , succesor(a(i)))
unde a(i) este atomul listei 宯lantuite, iar informatia succesor(a(i)) ne
permite sa identificam un nou element de lista 宯lantuita. Ordinea din memorie
a elementelor listei nu conteaza. Informatia care indica primul element al
listei se numeste "capul" listei. Informatiei succesor(a(i)) i se potriveste
notiunea de pointer (identificator), pointer-ul fiind o variabila care
pastreaza o adresa din memorie. El indica pozitia elementului urmator. C僴d
informatiile de 宯lantuire sunt pointeri, putem utiliza urmatoarea
reprezentare:


Capul de lista este un pointer separat care duce la primul element din lista,
iar 0 este pointer-ul nul (NULL) cu valoare zero. La implementarea listei
宯lantuite concentrarea se face la fluxul instructiunilor, nu la declaratiile
de variabile.

In programe vom utiliza urmatoarele notatii:
 x  adresa unui element din lista, deci un pointer;
 data(x)  atomul memorat 宯 elementul de lista indicat de x;
 link(x)  informatia de legatura memorata 宯 elementul de lista indicat de x,
          adica adresa elementului urmator;
 y = get_sp()  y (de acelasi tip cu x) primeste adresa unei zone de memorie
             宯 care se poate memora un element din lista (get space sau
             alocare de memorie c僴d este vorba de pointer);
 ret_sp(x)  elibereza memoria ocupata de elementul de lista indicat de x (din
             momentul respectiv	acolo se poate memora altceva).

Un element de lista va fi o astfel de structura:

 struct Element {
             Atom data;
             Element* link;
                };
Se va scrie:
 tipul lui x ---------------- Element* x
 data(x) ---------------- x  data
 link(x) ---------------- x  link
 y = get_sp() ---------------- y = new Element
 ret_sp() ---------------- delete x

Deoarece lucram cu conceptul de lista vom face declaratia :
 typedef Element* Lista;
Un pointer la un element de lista considerat aproximeaza lista ce porneste cu
elementul indicat.

Operatii primitive pentru liste 宯lantuite

1.Inserarea
Inserarea se face:  宯 fata, sau
宯 interior (la mijloc ori la sf價sit)
a) Inserarea 宯 fata

1 - Prima atribuire: link(x) = l
2 - A doua atribuire: l = x 

Observatie: daca lista este vida, l are valoarea 0 (capatul listei) iar 
atribuirile de mai sus ram僴 valabile:


b) Inserarea la mijloc

Analog pentru inserarea la sf價sit.
1 - Prima atribuire: link(x) = link(y)
2 - A doua atribuire: link(y) = x

2.a)Stergerea (stergerea din fata):

1 - Prima atribuire: p = l
2 - A doua atribuire: l = link(l)
3 - ret_sp(p)
Sau, stergerea din fata s-ar mai putea reprezenta astfel:
Situatia initiala:

Situatia finala:

(1) p = cap;
(2) cap = cap  link;
    delete p ;                // Elibereaza zona de memorie

Elementul care a fost izolat de lista trebuie sa fie procesat 宯 continuare,
cel putin pentru a fi eliberata zona de memorie pe care o ocupa, de aceea
adresa lui trebuie salvata (sa zicem 宯 variabila pointer p).
2.b)Stergerea de la mijloc sau de la sf價sit

Varibila q va indica elementul din fata celui care va fi sters.

Situatia initiala:

Situatia finala:

(1) p = q->link;
(2) q-> link = p->link;     // sau q->link = q->link->link;
    delete p;

Observatii:
Atunci c僴d q indica penultimul element dintr-o lista, atribuirile de mai sus
functioneaza corect si sterg ultimul element din lista.
Nu se poate face stergerea elementului indicat de q fara parcurgerea listei de
la capat.



                                 Curs 3


Operatia de inserare 宯tr-o lista 宯lantuita

Presupune adaugarea unui element 宯tr-o pozitie specificata 宯 lista. Exista
posibilitati diferite de a specifica pozitia 宯 care vrem sa inseram elementul:
Situatia 宯 care pozitia de inserat este data printr-un numar care sa indice al
c僼elea element trebuie sa fie 宯 lista elementul inserat;
Situatia 宯 care pozitia de inserat este data prin valoarea atomului dupa care
sau 宯ainte de care se face inserarea;
Situatia 宯 care pozitia de inserat poate fi data implicit prin valoarea
atomului de inserat.

Inserarea 宯 fata unui element specificat

Functia 宯scrie un element 宯 fata altui element dintr-o lista:

insert (l, a, b)

   // l  lista (pointer la primul element)
   // a  valoarea atomului de inserat
   // b  valoarea atomului 宯 fata caruia se insereaza
{
 p=get_sp();
 data(p)=a;
 if (l==0) or (data(l)==b) then
                {
                  link(p)=l;
                  l=p;
                 }
           else
              {
               q=l;
               while ((link(q)!=0)and (data(link(q)!=b))
                 do q=link(q);
                    link(p)=link(q);
                    link(q)=p;
               }
}

Operatia de stergere dintr-o lista 宯lantuita
Operatia delete sterge un atom dintr-o lista. Deci vom avea 宯 pseudocod,
o functie de forma:

delete(l, a)
 // l  lista
 // a  valoarea atomului care trebuie sters
{
 if l=0 then eroare ("Atomul nu se afla 宯 lista")
 else if data(l)=a then	|