Structuri de Date și Algoritmi

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).