Theory of Computing THC
Instructor: Dr Gyula Y. KATONA
Text: Michael Sipser: Introduction to the Theory
of Computation, Springer
Prerequisite: some introductory combinatorics, algebra
and number theory (e.g. definitions and basic properties of
graphs, binomial coefficients, primes and groups) is
helpful.
Course description:
-
Finite automata, regular and non-regular languages, pumping lemma.
-
Context-Free languages.
-
Turing Machines, universal Turing machines.
-
The existence of universal Turing machines.
-
Recursive functions. Recursive, recursively enumerable languages.
-
Algorithmic decidability,
-
Halting problem and other undecidable problems.
-
Storage and time, general theorems on space and time complexity
-
Non-deterministic Turing-machines. NP and co-NP.
-
Cook's theorem: SAT is NP-complete.
-
Other NP-complete problems.
-
RAM machines.
-
Kolmogorov-complexity of sequences.
-
Communication complexity.
The course has very little connection to programming, you don't need to know how to write programs. It is about the theoretical questions that arise from computers. Consider it more mathematics than computer science. However, nowadays every mathematician should know something about complexity theory.