Hardprob/Minimum Test Collection — различия между версиями
Материал из DISCOPAL
3xMike (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
* Коллекция <em>C</em> подмножеств конечного множества <em>S</em>. | * Коллекция <em>C</em> подмножеств конечного множества <em>S</em>. | ||
| − | * Найти подколлекцию <em>C'⊆ C</em>, такую, что для каждой пары различных элементов <m>x_1,x_2∈ S</m>, есть некоторое | + | * Найти подколлекцию <em>C'⊆ C</em>, такую, что для каждой пары различных элементов <m>x_1,x_2∈ S</m>, есть некоторое подмножество <m>c∈ C'</m>, которое содержит точно один элемент из этой пары. |
* Минимизировать мощность этой подколлекции <em>|C'|</em>. | * Минимизировать мощность этой подколлекции <em>|C'|</em>. | ||
Версия 11:25, 21 декабря 2023
- Коллекция C подмножеств конечного множества S.
- Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов , есть некоторое подмножество , которое содержит точно один элемент из этой пары.
- Минимизировать мощность этой подколлекции |C'|.
Код в «minimum-test-collection.ipynb» на гитлаб или живьем в лабе
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP6»
Задача зарезервирована: 3xMike 14:23, 26 ноября 2023 (UTC)