2022 № 4(57)
СОДЕРЖАНИЕ
Институт систем информатики им. А. П. Ершова, 630090, Новосибирск, Россия
СРАВНЕНИЕ ЯЗЫКОВЫХ И БИСИМУЛЯЦИОННЫХ ЭКВИВАЛЕНТНОСТЕЙ НЕПРЕРЫВНО-ВРЕМЕННЫХ СЕТЕЙ ПЕТРИ СО СЛАБОЙ ВРЕМЕННОЙ СТРАТЕГИЕЙ
Непрерывно-временные сети Петри (НВСП) — расширение сетей Петри, где каждый переход имеет локальные часы и временной интервал. Данная модель позволяет учитывать как функциональные (качественные), так и реально-временные (количественные) характеристики моделируемой системы. В работе рассматриваются НВСП со слабой временной стратегией (ход модельного времени не форсирует срабатывания сетевых переходов) и с промежуточной пространственной стратегией (при смене состояний сети срабатывание перехода порождает "промежуточную" разметку). В терминах данной модели определяются и исследуются языковые и бисимуляционные эквивалентности. При языковом подходе поведение системы полностью определяется множеством вариантов ее функционирования (процессов). При бисимуляцион- ном подходе учитываются точки выбора альтернативных действий моделируемой системы. Эквивалентности рассматриваются в семантиках интерливинга (процесс — последовательность действий), шага (процесс — последовательность множеств параллельных действий), частичного порядка (процесс — частично-упорядоченное множество действий) и в процессно-сетевой семантике (процесс — ациклическая бесконфликтная сеть). Анализируются взаимосвязи между данными эквивалентностями, приводится их иерархия.
Ключевые слова: непрерывно-временные сети Петри, слабая временная стратегия, промежуточная пространственная стратегия, поведенческие эквивалентности, семантика интерливаинга, шага, частичного порядка, процессно-сетевая семантика, языковая и бисимуляционная эквивалентности.
Библиографическая ссылка: Зубарев А.Ю. Сравнение языковых и бисимуляционных эквивалентностей непрерывно-временных сетей Петри со слабой временной стратегией // Проблемы информатики. 2022. № 4. С. 5-27. DOI: 10.24412/2073-0667-2022-4-5-27. EDN: BQQUXA.
Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия
ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ КОНТРОЛЬНЫХ УСТРОЙСТВ НА КАНАЛАХ В СЕТЯХ МОНИТОРИНГА
При анализе или проектировании больших сетей мониторинга часто возникает проблема выбора контрольных устройств (b-узлов) для сбора информации. После некоторой предварительной обработки или напрямую b-узлы передают информацию центральному узлу ( с-узлу) по надежным каналам. Одним из основных показателей качества таких сетей является размер территории, находящейся под надежным контролем, которую можно оценить с помощью MENC - математического ожидания количества узлов, связанных с одним специальным узлом. Гиперсети используются для представления сети. Задача вычисления MENC является NP-сложной задачей. Поэтому для оптимизации дорогостоящего размещения b-узлов был применен алгоритм имитации отжига.
Ключевые слова: надежность сети, гиперсети, оптимизация размещения контрольных устройств.
Библиографическая ссылка: Кальней А. М. Оптимизация размещения контрольных устройств на каналах в сетях мониторинга // Проблемы информатики. 2022. № 4. С. 28-38. DOI: 10.24412/2073-0667-2022-4-28-38. EDN: FBQEUC
Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия
МОЖНО ЛИ ДОБИТЬСЯ ДАЛЬНЕЙШЕГО УСКОРЕНИЯ РАСЧЕТА ХАРАКТЕРИСТИК СВЯЗНОСТИ СЛУЧАЙНОГО ГРАФА?
В докладе рассматриваются новые приемы ускорения расчета некоторых характеристик связности случайного графа (вероятность связности подмножества вершин, средняя вероятность парной связности, математическое ожидание размера связного подграфа, содержащего выделенную вершину и некоторые другие). Эти задачи имеют доказанно неполиномиальный характер сложности и, как правило, ищутся приближенные решения. Однако, с развитием вычислительной техники и разработкой параллельных алгоритмов, нахождение точных решений стало возможным для графов достаточно большой размерности для решения практических задач (до сотен вершин в случае небольшой их средней степени). Кроме того, найденные за годы решения этих задач, в том числе автором доклада, различные приемы редукции и декомпозиции позволили еще больше поднять размерность рассчитываемых графов. Точные решения необходимы также для оценки качества приближенных алгоритмов.
Предлагаются различные приемы развития известного метода факторизации, когда вместо рассмотрения одного разрешающего ребра рассматривается некоторое небольшое подмножество специальным образом выбранных ребер.
Ключевые слова: случайные графы, сетевая надёжность, алгоритмы
Библиографическая ссылка: Родионов А.С. Можно ли добиться дальнейшего ускорения расчета характеристик связности случайного графа? // Проблемы информатики. 2022. № 4. С. 39–52. DOI: 10.24412/2073-0667-2022-4-39-52. EDN: FMEYBE
Э.Х. Гимади*,**5 А. А. Штепа**
АСИМПТОТИЧЕСКИ ТОЧНЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАКСИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА С ФИКСИРОВАННЫМ ДИАМЕТРОМ В ПОЛНОМ НЕОРИЕНТИРОВАННОМ ГРАФЕ С ВХОДНЫМИ ДАННЫМИ ИЗ КЛАССА UNI(0; 1)
Мы рассматриваем труднорешаемую задачу отыскания максимального остовного дерева с фиксированным диаметром в полном неориентированном графе. Для приближенного алгоритма с трудоемкостью O(n2), решающего эту задачу, где n — количество вершин в графе, мы доказываем достаточные условия асимптотической точности в случае весов ребер графа из класса независимых, равномерно распределенных случайных величин UNI(0; 1).
Ключевые слова: максимальное остовное дерево, минимальное остовное дерево, приближенный алгоритм, вероятностный анализ, асимптотическая точность.
Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019) и при финансовой поддержке РФФИ (проект 20-31-90091).
Библиографическая ссылка: Гимади Э. Х., Штепа А. А. Асимптотически точный подход к решению задачи максимального остовного дерева с фиксированным диаметром в полном неориентированном графе с входными данными из класса UNI$(0;1) //Проблемы информатики. 2022. № 4. С. 53–62. DOI: 10.24412/2073-0667-2022-4-53-62. EDN: GMGWHI
Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия
ЭФФЕКТИВНОЕ СЖАТИЕ БЕЗ ПОТЕРЬ БОЛЬШИХ МАССИВОВ ИНФОРМАЦИОННЫХ ДАННЫХ
Рассматривается задача эффективного сжатия без потерь больших информационных массивов. Использование эффективного кодирования для таких данных позволяет не только уменьшить их физический размер и объем занимаемой ими оперативной памяти, но и увеличить скорость выполнения запросов. В данной работе предлагается алгоритм кодирования, позволяющий эффективно сжимать встречающие в массиве как числовые, так и строковые данные. Проведен эксперимент, подтверждающий увеличение степени сжатия и скорости кодирования и декодирования больших информационных массивов при использовании предложенного метода по сравнению с ранее известными методами.
Ключевые слова: кодирование без потерь, информационный массив, коэффициент сжатия, время кодирования, эффективность метода.
Библиографическая ссылка: Бакулина М. П. Эффективное сжатие без потерь больших массивов информационных данных //Проблемы информатики. 2022. № 4. С. 63-69. DOI: 10.24412/2073-0667-2022-4-63-69. EDN: HIQWPK
С. В. Бредихин, В.М. Ляпунов, Н.Г. Щербакова
Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия
ГИПЕРСЕТЬ НАУЧНОГО СОАВТОРСТВА. АНАЛИЗ ДАННЫХ БД REPEC
Рассмотрены вопросы моделирования комплексной сети научного соавторства, представленной в виде гиперграфа, в отличие от традиционного подхода к изучению этого феномена, базирующегося на построении взвешенного либо невзвешенного графа. Приведены формальные сведения, необходимые для описания множественных отношений между группами соавторов, представлены две модели анализируемого объекта. На основе реальной информации, извлеченной из библиографической базы данных, сконструирован гиперграф сети соавторства, измерены его параметры и сформулированы основные свойства. Приведен содержательный пример. В результате работы феномен научного соавторства рассмотрен с новой точки зрения.
Ключевые слова: комплексные сети, научное соавторство, гиперграф, двудольный граф, библиометрия.
Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН (0251-2021-0005).
Библиографическая ссылка: Бредихин С. В., Ляпунов В. М., Щербакова Н. Г. Гиперсеть научного соавторства. Анализ данных БД Repec // Проблемы информатики. 2022, № 4. С. 70–83. DOI: 10.24412/2073-0667-2022-4-70-83. EDN: MJFKPC
Р. Милихат*, М. Калимолдаев**, А. Абдильдаева**, М. Ocымaн***,****
КАК ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ МЕНЯЕТ МАРКЕТИНГ
В данной статье рассматривается использование искусственного интеллекта в маркетинге и его стратегическую основу реализации. Сила искусственного интеллекта (ИИ) с алгоритмами машинного обучения быстро меняют деловой мир и создает новые тенденции в маркетинге. Вызовы и возможности передовых технологий в эпоху четвертой промышленной революции. Мы утверждаем, что ИИ существенно изменит как маркетинговые стратегии, так и поведение клиентов, а также откроет новые возможности для отраслей и предприятий. Кроме того, мы описываем ключевые проблемы ИИ в маркетинге. В будущем ИИ станет новой отраслью управления бизнесом и коммерцией. Интеграция информатики и управления бизнесом станет новой тенденцией будущего. Ключевые проблемы ИИ в маркетинге.
Ключевые слова: искусственный интеллект, машинное обучение, цифровой маркетинг, маркетинговая стратегия.
Статья по докладу на XVIII Международной Азиатской школе-семинаре «Проблемы оптимизации сложных систем», Киргизия, Иссык-Куль, 20.07.2022-30.07.2022.
Библиографическая ссылка: Милихат Р., Калимолдаев М., Абдилдаева А., Отман М. Как искусственный интеллект меняет маркетинг сетей//Проблемы информатики. 2022. № 4. С. 84–106. DOI: 10.24412/2073-0667-2022-4-84-106. EDN: NSTTIT
В.Э. Малышкин*,**,***, А. В. Чмиль*, В. А. Перепелкин*,**,***
РАЗРАБОТКА ПОДСИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРИМЕНЕНИЯ АЛГОРИТМОВ ДИНАМИЧЕСКОЙ БАЛАНСИРОВКИ НАГРУЗКИ ДЛЯ СИСТЕМЫ LUNA
В научном численном моделировании на суперЭВМ часто возникает проблема статического или динамического обеспечения баланса вычислительной нагрузки. Эта проблема не имеет эффективного универсального решения, вследствие чего на практике используются различные частные и эвристические алгоритмы балансировки нагрузки на вычислительные узлы. Несмотря на то, что эта тема хорошо разработана в литературе и имеется большое количество методов, алгоритмов и программ балансировки нагрузки, их применение в каждом конкретном случае представляет собой проблему. Даже настройка параметров подходящего алгоритма балансировки нагрузки может стать непреодолимым препятствием для пользователя суперЭВМ. Это обуславливает актуальность автоматического обеспечения балансировки нагрузки на узлы как подзадача автоматического конструирования параллельных программ. Если в системе программирования имеется набор алгоритмов балансировки в виде, допускающем их автоматическое применение, то обозначенная проблема снимается с пользователя. В системе автоматического конструирования параллельных программ LuNA имеются средства для накопления и автоматического применения алгоритмов статической и динамической балансировки вычислительной нагрузки на узлы. В статье рассматривается подход, на основе которого такое накопление и применение возможно в системе LuNA.
Ключевые слова: Автоматическое конструирование параллельных программ, динамическая балансировка нагрузки, технология фрагментированного программирования, система LuNA.
Разработка алгоритмов метабалансировки выполнена в рамках государственного задания ИВМ и МГ СО РАН 0251-2021-0005. Программная реализация алгоритмов выполнена при частичной поддержке гранта МОН РК „ИРН АР09058423“.
Библиографическая ссылка: Малышкин В.Э., Чмиль А. В., Перепелкин В. А. Разработка подсистемы автоматизированного применения алгоритмов динамической балансировки нагрузки для системы LuNA //Проблемы информатики. 2022. № 4. С.107-119. DOI: 10.24412/2073-0667-2022-4-107-119. EDN: SKJWTU
В.В. Шахов*,** Х. Чен ***, А.Н. Юргенсон**, А.В. Лошкарев ****
К ВОПРОСУ ОЦЕНКИ НАДЕЖНОСТИ ЛИНЕЙНЫХ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ
Беспроводные сенсорные сети (БСС) способны осуществлять непрерывный контроль объектов критической инфраструктуры, в реальном времени обнаруживать любые аномалии и доставлять необходимые данные в центр принятия решений. Однако при этом возникает необходимость решения ряда задач, таких как рациональное размещение узлов, оптимизация энергопотребления, эффективная организация потоков данных и т.п. В работе предлагается подход к решению ряда задач, возникающих при мониторинге протяженных трубопроводов с использованием беспроводных сенсорных сетей. Для того, чтоб в полной мере воспользоваться потенциалом технологий Интернета вещей, архитектурную основу которого формируют беспроводные сенсорные сети, необходимо разработать средства оценки надежности указанных сетей. Для формализации критериев надежности разработаны соответствующие математические модели на основе Марковских процессов. Полученные результаты позволяют найти компромисс между надежностью сети мониторинга и затратами на ее развертывание и обслуживание.
Ключевые слова: беспроводные сенсорные сети, Интернет вещей, надежность сетей, мониторинг конструкций.
Исследование выполнено при финансовой поддержке РФФИ и ГФЕН в рамках научного проекта № 21-57-53011.
Статья по докладу на XVIII Международной Азиатской школе-семинаре «Проблемы оптимизации сложных систем», Киргизия, Иссык-Куль, 20.07.2022-30.07.2022.
Библиографическая ссылка: Шахов В. В., Чен X., Юргенсон А. Н., Лошкарев А. В. К вопросу оценки надежности линейных беспроводных сенсорных сетей //Проблемы информатики. 2022. № 4. С. 120–128. DOI: 10.24412/2073-0667-2022-4-120-128. EDN: XDGSRY
English
Русский