Реализация генератора дискретной случайной величины на основе d-арного дерева
https://doi.org/10.26907/2541-7746.2025.3.507-518
Аннотация
Предложен метод расчета закона распределения дискретной случайной величины (ДСВ) при использовании d-арного дерева. Количество n листьев дерева определяется по количеству элементов закона ДСВ, а количество остальных его вершин отражает генераторы ДСВ с законом, включающим d элементов (далее – d-ГДСВ). Варьирование закона распределения ДСВ через обнуление одного из его элементов сводится к пересчету законов d-ГДСВ, количество которых растет логарифмически в зависимости от значения n.
Об авторах
В. М. Захаров
Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ
Россия
Россия
Вячеслав Михайлович Захаров, доктор технических наук, профессор, профессор кафедры компьютерных систем
г. Казань
С. В. Шалагин
Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ
Россия
Россия
Сергей Викторович Шалагин, доктор технических наук, доцент, профессор кафедры компьютерных систем
г. Казань
Список литературы
1. Закревский А.Д. Реализация случайных событий с заданной вероятностью // Тр. СФТИ. 1965. Вып. 47. C. 56–59.
2. Бухараев Р.Г. Автоматное преобразование вероятностных последовательностей // Вероятн. методы и киберн. 1966. Вып. 1. С. 24–33.
3. Ченцов В.М. Об одном методе синтеза автономного стохастического автомата // Кибернетика. 1968. № 3. С. 32–35.
4. Бухараев Р.Г. Вероятностные автоматы. Казань: Изд-во Казан. ун-та, 1970. 188 с.
5. Поспелов Д.А. Вероятностные автоматы. М.: Энергия, 1970. 88 с.
6. Полляк Ю.Г. Вероятностное моделирование на электронных вычислительных машинах. М.: Сов. радио, 1971. 400 с.
7. Гладкий В.С. Вероятностные вычислительные модели. М.: Наука, 1973. 300 с.
8. Walker A.I. An efficient method for generating discrete random variables with general distributions // ACM Trans. Math. Software. 1977. V. 3, No 3. P. 253–256. https://doi.org/10.1145/355744.355749.
9. Федоров Р.Ф., Яковлев В.В., Добрис Г.В. Стохастические преобразователи информации. Л.: Машиностроение, 1978. 304 с. 10. Четвериков В.Н., Баканович Э.А., Меньков А.В. Вычислительная техника для статистического моделирования. М.: Сов. радио, 1978. 312 с.
10. Бухараев Р.Г. Основы теории вероятностных автоматов. М.: Наука, 1985. 287 с.
11. Походзей Б.Б. Сложность табличных методов моделирования конечных дискретных распределений // Изв. вузов. Матем. 1985. № 7. С. 45–50.
12. Левин Б.Р., Шварц В. Вероятностные модели и методы в системах связи и управления. М.: Радио и связь, 1985. 312 с.
13. Вероятностные автоматы и их приложения (Докл. симпоз., 6–8 июня 1983 г. / Сост. В.М. Захаров). Казань: Изд-во Казан. ун-та, 1986. 212 с.
14. Четвериков В.Н., Баканович Э.А. Стохастические вычислительные устройства систем моделирования. М.: Машиностроение, 1989. 272 с.
15. Дородницын А.А. и др. Словарь по кибернетике. Под ред. В.С. Михалевича. 2-е изд., перераб. и доп. Киев: Гл. ред. Укр. сов. энцикл., 1989. 751 с.
16. Захаров В.М., Шалагин С.В. О развитии аппаратных средств статистического моделирования // Тр. SORUCOM – 2014. III Международн. науч.-практ. конф. «Развитие вычислительной техники и ее программного обеспечения в России и в странах бывшего СССР: история и перспективы». Казань, 13–17 окт. 2014 г. C. 103–108. URL: https://computer-museum.ru/articles/materialy-mezhdunarodnoy-konferentsii-sorucom-2014/490/.
17. Шалагин С.В. Реализация цифровых устройств в архитектуре ПЛИС/FPGA при использовании распределенных вычислений в полях Галуа: монография. Казань: Изд-во КНИТУ – КАИ, 2016. 228 с. URL: https://e.lanbook.com/book/149577.
18. Захаров В.М., Шалагин С.В., Эминов Б.Ф. Автоматные марковские модели над конечным полем: монография. Казань: Спец. фонд упр. целев. капитал. для развит. КНИТУ – КАИ, 2022. 328 с. URL: https://e.lanbook.com/book/366542.
19. Захаров В.М., Шалагин С.В., Гумиров А.И. Генератор дискретной случайной величины с заданным законом распределения в архитектуре ПЛИС/FPGA // Вестн. ДГУ. Сер. 1: Естеств. науки. 2023. Т. 38, № 3. С. 28–33. https://doi.org/10.21779/2542-0321-2023-38-3-28-33.
20. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 1. М.: Мир, 1967. 499 с.
21. Воронцова И.П. Алгоритмы изменения переходных вероятностей стохастических автоматов // Пробл. передачи информ. 1965. Т. 1, вып. 3. C. 122–126. URL: https://www.mathnet.ru/rus/ppi756.
22. Zacharov V.M., Kuznetsov S.E. Complexity of the problem of approximation of stochastic matrix by rational elements // Budach L., Bukharajev R.G., Lupanov O.B. (Eds.) Fundamentals of Computation Theory: International Conference FCT’87 Kazan, USSR, June 22–26, 1987. Proceedings. Ser.: Lecture Notes in Computer Science. V. 278. Berlin, Heidelberg: Springer, 1987. P. 483–487. https://doi.org/10.1007/3-540-18740-5_106.
23. Шалагин С.В. Решение задачи коммивояжёра методом статистических испытаний при использовании сложных цепей Маркова // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2024. Т. 166, кн. 4. C. 639–650. https://doi.org/10.26907/2541-7746.2024.4.639-650.
24. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // Автомат. и телемех. 1989. № 11. C. 3–26. URL: https://www.mathnet.ru/rus/at6463.
25. Quang T.L., Aibin M. Traveling Salesman Problem: Exact solutions vs. heuristic vs. approximation algorithms. Baeldung. 2024. URL: https://www.baeldung.com/cs/tsp-exact-solutions-vs-heuristic-vs-approximation-algorithms.
26. Альпин Ю.А., Захаров В.М. Теоретико-автоматный метод описания и моделирования случайных процессов // Вероятн. методы и киберн. 1983. Вып. 19. C. 10–16. URL: https://eudml.org/doc/69222.
27. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. А.О. Слисенко; под ред. Ю.В. Матиясевича. М.: Мир, 1979. 536 с.
Рецензия
Для цитирования:
Захаров В.М., Шалагин С.В. Реализация генератора дискретной случайной величины на основе d-арного дерева. Ученые записки Казанского университета. Серия Физико-математические науки. 2025;167(3):507-518. https://doi.org/10.26907/2541-7746.2025.3.507-518
For citation:
Zakharov V.M., Shalagin S.V. Implementing a random variable generator based on a d-ary tree. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2025;167(3):507-518. (In Russ.) https://doi.org/10.26907/2541-7746.2025.3.507-518
Просмотров:
2
Послать статью по эл. почте 