Structurile de date erau definite in limbajul C drept organizarea datelor primare. In limbajul C++, acestea reprezinta o colectie de date impreuna cu operatiile lor (data obiect).
De exemplu, prin multimea N a numerelor naturale se va intelege 111d37b si elementele multimii N, dar si operatiile ce se pot efectua cu acestea: 1, 2, 3, , +, -, *, /. Sau prin multimea numerelor complexe:
C: , -, +, *, /, etc.
Algoritmul se defineste ca o metoda de rezolvare a unei probleme intr-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 in C++, de exemplu,
vom folosi
un pseudolimbaj (de trecere).
Masina este un model de calcul care se constituie din Unitate Centrala (U.C.), Memorie (M), I/O.
Masina Von Newman - presupune executia pe baza modelului de calcul cu:
Programarea este in 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 TURING
MODELUL functional - bazat pe teoria l - calcul.
Limbajele in acest model sunt LISP, ML, MIRANDA, etc. iar programarea este in acest caz programare functionala.
MODELUL logic - bazat pe predicate de ordin I.
Un exemplu de limbaj in 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 (estimarea algoritmului) se impune inca inainte de scrierea programelor.
Aceasta stiinta pune in 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 in 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 cate ori este nevoie.
Analiza performantelor presupune renuntand la acuratete estimarea timpului de lucru si a spatiului de stocare, nestiind inca limbajul care va fi folosit si calitatea programului ce se va obtine.
Presupunand 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 pana la o constanta c.
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 I N si const. c > 0
astfel incat 
.
|
