Structuri de Date și Algoritmi

Lucrarea 1

Evaluarea si masurarea timpului de executie al unui algoritm

1.Definitia unui tip de date abstract - TDA

Un TDA este un model matematic cu o colectie de operatori definiti pe el.

Intr-un TDA, operatorii pot avea ca operanzi nu numai instante ale TDA-ului respectiv, ci si ale altui TDA, dupa cum rezultatul poate fi o instanta a oricarui TDA, dar cel putin un operand sau rezultatul trebuie sa apartina TDA-ului respectiv.

Un TDA "incapsuleaza" un tip de date, in sensul ca definitia si toti operatorii tipului pot fi localizati intr-o sectiune a programului, astfel incit metoda de implementare a TDA-ului poate fi modificata usor, aceasta implicind doar rescrierea operatorilor tipului, restul programului raminind nemodificat.

In afara sectiunii unde este definit, TDA-ul poate fi privit ca un tip primitiv.

O implementare a unui TDA este "traducerea" intr-un limbaj de programare a declaratiei unei variabile a TDA si, prin cite o procedura, a fiecarui operator al TDA; o implementare foloseste o anumita structura de date pentru reprezentarea TDA.

Notiunile tip de date, structura de date si tip de date abstract, desi asemanatoare, au intelesuri diferite.

Intr-un limbaj de programare, tipul de date al unei variabile reprezinta setul (multimea) de valori pe care le poate lua variabila respectiva.

Daca un algoritm se elaboreaza folosind pseudocodul si tipuri de date abstracte, pentru implementarea algoritmului intr-un limbaj de programare, TDA-urile trebuie reprezentate in termenii tipurilor de date si a operatorilor definiti in limbajul respectiv. Pentru implementarea unui model matematic reprezentind un TDA, se folosesc structuri de date, care sint colectii de variabile, ce pot fi de tipuri diferite.

2.Timpul de executie al unui program

De multe ori, pentru rezolvarea unei probleme, trebuie ales un algoritm dintre mai multi posibili, doua criterii principale de alegere fiind contradictorii:

(1) algoritmul sa fie simplu de inteles, de codificat si de depanat;

(2) algoritmul sa foloseasca eficient resursele calculatorului, sa aiba un timp de executie redus.

Daca programul care se scrie trebuie rulat de un numar mic de ori, prima cerinta este mai importanta; in aceasta situatie, timpul de punere la punct a programului e mai important decit timpul lui de rulare, deci trebuie aleasa varianta cea mai simpla a programului.

Daca programul urmeaza a fi rulat de un numar mare de ori, avind si un numar mare de date de prelucrat, trebuie ales algoritmul care duce la o executie mai rapida. Chiar in aceasta situatie, ar trebui implementat mai inainte algoritmul mai simplu si calculata reducerea de timp de executie pe care ar aduce-o implementarea algoritmului complex.

Timpul de rulare al unui program depinde de urmatorii factori:

-datele de intrare

-calitatea codului generat de compilator

-natura si viteza de executie a instructiunilor programului

-complexitatea algoritmului care sta la baza programului.

Deci timpul de rulare e o functie de intrarea sa, de cele mai multe ori, nedepinzind de valorile de la intrare, ci de numarul de date.

Se noteaza cu T(n) timpul de rulare al unui program, ale carui date de intrare au dimensiunea n. De exemplu T(n) poate fi cn^2, unde c este o constanta.

Daca timpul de rulare depinde de valorile datelor de la intrare, in calculul lui T(n) se va lua in considerarea situatia cea mai defavorabila, cea care duce la timpul cel mai mare.

Cum timpul de rulare depinde nu numai de intrare (n) si de algoritm, ci si de performantele calculatorului pe care se executa programul, T(n) se apreciaza ca fiind proportional cu o anumita functie de n si nu se exprima in unitati reale de timp, deci T(n)=cf(n).

Timpul T(n) de rulare al unui program, poate fi apreciat printr-o functie O(f(n)), daca exista constantele pozitive c si n0, astfel incit T(n)<=cf(n), oricare ar fi n>=n0. Functia O(f(n)) reprezinta aproximarea limitei superioare a lui T(n) si se spune ca T(n) este O(f(n)), iar f(n) se numeste limita superioara a ratei de crestere a lui T(n).