CM2207: Introduction to the Theory of Computation
| School | Cardiff School of Computer Science and Informatics |
| Department Code | COMSC |
| Module Code | CM2207 |
| External Subject Code | 100366 |
| Number of Credits | 10 |
| Level | L5 |
| Language of Delivery | English |
| Module Leader | DR Richard Booth |
| Semester | Spring Semester |
| Academic Year | 2022/3 |
Outline Description of Module
The theory of computing deals with questions such as: what is computation? What problems can be computed? What is the inherent difficulty of a given problem? To answer such questions in a satisfactory manner, we need a formal definition of computation, which does not rely on any specific hardware or programming language. It is perhaps surprising that some real-world problems can be mathematically proven to be undecidable, i.e. regardless of any future advances in hardware, such problems are provably impossible to solve on a computer. In this module we will discuss the main models of computability and provide several examples of undecidable problems. While questions about computability have initially been studied from a theoretical perspective, the resulting theories have had many important practical applications. Among others, the methods discussed in this module are used for implementing compilers (in particular for parsing), for defining functional programming languages, and for formally verifying the correctness of software and hardware.
On completion of the module a student should be able to
- Use standard methods for proving mathematical properties
- Understand the basic rules of classical logic
- Demonstrate an understanding of formal languages and automata
- Explain the notion of undecidability and its importance for computer science
- Explain the basic concepts from complexity theory
How the module will be delivered
Modules will be delivered through blended learning. You will be guided through learning activities appropriate to your module, which may include:
- on-line resources that you work through at your own pace (e.g. videos, web resources, e-books, quizzes),
- on-line interactive sessions to work with other students and staff (e.g. discussions, live streaming of presentations, live-coding, team meetings)
- face to face small group sessions (e.g. help classes, feedback sessions)
Skills that will be practised and developed
Formally verifying the correctness of a program
Implementing a simple parser
Designing and implementing automata and Turing Machines to carry out various tasks
How the module will be assessed
A blend of assessment types which may include coursework and portfolio assessments, class tests, and/or formal examinations
Students will be provided with reassessment opportunities in line with University regulations.
Assessment Breakdown
| Type | % | Title | Duration(hrs) |
|---|---|---|---|
| Written Assessment | 50 | Problem Solving Sheet 1 | N/A |
| Written Assessment | 50 | Problem Solving Sheet 2 | N/A |
Syllabus content
Formal methods in computer science
Basic proof techniques: proof by contradiction, proof by induction
Propositional logic
Application: Boolean circuits
Application: Hoare Logic
Formal Languages and Automata
Regular expressions, finite state machines, Kleene's theorem
Push-down automata, context-free grammars, the pumping lemma
Application: parsing
Models of computation
Turing machines
Undecidability, the halting problem
Computational complexity
The complexity classes P, NP
Reductions, the SAT problem