Structuri de Date și Algoritmi

Curs
8.5/10 (2 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 70 în total
Cuvinte : 12595
Mărime: 193.27KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Barsan M.
Un curs foarte explicit si dupa care eu am invatat Facultatea de Automatica si Calculatoare

Extras din document

Curs 1

Structuri de date

Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o colectie de date împreuna cu operatiile lor (data obiect).

De exemplu, prin multimea N a numerelor naturale se va întelege 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 bÎR, i = sqrt(-1)}, -, +, *, /, etc.

Algoritmul se defineste ca o metoda de rezolvare a unei probleme într-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. Între limbajul natural si cel în 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 în 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

1. MODELUL functional - bazat pe teoria l - calcul.

Limbajele în acest model sunt LISP, ML, MIRANDA, etc. iar programarea este în acest caz programare functionala.

2. MODELUL logic - bazat pe predicate de ordin I.

Un exemplu de limbaj în acest model este PROLOG.Iar programarea se numeste programare logica.

În 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 înca înainte de scrierea programelor.

Etapele de realizare a unui produs software (software engineering)

Aceasta stiinta pune în 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 în 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âte ori este nevoie.

Analiza performantelor presupune ¾ renuntând la acuratete ¾ estimarea timpului de lucru si a spatiului de stocare, nestiind înca limbajul care va fi folosit si calitatea programului ce se va obtine.

Presupunând 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.

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
Structuri de Date și Algoritmi - Pagina 61
Structuri de Date și Algoritmi - Pagina 62
Structuri de Date și Algoritmi - Pagina 63
Structuri de Date și Algoritmi - Pagina 64
Structuri de Date și Algoritmi - Pagina 65
Structuri de Date și Algoritmi - Pagina 66
Structuri de Date și Algoritmi - Pagina 67
Structuri de Date și Algoritmi - Pagina 68

Conținut arhivă zip

  • Structuri de Date si Algoritmi.doc

Alții au mai descărcat și

Servicii Internet Magazine Virtulale

1. REŢEAUA INTERNET SERVICII INTERNET 1.1. Internet - descriere Internet-ul este o gigantică reţea de calculatoare – mai precis o reţea de reţele...

Proiect Structuri de Date - Orar

1. INTRODUCERE 1.1 Obiectivul problemei : Aceasta aplicatie informatica are ca obiectiv gestionarea cat mai buna a orarului unei facultati pentru...

Sistem Informatic cu Baze de Date Privind Gestiunea Stocurilor de Produse Finite

1. Definirea problemei Acest sistem informatic işi propune informatizarea gestiunii privind stocurile de produse finite, prin eliminarea...

Implementarea Algoritmului Quine - Mccluskey

Algoritmul Quine-McCluskey Acest algoritm este preferat pentru functii ce depind de mai mult de 5 variabile. In cazul formei disjunctive, aceasta...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Lucrul cu Numere Mari

De multe ori , in probleme, apar situatii cand este nevoie sa memoram numere intregi foarte mari (de ordinul sutelor de cifre), iar uneori trbuie...

Arbori Partiali de Cost Minim

I. Arbori Fie G un graf orientat. G este un arbore cu radacina r, daca exista in G un varf r din care oricare alt varf poate fi ajuns printr-un...

Algoritmi de Rutare

Algoritmii de rutare pot fi diferenţiaţi după obiectivul particular dorit, impactul asupra reţelei şi resurselor ruterului, metricile folosite....

Ai nevoie de altceva?