
|

«Информатика и ее применения» (Том 19, Выпуск 1, 2025)
Оглавление | Об авторах
Универсальные конструкции в алгебраической спецификации распределенных систем
- С. П. Ковалёв Институт проблем управления им. В. А. Трапезникова Российской академии наук, kovalyov@sibnet.ru
Аннотация: Работа посвящена развитию предложенного ранее метода обобщенной алгебраической спецификации распределенных систем на базе новой теоретико-категорной конструкции графалгебры. Основой графалгебраической спецификации служит ориентированный мультиграф, ребра которого представляют вычислительные операции, выполняемые в узлах системы, а вершины задают порты обмена данными между узлами. Таким способом размещение операций по узлам системы задается явно. В явной форме также целесообразно описывать на языке графалгебр процедуры конструирования систем, приводящие к целевому размещению. С этой целью в работе впервые даны определения и доказаны ключевые свойства конструкций подграфалгебры, фактор-графалгебры и бисимуляции графалгебр. Предложены способы построения пределов и копределов подходящих диаграмм графалгебр. Теоретические результаты проиллюстрированы примером вычисления предела в категории глубоких нейронных сетей.
Ключевые слова: алгебраическая спецификация; распределенная система; универсальная алгебра; теория категорий; графалгебра; подалгебра; бисимуляция
Об оптимизации сетевой структуры коммуникации в мультиагентных системах
- Н. С. Васильев Московский государственный технический университет им. Н. Э. Баумана, nik8519@yandex.ru
Аннотация: Для формализации и исследования больших мультиагентных систем (МС), представленных в форме игровой модели, применяется моноидальная категория бинарных отношений. Решению проблемы нахождения оптимальной коммуникационной сети способствует композициональность рассматриваемой задачи. Сетевая структура должна складываться в процессе рационального разрешения конфликта интересов на основе принципов равновесия и эффективности и служить одной из целей применения выбираемых игроками стратегий. Предложен метод построения этой структуры, основанный на использовании семейства естественных отношений, позволяющих сравнивать предпочтения участников операции. Выбор сетевой структуры игры моделируется процессом формирования эффективных коалиций агентов, в которых происходит оптимальная коммуникация. Изложенный подход может служить основой технологии создания больших МС, основанной на применении компьютерной алгебры теории категорий и матричной алгебры бинарных отношений.
Ключевые слова: моноидальная категория; отношение предпочтения; сеть коммуникации; сетевая структура игры; эффективная коалиция; характеристическое отношение; результирующее отношение; композициональность
Гарантированные оценки показателей работоспособности многопользовательской сети при повреждениях
- Ю. Е. Малашенко Федеральный исследовательский центр "Информатика и управление" Российской академии наук, malash09@ccas.ru
- И. А. Назарова Федеральный исследовательский центр "Информатика и управление" Российской академии наук, irina-nazar@yandex.ru
Аннотация: В рамках вычислительных экспериментов исследуются показатели работоспособности многопользовательской сети связи при разрушении отдельных узлов. При моделировании создаются массивы данных о маршрутах передачи максимальных межузловых потоков. Изучаются изменения загрузки ребер и транзитных потоков через неповрежденные сетевые узлы. Определяются относительные дифференцированные показатели, характеризующие зависимость передаваемых потоков от уменьшения пропускной способности сети при выходе из строя каждого узла. Формируются многокритериальные гарантированные оценки максимально возможных отклонений от показателей функционирования сети в стационарном режиме. Проводится сравнительный анализ результатов, полученных при использовании двух схем маршрутизации для равных межузловых потоков. Приводятся итоговые диаграммы для сетей с различными структурными особенностями.
Ключевые слова: потоковая модель сети связи; гарантированные оценки при повреждении узлов
Фильтрация состояний и параметров специальных марковских скачкообразных процессов по косвенным наблюдениям без шума
- А. В. Борисов Федеральный исследовательский центр "Информатика и управление" Российской академии наук, aborisov@frccsc.ru
Аннотация: Исследована задача оптимальной фильтрации состояний некоторого класса стохастических дифференциальных систем (СДС) наблюдения. Оцениваемое состояние включает в себя две блочные компоненты. Первая представляет собой марковский скачкообразный процесс (МСП) с конечным множеством состояний. Вторая изменяется синхронно с первой и при фиксированной первой компоненте образует последовательность независимых векторов. Доступная статистическая информация включает в себя известные функции состояния, наблюдаемые без шумов. Задача заключается в построении условного распределения состояния системы по имеющимся наблюдениям. В системах наблюдения с вырожденными шумами невозможно применение стандартных приемов решения задачи фильтрации, сводящих с помощью подходящей гирсановской замены меры доступные наблюдения к совокупности винеровских и пуассоновских процессов. Условное распределение состояния удается представить с помощью рекуррентно связанной последовательности обыкновенных дифференциальных и разностных уравнений.
Ключевые слова: марковский скачкообразный процесс; стохастическая дифференциальная система наблюдения; косвенные наблюдения без шума; мартингальное разложение; регулярная версия условного распределения
Анализ использования доплеровских измерений для идентификации параметров движения по наблюдениям со случайными запаздываниями
- А. В. Босов Федеральный исследовательский центр "Информатика и управление" Российской академии наук, ABosov@frccsc.ru
Аннотация: Для постановки задачи позиционирования движущегося объекта использована модель стохастической динамической системы наблюдения, учитывающая случайные временные задержки между поступившим наблюдением и фактическим состоянием объекта и наличие неизвестных параметров движения. Для такой модели на примере подводного аппарата (ПА) анализируются варианты формирования наблюдений. В первом используются только стационарные акустические сенсоры, позволяющие измерять только угловые координаты. Во втором варианте углы дополняются измерениями скорости, выполненными как на борту движущегося объекта, так и внешними наблюдателями. Каждая модель используется в двух видах: в предположении наличия полной априорной информации о параметрах движения ПА и при отсутствии данных о значениях части параметров. В последнем варианте задача позиционирования решается совместно с задачей идентификации неизвестных параметров движения. Модели и результаты их экспериментального применения сравниваются с целью качественной оценки эффективности использования измерений скорости. Для этого к задаче применен условно-минимаксный нелинейный фильтр (УМНФ). Сравнительный анализ моделей системы наблюдения выполнен в рамках масштабного вычислительного эксперимента.
Ключевые слова: нелинейная стохастическая система наблюдения; байесовская идентификация параметров; наблюдения со случайными временными запаздываниями; условно-минимаксный нелинейный фильтр; позиционирование; акустические сенсоры; эффект Доплера
Методы нормальной условно-оптимальной фильтрации для наблюдаемых неявных стохастических систем
- И. Н. Синицын Федеральный исследовательский центр "Информатика и управление" Российской академии наук, sinitsin@dol.ru
Аннотация: Рассмотрены методы синтеза нелинейных нормальных условно-оптимальных фильтров (НУОФ) по среднеквадратичному критерию (т. е. в смысле В. С. Пугачёва) для обработки информации во взаимосвязанных наблюдаемых непрерывных и дискретных гауссовских и негауссовских неявных стохастических систем (СтС), приводимых к явным. Представлены уравнения наблюдаемых непрерывных и дискретных явных и неявных гауссовских и негауссовских СтС, методы приведения неявных гладких и разрывных СтС к явным. Для взаимосвязанных неявных объектовых и явных систем наблюдения разработаны методы синтеза НУОФ, основанные на решении методом нормальной аппроксимации (МНА) совместных приведенных уравнений объекта, системы наблюдения и уравнений линейных и нелинейных условно-оптимальных фильтров (УОФ) для гауссовских и негауссовских СтС. В качестве дискретных неявных СтС, приводимых к дискретным, рассмотрены нелинейные регрессионные и авторегрессионные уравнения. Предложены обобщения методов синтеза УОФ для сложных неявных непрерывных и дискретных СтС.
Ключевые слова: метод нормальной аппроксимации распределения; неявная стохастическая система; нормальный условно-оптимальный фильтр (НУОФ); стохастический процесс (СтП); условно-оптимальный фильтр Пугачёва
Об одной системе обслуживания с коррелированным входящим потоком
- А. К. Берговин Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова, aIexey.bergovin@gmaiI.com
- А. М. Рязанов Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова, alryaz@asvk.cs.msu.ru
- В. Г. Ушаков Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова; Федеральный исследовательский центр "Информатика и управление" Российской академии наук, vgushakov@maiI.ru
Аннотация: Изучена однолинейная система массового обслуживания с бесконечным числом мест для ожидания, произвольным распределением времени обслуживания и пуассоновским входящим потоком со случайной интенсивностью, которая подчиняется авторегрессионной зависимости первого порядка. Найдено распределение количества пакетов, а также виртуальное время пребывания пакета в системе в нестационарном режиме. Найдены стационарные распределения и их вероятностные характеристики: среднее и дисперсия. Графически проиллюстрировано среднее время задержки передачи пакета данных в стационарном режиме в разных предположениях на распределение времени обслуживания пакетов и на характеристики входящего потока, проведено сравнение с классической системой обслуживания M|G|1.
Ключевые слова: случайная интенсивность; длина очереди; время ожидания; пассивный анализ трафика; качество обслуживания
Сравнительный анализ тестов стабильности системы массового обслуживания
- М. П. Кривенко Федеральный исследовательский центр "Информатика и управление" Российской академии наук, mkrivenko@ipiran.ru
Аннотация: Рассматриваются два типа процедур статистического контроля стабильности системы массового обслуживания (СМО): сравнение интенсивностей входного и выходного потоков и обнаружение нестационарности последовательности времен пребывания заявок в системе. В первом случае речь идет о методах обработки согласованных пар, а во втором - о тестах единичного корня для моделей авторегрессии первого порядка. Уточняется процедура сбора и фиксации исходных данных, так как в одном случае она привязана к моментам времени, а во втором - к номерам событий. Используемые тесты стабильности двух типов относятся к слабым критериям значимости, для которых базовые нулевые гипотезы различны и дополняют друг друга. Это сразу же проявляется при их сравнении: результаты получаются лучше, когда предположения соответствующих нулевых гипотез выполняются. Для учета подобных особенностей строится составной критерий на основе консенсуса и рандомизации, что приводит к увеличению числа безошибочных решений. Дальнейшего повышения качества принимаемых решений удается добиться в процедуре сравнения критических уровней значимости отдельных критериев. Результаты были получены методом статистических испытаний и для конкретного типа СМО, функционирующей при простейшем пуассоновском входном потоке. Нарушение этого предположения может стать дестабилизирующим фактором, для описания чего была введена модель пакетного пуассоновского процесса. Для него, варьируя интенсивность поступления пакетов и средний размер пакета, можно формировать входные потоки различной структуры с одной и той же интенсивностью. Было выяснено: с ростом размера пакета увеличивается число порождаемых СМО реализаций, демонстрирующих нестабильность; размер пакета может оказаться источником существенного роста времени пребывания заявок в системе по сравнению с вариантом единичных пакетов; применение тестов единичного корня может привести к ошибочным выводам относительно нестабильности.
Ключевые слова: СМО (система массового обслуживания); стабильность выборочной траектории; критерии для согласованных пар; тесты единичного корня; тесты Дики-Фуллера; составнойтест стабильности; пакетный пуассоновский процесс; размер пакета как дестабилизирующий фактор
Perturbation and truncation bounds for one class of Markov processes of birth-and-death type with catastrophes
- I. A. Usov Department of Applied Mathematics, Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation
- Y. A. Satin Department of Applied Mathematics, Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation, Moscow Center for Fundamental and Applied Mathematics, M.V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation
- A. I. Zeifman Department of Applied Mathematics, Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
- V. Yu. Korolev Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation, Moscow Center for Fundamental and Applied Mathematics, M.V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation, Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation
Некоторые оценки для одного класса марковских процессов типа рождения и гибели с двумя типами катастроф
- И. А. Усов Вологодский государственный университет, iusov35@yandex.ru
- Я. А. Сатин Вологодский государственный университет, yacovi@mail.ru
- А. И. Зейфман Вологодский государственный университет, Федеральный исследовательский центр "Информатика и управление" Российской академии наук, a_zeifman@mail.ru
- В. Ю. Королев Федеральный исследовательский центр "Информатика и управление" Российской академии наук, Московский центр фундаментальной и прикладной математики, Московский государственный университет имени М. В. Ломоносова, vkorolev@cs.msu.su
Аннотация: Рассматривается класс неоднородных марковских цепей с непрерывным временем со счетным множеством состояний типа рождения и гибели. В цепи возможны два типа дополнительных переходов, переводящих ее либо в граничное состояние, либо в соседнее с ним. Предполагается, что с ростом номера состояния интенсивности рождения (гибели) монотонно убывают (возрастают). Впервые получены оценки устойчивости с использованием специальных весовых норм, связанных с полной вариацией.
В той же норме построена оценка погрешности аппроксимации исходной цепи процессом с конечным числом состояний. Наконец, для случая, когда все интенсивности зависят от состояния цепи, с помощью метода логарифмической нормы представлены некоторые условия, гарантирующие (слабую) эргодичность в норме полной вариации. Результаты сопровождаются иллюстративными примерами.
Ключевые слова: система массового обслуживания; процесс рождения и гибели; катастрофы; аппроксимации; устойчивость
Решение обратных статистических задач с помощью методов пороговой обработки, допускающих построение несмещенной оценки среднеквадратичного риска
- О. В. Шестаков Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики; Федеральный исследовательский центр "Информатика и управление" Российской академии наук; Московский центр фундаментальной и прикладной математики, oshestakov@cs.msu.ru
Аннотация: Методы вейвлет-анализа в сочетании с процедурами пороговой обработки широко используются в задачах оценивания функции сигнала по зашумленным данным. Их популярность объясняется адаптивностью к локальным особенностям исследуемых функций и высокой скоростью алгоритмов обработки. Плодотворным данный подход оказался также при обращении линейных однородных операторов, возникающих в некоторых задачах обработки сигналов и изображений. Наиболее распространенными видами пороговой обработки стали жесткая и мягкая пороговая обработка. Однако при использовании жесткой пороговой обработки получаются оценки с большой дисперсией, а мягкая пороговая обработка приводит к появлению дополнительного смещения. В попытке избавиться от этих недостатков в последние годы были предложены различные альтернативные виды пороговой обработки. В данной работе рассматривается класс пороговых функций, допускающих построение несмещенной оценки среднеквадратичного риска. Эта оценка позволяет анализировать погрешность методов подавления шума. Исследование свойств несмещенной оценки риска представляет собой важную практическую задачу, поскольку позволяет оценить качество как самих методов, так и используемого оборудования. В работе обсуждаются стратегии выбора пороговых значений и приводятся утверждения об асимптотической нормальности и сильной состоятельности оценки риска.
Ключевые слова: пороговая обработка; линейный однородный оператор; несмещенная оценка риска
Метризация дискретных топологических пространств в контексте теории решеток. Часть 1. О нормальности пространств
- И. Ю. Торшин Федеральный исследовательский центр "Информатика и управление" Российской академии наук, tiy135@yahoo.com
Аннотация: Фундаментальной проблемой в машинном обучении и в других современных методах анализа данных стало решение вопроса о порождении метрических функций расстояний (метрик), которые были бы адекватны исследуемым прикладным задачам. В работе представлены результаты систематического анализа возможностей метризации дискретных топологических пространств с использованием понятий теории решеток. Доказана теорема о регулярности и нормальности топологических пространств, возникающих в задачах распознавания, классификации и числового прогнозирования. Регулярность (по Ю. И. Журавлёву) множества прецедентов гарантирует нормальность топологического пространства (аксиома отделимости T4) и, следовательно, метризуемость этого пространства. Планируется подготовить отдельную статью с практическими приложениями следствий теоремы о регулярности и нормальности, которые позволяют систематизировать поиск проблемно-ориентированных метрик, наиболее приемлемых для той или иной прикладной задачи.
Ключевые слова: топологический анализ данных; теория решеток; алгебраический подход Ю. И. Журавлёва и К. В. Рудакова; аксиомы отделимости
|

|