Delivered at:: Department of Informatics

Course type:: Elective course

When:: 2 year, 3, 4 module

Instructor

Mukhin, Mikhail

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

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

Bachelor’s Programme 'Computer technologies, systems and networks'

Fundamentals of the Theory of Intractable Problems

Instructor

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