Просмотр исходного текста страницы Участник:StasFomin/Innopolis/Wtf

Требуемая страница
* https://eduwiki.innopolis.university/index.php/BSc:_EfficientAlgorithms

Зарегистрироваться-залогинится не дает:
[[File:Wtf_2024-03-30_21-18-38_image0.png|360px|right]]
[[File:Wtf_2024-03-30_21-16-36_image0.png|360px|center]]

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

= Эффективные алгоритмы для труднорешаемых задач =
: '''Квалификация выпускника''': бакалавр
: '''Направление подготовки''':  Направление 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/%D0%9F%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%BA%D1%83%D0%B5%D0%BC%D1%81%D1%8F_%D0%92_%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0%D1%85 Практикуемся в алгоритмах]»
* «[https://discopal.ispras.ru/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D1%82%D1%80%D1%83%D0%B4%D0%BD%D0%BE%D1%80%D0%B5%D1%88%D0%B0%D0%B5%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87 Моделирование труднорешаемых задач]»
* «[https://discopal.ispras.ru/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B8%D0%B7%D0%BD%D0%B5%D1%81-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87 Моделирование бизнес-задач]»
* «[https://discopal.ispras.ru/%D0%A0%D0%B5%D1%88%D0%B0%D0%B5%D0%BC_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D1%83%D0%BF%D1%80%D0%B0%D0%B6%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F Решаем теоретические упражнения]»

=== Контроль успеваемости обучающихся по дисциплине: ===
См. примеры тестов:
* https://discopal.ispras.ru/Special:MediawikiQuizzer/Algs-innopolis-exam

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

;Основная книга: «[https://discopal.ispras.ru/%D0%A4%D0%B0%D0%B9%D0%BB:Book-advanced-algorithms.pdf Эффективные алгоритмы и сложность вычислений]»
;Дополнительные материалы: 
* 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 и др. 


<!-- бессмысленный булшит, копирую, как есть -->

{| class="wikitable" style="width:80%;"
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; font-weight:bold;"
| style="width:20%" | Вид учебных<br>занятий/деятельности
| style="width:80%" | Деятельность обучающегося
|- 
| style="vertical-align:middle; text-align:center;" | Лекция
| style="vertical-align:middle; text-align:left;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
|-
| style="vertical-align:middle; text-align:center;" | Практические (лабораторные) занятия
| style="vertical-align:middle; text-align:left;" | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов. 
|-
| style="vertical-align:middle; text-align:center;" | Самостоятельная работа
| style="vertical-align:middle; text-align:left;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка презентаций. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис. 
|-
| style="vertical-align:middle; text-align:center;" | Доклад
| style="vertical-align:middle; text-align:left;" | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
|-
| style="vertical-align:middle; text-align:center;" | Дискуссия
| style="vertical-align:middle; text-align:left;" | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
|-
| style="vertical-align:middle; text-align:center;" | Разработка отдельных частей кода
| style="vertical-align:middle; text-align:left;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
|-
| style="vertical-align:middle; text-align:center;" | Выполнение домашних заданий и групповых проектов
| style="vertical-align:middle; text-align:left;" | Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
|-
| style="vertical-align:middle; text-align:center;" | Индивидуальная работа
| style="vertical-align:middle; text-align:left;" | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
|-
| style="vertical-align:middle; text-align:center;" | Тестирование (устное/письменное)
| style="vertical-align:middle; text-align:left;" | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
|}

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

* Коллаборативное программирование и другая работа в реальном времени, см. доклад «[https://0x1.tv/20230128F Современные «интерактивные среды» и «живые лаборатории» — эффективное дистанционное образование по алгоритмам и математическим дисциплинам]»
* Обучающие вики-тесты, см. доклад «[https://0x1.tv/20150125K MediaWikiQuizzer или ВикиЭкзамены — тесты, удобные и для преподавателя и для студента]»
* Коллаборативная среда на wiki-платформе, см. доклад «[https://0x1.tv/20170129D Эффективная «домашка» — задачи студентам на MediaWiki]»
* Видеозаписи миникурсов, см. доклад «[https://0x1.tv/20190126Q OBS — швейцарский нож передачи знаний]»