Tehnici avansate de programare

Curs
6.8/10 (4 voturi)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 70 în total
Cuvinte : 14999
Mărime: 675.57KB (arhivat)
Cost: Gratis

Cuprins

Capitolul 1. Algoritmi. Elemente de analiză a complexităţii algoritmilor 2

1.1. Algoritmi. Recapitulare 2

1.2. Elemente de analiză a complexităţii algoritmilor 3

Capitolul 2. Tehnici clasice de programare 14

2.1. Tehnica forţei brute (brute force) 15

2.2. Tehnica reducerii dimensiunii problemei. Recursivitatea ca tehnică de programare 16

2.3. Tehnica Greedy (metoda optimului local) 25

2.4. Tehnica programării dinamice 39

2.5. Tehnica Backtracking (căutare cu revenire) 46

2.6. Tehnica Branch and Bound (“Ramifică şi mărgineşte”) 57

2.7. Tehnica Divide et Impera (“Împarte şi cucereşte”) 62

Extras din document

Capitolul 1. Algoritmi. Elemente de analiză a complexităţii algoritmilor

1.1. Algoritmi. Recapitulare

Etapele rezolvării unei probleme cu calculatorul:

1. Analiza problemei

2. Elaborarea algoritmului de rezolvare a problemei / alegerea unui algoritm deja existent

Modalități de descriere a algoritmului:

- în limbaj natural;

- schemă logică;

- pseudocod;

- în limbaj de programare.

3. Codificarea algoritmului într-un limbaj de programare

4. Testarea programului

4.1. Verificarea corectitudinii sintactice

4.2. Verificarea corectitudinii logice

5. Întreținerea programului

Algoritmul reprezintă o succesiune finită de pasi care, executați într-o ordine bine stabilită,

conduc de la un set de date numite date de intrare la un alt set de date numite date de iesire.

Algoritm

Operaţii de bază

citirea (operaţie

de intrare)

scrierea (operaţie

de ieşire)

atribuirea

Structuri de

control

secvenţa

decizia

iteraţia

Tehnici avansate de programare 2014-2015

Curs 1

3

Pseudocod Limbaj C / C++

Citire CITESTE x (xÎZ) scanf(”%i”,&x);/ cin>>x;

Scriere SCRIE x (xÎZ) printf(”%i”,x);/ cout<<x;

Atribuire var ← expr var = expr;

Secvenţa

instr1

instr2

{

instr1;

instr2;

}

Decizia

DACĂ cond ATUNCI

secv1

ALTFEL secv2

if (cond) secv1;

else secv2;

Iteraţia cu test

iniţial

CÂT TIMP cond EXECUTA

secventa

while (cond)

secventa;

Iteraţia cu test

final

EXECUTĂ

secventa

CÂT TIMP condiție

do

secventa;

while (cond);

Iteraţia cu

contor

PENTRU i← vi,vf,r EXECUTĂ

secventa

for(i=vi;i<=vf;i=i+r)

secventa;

1.2. Elemente de analiză a complexităţii algoritmilor

Analiza complexității unui algoritm are ca scop determinarea (estimarea) volumului de

resurse de calcul necesare pentru execuția algoritmului.

Există două tipuri de resurse:

- spațiul de memorie necesar pentru memorarea datelor prelucrate de algoritm;

- timpul de execuție al tuturor prelucrărilor specificate în algoritm.

Tehnici avansate de programare 2014-2015

Curs 1

4

Putem vorbi astfel despre complexitatea spațială si complexitatea temporală a unui

algoritm. Un algoritm are o complexitate temporală (respectiv spațială) cu atât mai mare, cu cât

timpul (respectiv spațiul de memorie) necesar algoritmului este mai mare.

Dintre cele două resurse de calcul (spațiu si timp) cea critică este timpul de execuție,

calculat ca fiind numărul de pasi executați de algoritm.

În calculul complexității se ține cont numai de operațiile critice din algoritm. Se

consideră ca fiind critice acele operații care prin natura lor fie sunt foarte consumatoare de timp,

