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

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

Направление подготовки: 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.	Формально об алгоритмах. Вычислительные модели.	Примеры простых алгоритмов.Random Access Machines.Одно и много-ленточные Машины Тьюринга. Универсальная машина Тьюринга. Вычислимость и разрешимость.
2.	Временная и пространственная сложность алгоритмов.	Классы DTIME, P, EXPTIME. Классы DSPACE, PSPACE.
3.	Полиномиальные сводимости и NP-полные задачи.	Полиномиальные сводимости по Куку и Карпу. Классы NP, coNP, NPC.
4.	Вероятностные вычисления и их сложность.	Классы «эффективно решаемых задач» RP, coRP, BPP.Класс «Безошибочно решаемых задач» ZPP. Неамплифицируемый класс PP.
5.	Жадные алгоритмы и анализ их качества.	Жадные алгоритмы в задачах о покрытии о покрытии множеств и вершин. Жадный алгоритм в задаче о рюкзаке.
6.	Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке.	Динамическое программирование для задачи о рюкзаке. Использование жадных алгоритмов и эвристик округления для получения FPTAS-алгоритма.
7.	Алгоритмы полиномиальные в среднем.	Полиномиальный в среднем алгоритм для задачи о рюкзаке.Полиномиальный в среднем алгоритм для SAT.Полиномиальный в среднем алгоритм для задачи упаковки.
8.	Приближенный алгоритм для метрической задачи коммивояжера.Вероятностные алгоритмы.	Вероятностная проверка тождеств.Вероятностный подсчет числа выполняемых наборов для ДНФ.Вероятностное округление для задач MAX-SAT и MAX-CUT.
9.	Дерандомизация.	Детерминированный приближенный алгоритм для MAX-SAT, полученный из вероятностного алгоритма..
10.	Неаппроксиминуемость.	ВВероятностно проверяемые доказательства. PCP-системы. PCP-теорема. PCP и аппроксимируемость.

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

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

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Пределы последовательностей и функций.	1. Найти предел последовательности \\[S=\\sum_{n=1}^\\infty \\left(f_n-f_{n+1}\\right)\\]
2.
3.
4.
5.
...

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

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1.	Пределы последовательностей и функций. Отношения порядка и непрерывные функции.	Устный опрос, Домашние работы, Письменный тест	В домашние работы включаются задачи, нерешенные во время семинарских занятий. Тестирование (письменное или компьютерное): 1. Две задачи из разделов «Числовые ряды» которые могут быть исследованы с помощью признаков Даламбера и Коши. 2. Две задачи из раздела «знакопеременные ряды», для решения первой может быть использован признак Лейбница, для второй — теорема Римана о сумме условно сходящегося ряда.
2.	Функциональные ряды: степенные ряды и ряды Фурье.	Домашние работы. Письменный тест. Устный опрос по темам разделов Коллоквиум	В домашние работы включаются задачи, нерешенные во время семинарских занятий. Письменный тест содержит пять задач из соответствующих разделов: 1. Степенные ряды для исследования на сходимость рядов и почленно продифференцированных рядов. 2. Задачи разложении в ряд Тейлора элементарных функций и комбинаций элементарных функций. 3. Вычисление коэффициентов рядов Фурье для гладких периодических функций. 4. Ряды Фурье для четных и нечетных функций. 5. Вычисление коэффициентов рядов Фурье разрывных функций.
3.	Пределы функций многих переменных, частные производные, градиент. Дифференцируемые многообразия. Экстремумы функций нескольких переменных.	Домашние работы. Письменный тест. Устный опрос по темам разделов	В домашние работы включаются задачи, нерешенные во время семинарских занятий. Письменный тест содержит пять задач из соответствующих разделов: предел функции двух переменных; частные производные и производные по направлению; Геометрический смысл частных производных и дифференцируемые многообразия; экстремальные точки и условия максима или минимума; Задачи минимизации на многообразиях — функция Ланранжа.
4.	Кратные интегралы и Векторный анализ	Домашние работы. Письменный тест. Устный опрос по темам разделов	В домашние работы включаются задачи, нерешенные во время семинарских занятий. Письменный тест содержит четыре задачи из раздела: Криволинейные интегралы и двумерные интегралы и формула Грина; двумерные и трехмерные интегралы и формула Остроградского-Гаусса; вычисление дивергенции и вычисление ротора для заданных векторных полей.

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Числовые ряды, абсолютно сходящиеся ряды, условно сходящиеся ряды.	1. Определение сходящегося ряда. Определение ряда, сходящегося абсолютно. Определение ряда, сходящегося условно. 2. Признаки сходимости Даламбера, Коши, интегральный признак сходимости. Геометрический ряд и его использование как мажорирующего ряда. 3. Перестановка порядка суммирования в условно сходящемся ряду и приведение его суммы к заранее заданному числу.
2.	Функциональные ряды: степенные ряды и ряды Фурье.	1. Определение интервала сходимости степенного ряда. 2. Почленное интегрирование и дифференцирование степенных рядов. 3. Вычисление коэффициентов рядов Фурье. Ряды Фурье для четных и нечетных функций. 4. Гладкость функций и асимптотические свойства коэффициентов Фурье.
3.	Пределы функций многих переменных, частные производные, градиент. Дифференцируемые многообразия. Экстремумы функций нескольких переменных	1. Условие существования предела функции нескольких переменных. 2. Условие перестановки пределов функции нескольких переменных. 3. Производная по направлению. Градиент. Касательная плоскость. 4. Дифференцируемое многообразие, карта, атлас. 5. Необходимое условие экстремума функции нескольких переменных. 6. Алгоритм определения экстремума функции нескольких переменных на многообразии.
4.	Кратные интегралы и Векторный анализ.	1. Определение и примеры вычисления криволинейных интегралов первого и второго рода. 2. Вывод и примеры использования формулы Грина. 3. Вывод и примеры использования формулы Остроградского-Гаусса. 4. Определения ротора и дивергенции векторного поля.

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. Определения абсолютной и условной сходимости ряда и чем они отличаются? Можете ли вы привести пример ряда, который является условно сходящимся, но не абсолютно сходящимся?
2. Признаки сходимости Даламбера, Коши, интегральный признак сходимости.
3. Геометрический ряд и его использование как мажорирующего ряда.
4. Признаки сходимости Абеля и Дирихле.
5. Перестановка порядка суммирования в условно сходящемся ряду и приведение его суммы к заранее заданному числу.
6. Что такое степенной ряд и как определяется его радиус сходимости? Можете ли вы привести пример степенного ряда и его радиуса сходимости?
7. Что такое дифференциальное уравнение и как построить степенной ряд для заданного дифференциального уравнения.
8. Что такое ряд Фурье и как он используется для аппроксимации периодических функций? Можете ли вы привести пример периодической функции и ее ряда Фурье?
9. Привести и обосновать формулы для рядов Фурье четных и нечетных функций. Привести примеры.
10. Что такое дифференцируемое многообразие и каково его касательное пространство? Можете ли вы привести пример дифференцируемого многообразия и его касательного пространства?
11. Что такое градиент функции и как он используется для решения задач оптимизации? Можете ли вы привести пример того, как найти градиент функции и использовать его для решения задачи оптимизации?
12. Что такое метод множителя Лагранжа и как он используется для нахождения экстремумов функции на многообразиях? Можете ли вы привести пример того, как использовать этот метод для решения задачи оптимизации?
13. Определение двойного интеграла. Суммы Дарбу. Теорема о мере границы.
14. Свойства двойных интегралов. Теорема о среднем значении. Примеры.
15. Приложения двойного интеграла. Объем, фильтры, масса плоской фигуры, центр масс плоской фигуры. Примеры.
16. Теорема Фубини, доказательство. Примеры.
17. Геометрический смысл двойных интегралов. Вектор нормали для поверхности. Примеры.
18. Критерии Дарбу для существования меры для данного трехмерного тела. Примеры.
19. Изменение переменных в двойных интегралах. Якобиан. Полярные координаты в качестве примера.
20. Изменение переменных в тройных интегралах. Якобиан. Примеры.
21. Сферические координаты и использование сферических координат для вычисления тройных интегралов. Примеры.
22. Преобразование Фурье. Определение. Набросок доказательства. Примеры.
23. Свойства преобразования Фурье. Гладкие функции и асимптотическое поведение образа Фурье.
24. Вычисление двойных интегралов и оценка погрешности.
25. Плоская кривая. Касательный вектор, вектор нормали, кривизна, длина кривой. Примеры.
26. Кривая в трехмерном пространстве. Бинормаль, плоскость соприкосновения, кручение. Пример.
27. Криволинейный интеграл. Работа потенциальной силы вдоль заданной траектории. Центр масс заданной кривой.
28. Определение скалярного поля и векторного поля. Дивергенция и ротор векторного поля. Примеры.
29. Формы представления криволинейного интеграла. Примеры использования.
30. Теорема Гирина. Вывод формулы Грина. Следствие теоремы Грина для кругового интеграла градиента.
31. Двумерные многообразия. Ориентированные и неориентированные многообразия. Примеры. Локальные карты и атлас. Примеры
32. Интеграл по поверхности для векторного поля. Различные формы поверхностных интегралов, такие как интеграл по проекциям и интегралы по локальной системе координат. Примеры.
33. Формула Остроградского-Гаусса. Доказательство формулы. Физическая интерпретация формулы. Примеры.
34. Ротор и дивергенция как предел циркуляции потока и обтекания поверхности для данного объема. Теорема о расходимости ротора.

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

