Theory of Computing - CO519

Looking for a different module?

Module delivery information

Location Term Level1 Credits (ECTS)2 Current Convenor3 2021 to 2022
Canterbury
Autumn 5 15 (7.5) DR S Kahrs checkmark-circle

Overview

Propositional & Predicate Logic, including proofs. Formal languages: finite automata, regular expressions, CFGs. Turing machines, decidability.

Details

Contact hours

Total contact hours: 32
Private study hours: 118
Total study hours: 150

Method of assessment

Main assessment methods
Logic and Regular Languages (Coursework) (25%)
Context-Free Languages and Decidability (Coursework) (25%)
2-hour unseen examination (50%)

Indicative reading

Huth, Ryan: Logic in Computer Science
Boolos, Jeffrey: Computability and Logic
Martin: Introduction to Languages and the Theory of Computation

See the library reading list for this module (Canterbury)

Learning outcomes

8. The intended subject specific learning outcomes.
On successfully completing the module students will be able to:
8.1 understand specifications in formal logical notation [A5]
8.2 write formal proofs [A4,A5,C4]
8.3 understand the expressiveness of various language formalisms [B1,D4]
8.4 appreciate the difference between decidable and undecidable problems [D4]

9. The intended generic learning outcomes.
On successfully completing the module students will be able to:
9.1 Understand, use and work with formal notation of various forms [A4,A5,B3]
9.2 Understand and judge the inherent complexity of certain classes of problems, and the techniques needed to approach them [A4,A5,B1,B3,B5,C1,C4,D4,D5]

Notes

  1. Credit level 5. Intermediate level module usually taken in Stage 2 of an undergraduate degree.
  2. ECTS credits are recognised throughout the EU and allow you to transfer credit easily from one university to another.
  3. The named convenor is the convenor for the current academic session.
Back to top

University of Kent makes every effort to ensure that module information is accurate for the relevant academic session and to provide educational services as described. However, courses, services and other matters may be subject to change. Please read our full disclaimer.