All issues

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

Problem of exploration finite undirected graphs by a collective of agents is considered in this work. Two agents-researchers simultaneously move on graph, they read and change marks of graph elements, transfer the information to the agent-experimenter (it builds explored graph representation). It was constructed an algorithm linear (from amount of the graph’s nodes) time complexity, quadratic space complexity and communication complexity, that is equal to O(n²·log(n)). Two agents (which move on graph) need two different colors (in total three colors) for graph exploration. An algorithm is based on depth-first traversal method.

Представлен итерационный алгоритм, который численно решает нелинейные одномерные несингулярные интегральные уравнения Фредгольма и Вольтерры второго рода типа Урысона. Показано, что метод последовательных приближений Пикара может быть использован при численном решении такого типа уравнений. Сходимость числовой схемы гарантируется теоремами о неподвижной точке. При этом квадратурный алгоритм основан на явной форме встроенного правила Рунге–Кутты пятого порядка с адаптивным контролем размера шага. Возможность контроля локальных ошибок квадратур позволяет создавать очень точные автоматические числовые схемы и значительно уменьшить основной недостаток итераций Пикара, а именно чрезвычайно большое количество вычислений с увеличением глубины рекурсии. Наш алгоритм организован так, что по сравнению с большинством подходов нелинейность интегральных уравнений не вызывает каких-либо дополнительных вычислительных трудностей, его очень просто применять и реализовывать в программе. Наш алгоритм демонстрирует практически важные черты универсальности. Во-первых, следует подчеркнуть, что метод столь же прост в применении к нелинейным, как и к линейным уравнениям типа Фредгольма и Вольтерры. Во-вторых, алгоритм снабжен правилами останова, по которым вычисления могут в значительной степени контролироваться автоматически. Представлен компактный C++-код описанного алгоритма. Реализация нашей программы является самодостаточной: она не требует никаких предварительных вычислений, никаких внешних функций и библиотек и не требует дополнительной памяти. Приведены числовые примеры, показывающие применимость, эффективность, надежность и точность предложенного подхода.

We present the iterative algorithm that solves numerically both Urysohn type Fredholm and Volterra nonlinear one-dimensional nonsingular integral equations of the second kind to a specified, modest user-defined accuracy. The algorithm is based on descending recursive sequence of quadratures. Convergence of numerical scheme is guaranteed by fixed-point theorems. Picard’s method of integrating successive approximations is of great importance for the existence theory of integral equations but surprisingly very little appears on numerical algorithms for its direct implementation in the literature. We show that successive approximations method can be readily employed in numerical solution of integral equations. By that the quadrature algorithm is thoroughly designed. It is based on the explicit form of fifth-order embedded Runge–Kutta rule with adaptive step-size self-control. Since local error estimates may be cheaply obtained, continuous monitoring of the quadrature makes it possible to create very accurate automatic numerical schemes and to reduce considerably the main drawback of Picard iterations namely the extremely large amount of computations with increasing recursion depth. Our algorithm is organized so that as compared to most approaches the nonlinearity of integral equations does not induce any additional computational difficulties, it is very simple to apply and to make a program realization. Our algorithm exhibits some features of universality. First, it should be stressed that the method is as easy to apply to nonlinear as to linear equations of both Fredholm and Volterra kind. Second, the algorithm is equipped by stopping rules by which the calculations may to considerable extent be controlled automatically. A compact C++-code of described algorithm is presented. Our program realization is self-consistent: it demands no preliminary calculations, no external libraries and no additional memory is needed. Numerical examples are provided to show applicability, efficiency, robustness and accuracy of our approach.

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

In this work, we use analytical and numerical methods to consider the problem of the structure and dynamics of coupled localized nonlinear waves in the sine-Gordon model with three identical attractive extended “impurities”, which are modeled by spatial inhomogeneity of the periodic potential. Two possible types of coupled nonlinear localized waves are found: breather and soliton. The influence of system parameters and initial conditions on the structure, amplitude, and frequency of localized waves was analyzed. Associated oscillations of localized waves of the breather type as in the case of point impurities, are the sum of three harmonic oscillations: in-phase, in-phase-antiphase and antiphase type. Frequency analysis of impurity-localized waves that were obtained during a numerical experiment was performed using discrete Fourier transform. To analyze localized breather-type waves, the numerical finite difference method was used. To carry out a qualitative analysis of the obtained numerical results, the problem was solved analytically for the case of small amplitudes of oscillations localized on impurities. It is shown that, for certain impurity parameters (depth and width), it is possible to obtain localized solitontype waves. The ranges of values of the system parameters in which localized waves of a certain type exist, as well as the region of transition from breather to soliton types of oscillations, have been found. The values of the depth and width of the impurity at which a transition from the breather to the soliton type of localized oscillations is observed were determined. Various scenarios of soliton-type oscillations with negative and positive amplitude values for all three impurities, as well as mixed cases, were obtained and considered. It is shown that in the case when the distance between impurities much less than one, there is no transition region where which the nascent breather, after losing energy through radiation, transforms into a soliton. It is shown that the considered model can be used, for example, to describe the dynamics of magnetization waves in multilayer magnets.

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

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

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

