Hardprob/Minimum Test Collection — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
---- | ---- | ||
{{hard-problem-on-lab17|{{PAGENAME}}}} | {{hard-problem-on-lab17|{{PAGENAME}}}} | ||
| − | + | * {{has-testdata-and-visualization}} | |
| − | + | * {{has-pyomo-model}} | |
| − | + | * {{has-npc-reduction}} | |
| − | + | * {{add-random-fuzzing-tests}} | |
| + | ** Вроде как все есть, но надо бы прорефакторить решение студента | ||
| + | |||
---- | ---- | ||
<small> | <small> | ||
| Строка 20: | Строка 22: | ||
<!-- * [ Задача в википедии] --> | <!-- * [ Задача в википедии] --> | ||
</small> | </small> | ||
| + | |||
| + | {{reserve-task|[[Участник:StasFomin|StasFomin]] 20:35, 21 мая 2025 (UTC)}} | ||
<!-- end --> | <!-- end --> | ||
[[Категория:ClassicHardProblems]] | [[Категория:ClassicHardProblems]] | ||
Версия 20:35, 21 мая 2025
- Коллекция C подмножеств конечного множества S.
- Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов (и для каждого элемента этой пары) , есть некоторое подмножество , которое содержит точно один элемент из этой пары.
- Минимизировать мощность этой подколлекции |C'|.
Для понимания названия задачи, представим, что S — это множество возможных болезней, а подмножества — это симптомы (или «тесты»), которые могут быть характерны для нескольких болезней. И мы должны выбрать такой набор симптомов-тестов, чтобы имея результаты, мы могли отличить у пациента любые пары болезней.
Код в «minimum-test-collection.ipynb» на гитлаб или живьем в лабе
-
— есть тестовые данные и визуализация. -
— есть Pyomo-формулировка для ЦЛП. -
— есть сведение на Python NP-полной задачи к данной. -
Можно доработать — сделать Вероятностное тестирование NPC-сведения!
- Вроде как все есть, но надо бы прорефакторить решение студента
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP6»
Задача зарезервирована: StasFomin 20:35, 21 мая 2025 (UTC)