Search

В статье разработан подход, который на основе метрического пространства состояний позволяет определить успешную ликвидацию чрезвычайной ситуации., Article contains an overview of the approach, which is based on metric space and allows determining the successful emergency liquidation., Естественные и технические науки, Выпуск 7 (158) 2021

Предлагаются алгоритм и построенная на его основе программа оценки эффективного кодирования источника сигналов при их преобразованиях в различных метрических пространствах (в частности, для широко используемого в настоящее время аналого-цифрового преобразования непрерывного сигнала в двоичный). Алгоритм оценки учитывает показатели искажений при кодировании двоичным кодом,вероятности появления этих искажений при передаче элементов сообщения и вероятности появления сообщения в канале связи. Помимо самого алгоритма, предложены его программная реализация, созданная с помощью языка программирования 0#,а также усовершенствованный интерфейс на базе MS Excel. В программной реализации имеется графическая среда для пользователя., This paper proposes an algorithm and a program built on its basis for evaluating the effective coding of a signal source during their transformations in various metric spaces, and, in particular, for the currently widely used analog-to-digital conversion of a continuous signal to a binary signal. The estimation algorithm takes into account the indicators of distortions under binary coding, the probability of occurrence of these distortions when transmitting message elements, and the probability of a message appearing in the communication channel. In addition to the algorithm itself, its software implementation, created using the C# programming language, and an improved interface based on MS Excel are proposed. Software implementation has a graphical user environment., Труды НИИР, Выпуск 4 (3) 2020

На данный момент существует большое количество задач по автоматизированной обработке многомерных данных, например, классификация, кластеризация, прогнозирование, задачи управления сложными объектами. Соответственно, возникает необходимость в развитии математического и алгоритмического обеспечения для решения возникающих задач. Целью исследования является развитие алгоритмов классификации точечных множеств на основе их пространственного распределения. В работе предлагается рассматривать данные как точки в многомерном метрическом пространстве. В работе рассмотрены подходы к описанию характеристик точечных множеств в пространствах высокой размерности и предлагается подход к описанию точечного множества на основе сигнатур, которые представляют собой характеристику заполненности точечного множества на основе расширения понятия пространственного хеширования. Обобщенный подход к вычислению сигнатур точечных множеств заключается в разбиении пространства, занимаемого множеством на регулярную сетку с помощью метода пространственного хеширования, вычисления геометрических характеристик множества в полученных ячейках и определения наиболее заполненных ячеек по каждому из пространственных измерений. Предлагается новый подход к классификации на основе сигнатур множества, который заключается в нахождении сигнатур для точек с известным значением принадлежности к некоторым классам, а для новых точек вычисляется расстояние от хеша точки до сигнатуры каждого из известных множеств, на основе чего определяется наиболее вероятный класс точки. В качестве используемых метрик предлагаются Евклидово расстояние и метрика городских кварталов. В работе проведён сравнительный анализ используемых метрик с точки зрения точности классификации. Преимуществами предложенного подхода являются простота вычислений и высокая степень точности классификации для равномерно распределенных точек. Представленный алгоритм реализован в виде программного приложения на языке Python с использованием библиотеки NumPy. Также рассмотрены варианты использования предложенного подхода для задач с не числовыми данными, такими как строковые и булевы значения. Для таких данных предложено использовать метрику Хэмминга, проведённые эксперименты показали работоспособность алгоритма для таких типов данных. There are many unsolved problems in the field of automatic multi-dimensional data processing, for example, classification, clustering, regression, and control of complex objects. This leads to the need of development of mathematical and algorithmical background for such problems. In our research we aim to development of classification algorithms of point sets based on their spatial distribution. We propose to consider data as points in multi-dimensional metric space. The approaches to describe point set features in high dimensional spaces are viewed. The algorithm of describing of point set based on their signatures, that are spatial distribution of point set is considered. In our approach we extend spatial hashing technique. The generalized method of computation of point set signatures is to split space, occupied by point set into regular grid by the spatial hashing algorithm, then we evaluate geometrical characteristics of the set in cells of the grid and define cells, that contain most of the points for the all of coordinate axis. The new approach to classification by means of point set signatures is developed that is to find signatures of known points with the classes defined and then we compute spatial hashes for unknown points and their distance to the signatures of classes. The probable class of the tested point is defined by the minimal distance among all distances to each signature. To define distance in our approach we use Manhattan and Euclidean metric. The comparative study of impact of metrics used to the classification error is provided. The main advantage of our method is computation simplicity and low classification error for evenly distributed points. Prototype implementation of our algorithm was written in order to test this algorithm for practical classification applications. The implementation was coded in Python with use NumPy library. The use of our algorithm to the classification of non-numerical data such as texts and booleans is viewed. For such data types we propose use of Hamming distance and experiments done show practical viability for such data types.

The Capacitated Vehicle Routing Problem (CVRP) is a classical extremal combinatorial routing problem with numerous applications in operations research. Although the CVRP is strongly NP-hard both in the general case and in the Euclidean plane, it admits quasipolynomial- and even polynomial-time approximation schemes (QPTAS and PTAS) in Euclidean spaces of fixed dimension. At the same time, the metric setting of the problem is APX-complete even for an arbitrary fixed capacity q ≥ 3. In this paper, we show that the classical Haimovich-Rinnooy Kan algorithm implements a PTAS and an Efficient Polynomial-Time Approximation Scheme (EPTAS) in an arbitrary metric space of fixed doubling dimension for q = o(log log n) and for an arbitrary constant capacity, respectively. © 2019 Krasovskii Institute of Mathematics and Mechanics. All right reserved.

