Postgraduate course 2019/2020

Theoretical Computer Science

Type: Elective course

Area of studies: Computer and Information Scienc

Delivered by: Big Data and Information Retrieval School

Where: Faculty of Computer Science

When: 2 year, 1 semester

Mode of studies: offline

Instructors: Bruno Frederik Bauwens

Language: English

ECTS credits: 4

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

• 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

• 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

• 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

• Intermediate exam
• 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 (1 semester)
  0.5 * Final assessment + 0.5 * Intermediate exam

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