• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2022/2023

Теория сложности вычислений

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус: Курс по выбору (Программная инженерия)
Направление: 09.03.04. Программная инженерия
Когда читается: 4-й курс, 1-3 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Преподаватели: Баувенс Бруно Фредерик Л., Захаров Павел Александрович, Таламбуца Алексей Леонидович
Язык: английский
Кредиты: 10
Контактные часы: 62

Course Syllabus

Abstract

This course teaches a mathematical theory that helps to invent better algorithms. With “better” we mean that the algorithms use fewer resources such as time or memory. We also consider parallel computation, distributed systems and learning problems. In these settings we might also optimize other types of resources. For example, in distributed systems we might want to minimize the amount of communication. We focuss on worst case guarantees. A large part of our time is devoted to the study of what is not possible. In other words, we study fundamental barriers for the existence of programs that use fewer resources than a given bound.
Learning Objectives

Learning Objectives

  • understand the concepts of the complexity classes P, NP, coNP, #P, EXP, NEXP, L, NL, PSPACE, EXPSPACE, BPP, RP
  • be able to critically analyse resources used by a program (and optimize them at a high level)
  • be able to recognize intractable problems and categorize their difficulty
  • have deeper understanding and trained problem solving skills of known materials in: algebra, probability theory, discrete math, algorithms
Expected Learning Outcomes

Expected Learning Outcomes

  • Be able to work with complexity classes P, PSPACE, EXP.
  • Be able to understand hierarchy theorems
Assessment Elements

Assessment Elements

  • non-blocking Homework
  • non-blocking Colloquium
  • non-blocking Project
    During the 3rd module Januari till March 2023. The task is to understand a theoretical paper better by either (Th) Rewrite some mathematical proof of a research paper in a more accessible way using your own words. You also need to give a lecture (you are not allowed to look at the paper during the lecture). I need to work out examples. Possibly examples that I give you on the spot. (Imp) Implement an algorithm (or parts of an algorithm) from a research paper and demonstrate that it works. You can propose projects yourself, but it is not allowed to have a theoretical paper about software verification. (Because there are too many definitions, and during the lecture it usually turns out the student does not understand them.)
  • non-blocking Exam
    The exam consists out of 8 exercises that you must solve in 3 hours time. There will be copies of Sipser's book available (as well as Arora and Barak and Mertens and Moore). You may bring your own copy if you have it, as well as handwritten notes. You can do the colloquium and the exam online if you received permission from the student office.
Interim Assessment

Interim Assessment

  • 2022/2023 2nd module
    0.5 * Homework + 0.5 * Colloquium
  • 2022/2023 3rd module
    0.25 * Colloquium + 0.25 * Homework + 0.25 * Project + 0.25 * Exam
Bibliography

Bibliography

Recommended Core Bibliography

  • Michael Sipser. (2005). Introduction to the Theory of Computation, Second Edition.
  • Лекции по дискретной математике : учебник, , 2021

Recommended Additional Bibliography

  • Parameterized Algorithms. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. - 2015, Springer International Publishing

Authors

  • Оруджева Альбина Александровна
  • PODOLSKIY VLADIMIR VLADIMIROVICH
  • Петрухина Анастасия Сергеевна