Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licență

FISA DISCIPLINEI

Codul
Denumirea disciplinei
MC006 Complexitatea calculului
Specializarea
Semestrul
Ore: C+S+L
Categoria
Statutul
Informatică - în limba engleză
8
2+2+0
optionala
Titularii de disciplina
Conf. Dr. TRÎMBITAS Radu Tiberiu,  tradumath.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.
Continutul
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.
Legaturi: Syllabus-urile tuturor disciplinelor
Versiunea in limba engleza a acestei discipline
Versiunea in format rtf a acestei discipline