2023 №4(61)

выход в свет 26.12.23

СОДЕРЖАНИЕ

  1. Монахова Э. А., Монахов О. Г. Открытие аналитических зависимостей параметров оптимальных хордальных сетей на основе анализа данных
  2. Коробов А. В., Мигов Д. А. Алгоритмы расчета надежности сети на основе декомпозиционного подхода               
  3. Вишневский В.М., Клименок В. И., Соколов А.М., Ларионов А. А. Исследование fork¬join системы с марковским входным потоком и распределением времени обслуживания фазового типа
  4. Бредихин С. В.,Щербакова Н. Г.,Юргенсон А. Н. Модели сети соавторства научного журнала. Часть 2       
  5. Бакулина М. П. Повышение эффективности сжатия изображений на основе метода RLE      
  6. Герб А. Р., Омарова Г. А. Алгоритмы разбиения графов на GPU          

Э.А. Монахова, О. Г. Монахов

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.8 + 519.7
DOI: 10.24412/2073-0667-2023-4-5-16
EDN: CSZMVY

ОТКРЫТИЕ АНАЛИТИЧЕСКИХ ЗАВИСИМОСТЕЙ ПАРАМЕТРОВ ОПТИМАЛЬНЫХ ХОРДАЛЬНЫХ СЕТЕЙ НА ОСНОВЕ АНАЛИЗА ДАННЫХ

Исследуется решение проблемы поиска общих аналитических зависимостей параметров семейств оптимальных по диаметру хордальных кольцевых сетей на основе анализа большого массива экспериментальных данных. Предложен новый подход, позволяющий автоматизировать процесс открытия аналитически описываемых семейств оптимальных сетей, задаваемых темплейтами с недоопределенными коэффициентами. При этом использованы алгоритмы дифференциальной эволюции, муравьиной колонии и исчерпывающий локальный поиск по заданным темплейтам на множестве экспериментальных данных. Предложенный подход позволил найти описания более 170 новых семейств оптимальных хордальных сетей (до этого было известно только шесть семейств). Благодаря хорошей масштабируемости и простоте маршрутизации оптимальные хордальные кольцевые сети представляют интерес как эффективные и надежные сети связи для сетей на кристалле иерархического типа, для телекоммуникационных сетевых структур и оптоволоконных сетей связи.

Ключевые слова: метаэвристический поиск, аналитические зависимости, хордальные кольцевые сети, темплейт, оптимальные графы.

Работа выполнена при финансовой поддержке бюджетным проектом ИВМиМГ СО РАН (код проекта 0251-2022-0005).

 

Библиографическая ссылка:  Монахова Э. А., Монахов О. Г. Открытие аналитических зависимостей параметров оптимальных хордальных сетей на основе анализа данных  //"Проблемы информатики", 2023, № 4, с.5-16. DOI: 10.24412/2073-0667-2023-4-5-16.


А. В. Коробов, Д.А. Мигов

Новосибирский государственный университет, 630090, Новосибирск, Россия
Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия
УДК 621.311.1+519.17
DOI: 10.24412/2073-0667-2023-4-17-28
EDX: HZLMJO

АЛГОРИТМЫ РАСЧЕТА НАДЕЖНОСТИ СЕТИ НА ОСНОВЕ ДЕКОМПОЗИЦИОННОГО ПОДХОДА

В статье рассматривается задача точного расчета структурной надежности сети с ненадежными ребрами и абсолютно надежными вершинами. В качестве показателя надежности используется вероятность связности соответствующего случайного графа. Точный расчет данного показателя — NP-трудная задача, что делает его затруднительным для сетей реальной размерности. Предлагаются модификации метода факторизации, использующегося для точного расчета, основанные на декомпозиции сети по вершинному разрезу (сечению, сепаратору), образованному двумя вершинами. Для более эффективного использования декомпозиции учитывается структурная схожесть получающихся при декомпозиции подграфов — собственно подграфов, и графов, получающихся из них склейкой разрезающих вершин. Разработано три алгоритма, в среднем ускоряющих процесс вычисления вероятности связности произвольного графа. Для сравнения предложенных алгоритмов с методом факторизации и методом факторизации с предварительной декомпозицией приводятся результаты численных экспериментов.

