Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
Расширение языка C для поддержки процедурно-параметрического полиморфизма
Get PDFSoftware development is often about expanding functionality. To improve reliability in this case, it is necessary to minimize the change in previously written code. For instrumental support of the evolutionary development of programs, a procedural-parametric programming paradigm was proposed, which made it possible to increase the capabilities of the procedural approach. This allows to extend both data and functions painlessly. The paper considers the inclusion of procedural-parametric programming in the C language. Additional syntactic constructions are proposed to support the proposed approach. These constructions include: parametric generalizations, specializations of generalizations, generalizing functions, specialization handlers. Their semantics, possibilities and features of technical implementation are described. To check the possibilities of using this approach, models of procedural-parametric constructions in the C programming language were built. The example in the article demonstrates the flexible extension of the program and support of multiple polymorphism.Разработка программного обеспечения зачастую связана с расширением функциональности. Для повышения надежности в этом случае необходимо минимизировать изменение ранее написанного кода. Для инструментальной поддержки эволюционной разработки программ была предложена процедурно-параметрическая парадигма программирования, что позволило повысить возможности процедурного подхода. Это обеспечивает безболезненное расширение как данных, так функций, используя при этом статическую типизацию. В работе рассматривается включение процедурно-параметрического программирования в язык C. Предлагаются дополнительные синтаксические конструкции, ориентированные на поддержку предлагаемого подхода. К ним относятся: параметрические обобщения, специализации обобщений, обобщающие функции, обработчики специализаций. Описываются их семантика, возможности и особенности технической реализации. Для проверки возможностей использования данного подхода построены модели процедурно-параметрических конструкций на языке программирования C. Приведенный пример демонстрирует гибкое расширение программы и поддержку множественного полиморфизма
Моделирование влияния внешних воздействий на процесс автоматизированной посадки БпЛА-квадрокоптера на подвижную платформу с использованием технического зрения
Get PDFThis article describes a series of experiments in the Gazebo simulation environment aimed at studying the influence of external weather conditions on the automatic landing of an unmanned aerial vehicle (UAV) on a moving platform using computer vision and a previously developed control system based on PID and polynomial controllers. As part of the research, methods for modeling external weather conditions were developed and landing tests were carried out simulating weather conditions such as wind, light, fog and precipitation, including their combinations. In all experiments, successful landing on the platform was achieved; during the experiments, landing time and its accuracy were measured. The graphical and statistical analysis of the obtained results revealed the influence of illumination, precipitation and wind on the UAV landing time, and the introduction of wind into the simulation under any other external conditions led to the most significant increase in landing time. At the same time, the study failed to identify a systemic negative influence of external conditions on landing accuracy. The results obtained provide valuable information for further improvement of autonomous automatic landing systems for UAVs without the use of satellite navigation systems.В данной статье проводится описание серии экспериментов в симуляционной среде Gazebo, направленных на исследование влияния внешних погодных условий на автоматическую посадку беспилотного летательного аппарата (БпЛА) на движущуюся платформу с использованием компьютерного зрения и разработанной ранее системы управления, основанной на ПИД и полиномиальных регуляторах. В рамках исследования разработаны методы моделирования внешних погодных условий, и проведены тесты посадки с имитацией таких погодных условий, как ветер, освещенность, туман и осадки, включая их комбинации. Во всех экспериментах была достигнута успешная посадка на платформу, в ходе экспериментов измерялось время посадки и ее точность. Проведенный графический и статистический анализ полученных результатов выявил влияние освещенности, осадков и ветра на время посадки БпЛА, а введение ветра в симуляцию при любых других внешних условиях привело к наиболее значительному увеличению времени посадки. При этом в ходе исследования не удалось выявить системного негативного влияния внешних условий на точность посадки. Полученные результаты представляют ценную информацию для дальнейшего совершенствования систем автономной автоматической посадки БпЛА без использования спутниковых систем навигации
Рекурсивно-параллельный алгоритм поиска максимального общего подграфа
Get PDFThe paper proposes an algorithm for solving the problem of finding the maximum common subgraph. Both the sequential and the parallel version of the algorithm, their software implementation are described, and an experimental study of their effectiveness is carried out.
This problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems related to the study of complex structures. We solve it in a statement when we need to find all possible isomorphisms of the found common subgraph. Due to the extremely high complexity of the problem, it is natural to want to speed up its solution by parallelizing the algorithm.
To organize parallel computing, the author used the RPM_ParLib library. It allows to develop effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework.The library supports a recursive-parallel programming style and provides effective work distribution and dynamic load balancing of computational modules during program execution. It can be used for applications written in any programming language supported by the .NET Framework.
The purpose of the numerical experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. For the experiment, the author developed a special application in the C# language designed to generate various sets of initial data with specified parameters. The paper describes the features of the generated initial pairs of graphs, as well as the results obtained during the experiment.В работе предложен алгоритм решения задачи нахождении максимального общего подграфа. Описаны последовательный и параллельный вариант алгоритма, их программная реализация и произведено экспериментальное исследование их эффективности. Данная задача является одной из самых известных NP"=полных задач. Ее решение может потребоваться при решении многих практических задач, связанных с исследованием сложных структур. Мы решаем ее в постановке, в которой требуется найти все возможные изоморфизмы найденного общего подграфа. Ввиду чрезвычайно высокой трудоемкости задачи желание ускорить ее решение за счет распараллеливания алгоритма является вполне естественным. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Целью численного эксперимента было исследование ускорения, достигаемого за счет рекурсивно"=параллельной организации вычислений. Для эксперимента автором было разработано специальное приложение на языке C#, предназначенное для генерации различных наборов исходных данных с заданными параметрами. В работе описаны характеристики сгенерированных исходных пар графов, а также результаты, полученные в ходе эксперимента
Извлечение именованных сущностей из русскоязычных документов с различной выраженностью структуры
Get PDFThis work is devoted to solving the problem of recognizing named entities for Russian-language texts based on the CRF model. Two sets of data were considered: documents on refinancing with a good document structure, semi-structured texts of court records. The model was tested under various sets of text features and CRF parameters (optimization algorithms). In average for all entities, the best F-measure value for structured documents was 0.99, and for semi-structured ones 0.86.Данная работа посвящена решению задачи распознавания именованных сущностей для русскоязычных текстов на основе модели CRF. Рассмотрены два набора данных: документы о рефинансировании с хорошей структурой документа, слабоструктурированные тексты судебных протоколов. Было проведено тестирование модели при различных наборах текстовых признаков и параметрах CRF (алгоритмов оптимизации). В среднем по всем сущностям лучшее значение F"=меры для структурированных документов составило 0.99, а для слабоструктурированных 0.86
Разметка корпусов текстов по тональности и наличию иронии в рамках проекта гражданской науки
Get PDFThe paper is devoted to construction of a sentence corpus annotated by the general sentiment into 4 classes (positive, negative, neutral, and mixed), a corpus of phrasemes annotated by the sentiment into 3 classes (positive, negative, and neutral), and a corpus of sentences annotated by the presence or absence of irony. The annotation was done by volunteers within the project “Prepare texts for algorithms” on the portal “People of science”.
The existing knowledge on the domain regarding each task was the basis to develop guidelines for annotators. A technique of statistical analysis of the annotation result based on the distributions and agreement measures of the annotations performed by various annotators was also developed.
For the annotation of sentences by irony and phrasemes by the sentiment the agreement measures were rather high (the full agreement rate of 0.60--0.99), whereas for the annotation of sentences by the general sentiment the agreement was low (the full agreement rate of 0.40), presumably, due to the higher complexity of the task. It was also shown that the results of automatic algorithms of detecting the sentiment of sentences improved by 12–13 % when using a corpus for which all the annotators (from 3 till 5) had the agreement, in comparison with a corpus annotated by only one volunteer.Статья посвящена построению корпуса предложений, размеченных по общей тональности на 4 класса (положительный, отрицательный, нейтральный, смешанный), корпуса фразеологизмов, размеченных по тональности на 3 класса (положительный, отрицательный, нейтральный), и корпуса предложений, размеченных по наличию или отсутствию иронии. Разметку проводили волонтёры в рамках проекта «Готовим тексты алгоритмам» на портале «Люди науки». На основе имеющихся знаний о предметной области для каждой из задач были составлены инструкции для разметчиков. Также была выработана методика статистической обработки результатов разметки, основанная на анализе распределений и показателей согласия оценок, выставленных разными разметчиками. Для разметки предложений по наличию иронии и фразеологизмов по тональности показатели согласия оказались достаточно высокими (доля полного совпадения 0.60--0.99), при разметке предложений по общей тональности согласие оказалось слабым (доля полного совпадения 0.40), по-видимому, из-за более высокой сложности задачи. Также было показано, что результаты работы автоматических алгоритмов анализа тональности предложений улучшаются на 12--13 % при использовании корпуса, относительно предложений которого сошлись мнения всех разметчиков (3--5 человек), по сравнению с корпусом с разметкой только одним волонтёром
LTL-спецификация для разработки и верификации управляющих программ
Get PDFThis work continues the series of articles on development and verification of control programs based on the LTL-specification. The essence of the approach is to describe the behavior of programs using formulas of linear temporal logic LTL of a special form. The developed LTL-specification can be directly verified by using a model checking tool. Next, according to the LTL-specification, the program code in the imperative programming language is unambiguously built. The translation of the specification into the program is carried out using a template. The novelty of the work consists in the proposal of two LTL-specifications of a new form — declarative and imperative, as well as in a more strict formal justification for this approach to program development and verification. A transition has been made to a more modern verification tool for finite and infinite systems — nuXmv. It is proposed to describe the behavior of control programs in a declarative style. For this purpose, a declarative LTL-specification is intended, which defines a labelled transition system as a formal model of program behavior. This method of describing behavior is quite expressive — the theorem on the Turing completeness of the declarative LTL-specification is proved. Next, to construct program code in an imperative language, the declarative LTL-specification is converted into an equivalent imperative LTL-specification. An equivalence theorem is proved, which guarantees that both specifications specify the same behavior. The imperative LTL-specification is translated into imperative program code according to the presented template. The declarative LTL-specification, which is subject to verification, and the control program built on it are guaranteed to specify the same behavior in the form of a corresponding transition system. Thus, during verification, a model is used that is adequate to the real behavior of the control program.Настоящая работа продолжает цикл статей по разработке и верификации управляющих программ на основе LTL"=спецификации. Суть подхода заключается в описании поведения программ с помощью формул линейной темпоральной логики LTL специального вида. Полученная LTL"=спецификация может быть непосредственно верифицирована с помощью инструмента проверки модели. Далее по LTL"=спецификации однозначно строится код программы на императивном языке программирования. Перевод спецификации в программу осуществляется по шаблону. Новизна работы состоит в предложении двух LTL"=спецификаций нового вида — декларативной и императивной, а также в более строгом формальном обосновании данного подхода к разработке и верификации программ. Выполнен переход на более современный инструмент верификации конечных и бесконечных систем — nuXmv. Предлагается описывать поведение управляющих программ в декларативном стиле. Для этого предназначена декларативная LTL"=спецификация, которая задаёт размеченную систему переходов как формальную модель поведения программы. Данный способ описания поведения является достаточно выразительным — доказана теорема о Тьюринг"=полноте декларативной LTL"=спецификации. Далее для построения кода программы на императивном языке декларативная LTL"=спецификация преобразуется в эквивалентную императивную LTL"=спецификацию. Доказана теорема об эквивалентности, которая гарантирует, что обе спецификации задают одно и то же поведение. Императивная LTL"=спецификация транслируется в императивный код программы по представленному шаблону. Декларативная LTL"=спецификация, которая подвергается верификации, и построенная по ней управляющая программа гарантированно задают одно и то же поведение в виде соответствующей системы переходов. Таким образом, при верификации используется модель, адекватная реальному поведению управляющей программы
Построение оптимальной схемы информационного обмена системы адаптивного управления движением группы беспилотных летательных аппаратов
Get PDFThe paper considers the problem of modeling an adaptive control system information exchange for a group of unmanned aerial vehicles (UAVs). The movement of the UAV group is carried out in accordance with the adaptive algorithm for optimal control. Optimal controls are constructed to provide a minimum of the total energy expended. The parameters of the mathematical model of the movement of the UAV group are refined during the flight in accordance with changing external conditions. In accordance with this, the control actions are specified. This task requires significant computing resources and imposes special requirements on the information exchange system between the UAV and the control point. A scheme of information exchange between the UAV and the control point is proposed, which makes it possible to calculate the optimal parameters of the transmitting devices.В работе рассмотрена задача моделирования информационного обмена адаптивной системы управления движением группы беспилотных летательных аппаратов (БЛА). Движение группы БЛА осуществляется в соответствии с адаптивным алгоритмом оптимального управления пространственной перестройкой. Оптимальные управления строятся обеспечивающими минимум общей затрачиваемой энергии. Параметры математической модели движения группы БЛА уточняются в процессе полета в соответствии с изменяющимися внешними условиями. В соответствии с этим уточняются управляющие воздействия. Это требует значительных вычислительных ресурсов и накладывает особые требования на систему информационного обмена между БЛА и пунктом управления. Предложена схема информационного обмена между БЛА и пунктом управления, позволяющая рассчитать оптимальные параметры передающих устройств
Полином Жегалкина многоместного самодостаточного оператора
Get PDFAmong functionally complete sets of Boolean functions, sole sufficient operators are of particular interest. They have a wide range of applicability and are not limited to the two-seat case. In this paper, the conditions, imposed on the Zhegalkin polynomial coefficients, are formulated. The conditions are necessary and sufficient for the polynomial to correspond to a sole sufficient operator. The polynomial representation of constant-preserving Boolean functions is considered. It is shown that the properties of monotone and linearity do not require special consideration in describing a sole sufficient operator. The concept of a dual remainder polynomial is introduced. The value of it allows one to determine the self-duality of a Boolean function. It is proved that the preserving 0 and 1 or preserving neither 0 nor 1 Boolean function is self-dual if and only if the dual remainder of its corresponding Zhegalkin polynomial is equal to 0 for any sets of function variable values. Based on this fact, a system of leading coefficients is obtained. The solution of the system made it possible to formulate the criterion for the self-duality of the Boolean function represented by the Zhegalkin polynomial. It imposes necessary and sufficient conditions on the polynomial coefficients. Thus, it is shown that Zhegalkin polynomials are a rather convenient tool for studying precomplete classes of Boolean functions.Среди полных систем булевых функций особый интерес представляют самодостаточные операторы. Они обладают широкой областью применимости и не ограничиваются двухместным случаем. В данной работе формулируются условия, накладываемые на коэффициенты полинома Жегалкина, необходимые и достаточные для того, чтобы полином соответствовал самодостаточному оператору. Рассмотрено полиномиальное представление булевых функций, сохраняющих константу. Показано, что свойства монотонности и линейности не требуют специального рассмотрения при описании самодостаточного оператора. Вводится понятие полинома двойственного остатка, значение которого позволяет определить самодвойственность булевой функции. Доказано, что сохраняющая 0 и 1 или не сохраняющая ни 0, ни 1 булева функция является самодвойственной тогда и только тогда, когда двойственный остаток соответствующего ей полинома Жегалкина равен 0 для любых наборов значений переменных функции. На основании этого факта получена система ведущих коэффициентов. Решение данной системы позволило сформулировать критерий самодвойственности булевой функции, представленной полиномом Жегалкина, накладывающий необходимые и достаточные условия на коэффициенты полинома. Таким образом, показано, что полиномы Жегалкина являются достаточно удобным инструментом при исследовании предполных классов булевых функций
Применение алгоритма поиска внешней медианы графа в задачах определения надежности технических систем
Get PDFThe problem of locating a service center for technical systems with known values of failure flows is considered. This problem was solved using the minisum algorithm of graph theory. The dependence of the system availability factor on the average time between failures and the average recovery time of the system elements is obtained. It is shown that the optimal location of the maintenance point is the median of the graph located at one of its vertices.Рассмотрена задача о размещении центра обслуживания технических систем при известных значениях потоков отказов. Даная задача решалась с помощью минисуммного алгоритма теории графов. Получена зависимость коэффициента готовности системы от среднего времени наработки между отказами и среднего времени восстановления элементов системы. Показано, что оптимальным местом расположения пункта технического обслуживания является медиана графа, расположенная в одной из его вершин
Генерация ключевых слов для русскоязычных научных текстов с помощью модели mT5
Get PDFIn this work, we applied the multilingual text-to-text transformer (mT5) to the task of keyphrase generation for Russian scientific texts using the Keyphrases CS&Math Russian corpus. The automatic selection of keyphrases is a relevant task of natural language processing since keyphrases help readers find the article easily and facilitate the systematization of scientific texts. In this paper, the task of keyphrase selection is considered as a text summarization task. The mT5 model was fine-tuned on the texts of abstracts of Russian research papers. We used abstracts as an input of the model and lists of keyphrases separated with commas as an output. The results of mT5 were compared with several baselines, including TopicRank, YAKE!, RuTermExtract, and KeyBERT. The results are reported in terms of the full-match F1-score, ROUGE-1, and BERTScore. The best results on the test set were obtained by mT5 and RuTermExtract. The highest F1-score is demonstrated by mT5 (11,24 %), exceeding RuTermExtract by 0,22 %. RuTermextract shows the highest score for ROUGE-1 (15,12 %). According to BERTScore, the best results were also obtained using these methods: mT5 — 76,89 % (BERTScore using mBERT), RuTermExtract — 75,8 % (BERTScore using ruSciBERT). Moreover, we evaluated the capability of mT5 for predicting the keyphrases that are absent in the source text. The important limitations of the proposed approach are the necessity of having a training sample for fine-tuning and probably limited suitability of the fine-tuned model in cross-domain settings. The advantages of keyphrase generation using pre-trained mT5 are the absence of the need for defining the number and length of keyphrases and normalizing produced keyphrases, which is important for flective languages, and the ability to generate keyphrases that are not presented in the text explicitly.Авторами предлагается подход к генерации ключевых слов для русскоязычных научных текстов с помощью модели mT5 (multilingual text-to-text transformer), дообученнной на материале текстового корпуса Keyphrases CS&Math Russian. Автоматический подбор ключевых слов является актуальной задачей обработки естественного языка, поскольку ключевые слова помогают читателям осуществлять поиск статей и облегчают систематизацию научных текстов. В данной работе задача подбора ключевых слов рассматривается как задача автоматического реферирования текстов. Дообучение mT5 осуществлялась на текстах аннотаций русскоязычных научных статей. В качестве входных и выходных данных выступали тексты аннотаций и списки ключевых слов, разделенных запятыми, соответственно. Результаты, полученные с помощью mT5, были сравнены с результатами нескольких базовых методов: TopicRank, YAKE!, RuTermExtract, и KeyBERT. Для представления результатов использовались следующие метрики: F-мера, ROUGE-1, BERTScore. Лучшие результаты на тестовой выборке были получены с помощью mT5 и RuTermExtract. Наиболее высокое значение F-меры продемонстрировала модель mT5 (11.24 %), превзойдя RuTermExtract на 0.22 %. RuTermExtract показал лучший результат по метрике ROUGE-1 (15.12 %). Лучшие результаты по BERTScore также были достигнуты этими двумя методами: mT5 — 76.89 % (BERTScore, использующая модель mBERT), RuTermExtract — 75.8 % (BERTScore на основе ruSciBERT). Также авторами была оценена возможность mT5 генерировать ключевые слова, отсутствующие в исходном тексте. К ограничениям предложенного подхода относятся необходимость формирования обучающей выборки для дообучения модели и, вероятно, ограниченная применимость дообученной модели для текстов других предметных областей. Преимущества генерации ключевых слов с помощью mT5 — отсутствие необходимости задавать фиксированные значения длины и количества ключевых слов, необходимости проводить нормализацию, что особенно важно для флективных языков, и возможность генерировать ключевые слова, в явном виде отсутствующие в тексте