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

Материал из DISCOPAL
Перейти к: навигация, поиск
Заголовок

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

Стас Фомин, 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»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.