Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
Применение генетического алгоритма для нахождения редакционного расстояния между моделями процессов
Get PDFFinding graph-edit distance (graph similarity) is an important task in many computer science areas, such as image analysis, machine learning, chemicalinformatics. Recently, with the development of process mining techniques, it became important to adapt and apply existing graph analysis methods to examine process models (annotated graphs) discovered from event data. In particular, finding graph-edit distance techniques can be used to reveal patterns (subprocesses), compare discovered process models. As it was shown experimentally and theoretically justified, exact methods for finding graph-edit distances between discovered process models (and graphs in general) are computationally expensive and can be applied to small models only. In this paper, we present and assess accuracy and performance characteristics of an inexact genetic algorithm applied to find distances between process models discovered from event logs. In particular, we find distances between BPMN (Business Process Model and Notation) models discovered from event logs by using different process discovery algorithms. We show that the genetic algorithm allows us to dramatically reduce the time of comparison and produces results which are close to the optimal solutions (minimal graph edit distances calculated by the exact search algorithm).Поиск редакционного расстояния между графовыми моделями (определение схожести графовых моделей) является важной задачей в различных областях компьютерных наук, таких как анализ изображений, машинное обучение, химическая информатика. В последнее время, в связи с развитием методов извлечения и анализа процессов, появилась необходимость в адаптации существующих методов сравнения графовых моделей для анализа моделей процессов (аннотированных графов), извлекаемых из логов событий информационных систем. Методы нахождения минимального редакционного расстояния между графами могут быть использованы для обнаружения шаблонов (подпроцессов), а также для сравнения извлекаемых моделей процессов. Как было показано экспериментально и теоретически обосновано, точные методы нахождения минимального редакционного расстояния между извлекаемыми моделями процессов (и графами в общем случае) имеют большую временную сложность и могут быть применены лишь к небольшим моделям процессов. В этой статье мы оцениваем точность и временные характеристики генетического алгоритма, применяемого для нахождения расстояний между моделями процессов, извлекаемых из логов событий. В частности мы находим расстояния между BPMN (Business Process Model and Notation) моделями, извлекаемыми из логов событий с помощью различных алгоритмов синтеза. В этой работе показано, что представленный генетический алгоритм позволяет в значительной степени уменьшить время вычислений, при этом показывая результаты, близкие к оптимальным (минимальным редакционным расстояниям)
Об одной сингулярно возмущенной задаче нелинейной теплопроводности в случае сбалансированной нелинейности
Get PDFOn the basis of the modified asymptotic method of boundary functions and the asymptotic method of differential inequalities, the question of the existence of Lyapunov-stable stationary solutions with internal layers of the nonlinear heat equation in the case of nonlinear dependence of the power of thermal sources from temperature is investigated. The main conditions of the existence of such solutions are discussed. We construct an asymptotic approximation of an arbitrary-order accuracy to such solutions and suggest an efficient algorithm for constructing an asymptotic approximation to the localization surface of the transition layer. To justify the constructed formal asymptotics, we use an asymptotic method of differential inequalities. The main complexity is related to the description of the transition surface in whose neighborhood the internal layer is localized. We use a more efficient method for localizing the transition surface, which permits one to develop an approach to a more complicated case of balanced nonlinearity. The results can be used to create a numerical algorithm which uses the asymptotic analyses to construct space-non-uniform meshes while describing internal layer behaviour of the solution. As an illustration, we consider a problem on the plane that allows us to visualize the numerical calculations. Numerical and asymptotic solutions of zero order are compared for different values of the small parameter. На основе модифицированного асимптотического метода пограничных функций и асимптотического метода дифференциальных неравенств исследуется вопрос о существовании устойчивых по Ляпунову стационарных решений с внутренними слоями уравнения нелинейной теплопроводности в случае нелинейной зависимости мощности тепловых источников от температуры. Обсуждаются основные условия существования таких решений, построение асимптотического приближения решения произвольного порядка точности, алгоритм определения положения поверхности перехода, в окрестности которой локализован внутренний слой контрастной структуры, и обоснование формальных построений. Основная трудность связана с описанием поверхности перехода. Предлагается эффективный алгоритм определения положения поверхности перехода, который развивает наш подход в описании многомерных задач на более сложный случай сбалансированной нелинейности. Результат может быть использован для создания численного алгоритма, основанного на применении асимптотического анализа с целью построения пространственно-неоднородных сеток при описании внутреннего слоя решения. В качестве иллюстрации рассматривается задача на плоскости, которая позволяет визуализировать численные расчеты. Сравниваются численные и асимптотические решения нулевого порядка при различных значениях малого параметра
Краевые состояния и киральные солитоны в топологических полях Черна–Саймонса– Холла
No full textThe multi-component extension problem of the (2+1)D-gauge topological Jackiw–Pi model describing the nonlinear quantum dynamics of charged particles in multi-layer Hall systems is considered. By applying the dimensional reduction (2 + 1)D → (1 + 1)D to Lagrangians with the Chern–Simons topologic fields , multi-component nonlinear Schrodinger equations for particles are constructed with allowance for their interaction. With Hirota‘s method, an exact two-soliton solution is obtained, which is of interest in quantum information transmission systems due to the stability of their propagation. An asymptotic analysis t →±∞ of soliton-soliton interactions shows that there is no backscattering processes. We identify these solutions with the edge (topological protected) states – chiral solitons – in the multi-layer quantum Hall systems. By applying the Hirota bilinear operator algebra and a current theorem, it is shown that, in contrast to the usual vector solitons, the dynamics of new solutions (chiral vector solitons) has exclusively unidirectional motion. The article is published in the author’s wording. Рассматривается проблема многокомпонентного расширения (2+1)D-калибровочной топологической модели Jackiw–Pi, описывающей нелинейную квантовую динамику заряженных частиц в многослойных системах Холла. Применяя размерную редукцию (2 + 1)D → (1+1)D к лагранжианам с топологическими полями Черна–Саймонса, мы построили многокомпонентные нелинейные уравнения Шредингера для частиц с учетом их взаимодействия. Используя метод Хироты, получили точное двухсолитонное решение, представляющее интерес для квантовых систем передачи информации в силу устойчивости их распространения. Асимптотический t →±∞ анализ солитон-солитонных взаимодействий показывает, что процессов обратного рассеяния нет. Мы отождествляем эти решения с краевыми (топологически защищенными) состояниями – киральными солитонами – в многослойных квантовых системах Холла. Применяя билинейную операторную алгебру Хироты и теорему тока, мы показали, что в отличие от обычных векторных солитонов динамика новых решений (киральных векторных солитонов) имеет исключительно однонаправленное движение. Статья публикуется в авторской редакции.
Измерение накладных расходов на параллелизм и виртуальную память
No full textWe present the methodology, as well as results of measurements and evaluation of overhead created by concurrency and virtual memory. A special measurement technique and testbed were used to obtain the most accurate data from the experiments. This technique is focused on the measurements of the overall performance degradation that is introduced by concurrency in the form of lightweight user-level threads on IA-32 processors. We have obtained and compared results of the experiments in an environment with and without enabled virtual memory to understand what loss of performance is caused by virtual memory in itself, and how it affects the overhead associated with concurrency. The results showed that overhead of concurrency outweighs virtual memory overhead and that there is a complex dependency between them. The article is published in the author’s wording.В данной статье представляется методология и результаты измерений и оценки накладных расходов, связанных с параллелизмом и виртуальной памятью. Для получения наиболее точных экспериментальных данных использовалась специальная методика измерений. Данная методика сфокусирована на измерениях совокупных потерь производительности, создаваемых параллелизмом, выраженным в форме легковесных потоков пользовательского режима на процессорах с архитектурой IA-32. Были получены и проанализированы данные, произведенные в средах с виртуальной памятью и без нее. Таким образом стало известно, какая потеря производительности вызывается виртуальной памятью, а также то, как она влияет на накладные расходы, связанные с параллелизмом. Эксперименты показали, что накладные расходы на параллелизм гораздо существеннее накладных расходов на виртуальную память. И тем не менее, между ними существует сложная взаимозависимость. Статья публикуется в авторской редакции.
Русскоязычные тезаурусы: автоматизированное построение и применение в задачах обработки текстов на естественном языке
Get PDFThe paper reviews the existing Russian-language thesauri in digital form and methods of their automatic construction and application. The authors analyzed the main characteristics of open access thesauri for scientific research, evaluated trends of their development, and their effectiveness in solving natural language processing tasks. The statistical and linguistic methods of thesaurus construction that allow to automate the development and reduce labor costs of expert linguists were studied. In particular, the authors considered algorithms for extracting keywords and semantic thesaurus relationships of all types, as well as the quality of thesauri generated with the use of these tools. To illustrate features of various methods for constructing thesaurus relationships, the authors developed a combined method that generates a specialized thesaurus fully automatically taking into account a text corpus in a particular domain and several existing linguistic resources. With the proposed method, experiments were conducted with two Russian-language text corpora from two subject areas: articles about migrants and tweets. The resulting thesauri were assessed by using an integrated assessment developed in the previous authors’ study that allows to analyze various aspects of the thesaurus and the quality of the generation methods. The analysis revealed the main advantages and disadvantages of various approaches to the construction of thesauri and the extraction of semantic relationships of different types, as well as made it possible to determine directions for future study.В работе выполнен обзор существующих электронных русскоязычных тезаурусов и методов их автоматического построения и применения. Авторы провели анализ основных характеристик тезаурусов, находящихся в открытом доступе, для научных исследований, оценили динамику их развития и эффективность в решении задач по обработке естественного языка. Были исследованы статистические и лингвистические методы построения тезаурусов, которые позволяют автоматизировать разработку и уменьшить затраты на труд экспертов-лингвистов. В частности, рассматривались алгоритмы выделения ключевых терминов из текстов и семантических тезаурусных связей всех типов, а также качество применения получившихся в результате их работы тезаурусов. Для наглядной иллюстрации особенностей различных методов построения тезаурусных связей был разработан комбинированный метод, генерирующий специализированный тезаурус полностью автоматически на основе корпуса текстов предметной области и нескольких существующих лингвистических ресурсов. С использованием предложенного метода были проведены эксперименты с русскоязычными корпусами текстов из двух предметных областей: статьи о мигрантах и твиты. Для анализа полученных тезаурусов использовалась комплексная оценка, разработанная авторами в предыдущем исследовании, которая позволяет определить различные аспекты тезауруса и качество методов его генерации. Проведённый анализ выявил основные достоинства и недостатки различных подходов к построению тезаурусов и выделению семантических связей различных типов, а также позволил определить потенциальные направления будущих исследований.
О безопасности одно- и многоместных IFP-операторов
Get PDFIn this paper, we investigate the safety of unary inflationary fixed point operators (IFPoperators). The safety is a computability in finitely many steps. IFP-operators exactly correspond to recursive SQL-queries hence this problem has a value for database theory. The problem appears from the fact that if recursive queries contain universe functions and relations, then its execution can fall into an infinite loop. Moreover, universal computational devices (Turing machines et al.) can be modelled by such queries. Hence the problem of the finite computability for such queries is undecidable. In our previous works we established some properties of a universe which imply the finite computability of all IFP-operators in the universe. Here, we investigate a connection between an arity of IFP-operators and their safety. We prove that some results for general IFP-operators don’t hold for unary ones. We construct a universe where all unary unnesed IFP-operators are safe. But in this universe there exist unsafe nested unary IFP-operators and unsafe unnested binary IFP-operators. This differs from general IFP-operators because in general case the safety of all unnesed IFP-operators implies the safety of all IFP-operators. Also there exist elementary equivalent universes where some unary unnesed IFPoperators become unsafe. For general IFP-operators it is also impossible.В работе изучается безопасность унарных операторов инфляционной неподвижной точки (IFP-операторов), то есть возможность их вычисления за конечное время. Такие операторы в точности соответствуют рекурсивным SQL-запросам, поэтому изучаемый вопрос имеет непосредственное отношение к базам данных. Исследуемая проблема возникает из-за того, что при одновременном применении в SQL запросе рекурсии и отношений универсума, например, сложения, может оказаться так, что процедура вычисления результата запроса зациклится. Более того, такая комбинация позволяет моделировать работу универсального вычислительного устройства, например, машины Тьюринга, поэтому вопрос о возможности вычисления SQL запроса за конечное время оказывается алгоритмически неразрешимым. В предыдущих работах были введены и изучены некоторые свойства универсумов, которые позволяют гарантировать возможность вычисления любых запросов за конечное время. Здесь мы изучаем вопрос о том, насколько существенна местность IFP-операторов в контексте их безопасности. Основным результатом настоящей работы является демонстрация того, что если ограничиться только унарными IFP-операторами, то не имеют места результаты, справедливые для IFP-операторов в общем случае без ограничения местности. Построен пример универсума, в котором все унарные IFP-операторы, не вложенные один в другой, безопасны. Вместе с тем в этом универсуме существуют небезопасные бинарные IFPоператоры, таким образом, при изменении местности безопасность может утрачиваться. Кроме того, существуют и небезопасные вложенные один в другой унарные операторы. Это контрастирует с общим случаем, в котором такое невозможно. Также существуют элементарно эквивалентные универсумы, в которых те же самые унарные IFP-операторы безопасными не являются. Такое поведение тоже отличается от поведения IFP-операторов произвольной местности
Векторное представление слов с семантическими отношениями: экспериментальные наблюдения
Get PDFThe ability to identify semantic relations between words has made a word2vec model widely used in NLP tasks. The idea of word2vec is based on a simple rule that a higher similarity can be reached if two words have a similar context. Each word can be represented as a vector, so the closest coordinates of vectors can be interpreted as similar words. It allows to establish semantic relations (synonymy, relations of hypernymy and hyponymy and other semantic relations) by applying an automatic extraction. The extraction of semantic relations by hand is considered as a time-consuming and biased task, requiring a large amount of time and some help of experts. Unfortunately, the word2vec model provides an associative list of words which does not consist of relative words only. In this paper, we show some additional criteria that may be applicable to solve this problem. Observations and experiments with well-known characteristics, such as word frequency, a position in an associative list, might be useful for improving results for the task of extraction of semantic relations for the Russian language by using word embedding. In the experiments, the word2vec model trained on the Flibusta and pairs from Wiktionary are used as examples with semantic relationships. Semantically related words are applicable to thesauri, ontologies and intelligent systems for natural language processing.Возможность идентификации семантической близости между словами сделала модель word2vec широко используемой в NLP-задачах. Идея word2vec основана на контекстной близости слов. Каждое слово может быть представлено в виде вектора, близкие координаты векторов могут быть интерпретированы как близкие по смыслу слова. Таким образом, извлечение семантических отношений (отношение синонимии, родо-видовые отношения и другие) может быть автоматизировано. Установление семантических отношений вручную считается трудоемкой и необъективной задачей, требующей большого количества времени и привлечения экспертов. Но среди ассоциативных слов, сформированных с использованием модели word2vec, встречаются слова, не представляющие никаких отношений с главным словом, для которого был представлен ассоциативный ряд. В работе рассматриваются дополнительные критерии, которые могут быть применимы для решения данной проблемы. Наблюдения и проведенные эксперименты с общеизвестными характеристиками, такими как частота слов, позиция в ассоциативном ряду, могут быть использованы для улучшения результатов при работе с векторным представлением слов в части определения семантических отношений для русского языка. В экспериментах используется обученная на корпусах Флибусты модель word2vec и размеченные данные Викисловаря в качестве образцовых примеров, в которых отражены семантические отношения. Семантически связанные слова (или термины) нашли свое применение в тезаурусах, онтологиях, интеллектуальных системах для обработки естественного языка
Математическая модель подключения оптимального числа потенциальных потребителей тепла к тепловой сети
Get PDFIn the modern world, the efficient use of energy is an extremely important aspect of human activity. In particular, heat supply systems have significant economic, environmental and social importance for both heat consumers and heat supply organizations. The economic status of all participants in the heat supply process depends on the efficiency of the functioning of the heat supply systems. The reliability of the functioning of systems depends on vital processes such as the work of hospitals and industrial enterprises. With such a close network communication, reliable and efficient operation of power supply systems is critical. In this article, ways to improve the efficiency of heat supply systems are considered. A mathematical model for improved planning of heat supply systems by connecting the optimal set of new heat consumers is presented. For each single customer, when there is an alternative option for connecting this consumer to the existing heat network, it is possible to choose the only optimal solution. This becomes possible due to the restrictions and the procedure for selecting variants from a subset of binary variables corresponding to alternatives. The procedure for finding the optimal number of consumers for connection to the existing heat network is presented, which is the rationale for increasing the number of existing consumers of the heat network. The testing was carried out and the results of the mathematical model by an example of test heat networks are presented. Directions of further study of increasing the efficiency of heat supply systems and integrating the presented mathematical model with modern software complexes are determined.В современном мире эффективное использование энергоносителей является крайне важным аспектом человеческой деятельности. В частности, системы теплоснабжения имеют значительное экономическое, экологическое и социальное значение как для потребителей тепла, так и для теплоснабжающих организаций. От эффективности функционирования систем теплоснабжения зависит экономическое состояние всех участников процесса теплоснабжения. От надежности функционирования систем зависят жизненно важные процессы, такие как работа больниц и промышленных предприятий. При такой тесной сетевой коммуникации критически важно безотказное и эффективное функционирование систем энергоснабжения. В данной статье рассмотрены пути повышения эффективности работы систем теплоснабжения. Представлена математическая модель для планирования работы систем теплоснабжения путем подключения оптимального множества новых потребителей тепла. Для отдельно взятого потенциального потребителя, каждый раз, когда возникает альтернативный вариант подключения этого потребителя к существующей тепловой сети, возможно выбрать единственное оптимальное решение. Это становится возможно за счет наложения ограничений и процедуры отбора вариантов из подмножества бинарных переменных, соответствующих альтернативам. Представлена процедура поиска оптимального числа потребителей для подключения к существующей тепловой сети, являющаяся обоснованием для увеличения числа существующих потребителей. Проведено тестирование и представлены результаты работы математической модели на примере тестовых тепловых сетей, сконфигурированных на основе ручного ввода основных условий и параметров работы. Определены направления дальнейших исследований по повышению эффективности систем теплоснабжения и интеграции представленной математической модели с современными программными комплексами.
Оптимизация инварианта цикла в языке Пифагор
Get PDFThe paper considers methods of program transformation equivalent to optimizing the cycle invariant, applied to the functional data-flow model implemented in the Pifagor programming language. Optimization of the cycle invariant in imperative programming languages is reduced to a displacement from the cycle of computations that do not depend on variables that are changes in the loop. A feature of the functional data flow parallel programming language Pifagor is the absence of explicitly specified cyclic computations (the loop operator). However, recurring calculations in this language can be specified recursively or by applying specific language constructs (parallel lists). Both mechanisms provide the possibility of parallel execution. In the case of optimizing a recursive function, repeated calculations are carried out into an auxiliary function, the main function performing only the calculation of the invariant. When optimizing the invariant in computations over parallel lists, the calculation of the invariant moves from the function that executes over the list items to the function containing the call. The paper provides a definition of ”invariant” applied to the Pifagor language, algorithms for its optimization, and examples of program source codes, their graph representations (the program dependence graph) before and after optimization. The algorithm shown for computations over parallel lists is applicable only to the Pifagor language, because it rests upon specific data structures and the computational model of this language. However, the algorithm for transforming recursive functions may be applied to other programming languages.В работе рассматриваются методы преобразования программ, эквивалентные оптимизации инварианта цикла, применительно к функционально-потоковой модели параллельных вычислений, реализованной в языке программирования Пифагор. В императивных языках при оптимизации инварианта из цикла выносятся вычисления, не зависящие от изменяемых в нем переменных. Особенностью языка функционально-потокового параллельного программирования Пифагор является отсутствие явно задаваемых циклических вычислений (оператора цикла). Тем не менее, повторяющиеся вычисления в этом языке можно задать рекурсивно или за счет применения специфических языковых конструкций (параллельных списков). Оба механизма обеспечивают возможность параллельного выполнения. В случае оптимизации рекурсивной функции повторяющиеся операции выносятся во вспомогательную функцию, а основная функция выполняет лишь вычисление инварианта. При оптимизации внутри параллельных списков вычисление инварианта перемещается в дополнительную функцию, содержащую вызов функции, использующую данный параллельный список. В статье приводится определение «инварианта» применительно к языку Пифагор, алгоритмы его оптимизации, а также примеры программ, их графовых представлений (граф программных зависимостей) до и после оптимизации. Алгоритм оптимизации, описанный для вычислений над параллельными списками, применим только для языка Пифагор, так как опирается на специфические структуры данных и модель вычислений этого языка. Вместе с тем, алгоритм преобразования рекурсивных функций может быть применим и для других языков программирования
Онтология процессов, ориентированная на верификацию
Get PDFThis paper presents the ontology of the concurrent processes close to Hoare communicating sequential processes. It is the part of the intellectual system for supporting verification of behavioural properties of these processes. Our ontological representation of the processes is oriented both to the application of formal verification methods and to the extraction of information from technical documentation (by our previously developed system of information extraction from a natural language text). We describe the ontology classes and domains that define communicating concurrent processes. These processes are characterized by sets of local and shared variables, a list of actions on these variables which change their values, a list of channels for the process communication (which, in turn, are characterized by the type of reading messages, capacity, ways of writing and reading, and reliability), and also a list of communication actions for sending messages. In addition to the formal mathematical definition of classes and domains of the ontology, examples of descriptions of some ontological classes as well as typical properties and axioms for them are specified in the editor Prot ́eg ́e in the OWL language with the use of the inference rules in the SWRL language. The formal operational semantics of communicating processes is determined on their ontological representation and is given as a labelled transition system. It is reduced to the local operational semantics of separate process instances in the interleaving model. We specialize several types of processes from the subject domain of automatic control systems that model the typical functional elements of the automatic control system (sensors, comparators and regulators) as well as their combinations. The concepts of the specialized ontology are illustrated by the example of a control part for a bottle-filling system.В статье представлена онтология процессов, близких взаимодействующим последовательным процессам Хоара. Она является частью интеллектуальной системы поддержки верификации свойств поведения таких процессов. Наше онтологическое представление процессов ориентировано как на применение формальных методов верификации, так и на извлечение информации из технической документации (с помощью нашей ранее разработанной системы извлечения информации из текстов на естественном языке). Мы описываем классы и домены онтологии, которые определяют взаимодействующие процессы. Эти процессы характеризуются множествами локальных и разделяемых переменных, списком действий над этими переменными, которые изменяют их значения, списком каналов взаимодействия процессов (которые, в свою очередь, характеризуются типом чтения сообщений, емкостью, способами записи и считывания, а также надежностью), списком коммуникационных действий для отправки сообщений. Помимо формального математического определения классов и доменов онтологии, приведены примеры описаний некоторых онтологических классов, а также типовых свойств и аксиом для них в редакторе Prot ́eg ́e на языке OWL с использованием правил вывода на языке SWRL. Для онтологического представления взаимодействующих процессов определяется их формальная операционная семантика, которая задается с использованием помеченной системы переходов. В интерливинговой модели она сводится к локальной операционной семантике отдельных экземпляров процессов. Представлена специализация онтологии для некоторых типов процессов из предметной области систем автоматического управления, моделирующих типовые функциональные элементы системы автоматического управления (датчики, сравнивающие устройства и регулирующие устройства), а также их комбинации. Понятия специализированной онтологии иллюстрируются на примере управляющей части системы розлива бутылок