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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Ваш квест .)
Строка 105: Строка 105:
 
** все для одной задачи,  
 
** все для одной задачи,  
 
** можно для разных (исправление ошибки или улучшение — ОК)
 
** можно для разных (исправление ошибки или улучшение — ОК)
 +
 +
===== Желательно напрямую с 3SAT . =====
 +
 +
Без классического дерева сведения (но можно копировать функции сведения тех задач).
 +
 +
[[File:Моделирование труднорешаемых задач_2023-04-27_00-05-30_image0.png|center|640px]]
  
 
==== Как с этим работаем . ====
 
==== Как с этим работаем . ====

Версия 21:05, 26 апреля 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]).

Тогда можно .

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

Конструктивные алгоритмические доказательства .

Задача о раскраске в 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 — потом.