SYLLABUS PAGE, 2007/08
06-05934
Models of Computation
Level 2/I
|
Dr V Sorge |
10 credits in Sem2 |
Programmes | Modules | Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus
The School of Computer Science Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)
Relevant Links
For more information (like notes, handouts) see the module web page at http://www.cs.bham.ac.uk/~vxs/teaching/moc/
Outline
| 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. |
Aims
The aims of this module are to:
- Introduce a variety of formal models of computation.
- Explain the significance of formal models from a practical and a foundational point of view.
- Make familiar with the fundamental results in the theory of computation.
- Explain the way in which formalisations are used to address real-life computational problems.
Learning Outcomes
| On successful completion of this module, the student should be able to: | Assessed by: | |
| 1 | Explain the basics of automata theory, formal language theory, computability theory, complexity theory and lambda calculus. | Examination, Continuous Assessment |
| 2 | Explain non-computability and non-decidability issues. | Examination, Continuous Assessment |
| 3 | Describe and use the connection between automata and languages. | Examination, Continuous Assessment |
| 4 | Explain and use lambda calculus as a theory of functional programming. | Examination, Continuous Assessment |
| 5 | Explain the connection between theory and applications. | Examination, Continuous Assessment |
Restrictions, Prerequisites and Corequisites
Restrictions:
| None |
Prerequisites:
| 06-18187 Foundations of Computer Science, 06-18189 Mathematics for Computer Science (or equivalent) |
Co-requisites:
| None |
Teaching
Teaching methods:
| 11 two-hour lectures, 11 one-hour exercise sessions, 2 one-hour review lectures |
Contact hours:
| 35 |
Assessment
Normal (sessional): 1.5 hr examination (80%), continuous assessment (20%).
Resit (supplementary) assessment (where allowed): By examination only with the continuous assessment mark carried forward.
Recommended Books
| Title | Author(s) | Publisher, Date | Comments |
| Module notes will be provided | The notes should normally be sufficient for following the module and for revision. | ||
| Introduction to the Theory of Computation | M. Sipser | PVS Publishing Company, 1997 | Supplementary reading. Clear, concise, accurate but tries to keep mathematical notation to a minimum. |
| Automata and Computability | D. Kozen | Springer Verlag, 1997 | Supplementary reading. Very good textbook. The material is presented in 39 small units. Goes deeper than the lectures but is only slightly more formal. Covers the first half of the module. |
| Introduction to Automata Theory, Languages, and Computation | J. E. Hopcroft, J. D. Ullman | Addison-Wesley, 1979 | Supplementary reading. The classic text. Very reliable and in the narrative parts very readable but far more mathematical than the lectures. |
| Theory of Computation; Formal Languages, Automata, and Complexity | Brookshear | Cummings, 1989 | Supplementary reading. Very clear. Not excessively mathematical but precise. A lot of illustrations and examples. |
| Models of Computation: Exploring the Power of Computing | Savage | Addison Wesley, 1998 | Supplementary reading. In addition to the basic theory, this book provides a very rich collection of applications. |
| Computability and Complexity: From a Programming Perspective | N. Jones | MIT Press, 1997 | Supplementary reading. Somewhat idiosyncratic. Contains numerous references to Compiler Design but is, on the whole, quite mathematical. |
| An Introduction to Functional Programming through Lambda Calculus. | Michaelson | Addison-Wesley, 1989 | Supplementary reading |
Detailed Syllabus
- Finite automata (4 hrs)
- Finite automata and regular languages
- Nondeterminism
- Limitations of finite automata
- Formal languages (2 hrs)
- Grammars
- Pushdown automata
- Limits of computation (4 hrs)
- The Halting Problem
- Reducibility
- Turing machines (4 hrs)
- The basic model
- Extensions and their equivalence with the basic model
- Church's Thesis
- Complexity Theory (4 hrs)
- Complexity of Turing machine programs
- The class P
- The class NP
- NP-complete problems
- Formalising functional programming (4 hrs)
- Rewriting as a computational paradigm
- Lambda calculus
- Typed lambda calculi
Programmes | Modules | Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus