Complexitatea calculului |
trul |
|||||
Cadre didactice indrumatoare |
Conf. Dr. TRÎMBITAS Radu Tiberiu, tradu@cs.ubbcluj.ro |
Obiective |
A da studentilor notiuni de complexitatea analitica si calitativa a calculului, a le permite sa analizeze algoritmi si clase de algoritmi, a le da criterii de selectie a algoritmilor si a-i face constienti de limitele calculabilitatii. |
Continut |
1. Formularea problemei, masurarea complexitatii.
2. Preliminarii matematice: ordin de marime, relatii de recurenta, enumerari, functii generatoare. 3. Analiza algoritmilor. 4. Algoritmi recursivi. 5. Algoritmi din teoria numerelor. 6. Metode de sortare si cautare. 7. NP - Completitudine si clase de complexitate. 8. Complexitatea algoritmilor numerici. 9. Analiza asistata de calculator a algoritmilor. 10. Elemente de complexitate calitativa. 11. Algoritmi probabilisti si aplicatii ale complexitatii in criptografie. |
Bibliografie |
1. Knuth, D.E., Tratat de programarea calculatoarelor. Vol.I, Algoritmi fundamentali, Ed. Tehnica, Bucuresti, 1974. Vol.II, Algoritmi seminumerici. Vol.III, Sortare si cautare, Ed. Tehnica, Bucurest, 1976.
2. Wilf, H.S., Algorithmes et complexite, Mason & Prentice Hall, 1985. 3. Baase, S., Computer Algorithms: Introduction to Design and Analysis, Addison- Wesley, 1983. 4. Aho, A.V., Hopcroft, J.E., Ullmann, J.D., The Design and Analysis of Computer Algorithms, Addison Wesley, 1974. 5. Comer, Leiserson, Rivest - Algorithms, MIT Press,1990. |
Evaluare |
Examen. |