The study presented in the paper is devoted to the problem of finite graph exploration using a collective of agents. Finite non-oriented graphs without loops and multiple edges are considered in this paper. The collective of agents consists of two agents-researchers, who have a finite memory independent of the number of nodes of the graph studied by them and use two colors each (three colors are used in the aggregate) and one agentexperimental, who has a finite, unlimitedly growing internal memory. Agents-researches can simultaneously traverse the graph, read and change labels of graph elements, and also transmit the necessary information to a third agent — the agent-experimenter. An agent-experimenter is a non-moving agent in whose memory the result of the functioning of agents-researchers at each step is recorded and, also, a representation of the investigated graph (initially unknown to agents) is gradually built up with a list of edges and a list of nodes.

The work includes detail describes of the operating modes of agents-researchers with an indication of the priority of their activation. The commands exchanged between agents-researchers and an agent-experimenter during the execution of procedures are considered. Problematic situations arising in the work of agentsresearchers are also studied in detail, for example, staining a white vertex, when two agents simultaneously fall into the same node, or marking and examining the isthmus (edges connecting subgraphs examined by different agents-researchers), etc. The full algorithm of the agent-experimenter is presented with a detailed description of the processing of messages received from agents-researchers, on the basis of which a representation of the studied graph is built. In addition, a complete analysis of the time, space, and communication complexities of the constructed algorithm was performed.

The presented graph exploration algorithm has a quadratic (with respect to the number of nodes of the studied graph) time complexity, quadratic space complexity, and quadratic communication complexity. The graph exploration algorithm is based on the depth-first traversal method.

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

This article is dedicated to numerical algorithms for solving problems of ignition and unsteady combustion of gunpowder on a uniform computational grid, and a grid with concentration near the surface of the combustion at a constant and adapts the depth under the heated layer of computational domain. The analysis of efficiency of a numerical grid.

В настоящий момент значительно возросла глубина работ по разведке кимберлитовых тел и рудных месторождений. Традиционные геологические методы поиска оказались неэффективными. Практически единственным прямым методом поиска является бурение системы скважин до глубин, которые обеспечивают доступ к вмещающим породам. Из-за высокой стоимости бурения возросла роль межскважинных методов. Они позволяют увеличить среднее расстояние между скважинами без существенного снижения вероятности пропуска кимберлитового или рудного тела. Метод радиоволнового просвечивания особенно эффективен при поиске объектов, отличающихся высокой контрастностью электропроводящих свойств. Физическую основу метода составляет зависимость распространения электромагнитной волны от проводящих свойств среды распространения. Источником и приемником электромагнитного излучения является электрический диполь. При измерениях они размещаются в соседних скважинах. Расстояние между источником и приемником известно. Поэтому, измерив величину уменьшения амплитуды электромагнитной волны при ее распространении между скважинами, можно оценить коэффициент поглощения среды. Породе с низким электрическим сопротивлением соответствует высокое поглощение радиоволн. Поэтому данные межскважинных измерений позволяют оценить эффективное электрическое сопротивление породы. Обычно источник и приемник синхронно погружаются в соседние скважины. Измерение величины амплитуды электрического поля в приемнике позволяет оценить среднее значение коэффициента затухания на линии, соединяющей источник и приемник. Измерения проводятся во время остановок, приблизительно каждые 5 м. Расстояние между остановками значительно меньше расстояния между соседними скважинами. Это приводит к значительной пространственной анизотропии в распределении данных. При проведении разведочного бурения скважины покрывают большую площадь. Наша цель состоит в построении трехмерной модели распределения электрических свойств межскважинного пространства на всем участке по результатом совокупности измерений. Анизотропия пространственного распределения измерений препятствует использованию стандартных методов геостатистики. Для построения трехмерной модели коэффициента затухания мы использовали один из методов теории машинного обучения — метод ближайших соседей. В этом методе коэффициент поглощения в заданной точке определяется его значениями для $k$ ближайших измерений. Число $k$ определяется из дополнительных соображений. Влияния анизотропии пространственного распределения измерений удается избежать, изменив пространственный масштаб в горизонтальном направлении. Масштабный множитель $\lambda$ является еще одним внешним параметром задачи. Для выбора значений параметров $k$ и $\lambda$ мы использовали коэффициент детерминации. Для демонстрации процедуры построения трехмерного образа коэффициента поглощения мы воспользовались данными межскважинного радиоволнового просвечивания, полученные на одном из участков в Якутии.

