Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licență

FISA DISCIPLINEI

Codul
Denumirea disciplinei
MIF0006 Analiza algoritmilor
Specializarea
Semestrul
Ore: C+S+L
Categoria
Statutul
Informatică - linia de studiu maghiară
7
2+1+1
optionala
Informatică - linia de studiu maghiară
5
2+1+1
specialitate
optionala
Matematică informatică - linia de studiu maghiară
5
2+1+1
specialitate
optionala
Titularii de disciplina
Lect. Dr. IONESCU Clara,  claracs.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 programelor
Continutul
* 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
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 - 5p
Legaturi: Syllabus-urile tuturor disciplinelor
Versiunea in limba engleza a acestei discipline
Versiunea in format rtf a acestei discipline