Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI
| Analiza si complexitatea algoritmilor |
trul |
|||||
| Cadre didactice indrumatoare |
|
| 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 |
| 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 |
|
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 |