Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate

SUBJECT

Code
Subject
MC006 Computational Complexity
Section
Semester
Hours: C+S+L
Category
Type
Computer Science - in English
8
2+2+0
optional
Teaching Staff in Charge
Assoc.Prof. TRÎMBITAS Radu Tiberiu, Ph.D.,  tradumath.ubbcluj.ro
Aims
To introduce students in basics of Computation Complexity, to allow them analize and chose algorithms and to make them aware of limits of computability.
Content
1. Models of computation.
(Turing Machines, RAM, circuits, Finite-state-machines, Church Thesis)
2. Algorithmic decidability (decidabilty in logic, Recursive and recursive-enumerable languages)
3. Storage and time. (Complexity classes, class P, linear space, general theorems on spece and complexity).
4. Non-determinism (Nondeterministic Turing machines, class NP, NP-completness).
6. Randomized algorithms (Monte-Carlo and Las Vegas algorithms, random numbers, Class BPP)
7. Information complexity
(Kolmogorov complexity, randomness, random number generation).
8. Real computing and complexity (Complexity of real and complex arithmetic, complexity in numerical analysis).
9. Applications - Criptography
References
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]
Assessment
Colloquim.
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject