The intuitive notion of algorithm and effectively computable function.
Various mathematical formalizations of these notions (Turing machines, partially recursive functions).
The idea of the universal algorithm. Main ideas showing the equivalence of the above formalizations, Church-Turing thesis.
Halting problem, Post Correspondence problem, and further undecidable problems.
Universal function, Kleene's Normal Form Theorem, recursive and recursively enumerable sets, Post's Theorem.
Recursion Theorem, Rice's Theorem. Recursive reducibility. Creative sets.
Decidability of logical theories.
Time and space complexity of algorithms and problems. The P-NP question.
NP-completeness and PSPACE-completeness.
EXPTIME, EXPSPACE, provably intractable problems.
Approximation algorithms, probabilistic algorithms.
Parallel and distributed algorithms.
Further topics (alternation, cryptography, ...).
Various mathematical formalizations of these notions (Turing machines, partially recursive functions).
The idea of the universal algorithm. Main ideas showing the equivalence of the above formalizations, Church-Turing thesis.
Halting problem, Post Correspondence problem, and further undecidable problems.
Universal function, Kleene's Normal Form Theorem, recursive and recursively enumerable sets, Post's Theorem.
Recursion Theorem, Rice's Theorem. Recursive reducibility. Creative sets.
Decidability of logical theories.
Time and space complexity of algorithms and problems. The P-NP question.
NP-completeness and PSPACE-completeness.
EXPTIME, EXPSPACE, provably intractable problems.
Approximation algorithms, probabilistic algorithms.
Parallel and distributed algorithms.
Further topics (alternation, cryptography, ...).