Computation Theory

Learning Outcomes

The learning objectives of the course are:

• To introduce students to the mathematical infrastructure of computation and specifically to automata theory, the theory of formal languages and grammars, the concepts of algorithm, diagnosability, complexity and computability.
• To develop students’ ability to understand and construct mathematical proofs for calculations and algorithms.

Upon completion of the course the student should be able to:

• categorize abstract machines and construct abstract machines suitable for specific problems
• demonstrate an understanding of the advantages and limitations of analytical techniques in software development
• recognize the importance of complexity classes and calculate the complexity of specific types of algorithms
• demonstrate a deeper and broader understanding of classes of complexity
• prove the basic results of the Theory of Computation

Indicative Module Content

• INTRODUCTION: Automata, Computability, and Complexity, mathematical concepts and terminology
• REGULAR LANGUAGES: Finite Automata, Arbitrary, Regular Expressions, Non-Regular Languages
• UNCONSUMABLE LANGUAGES: Uncontextualized Grammars, Stack Automata, Non-Uncontextualized Languages,
• THE CHURCH-TURING DOCTRINE: Turing Machines, Variations of Turing Machines, The Definition of Algorithm,
• DIAGNOSTICABILITY: Diagnosable Languages, The Termination Problem
• TIME COMPLEXITY: Measuring Complexity, The P Class, The NP Class
• SPATIAL COMPLEXITY: Savitch’s theorem, The PSPACE class