curs01.txt

STRUCTURI DE DATE SI ALGORITMI

				   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 .