Computer Laboratory > Teaching > Course material 2007–08 > Computer Science Tripos Syllabus and Booklist 2007-2008 > Mathematics for Computation Theory

next up previous contents
Next: Operating System Foundations Up: Michaelmas Term 2007: Part Previous: How to Study Computer   Contents


Mathematics for Computation Theory

Lecturer: Dr J.K.M. Moody

No. of lectures and practical classes: 12 + 6

This course is a prerequisite for Introduction to Security, Computation Theory, Artificial Intelligence I, Quantum Computing.

Aims

The aims of this course are to introduce the basic notation and constructs of set theory. The course will cover functions and relations, and will treat sufficient of the theory of partial orders to handle well-founded induction. The ideas are illustrated by developing the theory of finite automata and regular languages, including a proof of Kleene's Theorem.

Lectures

Part A. Discrete Mathematics

Part B. Finite Automata and Regular Languages

Objectives

At the end of the course students should

Recommended reading

Part A:

* Devlin, K. (2003). Sets, functions, and logic: an introduction to abstract mathematics. Chapman and Hall/CRC Mathematics (3rd ed.). ISBN 1-584-88449-5
Rosen, K.H. (2003). Discrete mathematics and its applications. McGraw-Hill (5th ed.). ISBN 0-072-93033-0
Kolman, B., Busby, R.C. & Ross, S.C. (2003). Discrete mathematical structures for computer science. Prentice Hall (5th ed.). ISBN 0-130-45797-3
Forster, T.E. (2003). Logic, induction and sets. LMS Student Text 56. Cambridge University Press. ISBN 0-521-53361-9

Part B:

Hopcroft, J.E., Motwani, R. & Ullman, J.D. (2001). Introduction to automata theory, languages and computation. Addison-Wesley (2nd ed.). ISBN 0-201-44124-1
Sudkamp, T.A. (1998). Languages and machines: an introduction to the theory of computer science. Addison-Wesley (2nd ed.). ISBN 0-201-15768-3
Hopcroft, J.E. & Ullman, J.D. (1974). The design and analysis of computer algorithms. Addison-Wesley. ISBN 0-201-00029-6

Closely related to parts of the course but out of print:

Conway, J.H. (1971). Regular algebra and finite machines. Chapman and Hall.
Stanat, D.F. & McAllister, D.F. (1977). Discrete mathematics in computer science. Prentice Hall.
Stone, H.S. (1973). Discrete mathematical structures and their applications. SRA.



next up previous contents
Next: Operating System Foundations Up: Michaelmas Term 2007: Part Previous: How to Study Computer   Contents