fie sunt efectuate de un număr foarte mare de ori (de exemplu, într-un algoritm de sortare o

operație critică este compararea elementelor, întrucât se execută de foarte multe ori).

Volumul de resurse folosite depinde de:

- datele de intrare (de exemplu timpul de sortare a unui vector diferă dacă vectorul este

deja sortat sau este “aproape sortat” sau este “bine amestecat”);

- dimensiunea datelor de intrare (dimensiunea problemei) - de exemplu timpul de sortare

a unui vector cu 5 elemente este mult mai mic decât în cazul unui vector cu 10000 de elemente.

Tipuri de analiză a complexității

- cazul cel mai favorabil - corespunde acelor instanțe ale problemei pentru care numărul

de operații efectuate este cel mai mic (pentru cel mai „prietenos input”). Această analiză permite

identificarea unei limite inferioare a timpului de execuție. Această analiză este utilă pentru a

identifica algoritmii ineficienți (dacă un algoritm are un cost mare în cel mai favorabil caz, atunci

el nu poate fi considerat o variantă acceptabilă).

- cazul cel mai nefavorabil - corespunde instanțelor pentru care numărul de operații

efectuate este maxim (pentru cel mai „neprietenos input”). Această analiză furnizează o limită

superioară a timpului de execuție (algoritmul nu se va purta niciodata mai rău decât atât).

- cazul mediu (complexitatea la care ne putem astepta în cazul inputurilor aleatoare) - o

analiză utilă, însă destul de dificil de realizat.

Tehnici avansate de programare 2014-2015

Curs 1

5

Complexitate exactă, complexitate aproximativă

Complexitatea exactă a unui algoritm este caracterizată de o funcție (numită funcție de

complexitate) : →  (unde N este mulțimea numerelor naturale, iar R+ este mulțimea

numerelor reale pozitive), f(n) reprezentând volumul de resurse consumate de algoritm pentru

dimensiunea n a problemei rezolvate.

Bibliografie

Cristea V., Athanasiu I., Kalisz E., IorgaV., Tehnici de programare, Ed. Teora, Bucuresti, 1993

2. Knuth D.E., The art of computer programming, Vol. I - Fundamental Algorithms, ediția a treia, Addison

Wesley Longman, 1997

3. Knuth D.E., The art of computer programming, Vol. III - Sorting and Searching, ediția a doua, Addison

Wesley Longman, 1998

4. Levitin A., Introduction to the design and analysis of algorithms, Pearson Education, third edition, 2012

5. Livovschi L., Georgescu H. Sinteza si analiza algoritmilor, Universitatea din Bucuresti, Fac. de Matematicã,

Bucuresti, 1985

6. Odagescu I., Tehnici de programare, Ed. Intact, Bucuresti, 1994

7. Robert Sedgewick, Algorithms, Brown University, Addison-Wesley Publishing Company, Addison-Wesley

Series in Computer Science 1983

8. Zaharie D., Introducere în proiectarea si analiza algoritmilor, Ed. Eubeea, 2008

Preview document

