Моделирование труднорешаемых задач — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Как с этим работаем .)
 
(не показаны 24 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
<noinclude><slideshow style="ispras" headingmark="." scaled=1 /></noinclude>
 
<noinclude><slideshow style="ispras" headingmark="." scaled=1 /></noinclude>
 +
 +
;Обязательно посмотрите:
 +
{{vimeoembed|820808618|800|450}}
 +
{{vimeoembed|887817907|800|450}}
 +
{{vimeoembed|887825798|800|450}}
 +
 +
Цели: для осеннего курса 2023, где собрались скорее заинтересованные практикой, чем сложностью задач, можно
 +
* Сделать одну задачу целиком (визуализация, постановка в ЦЛП и сведение от 3SAT)
 +
* Или пару задач «поверхностно» — постановка + визуализация (это легкая часть), без части про сведение от 3SAT и тестирования (это может быть очень головоломно).
 +
* Можно сделать и больше, такой же блок, может заменить решение задачи из [[Моделирование бизнес-задач]], если те почему-то не понравились.
 +
* Может можно будет даже сделать и меньше, если будет сделано качественно (красивая визуализация, или сложная задача и т.п) — т.е. не надо гнать количество, лучше сделать хорошо и красиво.
 +
* Разумеется, можно использовать все, что найдете в интернете (код, статьи, книги), или подскажут нейросети (но они обычно подсказывают неверно).
 +
  
 
==== Проблема текущих подходов. ====
 
==== Проблема текущих подходов. ====
Строка 39: Строка 52:
 
** Конструктивное сведение кодом, тестирование
 
** Конструктивное сведение кодом, тестирование
 
** Потом статья с объяснением.
 
** Потом статья с объяснением.
 +
 +
=== Конструктивные алгоритмические доказательства . ===
 +
 +
<noinclude>
 +
==== Задача о раскраске в 4 цвета . ====
 +
<slides split="-----" width="800">
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-45-17_image0.png]]
 +
-----
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-48-32_image0.png]]
 +
-----
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-50-12_image0.png]]
 +
-----
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-50-35_image0.png]]
 +
-----
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-51-03_image0.png]]
 +
-----
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-51-23_image0.png]]
 +
-----
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-51-39_image0.png]]
 +
-----
 +
[[File:Моделирование труднорешаемых задач_2023-04-25_09-52-28_image0.png]]
 +
</slides>
 +
</noinclude>
  
 
==== Что вы получите . ====
 
==== Что вы получите . ====
 
* Навыки моделирования  
 
* Навыки моделирования  
−
** в PYOMO, сразу см. [https://software.sandia.gov/downloads/pub/pyomo/Pyomo-Workshop-Summer-2018.pdf воркшоп]
+
** в PYOMO, сразу см. [https://software.sandia.gov/downloads/pub/pyomo/Pyomo-Workshop-Summer-2018.pdf воркшоп], [https://i.0x1.tv/s/SYaESibH4fpkmDT Зеркало]
 
** в PYSAT
 
** в PYSAT
 
** Jupyter Notebooks
 
** Jupyter Notebooks
−
→ Бизнес-аналитик-алгоритмист! (нарасхват!)
+
 
 +
----
 +
* → Бизнес-аналитик-алгоритмист! (нарасхват!)
 +
* → Курсовые-дипломы-статьи в JN
 +
** В любой ситуации
  
 
==== С чем работаем . ====
 
==== С чем работаем . ====
Строка 65: Строка 105:
 
==== Начать с простого . ====
 
==== Начать с простого . ====
 
* [[Hardprob/Maximum Set Packing]]
 
* [[Hardprob/Maximum Set Packing]]
−
* [[Hardprob/Minimum Set Covering]]
+
* [[Hardprob/Minimum Set Cover]]
 
* [[Hardprob/Maximum Cut]]
 
* [[Hardprob/Maximum Cut]]
 
* [[Hardprob/Maximum Set Splitting]]
 
* [[Hardprob/Maximum Set Splitting]]
−
 
  
 
==== Ваш квест . ====
 
==== Ваш квест . ====
Строка 77: Строка 116:
 
** все для одной задачи,  
 
** все для одной задачи,  
 
** можно для разных (исправление ошибки или улучшение — ОК)
 
** можно для разных (исправление ошибки или улучшение — ОК)
 +
 +
===== Желательно напрямую с 3SAT . =====
 +
 +
Без классического дерева сведения (но можно копировать функции сведения тех задач).
 +
 +
[[File:Моделирование труднорешаемых задач_2023-04-27_00-05-30_image0.png|center|640px]]
  
 
==== Как с этим работаем . ====
 
==== Как с этим работаем . ====
 
* Выбирайте задачи из [[Open Classic Hard Problems]], переходите к редактированию по «Беру…» →   
 
* Выбирайте задачи из [[Open Classic Hard Problems]], переходите к редактированию по «Беру…» →   
 
** Зарезервированные задачи просто помечаются в том же списке, для простоты.
 
** Зарезервированные задачи просто помечаются в том же списке, для простоты.
 +
*** Если видите, что зарезервировано кем-то в прошлом году — можно снять чужое резервирование, и поставить свое.
 
** Воркфлоу «взятия задачи» аналогичен блоку «[[Практикуемся_В_Алгоритмах]]»
 
** Воркфлоу «взятия задачи» аналогичен блоку «[[Практикуемся_В_Алгоритмах]]»
−
** Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в [[Lab17]].
+
** Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в «лаборатории»..
−
* Всего должно хватать в нашем [[Lab17]]
+
* Текущая лаборатория
 +
** [[Lab22]]  
 +
** [[Lab17]] заболела (и может сдохла).
 
* Как поотлаживаться локально через VSCode — потом.
 
* Как поотлаживаться локально через VSCode — потом.
 +
 +
=== Еще раз обо всем этом на одном слайде . ===
 +
[[File:Idea-hard-problems-course.svg|800px|center]]
 +
 +
[{{filepath:Idea-hard-problems-course.svg}} Картинка в полный размер]

Текущая версия на 22:41, 9 мая 2024

S5-ispras-preview.png
Slide Show
Заголовок

Моделирование труднорешаемых задач
Автор
Стас Фомин
Нижний колонтитул
Моделирование труднорешаемых задач
Дополнительный нижний колонтитул

Стас Фомин, 22:41, 9 мая 2024
Обязательно посмотрите

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

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


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

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

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

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

Результат .

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


Что делать?.

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

Тогда можно .

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

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

Задача о раскраске в 4 цвета .

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

Моделирование труднорешаемых задач 2023-04-25 09-48-32 image0.png

Моделирование труднорешаемых задач 2023-04-25 09-50-12 image0.png

Моделирование труднорешаемых задач 2023-04-25 09-50-35 image0.png

Моделирование труднорешаемых задач 2023-04-25 09-51-03 image0.png

Моделирование труднорешаемых задач 2023-04-25 09-51-23 image0.png

Моделирование труднорешаемых задач 2023-04-25 09-51-39 image0.png

Моделирование труднорешаемых задач 2023-04-25 09-52-28 image0.png


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

  • → Бизнес-аналитик-алгоритмист! (нарасхват!)
  • → Курсовые-дипломы-статьи в 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

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

Источник — «https://discopal.ispras.ru/index.php?title=Моделирование_труднорешаемых_задач&oldid=29523»