Disciplina: Complexitatea calculului	Cod: MC006	

Semestrul	Ore: C+S+L	Tipul	Specializarea	
8	2+2+0	optionala	Informatica	

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. 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
Criptografi	
Bibliografie selectiva	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