• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Postgraduate course 2020/2021

Theoretical Computer Science

Type: Elective course
Area of studies: Informatics and Computer Engineering
When: 2 year, 1 semester
Mode of studies: offline
Language: English
ECTS credits: 5
Contact hours: 38

Course Syllabus

Abstract

The course teaches basic concepts from computability theory and comutational complexity, as well as a few advanced topics of interest. The course is intended for students with a diverse background (not necessarily in computer science), who already have some mathematical maturity after studying.
Learning Objectives

Learning Objectives

  • 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
Expected Learning Outcomes

Expected Learning Outcomes

  • 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
Course Contents

Course Contents

  • Automata and regular languages
    Discrete finite automata: deterministic, non-deterministic, equivalence and pumping lemma. Regular expressions and equivalence with finite automata.
  • Computability theory
    Turing machines: expressive power, equivalence with register machines, tag-systems. Halting problem, undecidability of tilings and a few other problems.
  • Godel incompleteness
    Proof systems: decidability of arithmetic with addition, undecidability of number theory, and Godel incompleteness.
  • Computational complexity
    Classes 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.
Assessment Elements

Assessment Elements

  • non-blocking Intermediate exam
  • non-blocking Final assessment
    Students 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.
  • non-blocking Intermediate exam
  • non-blocking Final assessment
    Students 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.
Interim Assessment

Interim Assessment

  • Interim assessment (1 semester)
    0.5 * Final assessment + 0.5 * Intermediate exam
Bibliography

Bibliography

Recommended Core Bibliography

  • 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

Recommended Additional Bibliography

  • Introduction to the theory of computation, Sipser, M., 2013