Computer Laboratory > Teaching > Course material 2007–08 > Diploma in Computer Science Syllabus and Booklist 2007-2008 > Computation Theory

next up previous contents
Next: Computer Graphics and Image Up: Lent Term 2008 Previous: Compiler Construction   Contents


Computation Theory

Lecturer: Dr J.K.M. Moody

No. of lectures: 12

Prerequisite course: Discrete Mathematics or Mathematics for Computation Theory

This course is a prerequisite for Complexity Theory (Part IB and Diploma), Quantum Computing (Part II and Diploma).

Aims

The aim of this course is to introduce several apparently different formalisations of the informal notion of algorithm; to show that they are equivalent; and to use them to demonstrate that there are uncomputable functions and algorithmically undecidable problems.

Lectures

Objectives

At the end of the course students should

Recommended reading

* Hopcroft, J.E., Motwani, R. & Ullman, J.D. (2001). Introduction to automata theory, languages, and computation. Addison-Wesley (2nd ed.).
Cutland, N.J. (1980). Computability. An introduction to recursive function theory. Cambridge University Press.
Davis, M.D., Sigal, R. & Weyuker E.J. (1994). Computability, complexity and languages. Academic Press (2nd ed.).
Sudkamp, T.A. (1995). Languages and machines. Addison-Wesley (2nd ed.).



next up previous contents
Next: Computer Graphics and Image Up: Lent Term 2008 Previous: Compiler Construction   Contents