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

Бакалавриат 2021/2022

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Базовая кафедра фирмы 1С

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

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

Формат изучения: без онлайн-курса

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

Преподаватели: Дайняк Александр Борисович

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

Кредиты: 10

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

Полная версия программы учебной дисциплины

Аннотация

Один из основных вопросов, на который должен отвечать дизайнер алгоритмов — как эффективно алгоритм может масштабироваться с ростом объёма обрабатываемых данных, как будет расти объём памяти и процессорного времени, требуемого алгоритмом. Ответ на этот вопрос зависит от многих факторов: работаем мы на одном процессоре/ядре или нескольких; допускается ли неточный ответ с заранее оговоренной погрешностью или вероятностью погрешности, какие компромиссы между временем и памятью мы готовы принять, и пр. Математический аппарат, формализующих подобные вопросы и ответы на них, и составляет основу современной теории сложности вычислений. Беря своё начало в математической логике в первой половине XX века, теория сложности со временем обрела прочные связи с прикладной информатикой и является теперь стандартным элементом учебного плана студентов, изучающих компьютерные науки по всему миру. В рамках курса мы обсудим различные модели вычислений (т.е. формальные определения того, что такое компьютер), и обсудим, как формальные свойства отвечают реальным свойствам настоящих компьютеров. Мы введём основные сложностные классы — наборы задач, которые допускают решения различной эффективности. Введём понятия оракула и сводимости (отвечающие прикладным ситуациям использования библиотечных функций в программировании). Кроме этого, мы обсудим вероятностные алгоритмы, узнаем, почему вопрос “P=NP?” считается одним из центральных в современной теоретической информатике, и почему не стоит унывать, встретившись с формально трудной задачей на практике.

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

Знание основных теоретических моделей вычислений и соответствие их реальным вычислительным архитектурам
Знание основных различных характеризаций задач computer science как «сложных» или «простых», умение приводить аргументы в пользу «сложности» задач.
Знание основных подходов к решению «сложных» задач и их пределов.

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

Знание основных теоретических моделей вычислений и соответствие их реальным вычислительным архитектурам.

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

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

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

Домашние задания
Выдаются раз в две недели. Содержание заданий: реализация алгоритмов; ознакомление и суммаризация теоретических статей/разделов из книг.
Тесты на занятиях
Контроль посещаемости и самоконтроль знаний студентов. Напрямую не влияют на оценку.
Посещаемость

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

2021/2022 учебный год 3 модуль
Итог = Мин(Округление(0.1 * Посещаемость + 0.9 * ДЗ + Б), 10), где Б — бонус за активное участие в занятиях/выбор сложных заданий в домашней работе. Автоматы не предусмотрены.

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