На данный момент существует большое количество задач по автоматизированной обработке многомерных данных, например, классификация, кластеризация, прогнозирование, задачи управления сложными объектами. Соответственно, возникает необходимость в развитии математического и алгоритмического обеспечения для решения возникающих задач. Целью исследования является развитие алгоритмов классификации точечных множеств на основе их пространственного распределения. В работе предлагается рассматривать данные как точки в многомерном метрическом пространстве. В работе рассмотрены подходы к описанию характеристик точечных множеств в пространствах высокой размерности и предлагается подход к описанию точечного множества на основе сигнатур, которые представляют собой характеристику заполненности точечного множества на основе расширения понятия пространственного хеширования. Обобщенный подход к вычислению сигнатур точечных множеств заключается в разбиении пространства, занимаемого множеством на регулярную сетку с помощью метода пространственного хеширования, вычисления геометрических характеристик множества в полученных ячейках и определения наиболее заполненных ячеек по каждому из пространственных измерений. Предлагается новый подход к классификации на основе сигнатур множества, который заключается в нахождении сигнатур для точек с известным значением принадлежности к некоторым классам, а для новых точек вычисляется расстояние от хеша точки до сигнатуры каждого из известных множеств, на основе чего определяется наиболее вероятный класс точки.. В качестве используемых метрик предлагаются Евклидово расстояние и метрика городских кварталов. В работе проведён сравнительный анализ используемых метрик с точки зрения точности классификации. Преимуществами предложенного подхода являются простота вычислений и высокая степень точности классификации для равномерно распределенных точек. Представленный алгоритм реализован в виде программного приложения на языке Python с использованием библиотеки NumPy. Также рассмотрены варианты использования предложенного подхода для задач с нечисловыми данными, такими как строковые и булевы значения. Для таких данных предложено использовать метрику Хэмминга, проведённые эксперименты показали работоспособность алгоритма для таких типов данных, На даний момент існує велика кількість задач з автоматизованої обробки багатовимірних даних, наприклад, класифікація, кластеризація, прогнозування, задачі з керування складними об’єктами. Відповідно, виникає необхідність в розвитку математичного та алгоритмічного забезпечення для розв’язання таких задач. Метою дослідження є розвиток алгоритмів класифікації точкових множин на основі їх просторового розподілу. В дослідженні пропонується розглядати дані як точки в багатовимірному метричному просторі. В роботі розглянуто підходи до опису характеристик точкових множин в просторах високої розмірності та пропонується підхід до опису точкової множини на основі сигнатур, які представляють характеристику заповненості точкової множини на основі розширення поняття просторового хешування. Узагальнений підхід до обчислення сигнатур точкових множин полягає в розбитті простору, що займає множина на регулярну сітку з використанням методу просторового хешування, обчислення геометричних характеристик множини в отриманих клітинах сітки та визначення найбільш заповнених клітин за кожним з просторових вимірів. Пропонується новий підхід до розв’язання задачі класифікації на основі сигнатур множин, який полягає в визначенні сигнатур для точок з відомою належністю до заданих класів, а для невідомих точок обчислюється відстань від хешу цієї точки до сигнатур усіх заданих класів, на основі відстані визначається найбільш вірогідний клас точки. В якості метрик пропонується використання Евклідової відстані та метрики міських кварталів. У роботі проведений порівняльний аналіз використаних метрик з точки зору точності класифікації. До переваг розробленого підходу можна віднести простоту обчислень та високий ступінь точності класифікації для рівномірно розподілених точок. Представлений алгоритм реалізовано у вигляді програмного додатку на мові програмування Python з використанням бібліотеки NumPy. Також розглянуто варіанти використання запропонованого підходу для задач з нечисловими даними, такими як текстові та булеві значення. Для таких типів даних запропоновано використання метрики Геммінга, проведені експерименті показали доцільність використання алгоритму для таких типів даних, There are many unsolved problems in the field of automatic multi-dimensional data processing, for example, classification, clustering, regression, and control of complex objects. This leads to the need of development of mathematical and algorithmical background for such problems. In our research we aim to development of classification algorithms of point sets based on their spatial distribution. We propose to consider data as points in multi-dimensional metric space. The approaches to describe point set features in high dimensional spaces are viewed. The algorithm of describing of point set based on their signatures, that are spatial distribution of point set is considered. In our approach we extend spatial hashing technique. The generalized method of computation of point set signatures is to split space, occupied by point set into regular grid by the spatial hashing algorithm, then we evaluate geometrical characteristics of the set in cells of the grid and define cells, that contain most of the points for the all of coordinate axis. The new approach to classification by means of point set signatures is developed that is to find signatures of known points with the classes defined and then we compute spatial hashes for unknown points and their distance to the signatures of classes. The probable class of the tested point is defined by the minimal distance among all distances to each signature. To define distance in our approach we use Manhattan and Euclidean metric. The comparative study of impact of metrics used to the classification error is provided. The main advantage of our method is computation simplicity and low classification error for evenly distributed points. Prototype implementation of our algorithm was written in order to test this algorithm for practical classification applications. The implementation was coded in Python with use NumPy library. The use of our algorithm to the classification of non-numerical data such as texts and booleans is viewed. For such data types we propose use of Hamming distance and experiments done show practical viability for such data types

We propose method of studying implicit singular differential equations based on the results of the covering mapping theory. The article consists of three sections. In the first section we give the necessary designations and definitions and formulate the theorem on Lipcshitz perturbations of covering mappings. In the second section we introduce special spaces of measurable functions making it possible to study singular equations by methods of functional analysis and formulate the results about the Nemytskii operator in those spaces. In the last section we provide conditions for the resolubility of the Cauchy problem for implicit singular differential equations.