Module 05934 (2013)

Module Description - Models of Computation

The Module Description is a strict subset of the Syllabus Page, which gives more information

Module TitleModels of Computation
SchoolComputer Science
Module Code06-05934
DescriptorCOMP/06-05934/LI
Member of StaffPaul Levy
LevelI
Credits10
Semester2
Pre-requisites06-22754 (Foundations of Computer Science), 06-18189 Mathematics for Computer Science (or equivalent)
Co-requisitesNone
RestrictionsNone
Contact hours34
Delivery11 two-hour lectures, 11 one-hour exercise sessions, 1 one-hour revision lecture
DescriptionThe 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
AssessmentSessional: 1.5 hr examination (80%), continuous assessment (20%).
Supplementary (where allowed): 1.5 hr examination (100%).
Texts, Module notes will be provided,
M. Sipser, Introduction to the Theory of Computation, 1997
D. Kozen, Automata and Computability, 1997
J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 1979
Brookshear, Theory of Computation; Formal Languages, Automata, and Complexity, 1989
Savage, Models of Computation: Exploring the Power of Computing, 1998
N. Jones, Computability and Complexity: From a Programming Perspective, 1997
Michaelson, An Introduction to Functional Programming through Lambda Calculus., 1989