- students are familiar with basic concepts in the theory of computation: finite state machines, regular expressions, Turing machines, computable functions, Godel-incompleteness, polynomial time and space complexity, NP-hardness, probabilistic computation, hardness of approximation
- to train the ability of mathematical problem solving
- to improve English writing and presentation skills
- The ability to carry out research in the field of professional activity using current research methods and information and communication technologies
- The ability to carry out theoretical analysis and design of programming languages and systems, to use methods for analysing program semantics
- The ability to develop and use methods for improving the efficiency and reliability of data and knowledge processing and transmission in computing machinery, systems, and networks
- The ability to do research in transformation of information into data and knowledge, models of data and knowledge representation, methods for knowledge processing, machine learning and knowledge discovery methods, principles of building and operating software for automation of these processes
- Automata and regular languagesDiscrete finite automata: deterministic, non-deterministic, equivalence and pumping lemma. Regular expressions and equivalence with finite automata.
- Computability theoryTuring machines: expressive power, equivalence with register machines, tag-systems. Halting problem, undecidability of tilings and a few other problems.
- Godel incompletenessProof systems: decidability of arithmetic with addition, undecidability of number theory, and Godel incompleteness.
- Computational complexityClasses P and NP, dynamic programming, the Levin-Cook theorem, NP-completeness of Hamiltonian path, vertex cover, etc. Classes L, PSPACE, NPSPACE, EXPSPACE, Savitch theorem, completeness of: formula game, generalized geography, testing equivalence of regular expressions. Oracle computation and oracles A and B for which P^A = NP^A and P^B != NP^B.
- Intermediate exam
- Final assessmentStudents with a decent background in mathematics and theoretical computer science have the option to do a project, instead of the 2 exams. They should read 1 or more theoretical research papers, rewrite in a self-contained form intended for a general audience in computer science, and give a lecture.
- Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
- Introduction to the theory of computation, Sipser M., 2013