Traditional geological search methods going to be ineffective. The exploration depth of kimberlite bodies and ore deposits has increased significantly. The only direct exploration method is to drill a system of wells to the depths that provide access to the enclosing rocks. Due to the high cost of drilling, the role of inter-well survey methods has increased. They allows to increase the mean well spacing without significantly reducing the kimberlite or ore body missing probability. The method of inter-well radio wave survey is effective to search for high contrast conductivity objects. The physics of the method based on the dependence of the electromagnetic wave propagation on the propagation medium conductivity. The source and receiver of electromagnetic radiation is an electric dipole, they are placed in adjacent wells. The distance between the source and receiver is known. Therefore we could estimate the medium absorption coefficient by the rate of radio wave amplitude decrease. Low electrical resistance rocks corresponds to high absorption of radio waves. The inter-well measurement data allows to estimate an effective electrical resistance (or conductivity) of the rock. Typically, the source and receiver are immersed in adjacent wells synchronously. The value of the of the electric field amplitude measured at the receiver site allows to estimate the average value of the attenuation coefficient on the line connecting the source and receiver. The measurements are taken during stops, approximately every 5 m. The distance between stops is much less than the distance between adjacent wells. This leads to significant spatial anisotropy in the measured data distribution. Drill grid covers a large area, and our point is to build a three-dimensional model of the distribution of the electrical properties of the inter-well space throughout the whole area. The anisotropy of spatial distribution makes hard to the use of standard geostatistics approach. To build a three-dimensional model of attenuation coefficient, we used one of machine learning theory methods, the method of nearest neighbors. In this method, the value of the absorption coefficient at a given point is calculated by $k$ nearest measurements. The number $k$ should be determined from additional reasons. The spatial distribution anisotropy effect can be reduced by changing the spatial scale in the horizontal direction. The scale factor $\lambda$ is one yet external parameter of the problem. To select the parameters $k$ and $\lambda$ values we used the determination coefficient. To demonstrate the absorption coefficient three-dimensional image construction we apply the procedure to the inter-well radio wave survey data. The data was obtained at one of the sites in Yakutia.

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

Для решения прямой задачи используется численное моделирование сеточно-характеристическим методом. Сеточно-характеристический метод позволяет применять физически обоснованные алгоритмы расчета точек на внешних границах области и контактных границах внутри области интегрирования. Трещина принимается тонкой, для описания трещины используется специальное условие на створках трещины.

Обратная задача решается с помощью сверточных нейронных сетей. Входными данными нейронной сети являются сейсмограммы, интерпретируемые как изображения. Выходными данными являются маски, описывающие среду на структурированной сетке. Каждый элемент такой сетки относится к одному из двух классов: либо элемент сплош- ного геологического массива, либо элемент, через который проходит трещина. Такой подход позволяет рассматривать среду, в которой находится неизвестное наперед количество трещин.

Для обучения нейронной сети использовались исключительно примеры с одной трещиной. Для итогового тестирования обученной сети использовались отдельные примеры с несколькими трещинами, эти примеры никак не были задействованы в ходе обучения. Целью тестирования в таких условиях была проверка, что обученная сеть обладает достаточной общностью, распознает в сигнале признаки наличия трещины и при этомне страдает от переобучения на примерах с единственной трещиной в среде.

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

This paper considers the inverse problem of seismic exploration — determining the structure of the media based on the recorded wave response from it. Large cracks are considered as target objects, whose size and position are to be determined.

he direct problem is solved using the grid-characteristic method. The method allows using physically based algorithms for calculating outer boundaries of the region and contact boundaries inside the region. The crack is assumed to be thin, a special condition on the crack borders is used to describe the crack.

The inverse problem is solved using convolutional neural networks. The input data of the neural network are seismograms interpreted as images. The output data are masks describing the medium on a structured grid. Each element of such a grid belongs to one of two classes — either an element of a continuous geological massif, or an element through which a crack passes. This approach allows us to consider a medium with an unknown number of cracks.

The neural network is trained using only samples with one crack. The final testing of the trained network is performed using additional samples with several cracks. These samples are not involved in the training process. The purpose of testing under such conditions is to verify that the trained network has sufficient generality, recognizes signs of a crack in the signal, and does not suffer from overtraining on samples with a single crack in the media.

The paper shows that a convolutional network trained on samples with a single crack can be used to process data with multiple cracks. The networks detects fairly small cracks at great depths if they are sufficiently spatially separated from each other. In this case their wave responses are clearly distinguishable on the seismogram and can be interpreted by the neural network. If the cracks are close to each other, artifacts and interpretation errors may occur. This is due to the fact that on the seismogram the wave responses of close cracks merge. This cause the network to interpret several cracks located nearby as one. It should be noted that a similar error would most likely be made by a human during manual interpretation of the data. The paper provides examples of some such artifacts, distortions and recognition errors.