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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Что делать?.)
(Что делать?.)
Строка 19: Строка 19:
  
 
==== Что делать?. ====
 
==== Что делать?. ====
<div style="font-size:50%; background:#ffffbb>[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>
+
<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>
 +
 
 
* Научится формализованно формулировать  
 
* Научится формализованно формулировать  
 
** ЦЛП
 
** ЦЛП

Версия 12:15, 24 апреля 2023

Заголовок

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

Стас Фомин, 22:41, 9 мая 2024

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

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

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

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

Результат .

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


Что делать?.

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

Тогда можно .

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

Решения есть .

  • Win-Win!
  • Бизнес-аналитикам, алгоритмистам, прожект и продукт-менеджерам.
  • Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
    • Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab17.


  • Надо решить 2 задачи
    • Если красиво и понятно оформлено — бонусные очки (если задача окажется сложной — тоже).
  • Выбирайте задачи из Open Classic Hard Problems, переходите к редактированию по «Беру…» →
  • Зарезервированные задачи просто помечаются в том же списке, для простоты.


  • Как поотлаживаться локально через VSCode — потом
    • отладить установку зависимостей.
  • Параллельно можно смотреть воркшоп по Pyomo
    • Там будет видео в каждом питон-ноутбуке.
  • Оформляем свои ноутбуки в папке «advalg-2022-homeworks»