Analiza si proiectarea algoritmilor |
trul |
|||||
Cadre didactice indrumatoare |
Lect. IONESCU Clara, clara@cs.ubbcluj.ro |
Obiective |
Dupa insusirea materialului prezentat la aceasta disciplina studentul ar trebui:
* sa realizeze problemele care se ridica in activitatea de dezvoltare a produselor software * sa inteleaga necesitatea proiectarii programelor in acord cu cerintele utilizatorilor * sa poata verifica un produs program in urma realizarii lui * sa poata realiza produse program de dimensiuni medii * sa aiba deprinderi de folosire a instrumentelor de asistare a activitatii de dezvoltare a programelor |
Continut |
1. Introducere (1)
1.1. Algoritmi 1.2. Analiza algoritmilor. 1.3. Proiectarea algoritmilor 2. Instrumente de analiză (2) 2.1. Notaţia asimptotică 2.2. Notaţii standard şi funcţii comune 2.3. Analiza amortizată 3. Sume (3-4) 4. Recurenţe şi recursivitate 5. Mulţimi 6. Numărare şi probabilitate 7. Algoritmi din teoria numerelor (5-6) 7.1. Algoritmi de combinatorică iterativi 7.2. Cutia lui Dirichlet 7. Tehnici de programare 7.1. Clasificarea problemelor în funcţie de complexitate. NP-completitudine (7) 7.2. Divide et Impera (8) 7.3. Sortări (9) 7.4. Căutări (10) 7.5. Potrivirea şirurilor (11) 8. Tehnici avansate (12-13) 8.1. Algoritmi greedy 8.2. Euristica greedy 8.3. Programare dinamică 9. Rezolvarea problemelor NP-complete şi comparaţia diferitelor soluţii (14) 9.1. Backtracking 9.2. Euristica greedy 9.3. Algoritm probabilişti 9.4. Algoritmi aproximativi 9.5. Algoritmi evolutivi şi genetici |
Bibliografie |
1. T. Cormen, C. Leiserson, R. Rivest, Introducere in algoritmi, Computer Libris Agora, Cluj-Napoca, 2000
2. James A. Storer, An Introduction to Data Structures and Algorithms, Springer, New York, 2002 |
Evaluare |
In timpul semestrului studentii vor proiecta, implementa, si testa programe de dimensiuni medii. La sfarsitul semestrului vor sustine un examen scris. Nota finala obtinuta se va calcula astfel:
* Activitate laborator: 4 pct * Examen scris - o problema de programare: 6 pct |