Teaching Responsibility

LJMU Schools involved in Delivery:

Computer Science and Mathematics

Learning Methods

Lecture

Workshop

Module Offerings

7112COMP-JAN-CTY

Aims

To provide a rationale for the major concepts involved in computing: Investigating the underpinnings of computer systems and the concepts upon which programming languages are founded. To build on previous knowledge, in software development, to formalise concepts of computability and complexity. To synthesise problem definitions and likely computability based on common varieties of problems.

Learning Outcomes

1.
Define, design and use formal models of computation, including finite state automata/machines, pushdown automata, and Turing machines, applied to grammars for languages and computational problems to ascertain the limits of computation.
2.
Apply knowledge on the limitations of computation to identify complexity classes, using time and space, and deduce the complexity of various algorithms: Using NP-completeness concepts to create proofs regarding the computational complexity of problems.

Module Content

Outline Syllabus:Automata and Languages Finite State Machines Deterministic, Non-Deterministic and Universal Turing Machines Recursive Functions, Primitive, Partial and Total Recursion Church Turing Thesis The Halting Problem and Decidability Complexity Theory Time Complexity Space Complexity Non-Deterministic Algorithms Complexity Classes P and NP NP Complete Problems
Module Overview:
Computation theory is concerned with describing the underlying foundations on which computing and computability is based. It aims to:
  • give insight into the characteristics of computation
  • provide a rationale for the major concepts involved in computing
  • build on previous knowledge, in software development, to formalise concepts of computability and complexity
  • synthesise problem definitions and likely computability based on common varieties of problems
Additional Information:Computation theory is concerned with describing the underlying foundations on which computing and computability is based. It aims to give insight into the characteristics of computation. As such knowledge of computation theory is essential for a complete understanding and best practice approaches for computing professionals. It provides the basic constructs on which all programming on computers is founded and shows that there are problems that cannot be solved. More importantly it also provides tools for identifying those problems amenable to solution. In addition computation theory formalises intuitive notions regarding computation itself.

Assessments

Centralised Exam

Centralised Exam