Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
Задача 2 (минимальное покрытие множества, MSC) | '''Задача 2 (минимальное покрытие множества, MSC)''' | ||
Дано: конечное множество U и набор S подмножеств | Дано: конечное множество <math>\mathfrak{U} \; </math> и набор <math>S \; </math> подмножеств <math>S_1, S_2,... S_t \; </math> множества <math>\mathfrak{U} \; </math>. | ||
Требуется: найти минимальное покрытие множества | |||
Требуется: найти минимальное покрытие множества <math>S' \; </math>, где <math>S' \subseteq S \; </math> – покрытие множества <math>(\mathfrak{U}, S) \; </math>, если <math> \bigcup_{S_i \in S'} S_i = \mathfrak{U} \; </math> | |||