Текущая версия на 14:35, 31 марта 2024

Требуемая страница

• https://eduwiki.innopolis.university/index.php/BSc:_EfficientAlgorithms

Зарегистрироваться-залогинится не дает:

Поэтому копируйте отсюда:

Эффективные алгоритмы для труднорешаемых задач

Квалификация выпускника: бакалавр

Направление подготовки: Направление 01.04.02 «Прикладная математика и информатика».

Направленность (профиль) образовательной программы: «Системное программирование и компьютерные науки». Образовательная программа «Вычислительная математика».

Программу разработал(а): Фомин С.А.

1. Краткая характеристика дисциплины

Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области программного обеспечения и его разработки; искусственного интеллекта и его применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают:

• Теорию сложности, для определения
  • классов задач допускающих эффективное решение детерминированными и вероятностными алгоритмами — классы P, RP, ZPP, BPP и т.п.
  • классов задач, для которых считается невозможным существование эффективных алгоритмов точного решения — NP-complete, PSPACE-complete.
  • классов задач, для которых считается невозможным существование эффективных алгоритмов поиска приближенного решения — APX-complete.
• Классические алгоритмы решения задач на графах и множествах (кратчайшие пути, покрытия, сортировки)
• Алгоритмы, подходы и эвристики, для решения NP-полных задач:
  • приближенные алгоритмы с гарантированной точностью, включая алгоритмы с любой, заранее выбранной точностью — PTAS, FPTAS.
  • вероятностные алгоритмы, и эвристики их порождения — методы Монте-Карло, вероятностного округления и т.п.
  • методы дерандомизации — получения детерминированных приближенных алгоритмов из вероятностных.
• Практические методы программирования для реализации всего перечисленного.

2. Перечень планируемых результатов обучения

В ходе курса студенты научатся:

• Оценивать вычислительную сложность алгоритмических задач (в терминах вычислительных ресурсов).
• Классифицировать алгоритмические задачи их в основных сложностных классах — базовое ориентирование в огромном «зоопарке» классов сложности — студенты познакомятся с известными теоремами и открытыми гипотезами о соотношении сложностей задач.
• Устанавливать связи между сложностными классами.
• Выделять сложнорешаемые и практически решаемые алгоритмические задачи.
• Для трудноразрешимых задач, строить приближенные и вероятностные алгоритмы и дерандомизировать некоторые из них — познакомиться с несколькими красивыми и широко используемыми в узких кругах полиномиальными алгоритмами.
• Практически решать на Python классические задачи (возможность в дальнейшем использовать полученные навыки в дальнейшей работе по окончании ВУЗа), применение классических эвристик — «жадность», «динамическое программирование», известных алгоритмов на сортировки и графы и т.п.
• Использовать достижения программной индустрии — ЦЛП-солверы, SAT-солверы, Pyomo-формулировки для постановки и решения задач оптимизации.

Дисциплина участвует в формировании следующих компетенций образовательной программы:

• «СПК-9» — способность осуществлять математическую постановку задачи и решать ее современными оптимизационными методами для оптимального выбора средств защиты информации при ограничениях на их стоимость, габариты, энергопотребление и др.
• «СПК-1» — способность осуществлять поиск, изучение, обобщение и систематизацию научно-технической информации, нормативных и методических материалов в сфере профессиональной деятельности, в том числе на иностранном языке.
• «СПК-7»— способность разрабатывать научно-техническую документацию, готовить научно-технические отчеты, обзоры, публикации по результатам выполненных работ.

Общая характеристика результата обучения по дисциплине

Знания

• теоретических моделей вычисления.
• классов сложности оптимизационных задач.
• методов полиномиальной сводимости классических NP-полных задач.
• методов анализа сложности детерминированных и вероятностных алгоритмов, анализа точности в среднем и «для почти всех исходных данных».

Умения

• постановки оптимизационной формулировки для оптимизационной задачи
• использование ЦЛП и SAT-солверов
• доказательство труднорешаемости оптимизационной задачи
• оценка сложности алгоритма, «в худшем» и «в среднем»
• оценка качества приближения алгоритма, «в худшем» и «в среднем»

Навыки (владения)

• программирование на Python
• работа с Jupyter-ноутбуками
• работа с IDE VSCode/code-server
• использование фреймворка Pyomo, для постановки оптимизационных задач и решения их ЦЛП-солверами
• Использование фреймворка pySAT для решения SAT-задач

3. Структура и содержание дисциплины

Полугодовой курс состоит из двух основных частей:

• Закладываются основы теории сложности вычислений, которые далее при желании можно развивать в различных направлениях.
• Рассказывается о нескольких эффективных алгоритмах и подходах для решения труднорешаемых задач.

Основные вопросы курса: какие бывают вычислительные ресурсы, как подсчитывать их необходимое количество для решения данной алгоритмической задачи, как отличить решаемые на практике задачи от нерешаемых и как наиболее эффективно работать с решаемыми. Много внимания уделяется изучению различных сложностных классов, связей между ними и классификации конкретных задач.

