2026/2027

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

ID 1231520

Статус: Маго-лего

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 1, 2 модуль

Охват аудитории: для своего кампуса

Язык: русский

Кредиты: 6

Контактные часы: 56

Программа дисциплины

Аннотация

Цель вычислительной сложности - классифицировать вычислительные задачи по их сложности. В данном случае сложность измеряется различными ресурсами, необходимыми для получения ответов, такими как время вычислений, пространство, случайность, размеры схем. В частности, мы учимся отличать задачи, решаемые за полиномиальное время, от NP-сложных задач. Считается, что последние требуют экспоненциального времени для наихудших случаев, и, следовательно, в приложениях необходимо переформулировать проблему, использовать эвристику или оптимизировать полный поиск. Последнее теоретически изучается в области параметризованной сложности.

Цель освоения дисциплины

• Знать доказательство теоремы Кука-Левина: 3SAT является NP-полным
• Доказывать, что PSPACE = NPSPACE и что задача TQBF является PSPACE завершенной
• Вычислять с помощью Oracle и понимать барьер диагонализации при решении задачи P против NP
• Ознакомиться с известными алгоритмами потоковой передачи, такими как SpaceSaving, CountMinSketch, чтобы найти наиболее часто встречающийся элемент
• Знать параметризованные классы сложности FPT, W[i], XP. Применять метод кернелизации для получения FPT-алгоритмов

Планируемые результаты обучения

• Знать: Определения машин Тьюринга. Классы TIME(f(n)) и SPACE(f(n)). Теоремы об иерархии времени и пространства
• Знать: Определения классов L, NL, P, NP, PSPACE, EXP, NEXP, EXPSPACE, BPP, RP, #P и включений между ними. Некоторые известные проблемы в этих классах.
• Уметь в частных случаях проводить различие между задачами в P, которые являются NP-полными и которые являются PSPACE-полными

Содержание учебной дисциплины

• Этот курс: что и почему?
• Машины Тьюринга
• Теоремы об иерархии
• Класс NP
• NP-полнота
• Схемы
• Complexity zoo
• PSPACE
• Вероятностное вычисление
• Алгоритмы потоковой передачи данных
• Параметризованная сложность
• Алгоритмы аппроксимации

Элементы контроля

• Домашние задания
  Список заданий для каждого семинара содержит 2 вопроса для домашнего задания, аналогичные тем, которые были заданы на семинаре. Каждые 14 дней необходимо отправлять 4 вопроса. Иногда в ДЗ содержатся дополнительные баллы, они добавляются к баллам за экзамен.
• Коллоквиум
  В декабре. Студент получает 2 вопроса из списка, направленного за 2 недели до проведения. Ответы готовятся в письменном виде, и преподаватель проверяет их понимание, уточняя детали или приводя простые примеры. Учащиеся не могут обращаться к каким-либо справочным материалам
• Экзамен
  Во время сессии в декабре. После модуля 1 проводится письменный экзамен. Студенты могут использовать основные учебники и конспекты лекций, представленные в wiki. Экзамен проводится в компьютерном классе. В задании есть 4 вопроса, аналогичных тем, что были на семинарах и в домашних заданиях.

Промежуточная аттестация

• 2026/2027 2nd module
  0.35 * Домашние задания + 0.3 * Экзамен + 0.35 * Коллоквиум

Список литературы

Рекомендуемая основная литература

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

Рекомендуемая дополнительная литература

• The nature of computation, Moore, C., 2012

Авторы

• Емашева Валерия Анатольевна