Список основной литературы:
1. Кудрявцев, Л. Д. Курс математического анализа в 3 т. Том 1 : учебник для бакалавров / Л. Д. Кудрявцев. — 6-е изд. — Москва : Издательство Юрайт, 2023. — 703 с. — ISBN 978-5-9916-1807-6.
2. Фихтенгольц Г. М. Основы математического анализа. Т1. Издательство Лань, 2023, --444 с. -- ISBN 978-5-8114-7583-4, 978-5-8114-5337-5
3. Зорич В.А. Математический анализ, Часть 1, Издательство МЦНМО, 2019, --564 с. --ISBN 978-5-4439-4029-8.
4. Демидович Б. П. . Сборник задач и упражнений по математическому анализу: Учебное пособие для вузов Издательство АСТ, 2005. 558 с.

Список дополнительной литературы:
1. Пискунов Н.С. Дифференциальное и интегральное исчисление. Т1. Издательство Интеграл-Пресс, 2002, --416 с. --ISBN 5-89602-012-0
2. Лутц М., Изучаем Python: Т. 1, Издательство Диалектика, 2023, --824 c. --ISBN 9785521805532
3. Beazley D., Jones B.K. Python Cookbook, 3rd Edition by 2013 Publisher(s): O'Reilly Media, Inc. ISBN: 9781449357351

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

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

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

