Complexitatea calculului |
trul |
|||||
Cadre didactice indrumatoare |
|
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. Modele de calcul
(Masini Turing, Masini RAM, circuite, masini cu numar finit de stari, teza lui Church) 2. Decidabilitate algoritmica (Decidabilitate in logica, limbaje recursive si recursiv enumerabile) 3. Spatiu si timp (Clase de complexitate, clasa P, spatiu liniar, complexitate in spatiu si timp). 4. Non-determinism (Msini Turing nedeterministe, clasa NP, NP-completitudine). 6. Algoritmi probabilisti. (Algoritmi Monte-Carlo si Las-Vegas, numere aleatoare, clasa BPP) 7. Complexitatea informatiei. (Complexitate Kolmogorov, aleatorism, generatoare de numere aleatoare) 8. Calcul in real si complexitate (Complexitate in real si complex, complexitatea algoritmilor din Analiza numerica) 9. Applicatii 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. CORMEN, T. - LEISERSON, T., - RIVEST, R.: - Introduction to Algorithms, MIT Press,1990. 5. PAPADIMITRIOU C. H: Computational Complexity, Addison Wesley, 1995. 6. GAREY, M. JOHNSON, M. J: Computer and Intractability. A guide to NP-Completness, W. H. Freeman, 1979 7. SIPSER, M.: Introduction to the Theory of Computation, PWS Publishing, 1997 8. LOVASZ, L.: Computation Complexity, Lecture Notes, 1999, [www.research.microsoft.com/users/lovasz/notes.html] |
Evaluare |
Verificare pe parcurs. |