Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Complexitatea calculului
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Specializarea
MC006
8
2+2+0
10
optionala
Informatică
Cadre didactice indrumatoare
Conf. Dr. TRÎMBITAS Radu Tiberiu,  traducs.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
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.