Курс «Эффективные алгоритмы» для МФТИ — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 179 промежуточных версий 10 участников)
Строка 1: Строка 1:
<!-- * [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]] -->
+
__FORCETOC__
* [[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Еженедельная тренировка]]
+
* [[Special:MediawikiQuizzer/Python|Созвонный тест]]
 +
<!--
 +
* [[Special:MediawikiQuizzer/GRE-CS-v01|Созвонный тест]]
 +
-->
 +
{{SideBar|
 +
{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/12/sort=wlp_talk_updated}}
 +
|style=max-width:35%
 +
}}
 +
<!--
 +
* [https://логос.испран.рф/mipt-course-03/hard-problems.svg Частичный обзор курса]
 +
* [https://логос.испран.рф/mipt-course-06/course-algorigthms-balls.drawio.svg  Баллы и путь прохождения]
 +
-->
 +
----
 +
* [[Blog:Advanced_Algorithms/2024-09-08_Презентация_курса_«на_осень_2024»]]
 +
----
 +
 
 +
<!--
 +
* [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]]
 +
* [[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Созвонный тест по теортемам]]
 +
-->
  
 
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
 
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
 +
 +
----
 +
<!-- {{:Blog:Advanced Algorithms/2021-09-03 Анонс «Эффективных алгоритмов-2021»}} -->
 +
----
 +
 +
<!--
 +
В целом голосование за время созвона прошло, результаты на странице [[Голосование за выбор времени созвона]],
 +
но если сильно изменится ситуация — заходите и переголосуйте там.
 +
-->
  
 
<!--
 
<!--
Строка 9: Строка 37:
 
-->
 
-->
  
;Лекторы: д.ф.-м.н. [mailto:nnkuz@ispras.ru Н.Н. Кузюрин], [mailto:stas-fomin@yandex.ru С.А. Фомин]
+
;Преподаватель: [mailto:stas-fomin@yandex.ru С.А. Фомин]
 +
 
 +
<!-- Запись на курс 2021 года завершена, всем спасибо, исключений нет. -->
  
 
Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:
 
Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:
 
{{:Как зарегистрироваться на курс}}
 
{{:Как зарегистрироваться на курс}}
 +
 +
<!--
 +
+
 +
Зарегистрируйтесь на «лабе»
 +
* [[Lab17]]
 +
-->
 +
  
 
<poll>
 
<poll>
UNSAFE_ID=aa-20171022
+
UNSAFE_ID=aa-20240901
 
ALTERNATIVE
 
ALTERNATIVE
 
OPEN_RESULTS
 
OPEN_RESULTS
Строка 21: Строка 58:
 
AUTHORIZED
 
AUTHORIZED
 
ALLOW_REVOTE
 
ALLOW_REVOTE
END_POLL 2017-10-01
+
END_POLL 2024-10-30
Записываемся на курс «Advanced Algorithms-2017»?
+
Записываемся на курс «Advanced Algorithms-2024»?
 
Да
 
Да
 
Нет
 
Нет
 
</poll>
 
</poll>
 +
* Первое установочное занятие будет 6 сентября, в 18-30 в 907 КПМ
 +
<!--  Установочный созвон будет наверно 9 сентября, раньше обычно бессмысленно. -->
  
 
<!--
 
<!--
Строка 50: Строка 89:
 
-->
 
-->
  
 +
<!--
 
Вводное занятие проведено — всем изучать материалы на
 
Вводное занятие проведено — всем изучать материалы на
 
[[Курс лекций «Эффективные алгоритмы»]] — книгу, видео и все-такое.  
 
[[Курс лекций «Эффективные алгоритмы»]] — книгу, видео и все-такое.  
Ближайшая встреча — 29 октября, готовим темы из раздела [[#Фокус]]
+
Готовим темы из раздела [[#Фокус]]
  
 +
{{!|Встречаемся в 903 КПМ, 4 октября, 18:30}}
 +
-->
  
 
Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам.  
 
Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам.  
 +
 
<!-- Возможно, если будут новые темы, будут удаленные лекции (которых попробуем и также записать и зафиксировать). -->
 
<!-- Возможно, если будут новые темы, будут удаленные лекции (которых попробуем и также записать и зафиксировать). -->
  
  
 
+
Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [{{active-telegram-group-link}} группе].
 
+
Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [https://vk.com/discopal группе].
+
  
 
<!--
 
<!--
Строка 67: Строка 108:
 
-->
 
-->
  
 +
----
  
 +
* Проблемы → [mailto:stas-fomin@yandex.ru Стасу Фомину]
  
----
+
<html><center>
<!--
+
</p><div class="sites-embed-align-left-wrapping-off"><div class="sites-embed-border-on sites-embed sites-embed-full-width" style="width: 100%;"><h4 class="sites-embed-title">Успеваемость зарегистрированных студентов</h4><div class="sites-embed-object-title" style="display: none;">Эффективные алгоритмы(студенты).2007</div><div class="sites-embed-content sites-embed-type-spreadsheet"><iframe src="https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZElcGVLNjEtY3lfOHhkdkRQWTI1aUktUUE&single=true&gid=9&output=html" id="1695919049" frameborder="0" height="500" width="100%"></iframe></div></div>
Зафиксирована запись следующих участников:
+
</div>
 +
</center></html>
  
 +
В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса.
 +
В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.
  
Печально, что несложные несколько пунктов инструкции оказались невывыполнимы для многих (не осилили даже пункт «На своей личной странице, написать хотя бы ФИО и группу»).  
+
Если вы в зеленой группе — вы кандидат на «отлично автоматом».
 +
 
 +
<!--
 +
«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
 
-->
 
-->
  
  
<!--
+
== Блок 1 — Алгоритмическая практика ==
 +
{{:Практикуемся В Алгоритмах}}
  
SELECT user_name, user_real_name, user_email FROM `user` WHERE user_name IN (select poll_user from poll_vote WHERE poll_id='Xc12c3daeb861942efc77a234744170c') and user_id IN (select wl_user from watchlist where wl_title = "Advanced_Algorithms")
+
== Блок 2 — «Бизнес-моделирование» ==
 +
Моделирование труднорешаемых задач и решение из промышленными солверами.
 +
{{:Моделирование бизнес-задач}}
  
Итак, записались:
+
== Блок 3 — Моделирование труднорешаемых задач ==
 +
{{:Моделирование труднорешаемых задач}}
  
Списки переданы и зафиксированы в учебной части.
+
== Блок 4 — Теоретический ==
-->
+
Необязательно (если вы набрали нужные баллы другими блоками), но может быть полезно, у кого аллергия к коду, Pyomo, а хочется что-то читать и решать, как в старые добрые времена.  
 +
Тут буду упражнения, и простые темы, по которым будут тесты.
  
  
 +
== Бонусные квесты ==
 +
=== Визуализация алгоритмов ===
 +
{{:Визуализация алгоритмов}}
  
 +
=== Изучение тестов по Computer Science ===
 +
{{:Изучение тестов по Computer Science}}
  
 +
=== ТеорУпражнения ===
 +
Осенью 2024 достаточно 4 задач из двух тем.
 +
{{:Решаем теоретические упражнения}}
  
* Проблемы → [mailto:stas-fomin@yandex.ru Стасу Фомину]
+
=== Разбор статей ===
 +
{{:Разбор статей}}
  
<!-- * [[Календарь_лекций]] -->
 
  
<html><center>
+
=== Для избранных ===
</p><div class="sites-embed-align-left-wrapping-off"><div class="sites-embed-border-on sites-embed sites-embed-full-width" style="width: 100%;"><h4 class="sites-embed-title">Успеваемость зарегистрированных студентов</h4><div class="sites-embed-object-title" style="display: none;">Эффективные алгоритмы(студенты).2007</div><div class="sites-embed-content sites-embed-type-spreadsheet"><iframe src="https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZElcGVLNjEtY3lfOHhkdkRQWTI1aUktUUE&single=true&gid=9&output=html" id="1695919049" frameborder="0" height="800" width="100%"></iframe></div></div>
+
* Обычно согласовывается с посещающими студентами, выбор некой темы, связанной и с алгоритмами, сложностью и областью научно-практических интересов студента.
</div>
+
</center></html>
+
  
  
В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса.
 
В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.
 
  
Если вы в зеленой группе — вы кандидат на «отлично автоматом».
+
<!--
 +
== Блок 3 ==
  
«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
+
Выберем несколько тем и теоретических задач.
  
= Темы =
+
Те, кто по результатам предущих блоков вышел на  «хор», смогут улучшить оценку (но не затягивайте, держите в курсе, если это делаете).
 +
----
 +
{{:НаучныйПоиск}}
 +
-->
  
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.
+
<!--
 +
== Блок 1 ==
 +
{{vimeoembed|324745701|800|450}}
  
=== Пройденные ===
+
Простые классические алгоритмы. Динамическое программирование.
 +
Навыки мемоизации, работы с структурами данных.
 +
 
 +
 
 +
=== Теория ===
 
* [[Несложно о сложности. Примеры алгоритмов]]
 
* [[Несложно о сложности. Примеры алгоритмов]]
* [[Формально об алгоритмах. Вычислительные модели]]
 
* [[Временная и пространственная сложность алгоритмов]]
 
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
 
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
 
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
Строка 123: Строка 187:
 
* [[Динамическое программирование для задачи о рюкзаке]]
 
* [[Динамическое программирование для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 +
* [[Вероятностная проверка тождеств]]
 +
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для SAT]]
 
* [[Полиномиальный в среднем алгоритм для SAT]]
  
 
=== Фокус ===
 
Темы к ближайшему занятию.
 
 
<!-- * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]] -->
 
* [[Вероятностная проверка тождеств]]
 
 
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
 
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-CUT: вероятностное округление]]
 
* [[MAX-CUT: вероятностное округление]]
  
 +
* [[MAX-SAT: дерандомизация]]
 +
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 +
-->
  
 +
<!--
 +
<!--
 +
== Блок 2 ==
 +
;Квест «4 задачи»: До 3 декабря
 +
* [[Blog:Advanced_Algorithms/2021-10-15_Practical_Block]]
 +
* Прохождение квеста гарантирует «уд»
 +
* Непрохождение → «неуд»
  
=== Непройденные темы ===
+
;Квест «2 задачи из Spojcoding/Codechefing»
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
+
* До 15 декабря.
 +
* Прохождение квеста гарантирует «хор» (7)
 +
* Повторим условия:
 +
** Не Leetcoding
 +
** Только Python
 +
** Да, должна проходить TL
 +
 
 +
;Квест «4 задачи из Spojcoding/Codechefing»
 +
* До 15 декабря.
 +
* Прохождение квеста гарантирует «отл» (8)
 +
* Повторим условия:
 +
** Не Leetcoding
 +
** Только Python
 +
** Да, должна проходить TL
 +
-->
 +
 
 +
 
 +
<!--
 +
== Блок 3 ==
 +
Выберем несколько тем и теоретических задач.
 +
 
 +
Те, кто по результатам предущих блоков вышел на  «хор» до 12 декабря, смогут улучшить оценку
 +
* [[Blog:Advanced_Algorithms/2021-11-15_Research_Block]]
 +
-->
 +
 
 +
=== ТеорТемы ===
 +
Тут отобраны только детские темы про алгоритмы, никакой сложности, будем проверять, то что вы их читали тестами на созвонах — и так, можно будет набрать «переключающий балл» (отберем персентилями по сумме всех результатов). Плюс можно еще балл за задачи, ну или как-то вместе может они наберут балл, или как-то учтется в 10-бальной оценке.
 +
 
 +
{{SideBar40|Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.}}
 +
 
 +
* [[Несложно о сложности. Примеры алгоритмов]]
 +
 
 +
* [[Жадный алгоритм в задачах о покрытии]]
 +
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
 +
* [[Жадный алгоритм в задаче о рюкзаке]]
 +
 
 +
* [[Динамическое программирование для задачи о рюкзаке]]
 +
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 +
 
 +
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 +
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 +
* [[Полиномиальный в среднем алгоритм для SAT]]
 +
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
 +
* [[MAX-SAT: вероятностное округление]]
 +
* [[MAX-CUT: вероятностное округление]]
 
* [[MAX-SAT: дерандомизация]]
 
* [[MAX-SAT: дерандомизация]]
 +
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
  
 +
* [[Формально об алгоритмах. Вычислительные модели]]
 +
* [[Временная и пространственная сложность алгоритмов]]
 +
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
  
 +
<!--
 +
=== Не будет на курсе в этом году ===
  
<!-- * [[PCP и аппроксимируемость]] -->
+
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
<!-- {:Дерандомизация Люби} -->
+
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
<!-- * [[Параллельный алгоритм Люби для максимального по включению независимого множества]] -->
+
* [[PCP и аппроксимируемость]]
 +
* [[Параллельный алгоритм Люби для максимального по включению независимого множества]]
 +
-->
  
 +
<!--
 
= Тренировка =
 
= Тренировка =
 
[[Special:MediawikiQuizzer/Эффективные алгоритмы|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
 
[[Special:MediawikiQuizzer/Эффективные алгоритмы|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
Строка 154: Строка 277:
  
 
== Задачи ==
 
== Задачи ==
 +
* [[LeetCoding]]
 +
-->
 +
<!--
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
* [[:Category:Нерешенные задачи]].  Осталось  {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач.
 
* [[:Category:Нерешенные задачи]].  Осталось  {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач.
  
Решать надо создавая для решения ''подстраницу'' страницы с задачей, и ссылаясь в решении на задачу.
+
Решать надо создавая для решения ''подстраницу'' личной страницы, и ссылаясь в решении на задачу.
 
;Пример: Задача [[Вероятностная_проверка_тождеств/Задачи/determinant]] → Решение [[Участник:StasFomin/Задача determinant]].
 
;Пример: Задача [[Вероятностная_проверка_тождеств/Задачи/determinant]] → Решение [[Участник:StasFomin/Задача determinant]].
 
Cтатьи-решения задач помечать вставляя строку
 
Cтатьи-решения задач помечать вставляя строку
Строка 179: Строка 305:
 
Эти задачи заводим в
 
Эти задачи заводим в
 
[[:Category:Предложенные студентами задачи]]
 
[[:Category:Предложенные студентами задачи]]
 
 
 
  
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
Строка 196: Строка 319:
 
Проверенное решение перейдет в [[:Category:Решения]] или,
 
Проверенное решение перейдет в [[:Category:Решения]] или,
 
если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
 
если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
 +
-->
  
= Видеолекции =
+
= Материалы =
 +
Наверно не пригодятся для курса 2022 года.
 +
 
 +
<!--
 +
== Видеолекции ==
 
* [[/Лекции осеннего семестра 2011]]
 
* [[/Лекции осеннего семестра 2011]]
 
** [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент] с прошлогодними видео.
 
** [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент] с прошлогодними видео.
 
* [[/Лекции осеннего семестра 2012]]
 
* [[/Лекции осеннего семестра 2012]]
 
* [[Курс_лекций_«Сложность_алгоритмов»_(ИСПРАН,_3_курс_МФТИ)/Лекции_весеннего_семестра_2013]]
 
* [[Курс_лекций_«Сложность_алгоритмов»_(ИСПРАН,_3_курс_МФТИ)/Лекции_весеннего_семестра_2013]]
 
+
-->
 
== Книга ==
 
== Книга ==
  
Строка 216: Строка 344:
  
 
[[File:book-advanced-algorithms.pdf|512px]]
 
[[File:book-advanced-algorithms.pdf|512px]]
 +
 +
Смешное — [https://vk.com/im?sel=1712504&w=wall-54530371_213451%2F1a6855f382934ad3ee реакция «обычных программистов»]
 +
  
 
== Примечания и ссылки ==
 
== Примечания и ссылки ==
Строка 226: Строка 357:
 
* Еще один классический [http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps курс лекций по теории сложности от László Lovász.]
 
* Еще один классический [http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps курс лекций по теории сложности от László Lovász.]
 
* ''А. Китаев, А. Шень, М. Вялый'', [http://discopal.ispras.ru/img_auth.php/9/96/Qbook_.pdf Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности.
 
* ''А. Китаев, А. Шень, М. Вялый'', [http://discopal.ispras.ru/img_auth.php/9/96/Qbook_.pdf Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности.
 +
* ''С. Дасгупта, Х. Пападимитриу, У. Вазирани'', Алгоритмы [http://www.math.nsc.ru/LBRT/k5/OR-MMF/dasgupta_2014.pdf]
  
 
<references/>
 
  
 
----
 
----
 
{{:Библиотека}}
 
{{:Библиотека}}

Текущая версия на 04:42, 30 октября 2024





Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.




Преподаватель
С.А. Фомин


Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:

  • Зарегистрироваться здесь. Залогинится.
  • Зайти на страницу настроек, указать свой email и подтвердить его.
  • На своей личной странице (это не страница настроек, это то, что сверху слева, с иконкой человечка), написать хотя бы ФИО и группу.
    • Боже, как много народу с рассеянным вниманием уже до сюда не дочитывает.
  • Присоединится к телеграмм-группе  → все, два месяца прошло, набор закрыт.
  • Отметится в этом голосовании:


Записываемся на курс «Advanced Algorithms-2024»?

Да33
100%
ADanilenko, Akazikov, AlferovIS, Eavladimirov, EjenY, Evgeny Poturilo, Evvnes, Gallyamov.im, Glbmkrv, Isypovi, Izwin is, Kdzelenova, Korchagin sergey, KoshelevEA, LunevLA, Maratkhusainov, MariaZharova, Markvernikov, Miroshnichenko, MordashovAP, NikitaAkshaev, Nikitashapovalov, RomanFilonov, Seryj09, Solovev, Ssergomol, Ssyrovatkin, Tiniakov.ad, Vladyur, VoyakinaES, Yaroslav Klimov М05-304Б, Ydanyok, Зайченкова Екатерина
Нет0
0%

Вы должны войти в систему, чтобы участвовать в этом голосовании.

  • Первое установочное занятие будет 6 сентября, в 18-30 в 907 КПМ


Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам.


Вопросы пишите на почту, или задавайте в группе.



Успеваемость зарегистрированных студентов

В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса. В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.

Если вы в зеленой группе — вы кандидат на «отлично автоматом».


Содержание

Блок 1 — Алгоритмическая практика

2021-10-15 Practical Block 2021-11-03 14-27-56 image0.png

Концептуально:

2021-10-15 Practical Block 2021-11-03 15-02-30 image0.png

2021-10-15 Practical Block 2021-11-03 14-24-09 image0.png

(Их там 242)

    • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
  • Решенное
    • Ну смотрите, как оформлено в прошлые годы
    • Решение на подстранице вашей личной страницы
      • Вики-ссылка на задачу
      • Python-код в «<source lang="python"></source>»
      • Метка «{{checkme}}», когда решите.
2021-10-15 Practical Block 2021-11-03 14-22-47 image0.png

(Их там 174)


  • Как легче решать Python
    • Загрузка данных
    • Выбирайте более свежий CPython или PyPy.

Блок 2 — «Бизнес-моделирование»

Моделирование труднорешаемых задач и решение из промышленными солверами. Концептуально:

Уровень 1
«потренироваться на кошках» — решите пару уже решенных задач, постарайтесь оформлять максимально компактно и понятно:
  • используйте хелперы
  • выделите построение модели в функцию от параметров
  • максимально понятные русскоязычные атрибуты модели.
  • оформляем свои ноутбуки в подпапке «homeworks/2024-autumn», заведите там подпапку по вашему логину, желательно без пробелов. Там же можно сохранять какие-то версии обучающих ноутбуков, если хотите с ними жестко поиграть.
  • сравните с решением, если вроде решение совпадает (или вы уверены, нашли ошибку и решили более правильно) — пинганите меня на ревью.

Цена — 1 балла за две задачи, но это обязательно, чтобы перейти к остальным квестам этого блока. Если найдете более эффективную постановку — например, раньше не решалось быстро через CBC, а теперь решается, ну или раза в два быстрее стало с SCIP, и т.п. — 1-2 балла.

Бонусный квест
который можно совместить с обучением — сделать визуализацию (matplotlib-networkx-seaborn-d3js… что хотите, на худой конец просто таблицей), для какой-нибудь решенной задачи, как в

… если ее нет. Это креативная задача, при этом потребует понимания решенной задачи — балл за хорошую визуализацию. Цена: 1-2 балла (ну насколько хорошая будет визуализация)


Уровень 2
решение нерешенной задачи:
  • Надо решить одну! нерешенную задачу, но очень желательно сделать это красиво!
  • Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
  • Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук подпапке «homework/2024/autumn» на алгоритмах.
    • Если все совсем шикарно — бонусные очки (если задача окажется сложной — тоже).
  • Выбирайте задачи из Открытые бизнес-задачи, переходите к редактированию по «Беру…» →
  • Зарезервированные задачи убираются в Зарезервированные практические задачи

Цена: 1-2 балла (насколько хорошо оформленно, насколько хорошая будет визуализация)

  • Можно решать дополнительные задачи (к первой задаче), но наверно всего больше двух пока не надо (нерешенные задачи — ценный ресурс, я его экономлю). Старайтесь сделать качественно, тогда можно будет решать больше.
Уровень 3
записать видеоролик по хорошо решенной задаче (если она сдана, отработаны претензии к оформлению и все такое). Используйте OBS


Цена: 1 балл, но постарайтесь.

Для истории, презентация от 2022 года: 📹 видео 📹

Блок 3 — Моделирование труднорешаемых задач

Обязательно посмотрите

Цели: для осеннего курса 2023, где собрались скорее заинтересованные практикой, чем сложностью задач, можно

  • Сделать одну задачу целиком (визуализация, постановка в ЦЛП и сведение от 3SAT)
  • Или пару задач «поверхностно» — постановка + визуализация (это легкая часть), без части про сведение от 3SAT и тестирования (это может быть очень головоломно).
  • Можно сделать и больше, такой же блок, может заменить решение задачи из Моделирование бизнес-задач, если те почему-то не понравились.
  • Может можно будет даже сделать и меньше, если будет сделано качественно (красивая визуализация, или сложная задача и т.п) — т.е. не надо гнать количество, лучше сделать хорошо и красиво.
  • Разумеется, можно использовать все, что найдете в интернете (код, статьи, книги), или подскажут нейросети (но они обычно подсказывают неверно).


Проблема текущих подходов.

Моделирование труднорешаемых задач 2023-04-24 14-45-02 image0.png

Проблема текущих подходов к преподаванию вычислительной сложности и труднорешаемых задач:

  • «ненужная заумь для ботанов»
  • «всякой фигни как матло у нас нет, у нас проектный подход»© (день открытых дверей МФТИ).
  • множество книг, слайдов, видео и т.п. — но все как правило перепев «ГД», на досках или одноразовых веселых видео.
    • но не «живые модели»!

Результат .

  • Нет навыков проверяемых доказательств
  • Не получаются навыки работы с труднорешаемыми задачами.
    • Мучать «эвристики» и «нейросети» не приходя в сознание.
      • «Какая у вас задача» — ну мы тут «GAN» сети пробовали, вот теперь трансформеры… — Задача то какая?


Что делать?.

  • Научится формализованно формулировать
    • ЦЛП
    • 3SAT
  • Использовать решатели
    • ЦЛП (cbc, coin, SCIP, CPLEX, GUROBI, COPT, MIPT…)
    • SAT (см. SAT-Races [3]).

Тогда можно .

  • Часто решить задачу для реальных данных сходу
    • Или покрутить постановку чтобы задача решалась (релаксация бизнес-ограничений).
  • Начать тестировать
    • Алгоритмы полиномиальные в среднем
    • Приближенные алгоритмы с гарантией точности
    • Вероятностные алгоритмы
    • Эвристики
  • Доказать труднорешаемость
    • Конструктивное сведение кодом, тестирование
    • Потом статья с объяснением.

Конструктивные алгоритмические доказательства .

Что вы получите .


  • → Бизнес-аналитик-алгоритмист! (нарасхват!)
  • → Курсовые-дипломы-статьи в JN
    • В любой ситуации

С чем работаем .

  • Настоящие классические задачи в одном месте (ГД+ВК+…)
    • Open Classic Hard Problems
      • Не пугайтесь, вам достаточно изучить одну задачу… но можно и все.
        • Не «книга, толщиной защищающая от прочтения»
  • Там (см. беджики-ссылки)
    • Постановки
    • Наброски ноутбуков для всех задач в Lab17
    • Частично готовая модель
        • тестовые данные (генератор)
        • визуализация
        • сведение к ЦЛП через Pyomo
        • сведение с 3SAT к задаче
        • вероятностное тестирование
        • видео с разьяснениями

Начать с простого .

Ваш квест .

  • Pyomo-сведение к ЦЛП → PyomoLogo.png — есть Pyomo-формулировка для ЦЛП., Data-vis-logo.png — есть тестовые данные и визуализация.
  • 3SAT-сведение к задаче → Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.
  • Вероятностное тестирование → Yes-you-can-icon.png Можно доработать — сделать Вероятностное тестирование NPC-сведения!
  • Можно
    • все для одной задачи,
    • можно для разных (исправление ошибки или улучшение — ОК)
Желательно напрямую с 3SAT .

Без классического дерева сведения (но можно копировать функции сведения тех задач).

Моделирование труднорешаемых задач 2023-04-27 00-05-30 image0.png

Как с этим работаем .

  • Выбирайте задачи из Open Classic Hard Problems, переходите к редактированию по «Беру…» →
    • Зарезервированные задачи просто помечаются в том же списке, для простоты.
      • Если видите, что зарезервировано кем-то в прошлом году — можно снять чужое резервирование, и поставить свое.
    • Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
    • Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в «лаборатории»..
  • Текущая лаборатория
    • Lab22
    • Lab17 заболела (и может сдохла).
  • Как поотлаживаться локально через VSCode — потом.

Еще раз обо всем этом на одном слайде .

Файл:Idea-hard-problems-course.svg

Картинка в полный размер

Блок 4 — Теоретический

Необязательно (если вы набрали нужные баллы другими блоками), но может быть полезно, у кого аллергия к коду, Pyomo, а хочется что-то читать и решать, как в старые добрые времена. Тут буду упражнения, и простые темы, по которым будут тесты.


Бонусные квесты

Визуализация алгоритмов

Опциональный квест.

  • Но которым можно закрыть и весь курс!

Проблема текущих подходов.

См. доклад PyAlgovizualizer — эффективное преподавание алгоритмов

Почему это вам полезно практически? .

  • VSCode / CodeServer
  • Python — борьба за
    • компактность-лаконичность-понятность
    • эффективность
  • Matplotlib (Must for бизнес-аналитик-алгоритмист!)
  • Формулы LaTeX
  • OBS и навыки видеодокументирования

Полезно для других блоков .


Почему это вам удобно .

  • Вы уже решили задачи для визуализации
    • хорошо их помните
    • можно их сделать блестящими (ну или наконец понять)!
  • Вся среда настроена, коллаборативная, можете помогать друг-другу.
  • Хватит чтобы закрыть весь курс
    • В 2024ом, по 1 баллу за визуализацию, итого → 8 задач, (2+8) = 10.
      • Потом может быть меньше, посмотрим.

Что делать?.

  • Изучить визуализацию алгоритмов с PyVisualizer
    • Проект «algo-visual» на алгоритм.испран.рф (ну или где-то еще), файл «contributing.md»
  • Заведите подпапку «algo-visual/homeworks/2024/ВашЛогинНаDiscopal»
  • Там создавайте файлы визуализированных алгоритмов, с названиями как у LC задачи
  • Можно смотреть, как задачу визуализировали другие — подсмотрите идеи.

Воркфлоу.

Пометьте соотвествующее «решение» «на проверку», как в «Практикуемся В Алгоритмах»

  • написав что есть визуализация.
  • Я проверю, возможно будет фидбек, как при решении.

Когда все ОК

  • Запишите видео «прохождения с объяснением» с помощью OBS
    • можно выложить и подшить ссылку, или просто прислать

Получить фидбек — и повторить!

Изучение тестов по Computer Science

ТеорУпражнения

Осенью 2024 достаточно 4 задач из двух тем.

  • Нужно быть залогиненным
    • Скрыто из интернета
  • Надо решить N задач из M разных разделов.
  • Либо одну бонусную задачу — считаем, что ее решение закрывает квест.
  • Выбирайте задачи из Open Exercises, переходите к редактированию по «Беру…»
    • помечайте их как {{reserve-task|~~~~~}}
    • Решение на подстранице вашей личной страницы
      • Вики-ссылка на задачу
      • Решение — можно использовать текст, латех целиком внутри тега «latex», или просто вставки математики внутри тега «m»
      • На худой конец — очень аккуратно оформить на листочке, сфотографировать, загрузить файлы (разберетесь).
      • Метка «{{checkme}}», когда решите.
      • Внизу вставка всего этого по клику →
  • Они попадут в Категория:На проверку
  • Все как обычно в наших квестах.

Разбор статей

Важный квест, для тех, кто не хочет ограничится инженерным IT-уровнем.

  • Цель — попробовать разобраться в свежей статье, связанной с темой курса.
    • Понять постановку, описать максимально просто (оформляем на русском)
      • Чем больше иллюстраций — тем лучше, мы никак не ограничены.
      • Ссылки на видео, другие лекции, все что найдете в процессе разбора — ограничений нет.
    • Если есть доказательства — понять основные идеи
    • Если алгоритм — попробовать реализовать.

В процессе

  • Всяко научитесь пользоваться интерфейсом баз статей researchgate, citeseer, arxiv
  • Возможно найти опровержение или написать новую статью.
  • Поймете, как писать правильную понятную статью, ну или как не писать непонятную.


Оформлять можно

  • Вики-статьи (шаблон набросан, презентация получится сама)
    • Ну и опыт MediaWiki-разметки полезен — кроме Wikipedia, это самая распространенная вики-разметка (вики системы институтов, компаний, баз знаний), и наверно самая используемая плоская разметка, после Markdown (хелп тут).
  • git-репо где угодно с beamer-презентацией или jupyter-ноутбук (возможно погрузим в какую-нибудь лабу для быстрой совместной работы).
  • Выбираете «незанятую» страницу из Категория:Разбор актуальных статей
  • «Резервируете» ее.
  • Работаете, можете меня пинговать — буду смотреть-поправлять в процессе.
    • Если вот знаете интересную статью, как-то связанную (темы, задачи — сложность, алгоритмы в среднем и т.п.) — можете договорится (свяжитесь), и разбирать ее.
  • Бонус — 3-6 баллов (от качества и сложности).


Для избранных

  • Обычно согласовывается с посещающими студентами, выбор некой темы, связанной и с алгоритмами, сложностью и областью научно-практических интересов студента.





ТеорТемы

Тут отобраны только детские темы про алгоритмы, никакой сложности, будем проверять, то что вы их читали тестами на созвонах — и так, можно будет набрать «переключающий балл» (отберем персентилями по сумме всех результатов). Плюс можно еще балл за задачи, ну или как-то вместе может они наберут балл, или как-то учтется в 10-бальной оценке.

Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.


Материалы

Наверно не пригодятся для курса 2022 года.

Книга

Специальная верстка для чтения с ноутбуков и КПК:

  • альбомная ориентация
  • крупные беззасечные шрифты

Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).

Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.

File:Book-advanced-algorithms.pdf

Book-advanced-algorithms.pdf

Смешное — реакция «обычных программистов»


Примечания и ссылки

  • Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.

Полезная сопутствующая литература по курсу.



  1. Особенно для физтехов, которые скипают теорию и не приходя в сознание смотрят «как решать»