Теоретическая и системная информатика. Рубрика в журнале - Проблемы информатики
Статья научная
We consider two well-known optimization problems: the Minimum Spanning Tree Problem and the Maximum Spanning Tree Problem. There are some extensions of these problems, for example, if we want to find extremal spanning tree with bounded maximum degree of vertices or we search for extremal spanning tree with bounded diameter from above or from below by some integer. The diameter of a tree is the number of edges in the longest simple path within the tree connecting a pair of vertices. In current work, we consider the intractable problem of finding a maximum-weight spanning tree with a given diameter in a complete undirected graph. We construct O(n2)-time approximation algorithm solving the Maximum Spanning Tree Problem with a given diameter in a complete undirected n-vertex graph, and prove the sufficient conditions of asymptotic optimality for this algorithm in the case of independent uniformly distributed UNI(0; 1)-entries. This algorithm uses the algorithm for the Minimum Spanning Tree Problem with given diameter in a complete undirected graph.
Бесплатно
Queuing model of a processing node in mobile geo monitoring network
Статья научная
The article discusses a mathematical model of the data flow received by a processing center with a limited input buffer, receiving packets of the same type from a large number of independent sources. All sources send packets with the same frequency, and the initial moment (the moment when the first packet is sent) for each source is random in the first period. There is a probability of packet loss on the network, which is the same for all sources. The model arose in connection with the task of collecting information on air pollution in cities using sensors located on city electric transport cars and serves to assess the parameters of the corresponding system: the volume of the receiving buffer depending on a given interval of sending packets or vice versa, determining such an interval with a known size of the receiving buffer. Both tasks are solved based on the acceptable level of losses due to refusal to receive packets due to the lack of space in the receiving buffer. The analytical model is built on the basis of LDT — large deviation theory. The obtained analytical estimates were compared with the results of simulation experiments and showed good quality in terms of behavior when changing the model parameters.
Бесплатно
Автоматическая генерация тестов для GFX-offload компилятора Intel
Статья научная
Компилятор инструмент, требования к надежности которого чрезвычайно высоки. Так как дефекты программного обеспечения, вызванные ошибками в компиляторе, сложно выявить, а тем более исправить без вмешательства в сам компилятор, поэтому важнейшим этаном разработки компилятора является его верификация. Из-за сложности входных данных и производимых над ними преобразований задача верификации компиляторов является весьма трудоемкой и непростой. А в случае использования оптимизирующих) компилятора еще и алгоритмически неразрешимой, поэтому можем рассмотреть поведение компилятора только на некотором ограниченном классе программ. В статье представлен подход к автоматизации создания тестов для верификации GFX-offload компилятора, основанный на генераторе, использующем грамматики для порождения синтаксически корректных исполняемых тестов. Также приведены результаты использования полученной грамматики в процессе тестирования компилятора в компании Intel.
Бесплатно
Алгоритм глобальной оптимизации, использующий деревья решений для выявления локальных экстремумов
Статья научная
В работе рассматривается решение задач многомерной глобальной оптимизации с применением деревьев решений для выявления областей притяжения локальных минимумов. Предполагается, что целевая функция задачи задана как «черный ящик» и удовлетворяет условию Липшица с априори неизвестной константой. Мы предлагаем способ выделения окрестностей локальных экстремумов целевой функции на основе анализа накопленной поисковой информации средствами машинного обучения. Это позволяет принять решение о запуске локального метода для уточнения значения функции в локальном минимуме, что может ускорить сходимость алгоритма. Выдвинутое предположение подтверждается результатами вычислительных экспериментов, демонстрирующих ускорение при решении серии тестовых задач.
Бесплатно
Алгоритмы онлайн СППР для выбора закона распределения положительно определенной случайной величины
Статья научная
Рассматривается задача создания онлайн системы поддержки принятия решений (СППР) при выборе двухнараметричеткого закона распределения непрерывной, положительно определенной случайной величины с конечным вторым моментом. Приводятся алгоритмы и сценарии работы системы. При этом основным приоритетом является ориентированный на практическое применение и критерии пользователя подход, позволяющий при минимальной информации выбирать наиболее соответствующий конкретному исследованию вид закона распределения из конечного множества заданных моделей. В основе предлагаемого алгоритма выбора закона распределения случайных величин лежит естественная факторизация пространства эмпирических характеристик математического ожидания и среднеквадратического отклонения. Для наглядного сравнения законов распределения используются плотности распределения, значения параметров и дифференциальной энтропии; графики плотностей, функций распределений и интенсивностей отказов; диаграммы рассеяния; таблица метрик. Для ранжирования законов распределения предлагаются следующие простые, интуитивно понятные для пользователя (инженера, экономиста, биолога и др.), ориентированные на решение практических задач критерии: максимизация дифференциальной энтропии распределения, максимизация соответствия эмпирическим квантилям, максимизация соответствия эмпирическим моментам третьих) и более порядков, наличие или отсутствие аналитически заданной функции восстановления, характер функции интенсивности, возможность разложения на экспоненциальные фазы. Разрабатываемая СППР может применяться в комбинации с другими существующими методами выбора закона распределения случайной величины.
Бесплатно
Алгоритмы расчета надежности сети на основе декомпозиционного подхода
Статья научная
В статье рассматривается задача точного расчета структурной надежности сети с ненадежными ребрами и абсолютно надежными вершинами. В качестве показателя надежности используется вероятность связности соответствующего случайного графа. Точный расчет данного показателя - NP-трудная задача, что делает его затруднительным для сетей реальной размерности. Предлагаются модификации метода факторизации, использующегося для точного расчета, основанные на декомпозиции сети по вершинному разрезу (сечению, сепаратору), образованному двумя вершинами. Для более эффективного использования декомпозиции учитывается структурная схожесть получающихся при декомпозиции подграфов - собственно подграфов, и графов, получающихся из них склейкой разрезающих вершин. Разработано три алгоритма, в среднем ускоряющих процесс вычисления вероятности связности произвольного графа. Для сравнения предложенных алгоритмов с методом факторизации и методом факторизации с предварительной декомпозицией приводятся результаты численных экспериментов.
Бесплатно
Анализ надежности многоуровневых сетей c ненадежными вершинами
Статья научная
Рассматриваются вопросы расчета показателей надежности многоуровневых сетей е ненадежными вершинами. Представление показатели: вероятность связности нары узлов сети, средняя арифметическая вероятность связности нары узлов сети (АРС), средний размер связного подграфа, содержащих) выделенную вершину (ASCS). Для математического описания многоуровневых сетей используется гиперсеть. Был разработан алгоритм на основе известных методов расчета сети е ненадежными элементами. В статье приведен пример работы алгоритма для показателя ASCS, который показывает возможность его использования для оптимизации расстановки датчиков мониторинга окружающей среды части транспортной сети Новосибирска.
Бесплатно
Анализ сетей с нестационарной топологией. Обзор исследований
Статья научная
Статья представляет собой обзор научных публикаций на тему моделирования и анализа беспроводных самоорганизующихся сетей, не имеющих постоянной структуры. Основные задачи функционирования таких сетей связаны со сбором информации, распространением сообщений между движущимися узлами. В статье рассматриваются различные подходы к анализу функционирования сетей, описывается применение соответствующего математического аппарата, сравниваются системы имитационного моделирования.
Бесплатно
Статья научная
В данной статье рассматривается двухфазная система массового обслуживания следующего вида. На вход системы поступает простейший входящий ноток заявок, которые последовательно проходят две фазы. Каждая фаза содержит один обслуживающий прибор и один источник повторных вызовов (ИПВ), куда отправляется заявка, если застает прибор занятым. Приборы на обеих фазах обрабатывают заявку в течение экспоненциально распределенного промежутка времени. Находясь в ИПВ, заявка через экспоненциально распределенные промежутки времени делает попытки вновь встать на обслуживание. После обслуживания на второй фазе заявка считается обработанной и покидает систему. Целью данной работы является исследование числа заявок в ИПВ на обеих фазах. Исследование проводится методом асимптотического анализа в условии большой задержки в ИПВ. Получены семиинварианты первого порядка и проведено сравнение е результатами имитационной модели.
Бесплатно
Статья научная
Предлагается подход, позволяющий получить новые зависимости параметров нелинейных изгибных и продольных волн от степени поврежденности материала. В частности, рассмотрена задача о формировании интенсивных изгибных волн стационарного профиля в рамках геометрически нелинейной модели поврежденной балки, а также задача о формировании продольных волн, где дополнительно учитываются геометрическая и физическая нелинейности. В ходе исследования, при возникновении в элементе нелинейных изгибных волн, определено наличие как периодических, так и уединенных (локализованных в пространстве) несинусоидальных волн. Показано, что амплитуды уединённых и периодических волн увеличиваются с ростом параметра поврежденности, а длина периодической и ширина уединенной волны уменьшаются с ростом рассматриваемого параметра. При возникновении в элементе нелинейных продольных волн доказано, что ширина солитона уменьшается при уменьшении параметра поврежденности, в свою очередь, скорость солитона линейно увеличивается с ростом параметра поврежденности. Определены новые зависимости волновых параметров (амплитуда, ширина, длина волны) с учетом их геометрической нелинейности от параметров поврежденности материала. Данная работа является продолжением ряда статей о новом подходе, позволяющим сформулировать математическую модель, описывающую распространение волн в элементах с учетом накопления повреждений в их материалах.
Бесплатно
Статья научная
В работе рассматривается задача переупорядочения строк и столбцов разреженной матрицы с целью уменьшения заполнения фактора при прямом решении СЛАУ. Предлагается параллельный алгоритм многоуровневого метода вложенных сечений для систем с распределенной памятью, в котором выполняется согласованное использование процессов и потоков в рамках одной вычислительной системы. Приводятся результаты вычислительных экспериментов, показывающие конкурентоспособность реализации в сравнении с аналогами по времени переупорядочения и заполнению фактора матриц. Показано, что применение полученных перестановок позволяет сократить время решения СЛАУ с помощью открытой библиотеки MUMPS на ряде тестовых задач.
Бесплатно
Статья научная
Предлагается модель распространения зависимых отказов в сети по ее структурным разрезам. Подобное может происходить в электроэнергетических сетях: отказ линии электропередачи приводит к практически мгновенному перераспределению электроэнергии на другие линии электропередачи, в первую очередь на те линии, которые входят в разрез с отказавшей. Для показателей надежности сетей в таких условиях вероятности связности сети, вероятности связности каждого потребителя с центром питания разработаны методы их точного и приближенного расчета надежности, а также метод кумулятивного уточнения границ надежности.
Бесплатно
Статья научная
В настоящей работе исследуется fork-join система массового обслуживания с коррелированным марковским входным потоком. Каждая из поступающих в систему заявок разбивается на К запросов, которые попадают для обслуживания на К обслуживающих подсистем. Каждая из подсистем состоит из одного обслуживающего прибора и буфера. Время обслуживания на приборах имеет фазовое распределение. Для частного случая К = 2 получено условие стационарного режима, представлены алгоритмы для расчета стационарного распределения и стационарных показателей производительности системы. Для исследования характеристик производительности fork-join системы в общем случае К > 2 предложен подход, базирующийся на комбинации методов машинного обучения и имитационного моделирования. Приведены результаты численных примеров.
Бесплатно
Исследование задачи Коши для одномерной системы уравнений типа Бюргерса методом слабой аппроксимации
Статья научная
Получена система уравнений тина Бюргерса. Рассмотрена задача Коши для одномерной системы уравнений тина Бюргерса возникающая в двухскоростной гидродинамике. Методом слабой аппроксимации доказано существование и единственность решения задачи Коши для одномерной системы тина Бюргерса.
Бесплатно
Кластерный анализ сети цитирования научных журналов
Статья научная
Изучается есть цитирования научных журналов, представленная взвешенным ориентированным графом. Основное внимание сфокусировано на проблемах связности и выявлении модульной структуры сети. Рассмотрены методы анализа объектов остевой структуры. На основе реальных библиографических данных, извлеченных из БД RePEc [1], построены главная связная сетевая компонента G и производные сети: коцитирования - Gcoc и библиографического сочетания - Gblb. Для этих сетей измерены локальный и взвешенный коэффициенты кластеризации. Выявление модульности рассматривается как задача идентификации структурно эквивалентных вершин соответствующих графов. С применением алгоритмов BTW, IMP, WTR и MLO выполнен кластерный анализ компоненты G и производных сетей. Результаты представлены в виде рисунка и таблиц. Сравнение результатов осуществлено с помощью индексов согласованности NMI и RAND.
Бесплатно
Кумулятивные оценки показателей структурной надежности сети и их использование
Статья научная
Рассматриваются вопросы получения и использования кумулятивных оценок структурной надежности сетей на примере k-терминальной связности, средней вероятности связности пары узлов и математического ожидания размера связного подграфа, содержащего выделенную вершину (выделенные вершины). В качестве модели рассматривается неориентированный случайный граф с надежными вершинами и ненадежными, независимо выходящими из строя ребрами, однако подход может быть использован и в случае ненадежных вершин. В основе предлагаемых методов лежат метод факторизации, полный перебор и методы редукции и декомпозиции. Получаемые значения используются для принятия однозначных решений о надежности, проектирования эволюционных алгоритмов структурной оптимизации и получения приближенных значений показателей надежности, более точных, чем полученные к моменту расчета кумулятивные оценки.
Бесплатно
Локальное и глобальное время при моделировании развивающихся систем
Статья научная
Понятия глобального и локального времени обсуждаются с точки зрения их реализации в моделях развивающихся систем. Предлагается поход к изучению таких систем в рамках событийного механизма управления в имитационных моделях. Показана корректность использования времени в сочетании с этим механизмом.
Бесплатно
Математические модели динамики регионального бизнеса
Статья научная
В работе построены и исследованы простые математические модели функционирования предприятий малого бизнеса (таких как автосервис, парикмахерские, такси, мастерские но ремонту обуви, одежды, булочные, кондитерские и т. д.) по предоставлению товаров и услуг населению региона. Предполагается, что в регионе имеются также учреждения и предприятия другого типа: например, имеющие внешнее (бюджетное) финансирование (такие как школа, больница), либо коммерческие предприятия (такие как птицеферма, мясокомбинат, завод по переработке молока), продукция и услуги которых пользуются спросом за пределами данного региона. Модели реализованы в виде одной линейной и двух нелинейных автономных систем дифференциальных уравнений второго порядка Проведено качественное исследование соответствующих динамических систем в зависимости от параметров и построены их фазовые портреты. Результаты исследования всех трех динамических систем хорошо согласуются. При довольно естественных предположениях относительно параметров существует устойчивое состояние равновесия, соответствующее устойчивому функционированию предприятий малого бизнеса. Отличие состоит лишь в том, что в нелинейных системах это устойчивое состояние равновесия появляется при достаточно большом внешнем финансировании. Указаны бифуркационные соотношения между параметрами нелинейных систем, при прохождении через которые указанное состояние равновесия теряет устойчивость, а устойчивым состоянием становится другое, соответствующее отсутствию предприятий малого бизнеса.
Бесплатно
Модели многоуровневых сетей (краткий обзор)
Статья обзорная
Ограниченность модели графа при моделировании реальных сетей давно уже стала очевидна. Как следствие, стало появляться огромное количество трудов, учитывающих многоуровневый характер реальных сетей, однако вопросы унификации моделей и терминов стали подниматься лишь в прошлом десятилетии. В данной статье представлен исторический обзор развития моделей многоуровневых сетей. Описаны несколько наиболее развитых моделей на сегодняшний момент, а также логика их построения. Приведена таблица, показывающая примеры применения рассмотренных моделей.
Бесплатно
Моделирование и сравнение различных транспортных микромоделей
Статья научная
Данная работа является продолжением цикла работ авторов. В предложенном исследовании рассматриваются транспортные модели клеточных автоматов (СА) и модель Трайбера. Проведен сравнительный анализ результатов моделирования с более ранними работами и между собой. Приведены фундаментальные диаграммы моделирования рассматриваемых моделей. Продолжены исследования, где каждый объект характеризуется индивидуальной скоростью, в отличии от ранних работ, где скорости были равны.
Бесплатно
