ПРОБЛЕМЫ ИНФОРМАТИКИ 4 (57) 2022 ã.
Журнал выходит ежеквартально, издается с 2008 г.
Учредитель журнала Институт вычислительной математики и математической
геофизики СО РАН при поддержке Института информационных и вычислительных технологий
МОН РК.
Редакционный совет
Председатель акад. НАН РК М.Н. Калимолдаев,
àêàä. РАН À. Ë. Àñååâ, ïðîô. Â.À. Âàñåíèí, àêàä. РАН Ñ. Í. Âàñèëüåâ, ïðîô. B. Ì.
Вишневский, àêàä. РАН Ñ. Ñ. Ãîí÷àðîâ, àêàä. РАН Í. À. Êóçíåöîâ, àêàä. РАН À. Ï. Êóëåøîâ,
ïðîô. РАН Ì. À. Ìàð÷åíêî, ïðîô. À.Ã. Ìàð÷óê, À.Þ. Ïàëüÿíîâ, ïðîô. Á. ß. Ðÿáêî, àêàä. РАН
È. À. Ñîêîëîâ, ïðîô. À. Í. Ñîòíèêîâ, ÷ë.-êîð. РАН Þ.À. Ôëåðîâ.
Редколлегия
Главный редактор проф. В. Э. Малышкин,
Ä.Æ. Àõìåä-Çàêè, À.Ã. Вострецов, Á. Ñ. Гольдштейн, Â.È. Ãóæîâ, Þ.À. Загорулько,
C. Ä. Каракозов, Ì.Ì. Êàðèìîâ, Â. Í. Êàñüÿíîâ, Î. Â. Êèáèñ, Â. Â. Êîðíååâ, È. Â. Êîòåíêî,
È.Ì. Êóëèêîâ, Ò. Ï. Ëþáèìîâà, À. Í. Ëÿõîâ, Â. Â. Окольнишников, Á. Â. Ïîëëåð,
À. Ñ. Родионов (çàì. ãë. ðåäàêòîðà), Ì. À. Ñîíüêèí, Â. Â. Шахов (çàì. ãë. ðåäàêòîðà),
Ì. Ñ. Хайретдинов, È.Ã. ×åðíûõ, Moonseong Kim (Korea), V. D. Nguyen (Vietnam), Michele
Pagano (Italy).
Редакция: отв. секретарь М. С. Делидович, системный администратор В. А. Перепелкин,
верстка Д. В. Лазуткин, логист Л. В. Трофимова.
Адрес ðåäàêöèè, èçäàòåëÿ: 630090, ã. Новосибирск, ïðîñï. Академика Лаврентьева, ä. 6,
ИВМиМГ СОРАН
òåë. (383) 330-96-43; e-mail: problem-info@sscc.ru, http://www.problem-info.sscc.ru.
Журнал зарегистрирован в Федеральной службе по надзору в сфере массовых коммуникаций,
связи и охраны культурного íàñëåäèÿ. Свидетельство ПИ ÔÑ77-32088 от 27 мая 2008 ã.
Журнал распространяется по подписке. Оформление подписки на сайте ¾Объединенного
каталога ½Ïðåññà Ðîññèè“¿ https://www.pressa-rf.ru/cat/1/edition/y_e69980/, подписной
индекс 69980, и через интернет-магазин ¾Пресса по подписке¿
https://www.akc.ru/itm/problemy_i-informatiki/. Цена свободная. Журнал
распространяется на территории России.
Журнал включен в Перечень ведущих рецензируемых научных журналов,
рекомендованных для публикаций Высшей аттестационной комиссией.
Все права авторов сохранены. Использование материалов журнала возможно только
с разрешения редакции и авторов.
Отпечатано в типографии ¾АЛЕКСПРЕСС¿ ИП Малыгин Алексей Михайлович.
Àäðåñ: 630090, Новосибирск, ïð-ò Академика Лаврентьева, 6/1, îô. 104, òåë. +7 (383) 217-43-46.
Формат 60 Ч 84 1/8. Óñë. ïå÷. ë. 10,23. Печать îôñåòíàÿ.
Тираж 50 ýêç. Заказ 800. Подписано в печать 15.12.2022 ã. Выход в свет 26.12.2022 ã.
© Институт вычислительной математики и математической геофизики СО РАН, 2022
© Институт информационных и вычислительных технологий МОН РК, 2022
Стр.2
JOURNAL PROBLEMS OF INFORMATICS . No. 4 (57) 2022
Publisher: Institute of Computational Mathematics and Mathematical Geophysics of Siberian Branch
of Russian Academy of Sciences with the support of the Institute of Information and Computing
Technologies of the Ministry of Education of the Republic of Kazakhstan.
Editorial Council
Chairman Academician of the National Academy of Sciences of the Republic of Kazakhstan
M. N. Kalimoldayev
Full Member of the RAS A. L. Aseev, Professor V. A. Vasenin, Full Member of RAS C. N. Vassilyev,
Professor V.M. Vishnevsky, Full Member of RAS S. S. Goncharov, Full Member of RAS
N. A. Kuznetsov, Full Member of RAS A.P. Kuleshov, Professor of RAS M. A. Marchenko, Professor
A. G. Marchuk, A. YU. Palyanov, Professor B. Y. Ryabko, Full Member of RAS I. A. Sokolov,
Professor A.N. Sotnikov, Corr. Member RAS Y. A. Flerov.
Editorial board
The Editor-in-Chief Professor V. E. Malyshkin
Associate Editors-in-Chief: A. S. Rodionov, V. V. Shakhov
D. Zh. Akhmed-Zaki, À. G. Vostretsov, B. S. Goldstein, V. I. Guzhov, Y. A. Zagorulko, S. D.
Karakozov, Ì.Ì. Karimov, V. N. Kasyanov, Î. V. Kibis, V. V. Korneev, I. V. Kotenko, I. M. Kulikov,
T.P. Lyubimova, A. I. Lyakhov, V. V. Okolnishnikov, B. V. Poller, M. A. Sonkin, Ì. S. Khairetdinov,
I. G. Chernykh, Moonseong Kim (Korea), Van Duc Nguyen (Vietnam), Michele Pagano (Italy).
Editorial sta : Managing Editor M. S. Delidovich, System Administrator V. A. Perepelkin,
Maker-up D. V. Lazutkin, Logistician L. V. Tro mova.
Address of the editorial o ce: 630090, pr. Lavrentieva, 6, Novosibirsk, Russia, Institute of
Computational Mathematics and Mathematical Geophysics of SB RAS.
Phone: +7 (383) 330-96-43; e-mail: problem-info@sscc.ru, http://www.problem-info.sscc.ru.
The journal has been registered in accordance with Legislation of the Russian Federation. Certi cate
of Mass Media Registration: ПИ ÔÑ77-32088, of 27 May, 2008, ISSN 2073-0667. The journal is
distributed in Russia.
The journal Problems of Informatics is in the List of Peer-Reviewed Scienti c Journals for
publication of scienti c results of Ph.D. and Dr. of Sci.
All rights reserved. The journal contents may only be used by the permission of editors and authors.
© Institute of Computational Mathematics and Mathematical Geophysics of Siberian Branch of
Russian Academy of Sciences, 2022
© Institute of Information and Computing Technologies of the Ministry of Education of the
Republic of Kazakhstan, 2022
Стр.3
СОДЕРЖАНИЕ
Теоретическая и системная информатика
Зубарев А.Ю. Сравнение языковых и бисимуляционных эквивалентностей непрерывновременных
сетей Петри со слабой временной стратегией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Кальней А. М. Оптимизация размещения контрольных устройств на каналах в сетях
мониторинга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Родионов А. С. Можно ли добиться дальнейшего ускорения расчета характеристик связности
случайного ãðàôà? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39
Гимади Э. Х., Штепа А. А. Асимптотически точный подход к решению задачи максимального
остовного дерева с фиксированным диаметром в полном неориентированном
графе с входными данными из класса UNI(0; 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Прикладные информационные технологии
Бакулина М.П. Эффективное сжатие без потерь больших массивов информационных
данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Бредихин С. В., Ляпунов В. М., Щербакова Н.Г. Гиперсеть научного соавторства. Анализ
данных БД Repec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Милихат Р., Калимолдаев М., Абдилдаева А., Отман М. Как искусственный интеллект
меняет маркетинг . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Малышкин В. Э., Перепелкин В. А., Чмиль А. В. Разработка подсистемы автоматизированного
применения алгоритмов динамической балансировки нагрузки для системы
LuNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Шахов Â. Â., Чен Õ., Юргенсон À. Í., Лошкарев À. Â. К вопросу оценки надежности
линейных беспроводных сенсорных сетей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Алфавитный указатель авторов за 2022 год . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Правила представления и подготовки рукописей для публикации
в журнале ½ÏÐÎÁËÅÌÛ ИНФОРМАТИКИ“ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Примечание. В 3 журнала за 2022 ã.:
В тексте статьи Беляева Н. А. ¾Автоматическое конструирование высокопроизводительных параллельных
программ для задач разреженной линейной алгебры в системе LuNA¿ (DOI: 10.24412/20730667-2022-3-46-60)
на стр. 46 пропущена сноска следующего содержания: ¾Исследования выполнены в
рамках государственного задания ИВМиМГ СО РАН 0251-2021-0005¿.
В тексте статьи Власенко А. Ю., Мичурова М. А. и Мустафина Д. Э. ¾Автоматизация отладки и
балансировки нагрузки во фрагментированных программах¿ (DOI: 10.24412/2073-0667-2022-3-61-76) на
стр. 61 пропущена сноска следующего содержания: ¾Исследования выполнены в рамках государственного
задания ИВМиМГ СО РАН 0251-2021-0005¿.
ПРОБЛЕМЫ ИНФОРМАТИКИ
4 (57) 2022 ã.
Стр.4
CONTENTS
Theoretical informatics
Zubarev A. Y. Comparison of trace and bisimulation equivalences on time Petri nets with weak
time policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Kalney A. M. Optimizing Placement of Control Devices on Channels in Monitoring
Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Rodionov A. S. Is it possible to achieve further acceleration of the calculation of the connectivity
characteristics of a random graph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39
Gimadi E. Kh., Shtepa A. A. Asymptotically Optimal Approach for the Maximum Spanning
Tree Problem with Given Diameter in a Complete Undirected Graph on UNI(0; 1)-Entries 53
Applied information technologies
Bakulina M. P. E cient lossless compression of large information arrays . . . . . . . . . . . . . . . . . .63
Bredikhin S. V., Lyapunov V. M., Scherbakova N. G. The hyper-network of scienti c coauthorship.
DB RePEc data analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Milihat R., Kalimoldaev M., Abdildaeva A., Othman M. How Arti cial Intelligence is
Revolutionizing the Marketing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Malyshkin V. E., Perepelkin V. A., Chmil A. V. Dynamic Load Balancing Algorithms
Application Automation Subsystem Development for LuNA System . . . . . . . . . . . . . . . . . . . . . 107
Shakhov V. V., Chen H., Yurgenson A. N., Loshkarev A. V. On reliability of linear wireless
sensor networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Authors by alphabetical order published in 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Rules of presentation and preparation of manuscripts o ered for publication . . . . . . . . . . . . . 132
PROBLEMS OF INFORMATICS
N 4 (57) 2022
Стр.5