Module Title  LC Theories of Computation 
School  Computer Science 
Department  Computer Science 
Module Code  06 35392 
Module Lead  Dr Kashif Rajpoot 
Level  Certificate Level 
Credits  20 
Semester  Semester 2 
Prerequisites 

Corequisites 
LC Mathematical and Logical Foundations of Computer Science  (06 35391)

Restrictions  Incoming exchange students should have the equivalent of grade A at Alevel in Mathematics. 
Contact Hours 
Lecture44 hours
Practical Classes and workshops22 hours
Guided independent study134 hours
Total: 200 hours

Exclusions  
Description  Computers have been used to solve an astonishing range of different problems, but this does not mean that they can be used to solve all possible problems: some cannot be solved efficiently, and some cannot be solved at all. In this module, we will introduce a set of principles and techniques for formalising computation and computability to understand what problems can be solved, how efficiently they can be solved, and what problems cannot be solved. We will develop mathematical models of computations using ideas such as sutomata theory (including Turing machines), of formal languages using ideas such as regular expressions and grammars, and will conclude by considering the notions of noncomputability and complexity. 
Learning Outcomes  By the end of the module students should be able to:  Explain and apply mathematical models of computations
 Explain and apply concepts from automata theory, formal language theory, computability theory and complexity theory
 Describe and use the connection between finite automata and regular language
 Explain noncomputability and undecidability issues

Assessment 
3539201 : Continuous Assessment : Coursework (100%)

Assessment Methods & Exceptions  Main Assessments: Continuous assessment (100%)
Supplementary Assessments: Continuous assessment (100%) over the Summer period

Other  
Reading List 
