Основы теории трудноразрешимых задач

Бакалавриат 2025/2026

Статус: Курс по выбору (Компьютерные технологии, системы и сети)

Кто читает: Департамент информатики

Где читается: Школа информатики, физики и технологий

Когда читается: 2-й курс, 3, 4 модуль

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

Преподаватели: Мухин Михаил Сергеевич

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

Кредиты: 3

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

Дополнительные материалы в LMS Задать вопрос

Аннотация

Дисциплина нацелена на изучение современного состояния системного анализа и теории сложных систем. Раскрыты когнитивные аспекты оценки сложности. Дано описание проблемы сложности. Приведены основные направления исследований в теории алгоритмов, определены базовые понятия и требования, предъявляемые к написанию алгоритмов и определению порядка их сложности.

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

освоение студентами основ теории сложности и различных типов алгоритмов, таких как вероятностные и параметризованные.

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

Студент умеет использовать основные классы языков в теории сложности; основные методы и инструменты теории сложности;
Студент умеет применять неравенство Чернова;
Студент умеет строить вероятностные алгоритмы;
Студент умеет доказывать PSPACE-полноту различных задач; NP-полноту различных задач; NL-полноту различных задач.

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

Раздел 1. Машина Тьюринга. Иерархия по времени. Теорема Ладнера. Сложность по памяти.
Раздел 2. Класс NL. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. Полиномиальная иерархия.
Раздел 3. Вероятностные алгоритмы. Оценки Чернова. Схемы. Теорема Вэлианта-Вазирани.

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

Homework
Домашнее задание выдается студентам в одном варианте и состоит из 7 задач. Срок выполнения домашнего задания - 2 недели. Форма представления обучающимися домашнего задания - представленные в письменном виде решения задач. Шаблон отчёта о домашнем задании приведён в файле «HomeWork.pdf».
In-class assignment
Контрольная работа проводится в письменной форме. Каждый студент получает 6 задач. На проведение контрольной работы отводится 1,5 часа
Экзамен
Экзамен проводится в письменной форме во время контактной работы в соответствии с расписанием в присутствии преподавателя (синхронный элемент контроля). Продолжительность – 60 минут. Экзаменационный билет содержит пять вопросов из перечня вопросов к экзамену.

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

2025/2026 4th module
0.3 * Homework + 0.3 * In-class assignment + 0.4 * Экзамен

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

Авторы

Любавина Светлана Вячеславовна
Марковская Наталья Владимировна
Овчинников Андрей Анатольевич

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