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

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

Slide Show

Заголовок

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

Автор

Стас Фомин

Нижний колонтитул

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

Дополнительный нижний колонтитул

Стас Фомин, 15:10, 11 апреля 2024

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

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

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

Результат .

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