Все выпуски

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

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

Рассмотрена задача нахождения инвариантной меры неприводимой цепи Маркова с дискретным временем и конечным пространством состояний. Для такой цепи Маркова существует и единственна инвариантная мера, определенная с точностью до умножения на константу. Для каждого состояния эта инвариантная мера получена в виде суммы $n^{n−2}$ неотрицательных слагаемых, где $n$ — число состояний. Каждое слагаемое является произведением $n − 1$ условных вероятностей перехода. В стандартном представлении цепи Маркова ориентированным графом каждому состоянию ставится в соответствие вершина графа, а условной вероятности перехода — ориентированное ребро. В этом представлении каждое слагаемое в рассматриваемом выражении для инвариантной меры некоторого состояния взаимно-однозначно соответствует обратно ориентированному дереву с корнем в вершине, являющейся образом рассматриваемого состояния. Ребра ориентированы по направлению к корню. Дерево включает все вершины — образы состояний. Каждое слагаемое является произведением всех тех и только тех условных вероятностей перехода, образами которых являются ориентированные ребра соответствующего дерева.

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

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

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