Course Details in 2020/21 Session

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
Pre-requisites
Co-requisites	LC Mathematical and Logical Foundations of Computer Science - (06 35391)
Restrictions	Incoming exchange students should have the equivalent of grade A at A-level in Mathematics.
Contact Hours	Lecture-44 hours Practical Classes and workshops-22 hours Guided independent study-134 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 non-computability 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 non-computability and undecidability issues
Assessment	35392-01 : Continuous Assessment : Coursework (100%)
Assessment Methods & Exceptions	Main Assessments: Continuous assessment (100%) Supplementary Assessments: Continuous assessment (100%) over the Summer period
Other
Reading List