Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
FIŞA DISCIPLINEI

Codul	Disciplina	
MC006	Complexitatea calculului	

Specializarea	Semestrul	Ore: C+S+L	Categoria	Statutul	
Informatică - în limba engleză	8	2+2+0		optionala	

Titularii de disciplină	Conf. Dr. TRÎMBITAS Radu Tiberiu, tradu@math.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.	
Conţinutul	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.