COMP2210 Theory of Computing
This module aims to provide a broad and stimulating introduction to the theory of computing
Aims and Objectives
This module aims to provide a broad and stimulating introduction to the theory of computing.
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- The relationship between the regular, context-free and recursively enumerable classes of languages, and the state-machines that accept them
- The nature and examples of undecidable problems
- The diagonalisation proof technique
- The time and space complexity of algorithms and problems
- The complexity classes P and NP together with examples of NP-complete problems
- The complexity class PSPACE together with examples of PSPACE-complete problems
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Ascertain and prove whether or not a given language is regular
- Ascertain and prove whether or not a given language is context-free
- Use the reduction technique to show that a problem is undecidable
- Analyse the complexity of a given algorithm or problem
- Use polynomial-time reduction to reason about the complexity class of a problem
Automata theory - Finite state automata, regular expressions and regular languages - The pumping lemma for regular languages - Closure properties of regular languages - The Myhill-Nerode theorem - Context-free grammars and pushdown automata - Closure properties of context-free languages - The pumping lemma for context-free languages Computability theory - Turing machines, recursively enumerable and recursive languages - Church-Turing thesis - Limitations of algorithms: universality, the halting problem and undecidability Computational complexity theory - Complexity of algorithms and of problems - Complexity classes P, NP, PSPACE - Polynomial-time reduction - NP-Completeness and Cook's theorem - PSPACE-Completeness
Learning and Teaching
|Completion of assessment task||15|
|Preparation for scheduled sessions||18|
|Wider reading or practice||41|
|Total study time||150|
Resources & Reading list
Dexter C. Kozen (1999). Automata and Computabilty.
Dewdney AK (2001). The (new) Turing Omnibus.
Barwise J and Etchemendy J (1993). Turing's World.
Cohen D (1996). Introduction to Computer Theory.
Hein J (2002). Discrete Structures, Logic, and Computability.
Jones ND (1997). Computability and Complexity.
Gruska J (1996). Foundations of Computing.
Sipser M, (1997). Introduction to the Theory of Computation.
Harel D (1992). Algorithmics: The Spirit of Computing.
Hey AJG (1996). Feynman Lectures on Computation.
|Exam (2 hours)||70%|
Repeat type: Internal & External