Difference between revisions of "BSc: EfficientAlgorithms"
Jump to navigation
Jump to search
(Created page with "= <span style="color:red;">Название дисциплины</span> = : '''Квалификация выпускника''': <span style="color:red;">бакалавр/ма...") |
V.matiukhin (talk | contribs) |
||
| (8 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | = Эффективные алгоритмы для труднорешаемых задач = |
||
| − | = <span style="color:red;">Название дисциплины</span> = |
||
| − | : '''Квалификация выпускника''': |
+ | : '''Квалификация выпускника''': бакалавр |
| − | : '''Направление подготовки''': |
+ | : '''Направление подготовки''': 01.04.02 «Прикладная математика и информатика». |
| − | : '''Направленность (профиль) образовательной программы''': |
+ | : '''Направленность (профиль) образовательной программы''': «Системное программирование и компьютерные науки». Образовательная программа «Вычислительная математика» |
| − | : '''Программу разработал(а)''': |
+ | : '''Программу разработал(а)''': С.А. Фомин |
== 1. Краткая характеристика дисциплины == |
== 1. Краткая характеристика дисциплины == |
||
| − | Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области |
+ | Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области программного обеспечения и его разработки; искусственного интеллекта и его применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают:<br> |
| + | * Теорию сложности, для определения<br> |
||
| + | ** классов задач допускающих эффективное решение детерминированными и вероятностными алгоритмами — классы P, RP, ZPP, BPP и т.п. <br> |
||
| + | ** классов задач, для которых считается невозможным существование эффективных алгоритмов точного решения — NP-complete, PSPACE-complete. <br> |
||
| + | ** классов задач, для которых считается невозможным существование эффективных алгоритмов поиска приближенного решения — APX-complete. <br> |
||
| + | * Классические алгоритмы решения задач на графах и множествах (кратчайшие пути, покрытия, сортировки) <br> |
||
| + | * Алгоритмы, подходы и эвристики, для решения NP-полных задач: <br> |
||
| + | ** приближенные алгоритмы с гарантированной точностью, включая алгоритмы с любой, заранее выбранной точностью — PTAS, FPTAS. <br> |
||
| + | ** вероятностные алгоритмы, и эвристики их порождения — методы Монте-Карло, вероятностного округления и т.п. <br> |
||
| + | ** методы дерандомизации — получения детерминированных приближенных алгоритмов из вероятностных. <br> |
||
| + | * Практические методы программирования для реализации всего перечисленного. <br> |
||
== 2. Перечень планируемых результатов обучения == |
== 2. Перечень планируемых результатов обучения == |
||
| + | В ходе курса студенты научатся:<br> |
||
| − | : '''Целью освоения дисциплины''' ... |
||
| + | * Оценивать вычислительную сложность алгоритмических задач (в терминах вычислительных ресурсов).<br> |
||
| − | |||
| + | * Классифицировать алгоритмические задачи их в основных сложностных классах — базовое ориентирование в огромном «зоопарке» классов сложности — студенты познакомятся с известными теоремами и открытыми гипотезами о соотношении сложностей задач.<br> |
||
| − | : '''Задачами дисциплины''' вляются ... <span style="color:red;">(перечислить задачи дисциплины, например: изучение принципов организации подсистем обработки естественного языка для различных прикладных задач и тенденций развития лингвистических ресурсов в сфере интеллектуальных информационных технологий и т.д.).</span> |
||
| + | * Устанавливать связи между сложностными классами.<br> |
||
| + | * Выделять сложнорешаемые и практически решаемые алгоритмические задачи.<br> |
||
| + | * Для трудноразрешимых задач, строить приближенные и вероятностные алгоритмы и дерандомизировать некоторые из них — познакомиться с несколькими красивыми и широко используемыми в узких кругах полиномиальными алгоритмами.<br> |
||
| + | * Практически решать на Python классические задачи (возможность в дальнейшем использовать полученные навыки в дальнейшей работе по окончании ВУЗа), применение классических эвристик — «жадность», «динамическое программирование», известных алгоритмов на сортировки и графы и т.п.<br> |
||
| + | * Использовать достижения программной индустрии — ЦЛП-солверы, SAT-солверы, Pyomo-формулировки для постановки и решения задач оптимизации. |
||
| + | Дисциплина участвует в формировании следующих компетенций образовательной программы:<br> |
||
| + | * «СПК-9» — способность осуществлять математическую постановку задачи и решать ее современными оптимизационными методами для оптимального выбора средств защиты информации при ограничениях на их стоимость, габариты, энергопотребление и др.<br> |
||
| + | * «СПК-1» — способность осуществлять поиск, изучение, обобщение и систематизацию научно-технической информации, нормативных и методических материалов в сфере профессиональной деятельности, в том числе на иностранном языке.<br> |
||
| + | * «СПК-7»— способность разрабатывать научно-техническую документацию, готовить научно-технические отчеты, обзоры, публикации по результатам выполненных работ.<br> |
||
=== Общая характеристика результата обучения по дисциплине === |
=== Общая характеристика результата обучения по дисциплине === |
||
| − | : '''Знания:''' |
+ | : '''Знания: '''<br> |
| + | *теоретических моделей вычисления.<br> |
||
| − | <span style="color:red;">(информация, которой обладает обучающийся в определенных областях, полученная в процессе обучения, то есть это информация для осуществления какой-либо деятельности (действия))</span> |
||
| + | *классов сложности оптимизационных задач.<br> |
||
| + | *методов полиномиальной сводимости классических NP-полных задач.<br> |
||
| + | *методов анализа сложности детерминированных и вероятностных алгоритмов, анализа точности в среднем и «для почти всех исходных данных».<br> |
||
| + | : '''Умения: '''<br> |
||
| + | *постановки оптимизационной формулировки для оптимизационной задачи<br> |
||
| + | *использование ЦЛП и SAT-солверов<br> |
||
| + | *доказательство труднорешаемости оптимизационной задачи<br> |
||
| + | *оценка сложности алгоритма, «в худшем» и «в среднем»<br> |
||
| + | *оценка качества приближения алгоритма, «в худшем» и «в среднем»<br> |
||
| + | : '''Навыки (владения): '''<br> |
||
| + | *программирование на Python<br> |
||
| + | *работа с Jupyter-ноутбуками<br> |
||
| + | *работа с IDE VSCode/code-server<br> |
||
| + | *использование фреймворка Pyomo, для постановки оптимизационных задач и решения их ЦЛП-солверами<br> |
||
| + | *использование фреймворка pySAT для решения SAT-задач<br> |
||
| + | == 3. Структура и содержание дисциплины == |
||
| − | : '''Умения:''' сформированы умения ... |
||
| + | Полугодовой курс состоит из двух основных частей:<br> |
||
| − | <span style="color:red;">(предполагает целенаправленное выполнение действий, по изученной информации)</span> |
||
| + | *Закладываются основы теории сложности вычислений, которые далее при желании можно развивать в различных направлениях.<br> |
||
| − | : '''Навыки (владения):''' сформировано владение навыками ... |
||
| + | *Рассказывается о нескольких эффективных алгоритмах и подходах для решения труднорешаемых задач.<br> |
||
| − | <span style="color:red;">(автоматизированные устойчивые умения выполнять определенную работу, то есть действие выполняется без контроля сознания, автоматически)</span> |
||
| + | Основные вопросы курса: какие бывают вычислительные ресурсы, как подсчитывать их необходимое количество для решения данной алгоритмической задачи, как отличить решаемые на практике задачи от нерешаемых и как наиболее эффективно работать с решаемыми. Много внимания уделяется изучению различных сложностных классов, связей между ними и классификации конкретных задач.<br> |
||
| + | Как правило, в семестре разбираются следующие темы.<br> |
||
| − | == 3. Структура и содержание дисциплины == |
||
| − | <span style="color:red;">(Указываются: 1) порядковый номер раздела (количество разделов зависит от содержания Вашей дисциплины); 2) наименования разделов дисциплины; 3) темы указанных разделов (количество тем в каждом разделе зависит от содержания Вашей дисциплины)</span> |
||
{| class="wikitable" style="width:70%;" |
{| class="wikitable" style="width:70%;" |
||
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;" |
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;" |
||
| Line 31: | Line 65: | ||
| style="width:60%" | Содержание дисциплины по темам |
| style="width:60%" | Содержание дисциплины по темам |
||
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 1. || Формально об алгоритмах. Вычислительные модели. || Примеры простых алгоритмов.Random Access Machines.Одно и много-ленточные Машины Тьюринга. Универсальная машина Тьюринга. Вычислимость и разрешимость. <br> |
||
| − | | style="text-align:center;" | 1. || || -<br> -<br> -<br> -<br> |
||
|- style="background-color:#F8F9FA; color:#202122;" |
|- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 2. || Временная и пространственная сложность алгоритмов. || Классы DTIME, P, EXPTIME. Классы DSPACE, PSPACE. <br> |
||
| − | | style="text-align:center;" | 2. || || -<br> -<br> -<br> -<br> |
||
|- style="background-color:#F8F9FA; color:#202122;" |
|- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 3. || Полиномиальные сводимости и NP-полные задачи. || Полиномиальные сводимости по Куку и Карпу. Классы NP, coNP, NPC. <br> |
||
| − | | style="text-align:center;" | 3. || || -<br> -<br> -<br> -<br> |
||
|- style="background-color:#F8F9FA; color:#202122;" |
|- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 4. || Вероятностные вычисления и их сложность. || Классы «эффективно решаемых задач» RP, coRP, BPP.Класс «Безошибочно решаемых задач» ZPP. Неамплифицируемый класс PP. <br> |
||
| − | | style="text-align:center;" | 4. || || -<br> -<br> -<br> -<br> |
||
|- style="background-color:#F8F9FA; color:#202122;" |
|- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 5. || Жадные алгоритмы и анализ их качества. || Жадные алгоритмы в задачах о покрытии о покрытии множеств и вершин. Жадный алгоритм в задаче о рюкзаке. <br> |
||
| − | | style="text-align:center;" | 5. || || -<br> -<br> -<br> -<br> |
||
|- style="background-color:#F8F9FA; color:#202122;" |
|- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 6. || Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке. || Динамическое программирование для задачи о рюкзаке. Использование жадных алгоритмов и эвристик округления для получения FPTAS-алгоритма. <br> |
||
| − | | style="text-align:center;" | ... || || -<br> -<br> -<br> -<br> |
||
| + | |- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 7. || Алгоритмы полиномиальные в среднем. || Полиномиальный в среднем алгоритм для задачи о рюкзаке.Полиномиальный в среднем алгоритм для SAT.Полиномиальный в среднем алгоритм для задачи упаковки. <br> |
||
| + | |- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 8. || Приближенный алгоритм для метрической задачи коммивояжера.Вероятностные алгоритмы. || Вероятностная проверка тождеств.Вероятностный подсчет числа выполняемых наборов для ДНФ.Вероятностное округление для задач MAX-SAT и MAX-CUT. <br> |
||
| + | |- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 9. || Дерандомизация. || Детерминированный приближенный алгоритм для MAX-SAT, полученный из вероятностного алгоритма.. <br> |
||
| + | |- style="background-color:#F8F9FA; color:#202122;" |
||
| + | | style="text-align:center;" | 10. || Неаппроксиминуемость. || ВВероятностно проверяемые доказательства. PCP-системы. PCP-теорема. PCP и аппроксимируемость. <br> |
||
| + | |- style="background-color:#F8F9FA; color:#202122;" |
||
| + | |||
|} |
|} |
||
== 4. Методические и оценочные материалы == |
== 4. Методические и оценочные материалы == |
||
'''Задания для практических занятий:</b>''' |
'''Задания для практических занятий:</b>''' |
||
| + | |||
| − | {| class="wikitable" style="width:70%;" |
||
| + | См. примеры: |
||
| − | |- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;" |
||
| + | |||
| − | | style="width:10%" | №<br>п/п |
||
| + | *[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 "Практикуемся в алгоритмах"]<br> |
||
| − | | style="width:30%" | Наименование раздела<br>дисциплины (модуля) |
||
| + | *[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"Моделирование труднорешаемых задач"]<br> |
||
| − | | style="width:60%" | Перечень рассматриваемых тем (вопросов)<br><span style="color:red;">(Указываются ВСЕ задания для практических занятий по разделам дисциплины подробно в соответствии с темами)</span> |
||
| + | *[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"Моделирование бизнес-задач"]<br> |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| + | *[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"Решаем теоретические упражнения"]<br> |
||
| − | | style="text-align:center;" | 1. || || |
||
| + | |||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 2. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 3. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 4. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 5. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | ... || || |
||
| − | |} |
||
'''Текущий контроль успеваемости обучающихся по дисциплине:''' |
'''Текущий контроль успеваемости обучающихся по дисциплине:''' |
||
| + | См. примеры тестов: |
||
| − | <span style="color:red;">(К формам текущего контроля можно отнести собеседование, коллоквиум, тест, контрольную работу, лабораторную работу, эссе, реферат и иные творческие работы.)</span> |
||
| − | {| class="wikitable" style="width:70%;" |
||
| − | |- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;" |
||
| − | | style="width:5%" | №<br>п/п |
||
| − | | style="width:20%" | Наименование раздела<br>дисциплины |
||
| − | | style="width:25%" | Форма текущего контроля<br><br><span style="color:red;">(выберите соответствующие формы контроля)</span> |
||
| − | | style="width:50%" | Материалы текущего контроля<br><br><span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ текущего контроля успеваемости обучающихся по разделам дисциплины подробно в соответствии с требованиями)</span> |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 1. |
||
| − | | |
||
| − | | style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span> |
||
| − | | Например: |
||
| − | Устный / письменный опрос:<br>-<br>-<br>-<br>...<br> |
||
| − | Тематика групповых проектов:<br>-<br>-<br>-<br>...<br> |
||
| − | Темы докладов:<br>-<br>-<br>-<br>...<br> |
||
| − | Тематика эссе:<br>-<br>-<br>-<br>...<br> |
||
| − | Задания, в том числе, для групповых проектов:<br>-<br>-<br>-<br>...<br> |
||
| − | Тестирование (письменное или компьютерное):<br>-<br>-<br>-<br>...<br><br> |
||
| − | Проверка разработки отдельных частей кода программного продукта. |
||
| + | https://discopal.ispras.ru/Special:MediawikiQuizzer/Algs-innopolis-exam <br> |
||
| − | Другие формы текущего контроля, используемые Вами на занятиях<br>-<br>-<br>-<br>...<br> |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 2. |
||
| − | | |
||
| − | | style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span> |
||
| − | | |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 3. |
||
| − | | |
||
| − | | style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span> |
||
| − | | |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 4. |
||
| − | | |
||
| − | | style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span> |
||
| − | | |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 5. |
||
| − | | |
||
| − | | style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span> |
||
| − | | |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | ... || || || |
||
| − | |} |
||
| − | '''Контрольные вопросы для подготовки к промежуточной аттестации:''' |
||
| − | {| class="wikitable" style="width:70%;" |
||
| − | |- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;" |
||
| − | | style="width:10%" | №<br>п/п |
||
| − | | style="width:25%" | Наименование <br> раздела дисциплины |
||
| − | | style="width:65%" | Вопросы |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 1. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 2. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 3. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 4. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 5. || || |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | ... || || |
||
| − | |} |
||
| − | '''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:''' |
||
| + | === Перечень учебно-методического обеспечения дисциплины === |
||
| − | <span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ для промежуточной аттестации.)</span> |
||
| + | Курс соединяет различные разделы теории сложности вычислений и изучение конкретных алгоритмов. Такой набор редко встречается в литературе, а по сложности вычислений на русском языке имеется совсем немного книг. Студентам предлагается использовать книгу лектора, а также книги на английском языке или книги по отдельным частям на русском.<br> |
||
| − | 1.<br>2.<br>3.<br>...<br>48.<br>49.<br>50.<br>... |
||
| + | |||
| − | === Перечень учебно-методического обеспечения дисциплины === |
||
| + | '''Основная книга'''<br> |
||
| − | Список основной литературы: |
||
| + | [https://discopal.ispras.ru/%D0%A4%D0%B0%D0%B9%D0%BB:Book-advanced-algorithms.pdf "Эффективные алгоритмы и сложность вычислений"]<br> |
||
| + | |||
| + | Список дополнительной литературы:<br> |
||
| + | *https://discopal.ispras.ru/Дополнительные_материалы_по_сложности_вычислений <br> |
||
| + | *https://discopal.ispras.ru/Дополнительные_материалы_по_приближенным_алгоритмам <br> |
||
| + | *Н.Н. Кузюрин, С.А. Фомин, Эффективные алгоритмы и сложность вычислений», 2007 издательство МФТИ. ISBN 5-7417-0198-1.<br> |
||
| + | *S.Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.<br> |
||
| + | *M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.<br> |
||
| + | *C.Moore, S. Mertens, The Nature of Computation, Oxford University Press, 2011<br> |
||
| + | *Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание, Вильямс, 2019.<br> |
||
| + | *O. Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.<br> |
||
| + | *A. Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019.<br> |
||
| + | *C.Papadimitriou, Computational Complexity, Addison Wesley, 1994<br> |
||
| + | *В.Н.Крупский. Введение в сложность вычислений, Москва, Факториал Пресс, 2006<br> |
||
| + | *С.А. Абрамов, Лекции о сложности алгоритмов, Москва, МЦНМО, 2009<br> |
||
| + | *Д.В.Мусатов. Курс лекций по сложности вычислений (видеолекций, конспекты).<br> |
||
| + | *М.Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Москва, Мир, 1982<br> |
||
| + | *М. Вялый, А. Китаев, А. Шень, Классические и квантовые вычисления, Москва, МЦНМО, 1999.<br> |
||
| + | '''Необходимое программное обеспечение для студентов'''<br> |
||
| − | Список дополнительной литературы: |
||
| + | Браузер. |
||
=== Методические указания для обучающихся по освоению дисциплины === |
=== Методические указания для обучающихся по освоению дисциплины === |
||
| + | Самостоятельная работа учащихся состоит:<br> |
||
| − | <span style="color:red;">(Указываются рекомендации для обучающихся, которые раскрывают суть их работы при различных видах деятельности в рамках освоения дисциплины. Данные рекомендации должны охватывать работу с лекционным материалом, подготовку и работу во время проведения семинарских занятий, самостоятельную работу, подготовку к текущему контролю и промежуточной аттестации)</span> |
||
| + | *в изучении лекционного материала, доступных видео и конспектов лекций учебно-методической литературы, включая базовую книгу авторов курса<br> |
||
| − | |||
| + | *подготовки к практическим заданиям текущего контроля и промежуточной аттестации<br> |
||
| − | <span style="color:red;">(Выберите соответствующие виды учебных занятий, которые используются при изучении Вашей дисциплины)</span> |
||
| + | *тесты по всем материалам курса<br> |
||
| + | *решение теоретических задач по теории сложности<br> |
||
| + | *решение алгоритмических задач на языке Python<br> |
||
| + | *конструктивная постановка и исследование труднорешаемых задач с помощью ЦЛП и SAT-формулировок, с помощью технологий Jupyter Notebook, Pyomo и др.<br> |
||
{| class="wikitable" style="width:80%;" |
{| class="wikitable" style="width:80%;" |
||
| − | |- style="vertical-align:middle; text-align:center; background-color:#EAECF0 |
+ | |- style="vertical-align:middle; text-align:center; background-color:#EAECF0; font-weight:bold;" |
| style="width:20%" | Вид учебных<br>занятий/деятельности |
| style="width:20%" | Вид учебных<br>занятий/деятельности |
||
| style="width:80%" | Деятельность обучающегося |
| style="width:80%" | Деятельность обучающегося |
||
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Лекция |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Практическое (семинарское) занятие |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.<br>Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Устный/письменный опрос |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Реферат |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты.<br>Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Эссе |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Подготовка к промежуточной аттестации |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.<br>Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Практические (лабораторные) занятия |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Самостоятельная работа |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Видеопрезентация |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Доклад |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Дискуссия |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Контрольная работа |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Тестирование (устное/письменное) |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Индивидуальная работа |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Разработка отдельных частей кода |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем. |
|- |
|- |
||
| − | | style="vertical-align:middle; text-align:center |
+ | | style="vertical-align:middle; text-align:center;" | Выполнение домашних заданий и групповых проектов |
| − | | style="vertical-align:middle; text-align:left |
+ | | style="vertical-align:middle; text-align:left;" | Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. |
|} |
|} |
||
=== Методы и технологии обучения, способствующие формированию компетенции === |
=== Методы и технологии обучения, способствующие формированию компетенции === |
||
| + | |||
| − | <span style="color:red;">(Указываются все используемые преподавателем методы и технологии обучения)</span> |
||
| + | *Коллаборативное программирование и другая работа в реальном времени, см. доклад [https://0x1.tv/%D0%A1%D0%BE%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%C2%AB%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%81%D1%80%D0%B5%D0%B4%D1%8B%C2%BB_%D0%B8_%C2%AB%D0%B6%D0%B8%D0%B2%D1%8B%D0%B5_%D0%BB%D0%B0%D0%B1%D0%BE%D1%80%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%B8%C2%BB_%E2%80%94_%D1%8D%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B8%D1%81%D1%82%D0%B0%D0%BD%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0%D0%BC_%D0%B8_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%BC_%D0%B4%D0%B8%D1%81%D1%86%D0%B8%D0%BF%D0%BB%D0%B8%D0%BD%D0%B0%D0%BC_(%D0%A1%D1%82%D0%B0%D1%81_%D0%A4%D0%BE%D0%BC%D0%B8%D0%BD,_OSEDUCONF-2023) «Современные «интерактивные среды» и «живые лаборатории» — эффективное дистанционное образование по алгоритмам и математическим дисциплинам»]<br> |
||
| − | {| class="wikitable" |
||
| + | *Обучающие вики-тесты, см. доклад [https://0x1.tv/MediaWikiQuizzer_%D0%B8%D0%BB%D0%B8_%D0%92%D0%B8%D0%BA%D0%B8%D0%AD%D0%BA%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD%D1%8B_%E2%80%94_%D1%82%D0%B5%D1%81%D1%82%D1%8B,_%D1%83%D0%B4%D0%BE%D0%B1%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BF%D1%80%D0%B5%D0%BF%D0%BE%D0%B4%D0%B0%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8F_%D0%B8_%D0%B4%D0%BB%D1%8F_%D1%81%D1%82%D1%83%D0%B4%D0%B5%D0%BD%D1%82%D0%B0_(%D0%A1%D1%82%D0%B0%D1%81_%D0%A4%D0%BE%D0%BC%D0%B8%D0%BD,_OSEDUCONF-2015) «MediaWikiQuizzer или ВикиЭкзамены — тесты, удобные и для преподавателя и для студента»]<br> |
||
| − | |- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;" |
||
| + | *Коллаборативная среда на wiki-платформе, см. доклад [https://0x1.tv/%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%C2%AB%D0%B4%D0%BE%D0%BC%D0%B0%D1%88%D0%BA%D0%B0%C2%BB_%E2%80%94_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D1%81%D1%82%D1%83%D0%B4%D0%B5%D0%BD%D1%82%D0%B0%D0%BC_%D0%BD%D0%B0_MediaWiki_(%D0%A1%D1%82%D0%B0%D1%81_%D0%A4%D0%BE%D0%BC%D0%B8%D0%BD,_OSEDUCONF-2017) «Эффективная «домашка» — задачи студентам на MediaWiki»]<br> |
||
| − | | Методы и технологии обучения, способствующие формированию компетенции |
||
| + | *Видеозаписи миникурсов, см. доклад [https://0x1.tv/OBS_%E2%80%94_%D1%88%D0%B2%D0%B5%D0%B9%D1%86%D0%B0%D1%80%D1%81%D0%BA%D0%B8%D0%B9_%D0%BD%D0%BE%D0%B6_%D0%BF%D0%B5%D1%80%D0%B5%D0%B4%D0%B0%D1%87%D0%B8_%D0%B7%D0%BD%D0%B0%D0%BD%D0%B8%D0%B9._%D0%91%D0%BE%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BF%D1%80%D0%B8%D0%B5%D0%BC%D1%8B_Open_Broadcaster_Software_(%D0%A1%D1%82%D0%B0%D1%81_%D0%A4%D0%BE%D0%BC%D0%B8%D0%BD,_OSEDUCONF-2019) «OBS — швейцарский нож передачи знаний»]<br> |
||
| − | |- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;" |
||
| − | | |
||
| − | |} |
||
| − | <span style="color:red;">Например:</span> |
||
| − | {| class="wikitable" style="width:80%;" |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center; width:5%;" | 1. |
||
| − | | style="width:20%;" | Информационно – коммуникационная технология |
||
| − | | style="width:75%;" | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 2. |
||
| − | | Технология развития критического мышления |
||
| − | | Основные методические приемы развития критического мышления |
||
| − | # Прием «Кластер» |
||
| − | # Таблица |
||
| − | #Учебно-мозговой штурм |
||
| − | #Интеллектуальная разминка |
||
| − | #Зигзаг, зигзаг -2 |
||
| − | #Прием «Инсерт» |
||
| − | #Эссе |
||
| − | #Приём «Корзина идей» |
||
| − | #Приём «Составление синквейнов» |
||
| − | #Метод контрольных вопросов |
||
| − | #Приём «Знаю../Хочу узнать…/Узнал…» |
||
| − | #Круги по воде |
||
| − | #Ролевой проект |
||
| − | #Да – нет |
||
| − | #Приём «Чтение с остановками» |
||
| − | #Приём «Взаимоопрос» |
||
| − | #Приём «Перепутанные логические цепочки» |
||
| − | #Приём «Перекрёстная дискуссия» |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 3. |
||
| − | | Проектная технология |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 4. |
||
| − | | Технология проблемного обучения |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 5. |
||
| − | | Кейс – технология |
||
| − | | К методам кейс-технологий, активизирующим учебный процесс, относятся: |
||
| − | *метод ситуационного анализа (Метод анализа конкретных ситуаций, ситуационные задачи и упражнения; кейс-стадии) |
||
| − | *метод инцидента; |
||
| − | *метод ситуационно-ролевых игр; |
||
| − | *метод разбора деловой корреспонденции; |
||
| − | *игровое проектирование; |
||
| − | *метод дискуссии. |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 6. |
||
| − | | Технология интегрированного обучения |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 7. |
||
| − | | Педагогика сотрудничества |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 8. |
||
| − | | Технологии уровневой дифференциации |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 9. |
||
| − | | Групповая технология |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 10. |
||
| − | | Традиционные технологии (классно-урочная система) |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 11. |
||
| − | | Здоровьесберегающие технологии |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 12. |
||
| − | | Игровая технология |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 13. |
||
| − | | Модульная технология |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | style="text-align:center;" | 14. |
||
| − | | Технология мастерских |
||
| − | | |
||
| − | |- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;" |
||
| − | | |
||
| − | | и др. |
||
| − | | |
||
| − | |} |
||
Latest revision as of 19:16, 1 April 2024
Эффективные алгоритмы для труднорешаемых задач
- Квалификация выпускника: бакалавр
- Направление подготовки: 01.04.02 «Прикладная математика и информатика».
- Направленность (профиль) образовательной программы: «Системное программирование и компьютерные науки». Образовательная программа «Вычислительная математика»
- Программу разработал(а): С.А. Фомин
1. Краткая характеристика дисциплины
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области программного обеспечения и его разработки; искусственного интеллекта и его применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают:
- Теорию сложности, для определения
- классов задач допускающих эффективное решение детерминированными и вероятностными алгоритмами — классы P, RP, ZPP, BPP и т.п.
- классов задач, для которых считается невозможным существование эффективных алгоритмов точного решения — NP-complete, PSPACE-complete.
- классов задач, для которых считается невозможным существование эффективных алгоритмов поиска приближенного решения — APX-complete.
- классов задач допускающих эффективное решение детерминированными и вероятностными алгоритмами — классы P, RP, ZPP, BPP и т.п.
- Классические алгоритмы решения задач на графах и множествах (кратчайшие пути, покрытия, сортировки)
- Алгоритмы, подходы и эвристики, для решения NP-полных задач:
- приближенные алгоритмы с гарантированной точностью, включая алгоритмы с любой, заранее выбранной точностью — PTAS, FPTAS.
- вероятностные алгоритмы, и эвристики их порождения — методы Монте-Карло, вероятностного округления и т.п.
- методы дерандомизации — получения детерминированных приближенных алгоритмов из вероятностных.
- приближенные алгоритмы с гарантированной точностью, включая алгоритмы с любой, заранее выбранной точностью — 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. Методические и оценочные материалы
Задания для практических занятий:
См. примеры:
- "Практикуемся в алгоритмах"
- "Моделирование труднорешаемых задач"
- "Моделирование бизнес-задач"
- "Решаем теоретические упражнения"
Текущий контроль успеваемости обучающихся по дисциплине:
См. примеры тестов:
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 и др.
| Вид учебных занятий/деятельности |
Деятельность обучающегося |
| Лекция | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. |
| Практическое (семинарское) занятие | При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы. |
| Устный/письменный опрос | Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части. |
| Реферат | Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты. Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата. |
| Эссе | Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др. |
| Подготовка к промежуточной аттестации | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей. Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю. |
| Практические (лабораторные) занятия | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов. |
| Самостоятельная работа | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис. |
| Видеопрезентация | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы. |
| Доклад | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис. |
| Дискуссия | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию. |
| Контрольная работа | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. |
| Тестирование (устное/письменное) | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части. |
| Индивидуальная работа | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы. |
| Разработка отдельных частей кода | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем. |
| Выполнение домашних заданий и групповых проектов | Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. |
Методы и технологии обучения, способствующие формированию компетенции
- Коллаборативное программирование и другая работа в реальном времени, см. доклад «Современные «интерактивные среды» и «живые лаборатории» — эффективное дистанционное образование по алгоритмам и математическим дисциплинам»
- Обучающие вики-тесты, см. доклад «MediaWikiQuizzer или ВикиЭкзамены — тесты, удобные и для преподавателя и для студента»
- Коллаборативная среда на wiki-платформе, см. доклад «Эффективная «домашка» — задачи студентам на MediaWiki»
- Видеозаписи миникурсов, см. доклад «OBS — швейцарский нож передачи знаний»