Ключевые слова: надежность сети, случайный граф, вероятность связности, метод факторизации, декомпозиция сети, сечение, сепаратор.

Работа выполнена в рамках проекта № 0251-2021-0005 ПФИ ИВМиМГ СО РАН

 

Библиографическая ссылка: Коробов А. В., Мигов Д. А. Алгоритмы расчета надежности сети на основе декомпозиционного подхода //"Проблемы информатики", 2023, № 4, с.17-28. DOI: 10.24412/2073-0667-2023-4-17-28.


В.М. Вишневский*, В. И. Клименок**, А.М. Соколов*, А. А. Ларионов*

*Институт проблем управления им. В. А. Трапезникова РАН, 117997, Москва, Россия
"Белорусский Государственный Институт, 220030, Минск, Беларусь
УДК 519.872
DOI: 10.24412/2073-0667-2023-4-29-56
EDN: MEXKRY

ИССЛЕДОВАНИЕ FORK-JOIN СИСТЕМЫ С МАРКОВСКИМ ВХОДНЫМ ПОТОКОМ И РАСПРЕДЕЛЕНИЕМ ВРЕМЕНИ ОБСЛУЖИВАНИЯ ФАЗОВОГО ТИПА

В настоящей работе исследуется fork-join система массового обслуживания с коррелированным марковским входным потоком. Каждая из поступающих в систему заявок разбивается на K запросов, которые попадают для обслуживания на K обслуживающих подсистем. Каждая из подсистем состоит из одного обслуживающего прибора и буфера. Время обслуживания на приборах имеет фазовое распределение. Для частного случая K = 2 получено условие стационарного режима, представлены алгоритмы для расчета стационарного распределения и стационарных показателей производительности системы. Для исследования характеристик производительности fork-join системы в общем случае K > 2 предложен подход, базирующийся на комбинации методов машинного обучения и имитационного моделирования. Приведены результаты численных примеров.

Ключевые слова: fork-join система массового обслуживания, Марковский входной поток, фазовое распределение времени обслуживания, стационарные характеристики производительности, машинное обучение.

 

 

Библиографическая ссылка: Вишневский В.М., Клименок В. И., Соколов А.М., Ларионов А. А. Исследование fork¬join системы с марковским входным потоком и распределением времени обслуживания фазового типа //"Проблемы информатики", 2023, № 4, с.29-56. DOI: 10.24412/2073-0667-2023-4-29-56.


С. В. Бредихин, Н. Г. Щербакова, А. Н. Юргенсон

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.177
DOI: 10.24412/2073-0667-2023-4-57-72
EDN: OGXEXX

МОДЕЛИ СЕТИ СОАВТОРСТВА НАУЧНОГО ЖУРНАЛА. ЧАСТЬ 2.

Анализируются две модели сети научного соавторства. Первая, построенная на бинарных отношениях, возникающих между авторами, совместно создавшими по крайней мере одну статью, представлена в виде неориентированного графа, вершины которого соответствуют авторам, а ребра устанавливают связи между ними. Вторая, учитывающая групповые отношения между авторами одной статьи, представлена в виде двудольного графа. Приведены методы конструирования обеих моделей на основе данных, извлеченных из XML-архива статей научного журнала. Измерены базовые параметры моделей, центральность ее вершин и выявлены шаблоны сотрудничества. Оценена публикационная активность организаций, указанных в аффилиации авторов. Эта работа продолжает изучение и апробацию методов анализа сетей соавторства [1, 2].

Ключевые слова: анализ данных, библеометрия, научное соавторство, двудольный граф, XML-архив, параметры сети, центральность акторов, шаблоны сотрудничества.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН (FWNM-2022-0005).

Библиографическая ссылка: Бредихин С. В., Щербакова Н. Г., Юргенсон А. Н. Модели сети соавторства научного журнала. Часть 2.//"Проблемы информатики", 2023, № 4, с.57-72. DOI: 10.24412/2073-0667-2023-4-57-72.


