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

Содержание

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

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

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

Направление подготовки: Направление 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. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Введение в высокопроизводительные вычисления, OpenMP и OpenCL	- Существующие суперкомпьютерные системы - Модель общей памяти - Подходы к программированию MIMD и SIMD - Массивно-параллельные ускорители - Иерархия памяти
2.	Параллельные алгоритмы линейной алгебры	- Матричное умножение: оптимизация производительности различных реализаций на основе различных типов памяти устройства - Прямые методы решения СЛАУ: исключение Гаусса, разложение Холецкого, метод прогонки, параллельная реализация - Итерационные методы решения СЛАУ: метод Якоби, метод Зейделя, релаксационные методы, параллельная реализация
3.	Параллельные методы решения дифференциальных уравнений	- Решение систем обыкновенных дифференциальных уравнений - Решение волнового уравнения - Решение задачи теплопроводности - Решение задачи Дирихле для уравнения Пуассона
4.	Физически информированные нейронные сети	- Основы нейронных сетей - Основы методов оптимизации - Принципы преобразования задач, записанных в терминах дифференциальных уравнений, в оптимизационные - Повышение эффективности процедуры обучения
5.	Параллельные методы Монте-Карло	- Вычисление определенных интегралов - Способы уменьшения дисперсии - Генераторы псевдослучайных чисел - Подходы к распараллеливанию методов Монте-Карло
6.	Высокопроизводительные вычисления и современные языки программирования	- Многопоточность в современных языках программирования - Существующие обертки для OpenCL и CUDA - Другие высокоуровневые подходы к параллельному программированию

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

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

См. примеры:

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

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

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

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

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

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

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

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практические (лабораторные) занятия	Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа	Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка презентаций. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Доклад	Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Дискуссия	Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
Разработка отдельных частей кода	Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
Выполнение домашних заданий и групповых проектов	Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
Индивидуальная работа	При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
Тестирование (устное/письменное)	При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.

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

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

Участник:StasFomin/Innopolis/Wtf