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 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
Conținut arhivă zip
- Tehnici avansate de programare.pdf