Как правило, в семестре разбираются следующие темы.

Формально об алгоритмах. Вычислительные модели

• Примеры простых алгоритмов
• Random Access Machines
• Одно и много-ленточные Машины Тьюринга
• Универсальная машина Тьюринга
• Вычислимость и разрешимость

Временная и пространственная сложность алгоритмов

• Классы DTIME, P, EXPTIME
• Классы DSPACE, PSPACE

Полиномиальные сводимости и NP-полные задачи

• Полиномиальные сводимости по Куку и Карпу.
• Классы NP, coNP, NPC

Вероятностные вычисления и их сложность

• Классы «эффективно решаемых задач» RP, coRP, BPP
• Класс «Безошибочно решаемых задач» ZPP
• Неамплифицируемый класс PP

Жадные алгоритмы и анализ их качества

• Жадные алгоритмы в задачах о покрытии о покрытии множеств и вершин
• Жадный алгоритм в задаче о рюкзаке:

Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке

• Динамическое программирование для задачи о рюкзаке
• Использование жадных алгоритмов и эвристик округления для получения FPTAS-алгоритма

Алгоритмы полиномиальные в среднем

• Полиномиальный в среднем алгоритм для задачи о рюкзаке:
• Полиномиальный в среднем алгоритм для SAT:
• Полиномиальный в среднем алгоритм для задачи упаковки:

Приближенный алгоритм для метрической задачи коммивояжера

Вероятностные алгоритмы

• Вероятностная проверка тождеств
• Вероятностный подсчет числа выполняемых наборов для ДНФ
• Вероятностное округление для задач MAX-SAT и MAX-CUT

Дерандомизация

Детерминированный приближенный алгоритм для MAX-SAT, полученный из вероятностного алгоритма.

Неаппроксиминуемость

• Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема
• PCP и аппроксимируемость

4. Методические и оценочные материалы

Задания для практических занятий:

См. примеры:

• «Практикуемся в алгоритмах»
• «Моделирование труднорешаемых задач»
• «Моделирование бизнес-задач»
• «Решаем теоретические упражнения»

Контроль успеваемости обучающихся по дисциплине:

См. примеры тестов:

• https://discopal.ispras.ru/Special:MediawikiQuizzer/Algs-innopolis-exam

Перечень учебно-методического обеспечения дисциплины

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

Основная книга

«Эффективные алгоритмы и сложность вычислений»

Дополнительные материалы

• https://discopal.ispras.ru/Дополнительные_материалы_по_сложности_вычислений
• https://discopal.ispras.ru/Дополнительные_материалы_по_приближенным_алгоритмам
• Н.Н. Кузюрин, С.А. Фомин, Эффективные алгоритмы и сложность вычислений», 2007 издательство МФТИ. ISBN 5-7417-0198-1.
• S.Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
• M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
• C.Moore, S. Mertens, The Nature of Computation, Oxford University Press, 2011
• Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание, Вильямс, 2019.
• O. Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
• A. Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019.
• C.Papadimitriou, Computational Complexity, Addison Wesley, 1994
• В.Н.Крупский. Введение в сложность вычислений, Москва, Факториал Пресс, 2006
• С.А. Абрамов, Лекции о сложности алгоритмов, Москва, МЦНМО, 2009
• Д.В.Мусатов. Курс лекций по сложности вычислений (видеолекций, конспекты).
• М.Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Москва, Мир, 1982
• М. Вялый, А. Китаев, А. Шень, Классические и квантовые вычисления, Москва, МЦНМО, 1999.

Необходимое программное обеспечение для студентов

броузер.

Методические указания для обучающихся по освоению дисциплины

Самостоятельная работа учащихся состоит:

• в изучении лекционного материала, доступных видео и конспектов лекций учебно-методической литературы, включая базовую книгу авторов курса
• подготовки к практическим заданиям текущего контроля и промежуточной аттестации:
• тесты по всем материалам курса
• решение теоретических задач по теории сложности
• решение алгоритмических задач на языке Python
• конструктивная постановка и исследование труднорешаемых задач с помощью ЦЛП и SAT-формулировок, с помощью технологий Jupyter Notebook, Pyomo и др.

Методы и технологии обучения, способствующие формированию компетенции

• Коллаборативное программирование и другая работа в реальном времени, см. доклад «Современные «интерактивные среды» и «живые лаборатории» — эффективное дистанционное образование по алгоритмам и математическим дисциплинам»
• Обучающие вики-тесты, см. доклад «MediaWikiQuizzer или ВикиЭкзамены — тесты, удобные и для преподавателя и для студента»
• Коллаборативная среда на wiki-платформе, см. доклад «Эффективная «домашка» — задачи студентам на MediaWiki»
• Видеозаписи миникурсов, см. доклад «OBS — швейцарский нож передачи знаний»