Бакалавриат
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), где Б — бонус за активное участие в занятиях/выбор сложных заданий в домашней работе. Автоматы не предусмотрены.
Список литературы
Рекомендуемая основная литература
- Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
- Cristopher Moore, & Stephan Mertens. (2011). The Nature of Computation. OUP Oxford.
Рекомендуемая дополнительная литература
- Cormen, T. H. (2001). Introduction to Algorithms: Vol. 2nd ed. MIT Press.