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

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

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

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

Нет навыков проверяемых доказательств
Не получаются навыки работы с труднорешаемыми задачами.
- Мучать «эвристики» и «нейросети» не приходя в сознание.
  - «Какая у вас задача» — ну мы тут «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»

@@ Строка 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>
 * Научится формализованно формулировать
 ** ЦЛП