https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5%3A%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B2_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D1%85_%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8%2F%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8%2FHitting-set 2026-05-06T09:49:27Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B2_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D1%85_%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/Hitting-set&diff=501&oldid=prev 2011-06-14T17:00:43Z

<p>Решение</p> <p><b>Новая страница</b></p><div>== Решение ==<br /> <br /> Задача аналогична задаче о поиске покрытия из курса.<br /> На каждом шаге добавляем в S такой элемент, котороый содержится в наибольшем количестве еще не покрытых множеств.<br /> Таким образом, будет так же справедлива оценка X&lt;sub&gt;k+1&lt;/sub&gt; &lt;= X&lt;sub&gt;k&lt;/sub&gt;(1-1/M) и мощность множества S, построенного данным алгоритмом, будет превосходить мощность S*, построенного оптимальным алгоритмом, не более чем в 1+ln(m) раз, где m - количество подмножеств в данном семействе.</div>

Flid