Методы и технологии обучения, способствующие формированию компетенции
В курсе планируется использовать несколько технологий обучения. Таких как: интерактивные лекции , поощряющие участие студентов посредством сессий вопросов и ответов, живых демонстраций концепций квантовых вычислений или групповых дискуссий. Проблемно-ориентированное обучение – мероприятия по решению проблем, которые побуждают студентов применять концепции квантовых вычислений в практических ситуациях. Этот метод может улучшить навыки критического мышления и закрепления знаний. Будут применяться программные библиотеки для аналитических и численных методов: SymPy, NumPy, и SciPy , что позволит использовать компьютер как инструмент для изучения свойств аналитических функции, изучать теорию аппроксимаций и получить опыт использования компьютерных вычислений в задачах математического анализа. Планируется предложить совместные проекты , которые требуют применения концепций квантовых вычислений в реальных сценариях или создания новых квантовых алгоритмов. Такой подход может способствовать командной работе, навыкам общения и креативности, одновременно углубляя понимание студентами концепций квантовых вычислений. Важный элемент курса – смешанное обучение : сочетание традиционного очного обучения с онлайн-учебными ресурсами, такими как видео, симуляторы или интерактивные викторины. Такой подход может учитывать различные стили обучения и предпочтения, одновременно улучшая понимание учащимися концепций квантовых вычислений.

BSc: EfficientAlgorithms

Contents