Аспирантура
2023/2024
Теоретическая информатика
Статус:
Курс по выбору
Направление:
00.00.00. Аспирантура
Когда читается:
1-й курс, 1 семестр
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Баувенс Бруно Фредерик Л.
Язык:
английский
Кредиты:
4
Контактные часы:
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.
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
- HomeworkThe 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 semesterGrade = 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