Disciplina: Analiza si complexitatea algoritmilor	Cod: MI019	

Semestrul	Ore: C+S+L	Tipul	Specializarea	
6	2+1+0	optionala	Informatica	

Cadre didactice indrumatoare	Lect. Dr. IONESCU Clara, clara@cs.ubbcluj.ro	
Obiective	Dupa insusirea materialului prezentat la aceasta disciplina studentul ar trebui: 
* sa utilizeze mecanismele de analiza a unui algoritm
* sa fie capabil sa realizeze analiza complexitatii unui algoritm 
* sa identifice clasa de probleme din care o anumita problema face parte 
* sa fie capabil sa proiecteze si sa analizeze algoritmi 
* sa proiecteze programe in acord cu cerintele utilizatorilor 
* sa verifice un produs program in urma realizarii lui 
* sa aiba deprinderi de folosire a instrumentelor de asistare a activitatii de dezvoltare a programelo	
Continut	* Introducere (Algoritmi. Analiza algoritmilor. Proiectarea algoritmilor)
* Instrumente de analiză a complexităţii algoritmilor (Notaţia asimptotică. Notaţii standard şi funcţii comune. Analiza amortizată)
* Baze matematice (Sume. Recurenţe şi recursivitate. Mulţimi. Numărare şi probabilitate)
* Algoritmi din teoria numerelor 
* Algoritmi de combinatorică
* Cutia lui Dirichlet
* Clasificarea problemelor în funcţie de complexitate. NP-completitudine
* Tehnici de programare (Divide et Impera. Sortări. Căutări. Potrivirea şirurilor)
* Tehnici de programare avansate (Algoritmi greedy. Euristica greedy. Programare dinamică. Elemente de geometrie computaţională)
* Rezolvarea problemelor NP-complete şi comparaţia diferitelor soluţii (Metoda backtracking.  Euristica greedy. Algoritmi probabilişti. Algoritmi de aproximare. Algoritmi evolutivi	
Bibliografie selectiva	1. CORMEN, T.  - LEISERSON, CH. - RIVEST, R.  - STEIN, C. : Új algoritmusok, Scolar Kiadó, Budapest, 2003.
2. CORMEN, T. - LEISERSON, CH. - RIVEST, R. : Introducere în algoritmi, Editura Computer Libris Agora, Cluj-Napoca, 2000.
3. BRASSARD, G. - BRATLEY, P. : Algorithmics: Theory and Practice, Prentice Hall, 1988.
4. BRASSARD, G. - BRATLEY, P. : Fundamentals of Algorithmics, Prentice Hall, 1996.
5. HOROWITZ, E. - SAHNI, S. : Fundamentals of Computer Algorithms, Computer Science Press, 1978.
6. HOROWITZ, E. - SAHNI, S. - RAJASEKARAN, S. : Computer Algorithms, Computer Science Press, 1998. 
7. KNUTH, D. : Arta programării calculatoarelor, vol. III, Sortare şi Căutare, Editura Teora, Bucuresti, 2001.
8. RÓNYAI, L. - IVANYOS, G. - SZABÓ, R. : Algoritmusok, Typotex, Budapest, 1999. 
9. STORER, J.A. : An Introduction to Data Structures and Algorithms, Birkhauser Springer 2002. 
10. WIRTH, N. : Algorithms + Data Structures = Programs, Prentice Hall, 1976	
Evaluare	* In timpul semestrului studentii vor primi teme de casă, necesitand studiu individual. 
* In saptamana a saptea vor susţine un examen parţial. 
* La sfarsitul semestrului vor sustine un examen scris. 
* Nota finala se va calcula astfel: 
- Teme de casă - +1/0/-1 p
- Examen parţial - 4p
- Examen scris - 5