Theory of Computation

The objective of this course is to familiarize MicroMaster Algorithm students with the theoretical foundations of problem computability and, for computable problems, the fundamentals of algorithm science and complexity analysis. Topics include various computational models, their computational capabilities, their computational properties, and their applications. Other topics include concepts of computability, decidability, and the Church-Turing thesis regarding algorithms. Special emphasis will be placed on the theory of algorithm complexity and the relationships between complexity classes.

• Preliminaries (2 sessions)
  • Introduction to main concepts and history of computation theory, complexity theory, and formal languages/automata theory
  • Supplementary topics in logic and set algebra, countable sets, languages and grammars
• Finite Automata and Regular Languages (4 sessions)
  • Deterministic and non-deterministic finite acceptors, regular languages and regular expressions
  • Right-linear and left-linear grammars, regular grammars, Pumping lemma for regular languages
• Context-Free Languages and Pushdown Automata (4 sessions)
  • Context-free grammars, context-free languages
  • Leftmost and rightmost derivations, parse trees, ambiguous and unambiguous grammars, inherently ambiguous/unambiguous languages
  • Simplification of context-free grammars and their Chomsky/Greibach normal forms
  • Pushdown automata, equivalence between pushdown automata and context-free grammars, deterministic pushdown automata
  • Deterministic context-free languages, non-context-free languages, Pumping lemma for context-free languages
• Computability (4 sessions)
  • Turing machines, Church-Turing thesis
  • Decidability and undecidability, recognizability and unrecognizability of languages and problems
  • Halting problem, Post correspondence problem, and other examples of problems from decidability/recognizability perspective
  • Problem reduction methods for proving (un)decidability or (un)recognizability
• Computational Complexity Theory (4 sessions)
  • Time complexity of algorithms, polynomial-time reduction
  • Time complexity classes including P, NP and Co-NP classes, complete problem definition with emphasis on NP-complete problems
  • Methods for proving NP-completeness, Cook-Levin theorem
  • Examples of NP-complete problems (Hamiltonian cycle, vertex cover, subset sum, etc.)
  • Space complexity of problems and related classes (logarithmic space, polynomial space and their complements)
  • Relationships between space complexity classes
  • Relationships between time and space complexity classes

• Homework assignments: 6 points
• Final exam: 14 points