Версия 18:17, 30 марта 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/Дополнительные_материалы_по_приближенным_алгоритмам

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

броузер.

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

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

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