Theory of Computation module (AC32008)
About the Module
This module aims to introduce general models of computation such as finite state automata and Turing machines and their relationship to classes of languages, and use these models to explore the limits of the power of computers.
There are 20 SCQF points available on this module.
|1||Introduction to languages, finite automata|
|2||Deterministic and nondeterministic finite automata; equivalence of DFA and NFA|
|3||Regular expressions, equivalence with finite automata, Pumping Lemma|
|4||Turing machines, (partially) decidable languages, computable functions|
|5||Church-Turing thesis, TMs as generators, Universal Turing Machines|
|6||Undecidability, the Halting Problem, examples of undecidable problems|
|7||Time complexity, decision problems, polynomial time, the class P|
|8||Non-deterministic TMs, polynomial transformations, the class NP|
|9||NP-completeness, Cook's theorem, examples of NP-complete problems|
Assessment and Coursework
Coursework counts for 20% of the final module mark.
The final degree exam counts for 80% of the final module mark.
|Title||Week Given||Week Due||Effort Expected (hours)||Value (%)|
|Class Test 1||5||5||10||10|
|Class Test 2||9||9||10||10|
All course material is available on My Dundee. This includes copies of lecture materials, practical exercises and assignments. The reading list for this module can be accessed from My Dundee, and provides recommended materials for completing the module.