Structuri de Date și Algoritmi

Seminar
8/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 60 în total
Cuvinte : 17615
Mărime: 59.90KB (arhivat)
Cost: Gratis

Extras din document

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

Preview document

Structuri de Date și Algoritmi - Pagina 1
Structuri de Date și Algoritmi - Pagina 2
Structuri de Date și Algoritmi - Pagina 3
Structuri de Date și Algoritmi - Pagina 4
Structuri de Date și Algoritmi - Pagina 5
Structuri de Date și Algoritmi - Pagina 6
Structuri de Date și Algoritmi - Pagina 7
Structuri de Date și Algoritmi - Pagina 8
Structuri de Date și Algoritmi - Pagina 9
Structuri de Date și Algoritmi - Pagina 10
Structuri de Date și Algoritmi - Pagina 11
Structuri de Date și Algoritmi - Pagina 12
Structuri de Date și Algoritmi - Pagina 13
Structuri de Date și Algoritmi - Pagina 14
Structuri de Date și Algoritmi - Pagina 15
Structuri de Date și Algoritmi - Pagina 16
Structuri de Date și Algoritmi - Pagina 17
Structuri de Date și Algoritmi - Pagina 18
Structuri de Date și Algoritmi - Pagina 19
Structuri de Date și Algoritmi - Pagina 20
Structuri de Date și Algoritmi - Pagina 21
Structuri de Date și Algoritmi - Pagina 22
Structuri de Date și Algoritmi - Pagina 23
Structuri de Date și Algoritmi - Pagina 24
Structuri de Date și Algoritmi - Pagina 25
Structuri de Date și Algoritmi - Pagina 26
Structuri de Date și Algoritmi - Pagina 27
Structuri de Date și Algoritmi - Pagina 28
Structuri de Date și Algoritmi - Pagina 29
Structuri de Date și Algoritmi - Pagina 30
Structuri de Date și Algoritmi - Pagina 31
Structuri de Date și Algoritmi - Pagina 32
Structuri de Date și Algoritmi - Pagina 33
Structuri de Date și Algoritmi - Pagina 34
Structuri de Date și Algoritmi - Pagina 35
Structuri de Date și Algoritmi - Pagina 36
Structuri de Date și Algoritmi - Pagina 37
Structuri de Date și Algoritmi - Pagina 38
Structuri de Date și Algoritmi - Pagina 39
Structuri de Date și Algoritmi - Pagina 40
Structuri de Date și Algoritmi - Pagina 41
Structuri de Date și Algoritmi - Pagina 42
Structuri de Date și Algoritmi - Pagina 43
Structuri de Date și Algoritmi - Pagina 44
Structuri de Date și Algoritmi - Pagina 45
Structuri de Date și Algoritmi - Pagina 46
Structuri de Date și Algoritmi - Pagina 47
Structuri de Date și Algoritmi - Pagina 48
Structuri de Date și Algoritmi - Pagina 49
Structuri de Date și Algoritmi - Pagina 50
Structuri de Date și Algoritmi - Pagina 51
Structuri de Date și Algoritmi - Pagina 52
Structuri de Date și Algoritmi - Pagina 53
Structuri de Date și Algoritmi - Pagina 54
Structuri de Date și Algoritmi - Pagina 55
Structuri de Date și Algoritmi - Pagina 56
Structuri de Date și Algoritmi - Pagina 57
Structuri de Date și Algoritmi - Pagina 58
Structuri de Date și Algoritmi - Pagina 59
Structuri de Date și Algoritmi - Pagina 60

Conținut arhivă zip

  • Structuri de Date si Algoritmi.doc

Alții au mai descărcat și

Baze de Date

– Cunoaşterea limbajului de manipulare a datelor utilizat la extragerea informaţiilor prin intermediul clauzelor (SELECT, FROM, WHERE, GROUP BY,...

Baze de Date Relaționale

Notiuni introductive, concepte fundamentale Prin sistem se întelege un ansamblu (grupare) de elemente interdependente legate între ele pentru...

Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor

Obiective In urma parcurgerii acestui laborator, studentul va fi capabil: - sa inteleaga notiunea de arbore si structura unui arbore binar; - sa...

Elemente Fundamentale ale Limbajului C și C++

Un limbaj de programare reprezinta o interfata între problema de rezolvat si programul de rezolvare. Limbajul de programare, prin specificarea...

Functii si Variabile in C si C++

In cazul în care apelul functiei precede definitia, trebuie dat, la începutul textului sursa, un prototip al functiei, care sa anunte ca definitia...

Functii, Tablouri și Pointeri în C și C++

3. Pointeri la functii. Numele unei functii reprezinta adresa de memorie la care începe functia. Numele functiei este, de fapt, un pointer la...

Instructiuni in C si C++

1. Instructiunea expresie. O instructiune expresie se obtine punând terminatorul de instructiune (punct-virgula) dupa o expresie: expresie;...

Operatii de Intrare si Iesire in C si C++

Operatii de intrare / iesire în C++ . Ca si în C, în C++ facilitatile de intrare / iesire sunt implementate prin intermediul unei biblioteci de...

Ai nevoie de altceva?