Tehnici avansate de programare - Pagina 1
Tehnici avansate de programare - Pagina 2
Tehnici avansate de programare - Pagina 3
Tehnici avansate de programare - Pagina 4
Tehnici avansate de programare - Pagina 5
Tehnici avansate de programare - Pagina 6
Tehnici avansate de programare - Pagina 7
Tehnici avansate de programare - Pagina 8
Tehnici avansate de programare - Pagina 9
Tehnici avansate de programare - Pagina 10
Tehnici avansate de programare - Pagina 11
Tehnici avansate de programare - Pagina 12
Tehnici avansate de programare - Pagina 13
Tehnici avansate de programare - Pagina 14
Tehnici avansate de programare - Pagina 15
Tehnici avansate de programare - Pagina 16
Tehnici avansate de programare - Pagina 17
Tehnici avansate de programare - Pagina 18
Tehnici avansate de programare - Pagina 19
Tehnici avansate de programare - Pagina 20
Tehnici avansate de programare - Pagina 21
Tehnici avansate de programare - Pagina 22
Tehnici avansate de programare - Pagina 23
Tehnici avansate de programare - Pagina 24
Tehnici avansate de programare - Pagina 25
Tehnici avansate de programare - Pagina 26
Tehnici avansate de programare - Pagina 27
Tehnici avansate de programare - Pagina 28
Tehnici avansate de programare - Pagina 29
Tehnici avansate de programare - Pagina 30
Tehnici avansate de programare - Pagina 31
Tehnici avansate de programare - Pagina 32
Tehnici avansate de programare - Pagina 33
Tehnici avansate de programare - Pagina 34
Tehnici avansate de programare - Pagina 35
Tehnici avansate de programare - Pagina 36
Tehnici avansate de programare - Pagina 37
Tehnici avansate de programare - Pagina 38
Tehnici avansate de programare - Pagina 39
Tehnici avansate de programare - Pagina 40
Tehnici avansate de programare - Pagina 41
Tehnici avansate de programare - Pagina 42
Tehnici avansate de programare - Pagina 43
Tehnici avansate de programare - Pagina 44
Tehnici avansate de programare - Pagina 45
Tehnici avansate de programare - Pagina 46
Tehnici avansate de programare - Pagina 47
Tehnici avansate de programare - Pagina 48
Tehnici avansate de programare - Pagina 49
Tehnici avansate de programare - Pagina 50
Tehnici avansate de programare - Pagina 51
Tehnici avansate de programare - Pagina 52
Tehnici avansate de programare - Pagina 53
Tehnici avansate de programare - Pagina 54
Tehnici avansate de programare - Pagina 55
Tehnici avansate de programare - Pagina 56
Tehnici avansate de programare - Pagina 57
Tehnici avansate de programare - Pagina 58
Tehnici avansate de programare - Pagina 59
Tehnici avansate de programare - Pagina 60
Tehnici avansate de programare - Pagina 61
Tehnici avansate de programare - Pagina 62
Tehnici avansate de programare - Pagina 63
Tehnici avansate de programare - Pagina 64
Tehnici avansate de programare - Pagina 65
Tehnici avansate de programare - Pagina 66
Tehnici avansate de programare - Pagina 67
Tehnici avansate de programare - Pagina 68
Tehnici avansate de programare - Pagina 69
Tehnici avansate de programare - Pagina 70

Conținut arhivă zip

  • Tehnici avansate de programare.pdf

Alții au mai descărcat și

Proiect Java - Joc Carti - Macao

ENUNT: Folosind Java Swing, sa se proiecteze o aplicatie ce va simula un joc de carti (la alegere). Va fi disponibil un pachet de carti de joc,...

Baze de Date - Proiect în SQL

1. Descrierea bazei de date si a entitatilor Baza de date contine informatii despre produsele aflate intr-un depozit de aparate si accesorii de...

Exploatare si Deservirea Calculatoarelor - Crearea de Imagini Animate pentru Web Utilizand Adobe Photoshop

INTRODUCERE Internetul a progresat extrem de rapid în aceşti ultimi ani. Odată un tărâm al academicienilor, cercetătorilor şi al agenţiilor de...

Crearea unui Arhivator și a Unui Dezarhivator

Introducere „Un calculator, nu face ceea ce vrei tu sa faca, dar ceea ce îi spui sa faca” - Legea lui Murphy C/C++ sunt limbaje, si sunt...

Evidenta Unui Service de Masini - Proiectarea Bazelor de Date

Să se creeze o bază de date care să ţină evidenţ a unui service de maşini. Service-ul poate repara mai multe tipuri de maşini, ale unui anumit...

Tablou de Structuri

Tema: Emplementarea tipului abstract de date.Tablouri de structuri in C. Scopul lucrarii: Prelucrarea si utilizarea tipului abstract de date....

Algoritmi și Structuri de Date

Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...

Medii de Programare Vizuala - Visual Basic

CURS 1 Microsoft Visual Basic reprezintă cel mai rapid şi mai uşor mod de a crea aplicaţii Windows. Indiferent dacă sunteţi un profesionist cu...

Ai nevoie de altceva?