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:
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.