Method for Constructing Optimal Dark Coverings

The problem of constructing metric ε-nets and corresponding coverings by balls for compact sets with a probability measure is considered. In the case of sets having metrically significant parts with a small measure (dark sets), methods for constructing ε-nets are combined with the deep holes method in a unified approach. According to this approach, a constructed metric net is supplemented with its deep hole (the most distant element of the set) until the required accuracy is achieved. An existing implementation of the method for a metric set with a given probability measure is based on a pure global search for deep holes. To construct dark coverings, the method is implemented on the basis of a random multistart. For the resulting nets, the logarithm of the number of their elements is shown to be close to ε-entropy, which means that they are optimal. Techniques for estimating the reliability and completeness of constructed (ε, δ)-coverings in the sense of C.E. Shannon are described. The methods under consideration can be used to construct coverings of implicitly given sets with a measure defined on the preimage and to recover compact supports of multidimensional random variables with an unknown distribution law.

Keywords

ε-nets, Shannon (ε, δ)-net, ε-entropy, ε-capacity, fractal dimension, coverings, approximation, deep holes method, global optimization, local optimization, pure global search, random multistart, mathematical modeling, support of a random variable

Received

11.10.2018

Publication date

11.10.2018

Number of characters

5658

Cite Download pdf To download PDF you should sign in

GOST	Kamenev G. Method for Constructing Optimal Dark Coverings // Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki – 2018. – V. 58. – Issue 7 C. 1089-1097 [Electronic resource]. URL: http://ras.jes.su/zvmmf/s004446690000330-4-1-en (circulation date: 25.04.2024). DOI: 10.31857/S004446690000330-4
MLA	Kamenev, G. "Method for Constructing Optimal Dark Coverings." Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58.7 (2018):1089-1097. DOI: 10.31857/S004446690000330-4
APA	Kamenev G. (2018). Method for Constructing Optimal Dark Coverings. Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58(7), pp.1089-1097 DOI: 10.31857/S004446690000330-4

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной


1	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg Подпись к рисунку/медиа Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg
2	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg
3	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg
4	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg
5	Наша компания приготовила для своих клиентов, желающих заказать штукатурные работы в Санкт-Петербурге http://www.plasterers-spb.ru по наиболее выгодным расценкам. Высококвалифицированные специалисты, обладающие практическим опытом, помогут с правильным выбором штукатурки и окажут содействие с подбором материала. Мы гарантируем выполнение работ в несколько этапов, на высоком профессиональном уровне придерживаясь сжатых сроков. На официальном сайте, вы можете ознакомиться с широким выбором видов работ, осуществляемых нашими штукатурами. http://www.plasterers-spb.ru - https://b.radikal.ru/b01/1810/de/883b59b2b552.jpg

Readers community rating: votes 0

1. Bushenkov V.A., Chernykh O.L., Kamenev G.K., Lotov A.V. Multidimensional images given by mappings: Construction and visualization // Pattern Recognition and Image Analysis. 1995. V. 5. № 1. P. 35–56.

2. Lotov A.V., Bushenkov V.A., Kamenev G.K., Chernykh O.L. Komp'yuter i poisk kompromissa. Metod dostizhimykh tselej. M.: Nauka, 1997.

3. Lotov A.V., Bushenkov V.A., Kamenev G.K. Interactive decision maps. Approximation and visualization of Pareto frontier // Appl. Optimizat. V. 89. Boston: Kluwer, 2004.

4. Konvej Dzh., Sloen N. Upakovki sharov, reshetki i gruppy. M.: Mir, 1990. T.1.

5. Evtushenko Yu.G. Chislennyj metod poiska global'nogo ehkstremuma funktsij (perebor na neravnomernoj setke) // Zh. vychisl. matem. i matem. fiz. 1971. T. 11. № 6. S. 1390–1403.

6. Evtushenko Yu.G., Posypkin M.A. Metod neravnomernykh pokrytij dlya resheniya zadach mnogokriterial'noj optimizatsii s garantirovannoj tochnost'yu // Zh. vychisl. matem. i matem. fiz. 2013. T. 53. № 2. S. 209–224.

7. Kamenev G.K., Kondrat'ev D.L. Ob odnom metode issledovaniya nezamknutykh nelinejnykh modelej // Matem. modelirovanie.1992. № 3. S. 105–118.

8. Kolmogorov A.N., Tikhomirov V.M. E-ehntropiya i E-emkost' mnozhestv v funktsional'nykh prostranstvakh // Uspekhi matem. nauk. 1959. T. 14. № 2. C. 3–86.

9. Shennon K. Matematicheskaya teoriya svyazi (1948), prilozhenie 7. V kn. Shennon K. Raboty po teorii informatsii i kibernetike. M.: Izd. Inostrannoj Literatury, 1963.

10. Kamenev G.K. Approksimatsiya vpolne ogranichennykh mnozhestv metodom Glubokikh Yam // Zh. vychisl. matem. i matem. fiz. 2001. T. 41. № 11. S. 1751–1760.

11. Zhiglyavskij A.A., Zhilinskas A.G. Metody poiska global'nogo ehkstremuma. M.: Nauka, 1991.

12. Kamenev G.K. Metod approksimatsii metricheskikh obrazov s maloj meroj proobraza // IX Vseros. nauchnaya konferentsiya «Matematicheskoe modelirovanie razvivayuschejsya ehkonomiki, ehkologii i tekhnologij», EhKOMOD-2016, [Ehlektronnyj resurs]: g. Kirov, 4–9 iyulya 2016 / Sb. materialov konferentsii. Kirov: izd-vo VyatGU, 2016. ISBN 978-5-98228-116-6, s. 272–275.

13. Kamenev G.K. Issledovanie skorosti skhodimosti i ehffektivnosti dvukhfaznykh metodov approksimatsii obolochki Ehdzhvorta–Pareto // Zh. vychisl. matem. i matem. fiz. 2013. T. 53. № 4. S. 507–519.

14. Kamenev G.K. Postroenie temnykh pokrytij i setok fantomov (doklad) // Mezhdunar. konferentsiya “Chislennaya geometriya, postroenie raschetnykh setok i vysokoproizvoditel'nye vychisleniya” (NUMGRID2016), DOI: 10.13140/RG.2.2.32217.11360

15. Shiryaev A.N. Veroyatnost'. M.: Nauka, 1980.