Метод построения оптимальных темных покрытий

Рассматривается задача построения метрических $\varepsilon$-сетей и соответствующих им покрытий шарами для компактных множеств с вероятностной мерой. Для случая множеств, имеющих метрически значимые части малой меры (темные множества), предлагается использовать методы построения $\varepsilon$-сетей, которые можно объединить в рамках единого подхода метода глубоких ям. В этом подходе построенная метрическая сеть пополняется ее глубокой ямой (наиболее удаленным элементом множества) до достижения требуемой точности. Существующая реализация метода для метрического множества с заданной на нем вероятностной мерой основана на поиске глубоких ям с помощью чистого глобального поиска. Для построения темных покрытий предлагается реализация метода на основе случайного мультистарта. Показана близость логарифма числа элементов получаемых сетей к $\varepsilon$-энтропии, что позволяет говорить об их оптимальности. Приводятся способы оценки надежности и полноты получаемых $(\varepsilon, \delta)$-покрытий в смысле К. Э. Шеннона. Рассматриваемые методы могут использоваться в задачах построения покрытий неявно заданных множеств с мерой, определенной на прообразе, а также в задачах восстановления компактных носителей многомерных случайных величин с неизвестным законом распределения. Библ. 15. Фиг. 2. Табл. 1.