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)
Publicat de: Ionut Cosmin B.
Puncte necesare: 0

Cuprins

  1. Capitolul 1. Algoritmi. Elemente de analiză a complexităţii algoritmilor 2
  2. 1.1. Algoritmi. Recapitulare 2
  3. 1.2. Elemente de analiză a complexităţii algoritmilor 3
  4. Capitolul 2. Tehnici clasice de programare 14
  5. 2.1. Tehnica forţei brute (brute force) 15
  6. 2.2. Tehnica reducerii dimensiunii problemei. Recursivitatea ca tehnică de programare 16
  7. 2.3. Tehnica Greedy (metoda optimului local) 25
  8. 2.4. Tehnica programării dinamice 39
  9. 2.5. Tehnica Backtracking (căutare cu revenire) 46
  10. 2.6. Tehnica Branch and Bound (“Ramifică şi mărgineşte”) 57
  11. 2.7. Tehnica Divide et Impera (“Împarte şi cucereşte”) 62

Extras din curs

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

Programare orientată pe obiect C++

1. INTRODUCERE ÎN C++ Exista limbaje concepute strict pe baza conceptelor programării orientate pe obiecte (POO), de exemplu Simula sau Smalltalk....

Medii de programare vizuală - 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...

Programare HTML și XML

CAPITOLUL I NOTIUNI GENERALE [13, 28, 78, 77] 1.1 INTERNET Internet-ul, sau reteaua mondială de calculatotore, reprezintă un puternic instrument...

Inginerie Software

Fazele dezvoltării unui produs software 1 Ce este ingineria programării? 2. Fazele ingineriei programării 2.1. Faza de analiză 2.2. Faza de...

Limbaje de Asamblare

Introducere. Necesitatea programării în limbaje de asamblare Modalităţile de programare s-au schimbat imens de la inventarea calculatorului, în...

Rețele de Calculatoare

O reţea de calculatoare (computer network) este un ansamblu de calculatoare interconectate prin intermediul unui mediu de comunicaţie (cablu...

Programarea orientată spre obiecte - limbajul Java

1. INTRODUCERE IN PROGRAMAREA ORIENTATA SPRE OBIECTE OBIECTE D. Un obiect este un un mod simplificat de a identifica într-un program un lucru, o...

Administrare rețele de calculatoare

ELEMENTELE COMPONENTE ALE UNUI SISTEM DE CALCUL Monitorul Este o periferica de iesire/intrare si este caracterizat prin: - Diagonala ecranului...

Te-ar putea interesa și

Managementul Recompenselor în Cadrul SC XS SRL

1. Prezentarea societăţii S.C. XS S.R.L. S.C. XS S.R.L.este o societate cu răspundere limitată şi a fost înfiinţată în toamna anului 1998. Este o...

Dezvoltarea și retehnologizarea unei microintreprinderi producătoare de mase plastice

Cap.1. Introducere 1.1.Promovarea spiritului antreprenorial în Uniunea Europeană IMM-urile au devenit din ce în ce mai importante în societatea...

Cheltuieli Publice pentru Cercetare Stiintifică și Dezvoltare Tehnologică și Impactul Lor

1. Caracterizarea generală a cheltuielilor pentru cercetare stiintifică si dezvoltare tehnologică 1.1 Conceptul de cheltuieli publice şi...

Prelucrare Neuronală de Imagini pentru Controlul unui Vehicul

1. Introducere Nu există niciun dubiu că de la începutul anilor ‘90 până în prezent, omenirea a făcut un progres uimitor în domeniul roboticii....

Proiect mașini unelte - MVP 13

SPECIFICATIILE MASINII Curse de lucru MVP-13 Cursa axei X 1300 mm Cursa axei Y 700 mm Cursa axei Z 650 mm Distanta de la sfarsitul axului pana...

Program pentru evidența vânzărilor unui magazin de jucării

Introducere Cresterea complexitatii vietii moderne a dus la necesitatea prelucrarii unui volum din ce in ce mai mare de informatii, cu ajutorul...

Era Analogică și Era Digitală în Transmisiile Mediatice

Semnalul analogic se referă la un semnal care are continuitate în timp pe o scara de distribuţie reală a valorilor. Un semnal analogic diferă prin...

Departamentul de Marketing

I. PARTICULARITATI A ORGANIZARII RETAILULUI Notiuni generale Termenul vine de la cuvantul francez retailer, care se refera la " a taia, a...

Ai nevoie de altceva?