Моделирование труднорешаемых задач — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
* множество книг, слайдов, [https://www.youtube.com/results?search_query=NP+complete+proof видео] и т.п. — но все как правило перепев «ГД», на досках или [https://www.youtube.com/watch?v=ctwX--JEzSA&t=9s одноразовых веселых видео]. | * множество книг, слайдов, [https://www.youtube.com/results?search_query=NP+complete+proof видео] и т.п. — но все как правило перепев «ГД», на досках или [https://www.youtube.com/watch?v=ctwX--JEzSA&t=9s одноразовых веселых видео]. | ||
** но не «живые модели»! | ** но не «живые модели»! | ||
| − | |||
==== Результат . ==== | ==== Результат . ==== | ||
| − | |||
* Нет навыков проверяемых доказательств | * Нет навыков проверяемых доказательств | ||
* Не получаются ''навыки'' работы с труднорешаемыми задачами. | * Не получаются ''навыки'' работы с труднорешаемыми задачами. | ||
** Мучать «эвристики» и «нейросети» не приходя в сознание. | ** Мучать «эвристики» и «нейросети» не приходя в сознание. | ||
| + | *** «Какая у вас задача» — ну мы тут «GAN» сети пробовали, вот теперь трансформеры… — Задача то какая? | ||
| + | |||
| + | |||
| + | ==== Что делать?. === | ||
| + | {{SideBar40| [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 … — Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.… — Мы сами знаем, что она не имеет решения, … Мы хотим знать, как её решать. ©]}} | ||
| + | * Научится формализованно формулировать | ||
| + | ** ЦЛП | ||
| + | ** 3SAT | ||
| + | * Использовать решатели | ||
| + | ** ЦЛП (cbc, coin, SCIP, CPLEX, GUROBI, COPT, MIPT…) | ||
| + | ** SAT (см. SAT-Races [http://sat-race-2019.ciirc.cvut.cz/]). | ||
| + | === Тогда можно . === | ||
| + | * Часто решить задачу для реальных данных сходу | ||
| + | ** Или покрутить постановку чтобы задача решалась (релаксация бизнес-ограничений). | ||
| + | * Начать тестировать | ||
| + | ** Алгоритмы полиномиальные в среднем | ||
| + | ** Приближенные алгоритмы с гарантией точности | ||
| + | ** Вероятностные алгоритмы | ||
| + | ** Эвристики | ||
| + | * Доказать труднорешаемость | ||
| + | ** Конструктивное сведение кодом, тестирование | ||
| + | ** Потом статья с объяснением. | ||
==== Решения есть . ==== | ==== Решения есть . ==== | ||
Версия 12:11, 24 апреля 2023
- Заголовок
- Моделирование труднорешаемых задач
- Автор
- Стас Фомин
- Нижний колонтитул
- Моделирование труднорешаемых задач
- Дополнительный нижний колонтитул
- Стас Фомин, 22:41, 9 мая 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»