Complexitatea calculului | Computation complexity |
trul |
|||||
(Computer Science) |
Cadre didactice indrumatoare | Teaching Staff in Charge |
Conf. Dr. TRÎMBIŢAŞ Radu Tiberiu, tradu@cs.ubbcluj.ro |
Obiective | Aims |
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. |
To introduce students in basics of Computation Complexity, to allow them analize and chose algorithms and to make them aware of limits of computability. |
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. |
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 | Assessment |
Examen. |
Exam. |