University of Birmingham School of Computer Science
Home double arrow Internal double arrow Modules

MODULE DESCRIPTION, 2007/08

06-05934
Models of Computation

This School of Computer Science Module Description is a strict subset of the Syllabus Page, which gives more information.

Course Code 06-05934
Title Models of Computation
Code COMP/06-05934/LI
School/Department Computer Science
Member of Staff Dr V Sorge
Level I
Credits 10
Semester 2
Restrictions None
Pre-requisites 06-18187 Foundations of Computer Science, 06-18189 Mathematics for Computer Science (or equivalent)
Co-requisites None
Contact hours 35
Delivery 11 two-hour lectures, 11 one-hour exercise sessions, 2 one-hour review lectures
Description The module will introduce various automata theoretic models of computation and discuss their practical and theoretical significance. Finite automata, grammars and stack automata and Turing machines will be introduced. The fundamental ideas of (non-)computability and complexity will be presented. There will also be a section on the Lambda Calculus and its connection with Functional Programming.
Outcomes
On successful completion of this module, the student should be able to: Assessed by:
explain the basics of automata theory, formal language theory, computability theory, complexity theory and lambda calculus; Examination, Continuous Assessment
explain non-computability and non-decidability issues; Examination, Continuous Assessment
describe and use the connection between automata and languages; Examination, Continuous Assessment
explain and use lambda calculus as a theory of functional programming; Examination, Continuous Assessment
explain the connection between theory and applications. Examination, Continuous Assessment
Assessment Sessional: 1.5 hr examination (80%), continuous assessment (20%).
Supplementary (where allowed): By examination only with the continuous assessment mark carried forward.
Other -
Texts Module notes will be provided.
M. Sipser, Introduction to the Theory of Computation, PVS Publishing Company, 1997.
D. Kozen, Automata and Computability, Springer Verlag, 1997.
J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
Brookshear, Theory of Computation; Formal Languages, Automata, and Complexity, Cummings, 1989.
Savage, Models of Computation: Exploring the Power of Computing, Addison Wesley, 1998.
N. Jones, Computability and Complexity: From a Programming Perspective, MIT Press, 1997.
Michaelson, An Introduction to Functional Programming through Lambda Calculus., Addison-Wesley, 1989.