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

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Как с этим работаем .)
 
(не показано 38 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
<noinclude><slideshow style="ispras" headingmark="." scaled=1 /></noinclude>
 +
 +
;Обязательно посмотрите:
 +
{{vimeoembed|820808618|800|450}}
 +
{{vimeoembed|887817907|800|450}}
 +
{{vimeoembed|887825798|800|450}}
 +
 +
Цели: для осеннего курса 2023, где собрались скорее заинтересованные практикой, чем сложностью задач, можно
 +
* Сделать одну задачу целиком (визуализация, постановка в ЦЛП и сведение от 3SAT)
 +
* Или пару задач «поверхностно» — постановка + визуализация (это легкая часть), без части про сведение от 3SAT и тестирования (это может быть очень головоломно).
 +
* Можно сделать и больше, такой же блок, может заменить решение задачи из [[Моделирование бизнес-задач]], если те почему-то не понравились.
 +
* Может можно будет даже сделать и меньше, если будет сделано качественно (красивая визуализация, или сложная задача и т.п) — т.е. не надо гнать количество, лучше сделать хорошо и красиво.
 +
* Разумеется, можно использовать все, что найдете в интернете (код, статьи, книги), или подскажут нейросети (но они обычно подсказывают неверно).
 +
 +
 +
==== Проблема текущих подходов. ====
 +
 
[[File:Моделирование труднорешаемых задач_2023-04-24_14-45-02_image0.png|right|360px]]
 
[[File:Моделирование труднорешаемых задач_2023-04-24_14-45-02_image0.png|right|360px]]
  
Строка 4: Строка 21:
 
* «ненужная заумь для ботанов»
 
* «ненужная заумь для ботанов»
 
* «всякой фигни как матло у нас нет, у нас проектный подход»© (день открытых дверей МФТИ).
 
* «всякой фигни как матло у нас нет, у нас проектный подход»© (день открытых дверей МФТИ).
−
* 100500 книг, видео и т.п. — но все как правило перепев «ГД», на досках или одноразовых видео.
+
* множество книг, слайдов, [https://www.youtube.com/results?search_query=NP+complete+proof видео] и т.п. — но все как правило перепев «ГД», на досках или [https://www.youtube.com/watch?v=ctwX--JEzSA&t=9s одноразовых веселых видео].
 
** но не «живые модели»!
 
** но не «живые модели»!
  
 +
==== Результат . ====
 +
* Нет навыков проверяемых доказательств
 +
* Не получаются ''навыки'' работы с труднорешаемыми задачами.
 +
** Мучать «эвристики» и «нейросети» не приходя в сознание.
 +
*** «Какая у вас задача» — ну мы тут «GAN» сети пробовали, вот теперь трансформеры… — Задача то какая?
  
−
* Win-Win!
 
−
* Бизнес-аналитикам, алгоритмистам, прожект и продукт-менеджерам.
 
−
* Воркфлоу «взятия задачи» аналогичен блоку «[[Практикуемся_В_Алгоритмах]]»
 
−
** Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в [[Lab17]].
 
  
 +
==== Что делать?. ====
 +
<div style="font-size:50%; background:#ffffdd>[https://ru.wikibooks.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%9A%D1%80%D0%B8%D1%81%D1%82%D0%BE%D0%B1%D0%B0%D0%BB%D1%8F_%D0%A5%D1%83%D0%BD%D1%82%D1%8B … — Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.… — Мы сами знаем, что она не имеет решения, … Мы хотим знать, как её решать. ©]</div>
  
−
* Надо решить 2 задачи
+
* Научится формализованно формулировать
−
** Если красиво и понятно оформлено — бонусные очки (если задача окажется сложной — тоже).
+
** ЦЛП
 +
** 3SAT
 +
* Использовать решатели
 +
** ЦЛП (cbc, coin, SCIP, CPLEX, GUROBI, COPT, MIPT…)
 +
** SAT (см. SAT-Races [http://sat-race-2019.ciirc.cvut.cz/]).
  
−
* Выбирайте задачи из [[Open Classic Hard Problems]], переходите к редактированию по «Беру…» → 
+
=== Тогда можно . ===
−
* Зарезервированные задачи просто помечаются в том же списке, для простоты.
+
* Часто решить задачу для реальных данных сходу
 +
** Или покрутить постановку чтобы задача решалась (релаксация бизнес-ограничений).
 +
* Начать тестировать
 +
** Алгоритмы полиномиальные в среднем
 +
** Приближенные алгоритмы с гарантией точности
 +
** Вероятностные алгоритмы
 +
** Эвристики
 +
* Доказать труднорешаемость
 +
** Конструктивное сведение кодом, тестирование
 +
** Потом статья с объяснением.
  
 +
=== Конструктивные алгоритмические доказательства . ===
 +
 +
<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 воркшоп], [https://i.0x1.tv/s/SYaESibH4fpkmDT Зеркало]
 +
** в PYSAT
 +
** Jupyter Notebooks
 +
 +
----
 +
* → Бизнес-аналитик-алгоритмист! (нарасхват!)
 +
* → Курсовые-дипломы-статьи в JN
 +
** В любой ситуации
 +
 +
==== С чем работаем . ====
 +
* Настоящие классические задачи в одном месте (ГД+ВК+…)
 +
** [[Open Classic Hard Problems]]
 +
*** Не пугайтесь, вам достаточно изучить одну задачу… но можно и все.
 +
**** Не «книга, толщиной защищающая от прочтения»
 +
* Там (см. беджики-ссылки)
 +
** Постановки
 +
** Наброски ноутбуков для всех задач в [[Lab17]]
 +
** Частично готовая модель
 +
**** тестовые данные (генератор)
 +
**** визуализация
 +
**** сведение к ЦЛП через Pyomo
 +
**** сведение с 3SAT к задаче
 +
**** вероятностное тестирование
 +
**** видео с разьяснениями
 +
 +
==== Начать с простого . ====
 +
* [[Hardprob/Maximum Set Packing]]
 +
* [[Hardprob/Minimum Set Cover]]
 +
* [[Hardprob/Maximum Cut]]
 +
* [[Hardprob/Maximum Set Splitting]]
 +
 +
==== Ваш квест . ====
 +
* Pyomo-сведение к ЦЛП → {{has-pyomo-model}}, {{has-testdata-and-visualization}}
 +
* 3SAT-сведение к задаче → {{has-npc-reduction}}
 +
* Вероятностное тестирование → {{add-random-fuzzing-tests}}
 +
* Можно
 +
** все для одной задачи,
 +
** можно для разных (исправление ошибки или улучшение — ОК)
 +
 +
===== Желательно напрямую с 3SAT . =====
 +
 +
Без классического дерева сведения (но можно копировать функции сведения тех задач).
 +
 +
[[File:Моделирование труднорешаемых задач_2023-04-27_00-05-30_image0.png|center|640px]]
 +
 +
==== Как с этим работаем . ====
 +
* Выбирайте задачи из [[Open Classic Hard Problems]], переходите к редактированию по «Беру…» → 
 +
** Зарезервированные задачи просто помечаются в том же списке, для простоты.
 +
*** Если видите, что зарезервировано кем-то в прошлом году — можно снять чужое резервирование, и поставить свое.
 +
** Воркфлоу «взятия задачи» аналогичен блоку «[[Практикуемся_В_Алгоритмах]]»
 +
** Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в [[Lab17]].
 +
* Всего должно хватать в нашем [[Lab17]]
 +
* Как поотлаживаться локально через VSCode — потом.
  
−
* Как поотлаживаться локально через VSCode — потом
+
=== Еще раз обо всем этом на одном слайде . ===
−
** отладить установку зависимостей.
+
[[File:Idea-hard-problems-course.svg|800px|center]]
  
−
* Параллельно можно смотреть [https://software.sandia.gov/downloads/pub/pyomo/Pyomo-Workshop-Summer-2018.pdf воркшоп по Pyomo]
+
[{{filepath:Idea-hard-problems-course.svg}} Картинка в полный размер]
−
** Там будет видео в каждом питон-ноутбуке.
+
−
* Оформляем свои ноутбуки в папке «[https://discopal-lab.0x1.tv/projects/3b41be68-a970-4f60-9138-1aa73f8ee1fa/files/advalg-2022-homeworks/?session=default advalg-2022-homeworks]»
+

Текущая версия на 15:10, 11 апреля 2024

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

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

Стас Фомин, 15:10, 11 апреля 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, переходите к редактированию по «Беру…» →
    • Зарезервированные задачи просто помечаются в том же списке, для простоты.
      • Если видите, что зарезервировано кем-то в прошлом году — можно снять чужое резервирование, и поставить свое.
    • Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
    • Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab17.
  • Всего должно хватать в нашем Lab17
  • Как поотлаживаться локально через VSCode — потом.

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

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

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

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