| Module Title |
Models of Computation |
| School |
School of Computer Science |
| Module Code |
06-05934 |
| Level |
2/I |
| Member of Staff |
Steven Vickers
|
| Semester |
Semester 2 - 10 credits
|
| Delivery |
11 two-hour lectures, 11 one-hour exercise sessions, 2 one-hour
review lectures
|
| Outcomes |
On successful completion of this module, the student should
be able to:
- explain the basics of automata theory, formal language theory, computability theory, complexity theory and lambda calculus
- explain non-computability and non-decidability issues
- describe and use the connection between automata and languages
- explain and use lambda calculus as a theory of functional programming
- explain the connection between theory and applications
|
| Assessment |
- Sessional: 1.5 hr examination (80%), continuous assessment (20%).
- Supplementary: 1.5 hr examination (100%).
|
| Texts |
| Title | Author | Publisher |
| An Introduction to Functional Programming Through Lambda Calculus |
Greg Michaelson |
Dover Publications |
| Automata and Computability |
D. Kozen |
Springer Verlag |
| Computability and Complexity: From a Programming Perspective |
N. Jones |
MIT Press |
| Introduction to Automata Theory, Languages, and Computation |
J. E. Hopcroft, J. D. Ullman |
Addison-Wesley |
| Introduction to the Theory of Computation |
M. Sipser |
PVS Publishing Company |
| Models of Computation: Exploring the Power of Computing |
Savage |
Addison Wesley |
| Module notes will be provided |
|
|
| Theory of Computation; Formal Languages, Automata, and Complexity |
Brookshear |
Cummings |
|