М. П. Бакулина

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.722
DOI: 10.24412/2073-0667-2023-4-73-77
EDX: QBTMBL

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ СЖАТИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ МЕТОДА RLE

В работе рассмотрена актуальная на сегодняшний день задача повышения эффективности сжатия цифровых изображений. Как известно, цифровое изображение, предназначенное для передачи или хранения, преобразуется в растровое. При этом для растровых изображений с большими одноцветными областями особенно эффективен метод RLE, основанный на кодировании длин серий. На основе алгоритма RLE и арифметического кода предлагается новый алгоритм кодирования длин серий, обеспечивающий более высокую по сравнению с RLE степень сжатия растровых изображений.

Ключевые слова: кодирование без потерь, растровое изображение, RLE, коэффициент сжатия.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН 0251-2022-0005.

Список литературы

1.           Тропченко А.Ю, Тропченко А. А. Методы сжатия изображений, аудиосигналов и видео. СПб:СПбГУ ИТМО, 2009.108 с.
2.           Bell Т.С., Moffat A., Witten I. Н. Compressing the Digital Library//Proc.Digital Libraries—Texas: College Station,1994.P.41-46.
3.           Jiawan Zh., Jizhou S., Zhigang S. Accelerate volume splatting by using run length encoding // Lecture Notes in Computer Science. 2003. V. 2657. P. 907-914.
4.           Witten I. H., Neal R., Cleary J. G. Arithmetic coding for data compression // Comm. ACM. 1987. V. 30, N 6. P. 520-540.
5.           Сэломон M. Сжатие данных, изображений и звука. М.: Техносфера, 2004. 368 с.

Библиографическая ссылка: Бакулина М. П. Повышение эффективности сжатия изображений на основе метода RLE //"Проблемы информатики", 2023, № 4, с.73-77. DOI: 10.24412/2073-0667-2023-4-73-77.


А. Р. Герб, Г. А. Омарова

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.17+519.61
DOI: 10.24412/2073-0667-2023-4-78-87
EDX: WBDTOQ

АЛГОРИТМЫ РАЗБИЕНИЯ ГРАФОВ НА GPU

В данной работе рассматриваются два модифицированных и реализованных на GPU алгоритма: алгоритм меток и алгоритм Ja-Be-Ja. Проведен сравнительный анализ работы на больших графах.

Ключевые слова: граф, GPU, разреженная матрица, итерации, минимальный разрез.

Работа выполнена при финансовой поддержке Министерства пауки и высшего образования Российской Федерации (код проекта: 0251-2022-0001).

Список литературы

1.           CUDA С Programming Guide 7.5. ed: NVIDIA Corporation, 2016.
2.           Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 38, 1, Article 1 (December 2011), 25 pages. DOI: https://doi.org/10.1145/2049662.2049663, 2011.
3.           Meyerhenke H., Monien B., Schamberger S. Graph partitioning and disturbed diffusion Parallel Computing. 2009. V. 35, iss. 10-11. P. 544-569.
4.           Gottesburen L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.
5.           Kumar R., Charpiat G., Thonnat M. Multiple object tracking by efficient graph partitioning // Computer Vision-ACCV 2014: 12th Asian Conference on Computer Vision, Singapore (Singapore), Nov. 1-5, 2014. Revised Selected Papers, Part IV 12. Springer International Publishing, 2015.
6.           Subelj L., Bajec M. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction // Physical Review E. 2011. V. 83, iss. 3.
7.           Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scale networks // Physical review E. 2007. V. 52, No 3.
8.           Rahimian F., et al. Ja-be-ja: A distributed algorithm for balanced graph partitioning // IEEE 7th International Conference on Self-Adaptive and Self-Organizing Systems. IEEE, 2013. (с) А. Р. Герб, Г. А. Омарова, 2023

Библиографическая ссылка: Герб А. Р., Омарова Г. А. Алгоритмы разбиения графов на GPU //"Проблемы информатики", 2023, № 4, с.78-87. D