Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
Автоматизированный поиск и анализ стилометрических характеристик, описывающих стиль прозы 19-21 веков
Get PDFThe article is devoted to comparison of stylometric features of several levels, which are markers of the style of the prose text and analysis of the stylistic changes in Russian and British prose of the 19th-21st centuries. Stylometric features include the low-level features based on the words and symbols and high-level based on rhythmic. These features model the style of a text and are the indicators of the time when the text was created.Calculations of all the features are performed completely automatically, so it allows to conduct the large-scale experiments with artworks of a large volume and speeds up the work of a linguist. To calculate the stylometric features including ones based on the search results for rhythmic figures the ProseRhythmDetector program is used. As a result of its work, each text is presented as a set of the same features of three levels: characters, words, rhythm. Texts are combined by decades, for each decade there are found average values of stylometric features. The obtained models of decades are compared using standard similarity metrics, results of comparison are visualized in the form of the heat maps and dendrograms. Experiments with two corpora of Russian and British texts show that during the 19th-21st centuries there are general trends in style change for both corpora, for example, a decrease in the number of rhythmic figures per sentence, and also particular trends for each language, for example, dynamics of change of the word and sentence lengths. Stylometric features of all levels reveal the similarity in the style of texts published in one century. Also, features of three levels in the complex better demonstrate the uniqueness of each decade than features of a particular level. This study shows the importance of stylometric features as style markers of the different eras and allows us to identify trends in style during several centuries.Статья посвящена сравнению стилометрических характеристик нескольких уровней, являющихся маркерами стиля прозаического текста, и анализу стилистических изменений русской и британской прозы 19-21 веков. Стилометрические характеристики включают в себя низкоуровневые характеристики, основанные на словах и символах, и высокоуровневые — ритмические. Подобные характеристики моделируют стиль текста и являются индикаторами времени его создания.Вычисление всех характеристик происходит полностью автоматически, что позволяет проводить крупные эксперименты с художественными произведениями большого объёма и ускоряет работу эксперта-лингвиста. Для подсчёта стилометрических характеристик, в том числе основанных на результатах поиска ритмических средств, используется программа ProseRhythmDetector. В результате её работы каждый текст представляется в виде набора одних и тех же характеристик трёх уровней: символов, слов, ритма. Тексты объединяются по десятилетиям, для каждого десятилетия находятся средние значения стилометрических характеристик. Полученные модели десятилетий сравниваются при помощи стандартных метрик близости, результаты сравнения визуализируются в виде тепловых карт и дендрограмм. Эксперименты с двумя корпусами русских и британских текстов показывают, что в течение 19-21 веков появляются как общие тенденции изменения стиля для обоих корпусов, например, уменьшение количества ритмических средств в расчёте на одно предложение, так и собственные для каждого языка, например, динамика изменения длин слов и предложений. Стилометрические характеристики всех уровней выявляют схожесть стиля текстов, опубликованных в одном веке. Также характеристики трёх уровней в комплексе лучше демонстрируют уникальность каждого десятилетия, чем характеристики конкретного уровня. Это исследование показывает значимость стилометрических характеристик как маркеров стиля различных эпох и позволяет выявить тенденции изменения стиля на протяжении нескольких веков
Об одном разбиении отрезка, применяемом для оценки энтропии
Get PDFLet be a partition of the interval defines as\begin{array}{l}Q_1 =\{0,q^2,q,1\}. \\Q_{n+1}' = qQ_n \cap q^2Q_n, \ \Q_{n+1}'' = q^2+qQ_n \cap qQ_n, \ \Q_{n+1}'''= q^2+qQ_n \cap q+q^2Q_n, \\Q_{n+1} = Q_{n+1}'\cup Q_{n+1}'' \cup Q_{n+1}''', \end{array}where .The sequence defines as follows.where are Fibonacci numbers ().The main result of this paper.where .В работе изучается разбиение отрезка, которое строится по следующему правилу:\begin{array}{l}Q_1 =\{0,q^2,q,1\}. \\Q_{n+1}' = qQ_n \cap q^2Q_n, \ \Q_{n+1}'' = q^2+qQ_n \cap qQ_n, \ \Q_{n+1}'''= q^2+qQ_n \cap q+q^2Q_n, \\Q_{n+1} = Q_{n+1}'\cup Q_{n+1}'' \cup Q_{n+1}''', \end{array}где .Введем последовательность чисел , положивгде - числа Фибоначчи ().Основной результат работы.где
Метод совместной кластеризации в графовом и корреляционном пространствах
Get PDFNetwork algorithms are often used to analyze and interpret the biological data. One of the widely used approaches is to solve the problem of identifying an active module, where a connected subnetwork of a biological network is selected which best reflects the difference between the two considered biological conditions. In this work this approach is extended to the case of a larger number of biological conditions and the problem of the joint clustering in network and correlation spaces is formulated.To solve this problem, an iterative method is proposed at takes as the input graph G and matrix X, in which the rows correspond to the vertices of the graph. As the output, the algorithm produces a set of subgraphs of the graph G so that each subgraph is connected and the rows corresponding to its vertices have a high pairwise correlation. The efficiency of the method is confirmed by an experimental study on the simulated data.Алгоритмы на графах часто используются для анализа и интерпретации биологических данных. Одним из широко используемых подходов является решение задачи поиска активного модуля, в которой в графе биологических взаимодействий выделяется связный подграф, лучше всего отражающий разницу между двумя рассматриваемыми биологическими состояниями. В настоящей работе этот подход расширяется на случай большего числа биологических состояний и формулируется задача совместной кластеризации в графовом и корреляционном пространстве.Для решения этой задачи предлагается итеративный метод, принимающий на вход граф G и матрицу X, в которой строки соответствуют вершинам графа. На выходе алгоритм выдает набор подграфов графа G так, что каждый подграф является связным и строки, соответствующие его вершинам, обладают высокой попарной корреляцией.Эффективность метода подтверждается экспериментальным исследованием на смоделированных данных
Алгоритм оценки максимального времени отклика задач в многопроцессорных системах с интервальной неопределенностью длительности выполнения работ
Get PDFThe paper presents an algorithm for the worst case response time (WCRT) estimation for multiprocessor systems with fixed-priority preemptive schedulers and the interval uncertainty of tasks execution times. Each task has a unique priority within its processor, a period, an execution time interval [BCET, WCET] and can have data dependency on other tasks. If a decrease in the execution time of the task A can lead to an increase in the response time of the another task B, then task A is called an anomalous task for task B. According to the chosen approach, in order to estimate a task’s WCRT, two steps should be performed. The first one is to construct a set of anomalous tasks using the proposed algorithm for the given task. The paper provides the algorithm and the proof of its correctness. The second one is to find the WCRT estimation using a genetic algorithm. The proposed approach has been implemented software as a program in Python3. A set of experiments have been carried out in order to compare the proposed method in terms of precision and speed with two well-known WCRT estimating methods: the method that does not take into account interval uncertainty (assuming that the execution time of a given task is equal to WCET) and the brute force method. The results of the experiments have shown that, in contrast to the brute force method, the proposed method is applicable to the analysis of the real scale computing systems and also allows to achieve greater precision than the method that does not take into account interval uncertainty.В данной статье предложен алгоритм оценки максимального времени отклика задач (Worst Case Response Time — WCRT) в многопроцессорных системах с планировщиками с приоритетом и вытеснением и интервальной неопределенностью длительности выполнения работ. Между задачами имеются зависимости по данным. Для каждой задачи задан приоритет, период и интервал [BCET, WCET], которому принадлежит время выполнения на процессоре работ этой задачи. Если уменьшение времени выполнения задачи A может привести к увеличению времени отклика задачи B, то задача A называется аномальной задачей для задачи B. Согласно выбранному авторами подходу, для получения оценки WCRT некоторой задачи необходимо выполнить два шага. На первом шаге с помощью предложенного в работе алгоритма осуществляется построение множества задач, аномальных для заданной задачи. Приведено доказательство корректности этого алгоритма. На втором шаге с помощью генетического алгоритма выполняется поиск WCRT. Пространство поиска — множество всевозможных наборов длительностей выполнения аномальных задач. Было разработано инструментальное средство на языке Python3, реализующее предложенный подход. Проведено экспериментальное исследование, в ходе которого предложенный метод сравнивался по точности и скорости с двумя известными методами оценки WCRT: методом, не учитывающим интервальную неопределенность, т.е. предполагающим, что время выполнения всех работ равно WCET, а также с переборным методом. Экспериментальное исследование показало, что в отличие от переборного метода, предложенный метод применим для анализа вычислительных систем реальной размерности, а также позволяет достичь большей точности, чем метод, не учитывающий интервальную неопределенность
Параллельный алгоритм решения задачи об изоморфизме графов
Get PDFIn this paper, we offer an efficient parallel algorithm for solving the Graph Isomorphism Problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected graphs without loops and multiple edges, it is assumed that the graphs can be disconnected. e question of the existence or absence of an algorithm for solving this problem with polynomial complexity is currently open. Therefore, as for any time-consuming task, the question arises of accelerating its solution by parallelizing the algorithm. We used the RPM ParLib library developed by the author as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network in the .NET Framework. Such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support for the .NET Framework can be used as a programming language in conjunction with this library. For our experiments, we developed some C# applications using this library. The main purpose of these experiments was to study the acceleration achieved by recursive-parallel computing. Specially generated random regular graphs with varying degrees of vertices were used as initial data. A detailed description of the algorithm and its testing, as well as the results obtained, are also given in the paper.В данной работе предлагается параллельный алгоритм решения задачи об изоморфизме графов. Целевым результатом для нас выступает построение подходящей подстановки вершин, либо доказательство отсутствия таковой. Задача решается для неориентированных графов без петель и кратных ребер, допускается, что графы могут быть несвязными. Вопрос о существовании либо отсутствии алгоритма с полиномиальной трудоемкостью в настоящее время является открытым. Следовательно, как и для любой трудоемкой задачи, возникает вопрос об ускорении ее решения за счет распараллеливания алгоритма. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Для решения нашей задачи и проведения численного эксперимента было разработано несколько приложений на языке C#. Целью эксперимента было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. В качестве исходных данных использовались специально сгенерированные случайные регулярные графы с различной степенью вершин. Подробное описание алгоритма и эксперимента, а также полученные результаты также приводятся в работе
Правило «одной пятой» с возвратами для настройки размера популяции в генетическом алгоритме (1 + (λ,λ))
Get PDFSelf-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ,λ)) genetic algorithm, where adaptation of the population size helps to achieve the linear running time on the OneMax problem. However, on problems which interfere with the assumptions behind the self-adjustment procedure, its usage can lead to the performance degradation. In particular, this is the case with the “one-fifth rule” on problems with weak fitness-distance correlation.We propose a modification of the “one-fifth rule” in order to have less negative impact on the performance in the cases where the original rule is destructive. Our modification, while still yielding a provable linear runtime on OneMax, shows better results on linear function with random weights, as well as on random satisfiable MAX-3SAT problems.Известно, что настройка параметров может существенно улучшить время работы эволюционных алгоритмов.Ярким примером этого является генетический алгоритм (1 + (λ,λ)), где адаптация размера популяции в процессе работы помогает достичь линейного времени работы на задаче OneMax. Однако если свойства решаемой задачи вступают в конфликт с принципами работы используемого метода настройки параметров, производительность эволюционного алгоритма может существенно ухудшаться. Так, например, происходит при использовании правила «одной пятой» в упомянутом алгоритме при решении задач со слабой корреляцией между приспособленностью и расстоянием до оптимума.В данной работе предлагается модификация правила «одной пятой», существенно снижающая отрицательные эффекты от его использования при их наличии. Показывается, что данная модификация также достигает линейного времени работы на задаче OneMax, при этом ее использование приводит к улучшению производительности на линейных псевдобулевых функциях со случайными весами, а также на некотором классе задач MAX-3SAT
Архитектура формально-верифицированной системы распределенного реестра InnoChain
Get PDFIn this paper we consider the software architecture of InnoChain, a distributed ledger system (DLS) with 5 levels of formal verification, including a formally-verified underlying operating system (OS). The objective of this architecture is to achieve a higher level of DLS dependability compared to more traditional software architectures and quality assurance (QA) methods. The architecture of InnoChain includes (1) a programming language for smart contracts which is a domain-specific language with formal semantics embedded into CakeML, which is a functional language ofthe ML family; this allows us to carry out formal verification of smart contracts' correctness properties using higher-order logic systems, such as HOL4; (2) trusted compilation of smart contracts into the machine code using the verified compiler available for CakeML, rather than relying on a virtual machine for execution of smart contracts; (3) using CakeML for implementation of InnoChain node functionality which allows for formal verification of code correctness and trusted compilation into the machine code; (4) formal verification of the consensus protocol used InnoChain, namely HotStuff BFT; (5) using seL4, a formally-verified microkernel, as the underlying OS for InnoChain instead of more traditional general-purpose OSes such as Linux. The proposed verified architecture will allow InnoChain to be used in mission-critical applications, such as the decentralized Aircraft Fuelling Control System which is currently under development for JSC Aeroflot, the Russian national air carrier.В настоящей работе рассматривается архитектура системы распределенного реестра (СРР) InnoChain. Основной целью этой архитектуры является реализуемость 5-ти уровней формальной верификации программного обеспечения (ПО) системы InnoChain, включая операционное окружение. Методы формальной верификации являются основными методами обеспечения качества ПО с критическими требованиями по надежности, но до сих пор онине находилиширокого применения в СРР. Архитектура InnoChain включает (1) предметно-ориентированный язык смарт-контрактов с формальной семантикой, встроенный в функциональный язык CakeML (диалект языка ML), что позволяет осуществлять формальную верификацию свойств корректности смарт-контрактов в системах логики высших порядков (например, HOL4); (2) верифицированную трансляцию смарт-контрактов в машинный код с использованием компилятора CakeML вместо использования виртуальных машин для исполнения смарт-контрактов; (3) реализацию функционала узла СРР также на CakeML с формальной верификацией свойств корректности и с верифицированной трансляцией исходного кода узла в машинный код; (4) формальную верификацию протокола консенсуса СРР (HotStuff BFT); (5) использование формально-верифицированного микроядра seL4 в качестве операционного окружения СРР вместо операционных систем общего назначения. Предлагаемая архитектура открывает возможности для использования СРР InnoChain в критических по надежности приложениях, в частности, в системе управления заправкой воздушных судов ПАО Аэрофлот
Исследование свойств АГ-кодов как кодов для защиты от копирования
Get PDFTraceability schemes which are applied to the broadcast encryption can prevent unauthorized parties from accessing the distributed data. In a traceability scheme a distributor broadcasts the encrypted data and gives each authorized user unique key and identifying word from selected error-correcting code for decrypting. The following attack is possible in these schemes: groups of c malicious users are joining into coalitions and gaining illegal access to the data by combining their keys and identifying codewords to obtain pirate key and codeword. To prevent this attacks, classes of error-correcting codes with special c-FP and c-TA properties are used. In particular, c -FP codes are codes that make direct compromise of scrupulous users impossible and c -TA codes are codes that make it possible to identify one of the aackers. We are considering the problem of evaluating the lower and the upper boundaries on c, within which the L-construction algebraic geometric codes have the corresponding properties. In the case of codes on an arbitrary curve the lower bound for the c-TA property was obtained earlier; in this paper, the lower bound for the c-FP property was constructed. In the case of curves with one infinite point, the upper bounds for the value of c are obtained for both c-FP and c-TA properties. During our work, we have proved an auxiliary lemma and the proof contains an explicit way to build a coalition and a pirate identifying vector. Methods and principles presented in the lemma can be important for analyzing broadcast encryption schemes robustness. Also, the c-FP and c-TA boundaries monotonicity by subcodes are proved.Схемы специального широковещательного шифрования используются для защиты легально тиражируемой цифровой продукции от несанкционированного копирования. В таких схемах распространитель тиражирует данные свободно в зашифрованном виде, а для расшифрования выдаёт каждому легальному пользователю уникальный набор ключей и идентифицирующих векторов из некоторого помехоустойчивого кода. Однако, в этих схемах возможна атака, в ходе которой группы из c недобросовестных пользователей могут объединяться в коалиции и получать нелегальный доступ к данным, комбинируя выданную им ключевую информацию для получения пиратской ключевой информации — идентификационного вектора и ключа. Для борьбы с коалиционными атаками применяются классы помехоустойчивых кодов, обладающих специальными c-FP и c-TA свойствами. Класс c-FP-кодов составляют коды, исключающие возможность прямой компрометации добросовестных пользователей, а класс c-TA-кодов составляют коды, позволяющие гарантированно определить одного из злоумышленников. Рассматривается задача нахождения нижних и верхних границ значения величины c, в пределах которых алгеброгеометрические коды L-конструкции обладают соответствующими свойствами. В лучае кодов на произвольной кривой ранее была получена нижняя граница для свойства c-TA, в настоящей работе построена нижняя граница для свойства c-FP. В случае кривых с одной бесконечной точкой получены верхние границы значения c как для c-FP, так и для c-TA свойств. При нахождении этих границ получена вспомогательная конструктивная лемма, в доказательстве которой содержится явный способ построения коалиции и пиратского идентификационного вектора; этот способ важен при анализе стойкости схем широковещательного шифрования. Доказаны свойства монотонности рубежей c-FP и c-TA свойств по подкодам
Исправление к статье: В. А. Соколов, “О проблеме существования конечных базисов тождеств в алгебрах рекурсивных функций”, Моделирование и анализ информационных систем, Том. 27, № 3, с. 304-315, 2020. DOI: https://doi.org/10.18255/1818-1015-2020-3-304-315
Get PDFThe author regrets that in the original list the references [3] and [4] are in the wrong places and they should be rearranged. In addition, [3] has the wrong article title. The corrected reference list is shown below.The author would like to apologize for an inconvenience caused.References[1] A. I. Mal'tsev, “Constructive algebras I”, Russian Mathematical Surveys, vol. 16, no. 3, pp. 77-129, 1961.[2] A. I. Mal'tsev, Algoritmy i rekursivnye funktsii. Moscow: Nauka, 1965, In Russian.[3] R. M. Robinson, “Primitive recursive functions”, Bulletin of the American Mathematical Society, vol. 53, no. 10,pp. 925-942, 1947.[4] J. Robinson, “General recursive functions”, Proceedings of the American Mathematical Society, vol. 1, no. 6,pp. 703-718, 1950.[5] V. A. Sokolov, “Ob odnom klasse tozhdestv v algebre Robinsona”, in 14-ya Vsesoyuznaya algebraicheskaya konferentsiya: tezisy dokladov, In Russian, vol. 2, Novosibirsk, 1977, pp. 123-124.[6] P. M. Cohn, Universal Algebra. New York, Evanston, and London: Harper & Row, 1965.[7] A. Robinson, “Equational logic for partial functions under Kleene equality: a complete and an incomplete set of rules”, The Journal of Symbolic Logic, vol. 54, no. 2, pp. 354-362, 1989.Автор сожалеет, что в исходном списке ссылки [3] и [4] находятся в неправильных местах и их следует переставить.Кроме того, [3] содержит ошибку в названии статьи. Исправленный список цитируемых источников приведен ниже. Автор приносит извинения за причиненные неудобства.References[1] A. I. Mal'tsev, “Constructive algebras I”, Russian Mathematical Surveys, vol. 16, no. 3, pp. 77-129, 1961.[2] A.I. Mal'tsev, Algoritmy i rekursivnye funktsii. Moscow: Nauka, 1965, In Russian.[3] R. M. Robinson, “Primitive recursive functions”, Bulletin of the American Mathematical Society, vol. 53, no. 10, pp. 925-942, 1947.[4] J. Robinson, “General recursive functions”, Proceedings of the American Mathematical Society, vol. 1, no. 6, pp. 703-718, 1950.[5] V.A. Sokolov, “Ob odnom klasse tozhdestv v algebre Robinsona”, in 14-ya Vsesoyuznaya algebraicheskaya konferentsiya: tezisy dokladov, In Russian, vol. 2, Novosibirsk, 1977, pp. 123-124.[6] P. M. Cohn, Universal Algebra. New York, Evanston, and London: Harper & Row, 1965.[7] A. Robinson, “Equational logic for partial functions under Kleene equality: a complete and an incomplete set of rules”, The Journal of Symbolic Logic, vol. 54, no. 2, pp. 354-362, 1989