Postgraduate course 2023/2024

Theoretical Informatics

Type: Elective course

Area of studies: Postgraduate Studies

Delivered by: Big Data and Information Retrieval School

When: 1 year, 1 semester

Mode of studies: offline

Open to: students of one campus

Instructors: Bruno Frederik Bauwens

Language: English

ECTS credits: 4

Contact hours: 38

Course Syllabus

Abstract

The course studies the classification of problems by their difficulty. At the easiest level, there are the problems modeled by regular languages, and represent problems solvable with a constant amount of memory. On the other extreme, there are problems that can not be solved at all, for example, given a set of (Wang) tiles, can we cover the whole plane with them, while no 2 tiles overlap? Given an equation with integer coefficients in many variables, can we find an integer solution? Most optimization problems in research are in the middle, they are NP-complete. In this course, we learn the theory behind these levels of difficulty and how we can classify the level of difficulty. Finally, we consider parameterized complexity. This theory studies various brute force algorithms and is useful to recognize finer levels of difficulty inside NP-complete problems.

Learning Objectives

• Understand basic concepts of the computation theory

Expected Learning Outcomes

• Understand basic concepts of the computability theory
• Understand Turing machines, multitape Turing machines, connection between them

Course Contents

• Regular languages 1
• Regular languages 2
• Undecidable problems and computability theory
• The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness
• Circuits and completeness of 3SAT. More reductions
• Parameterized complexity, the class FPT, kernelization
• Treewidth and the W-hierarchy

Assessment Elements

• Homework
  The evaluation criteria is that there are 6 homeworks. Each exercise in each homework has the same weight. The final grade is then arithmetically rounded.

Interim Assessment

• 2023/2024 1st semester
  Grade = w_1 O_1 + ... + w_6 O_6, where O_i = score of the i-th homework. where w_i = [number of exercises in HW_i]/[total number of exercises in all homeworks]

Bibliography

Recommended Core Bibliography

• Cristopher Moore, & Stephan Mertens. (2011). The Nature of Computation. OUP Oxford.
• Discrete Mathematics for Computer Science - CCBY4_028 - Mark A. Fitch - 2022 - Open Educational Resources: libretexts.org - https://ibooks.ru/bookshelf/390548 - 390548 - iBOOKS

Recommended Additional 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