Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа
Get PDFIn this paper, we study the two-step colouring problem for an undirected connected graph. It is required to colour the graph in a given number of colours in a way, when no pair of vertices has the same colour, if these vertices are at a distance of 1 or 2 between each other. Also the corresponding recognition problem is set. The problem is closely related to the classical graph colouring problem. In the article, we study and prove the polynomial reduction of the problems to each other. So it allows us to prove NP-completeness of the problem of two-step colouring. Also we specify some of its properties. Special interest is paid to the problem of two-step colouring in application to rectangular grid graphs. The maximum vertex degree in such a graph is between 0 and 4. For each case, we elaborate and prove the function of two-vertex colouring in the minimum possible number of colours. The functions allow each vertex to be coloured independently from others. If vertices are examined in a sequence, colouring time is polynomial for a rectangular grid graph.В данной статье рассматривается задача о двухшаговой раскраске произвольного неориентированного связного графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Также в работе ставится соответствующая задача распознавания. Данная задача тесно связана с классической задачей о раскраске графа. В статье рассматривается и обосновывается полиномиальное сведение задач друг к другу. В частности, это позволяет доказать NP-полноту задачи о двухшаговой раскраске. Кроме того, определяются некоторые ее свойства. Отдельно исследуется задача о двухшаговой раскраске в приложении к прямоугольным графам решетки. Максимальная степень вершины таких графов может принимать значение от 0 до 4, и для каждого возможного случая была определена и обоснована функция двухшаговой раскраски в минимальное число цветов. Полученные функции строятся таким образом, что каждая вершина графа может быть раскрашена независимо от остальных, а время раскраски прямоугольного графа решетки полиномиально при последовательном переборе вершин
Система распределения ключей на дизайнах
Get PDFThe problem of key distribution in a community for providing secure communication between its participants is studied. To solve this problem, key predistribution systems can be used, in which each user receives some key information that can later be used to independently calculate required shared secret keys for conferences they participate in. Such key distribution systems can be based on different structures, such as error-correcting codes and combinatorial designs. The drawback of such systems is the possibility of collusive attacks, when traitors within the system can form a coalition and use their key information to try to calculate shared secret keys of other users. But the secrecy of keys is guaranteed by the system when the number of traitors in the coalition does not exceed a threshold defined by the system structure. In this paper, a key distribution system is based on combinatorial designs and, in particular, on Hadamard 3-design that guarantees the secrecy of communications in the presence of coalitions with less than three users. New notions of combinatorial span and combinatorial rank of a subset of Hadamard code that are required for the study of the resilience of the system to collusive attacks are introduced. The probability of successful collusive attack on an arbitrary conference against the cardinality of coalition is calculated for this system.Изучается актуальная задача распределения ключей в сообществе для обеспечения безопасности переписки между ее участниками. Для решения этой задачи могут рассматриваться системы предварительного распределения ключей в сообществе, при этом каждый пользователь получает некоторую ключевую информацию, на основе которой он затем может независимо от других участников системы вычислить необходимые общие секретные ключи для тех конференций, в которые он входит. Такие системы предварительного распределения ключей могут быть основаны на разных базовых структурах, в частности, на помехоустойчивых кодах и комбинаторных дизайнах. Слабостью подобных систем является возможность проведения коалиционных атак, когда недобросовестные пользователи системы могут объединиться в коалицию и на основе всей имеющейся у них ключевой информации попытаться вычислить общие секретные ключи других участников сообщества. Однако системой гарантируется безопасность ключей в случае, если мощность коалиции злоумышленников не превышает некоторого значения, которое определяется конструкцией системы.В работе рассматривается разработанная нами система распределения ключей, основанная на комбинаторных дизайнах, а именно на 3-дизайнах Адамара, гарантирующая безопасность переписки пользователей при наличии коалиции из не более чем двух злоумышленников. Для исследования стойкости системы к коалиционным атакам в случае превышения предусмотренного значения мощности коалиции вводятся новые понятия комбинаторной оболочки и комбинаторного ранга подмножества кода Адамара и изучаются некоторые комбинаторные свойства кодов Адамара. Для построенной системы распределения ключей вычисляется вероятность успешного проведения коалиционной атаки на произвольную конференцию в зависимости от мощности коалиции злоумышленников
Методы специализации онтологии процессов, ориентированной на верификацию
Get PDFUser-friendly formal specifications and verification of parallel and distributed systems from various subject fields, such as automatic control, telecommunications, business processes, are active research topics due to its practical significance. In this paper, we present methods for the development of verification-oriented domain-specific process ontologies which are used to describe parallel and distributed systems of subject fields. One of the advantages of such ontologies is their formal semantics which make possible formal verification of the described systems. Our method is based on the abstract verification-oriented process ontology. We use two methods of specialization of the abstract process ontology. The declarative method uses the specialization of the classes of the original ontology, introduction of new declarative classes, as well as use of new axioms system, which restrict the classes and relations of the abstract ontology. The constructive method uses semantic markup and pattern matching techniques to link sublect fields with classes of the abstract process ontology. We provide detailed ontological specifications for these techniques. Our methods preserve the formal semantics of the original process ontology and, therefore, the possibility of applying formal verification methods to the specialized process ontologies. We show that the constructive method is a refinement of the declarative method. The construction of ontology of the typical elements of automatic control systems illustrates our methods: we develop a declarative description of the classes and restrictions for the specialized ontology in the Prot´eg´e system in the OWL language using the deriving rules written in the SWRL language and we construct the system of semantic markup templates which implements typical elements of automatic control systems.Удобная для пользователя формальная спецификация и верификация параллельных и распределённых систем, принадлежащих различным предметным областям, таким как системы автоматического управления, телекоммуникации, бизнес-процессы, являются активными темами исследований в силу их практической значимости. В этой статье мы представляем методы разработки специализированных ориентированных на верификацию онтологий процессов, которые используются для описания параллельных и распределенных систем предметных областей. Одним из преимуществ таких онтологий является их формальная семантика, которая делает возможной формальную верификацию описанных систем. Наш метод основан на абстрактной онтологии процессов, ориентированной на верификацию. Мы используем два метода специализации абстрактной онтологии процессов. Декларативный метод с помощью специализации классов исходной онтологии, введения новых декларативных классов, а также системы аксиом задаёт ограничения для классов и отношений абстрактной онтологии. Конструктивный метод использует техники семантической разметки и сопоставления с образцом, чтобы связать понятия предметной области с классами абстрактной онтологии процессов. Мы даём подробные онтологические спецификации этих техник. Наши методы сохраняют формальную семантику исходной онтологии процессов и, следовательно, возможность применения формальных методов верификации к специализированным онтологиям процессов. Мы показываем, что конструктивный метод является уточнением декларативного метода. Построение онтологии типовых элементов систем автоматического управления иллюстрирует наши методы: разработано декларативное описание классов и ограничений специализированной онтологии в системе Protege на языке OWL с использованием правил вывода на языке SWRL и построена система шаблонов семантической разметки, которая реализует типовые элементы систем автоматического управления
Бифуркация Андронова–Хопфа в одной биофизической модели реакции Белоусова
Get PDFWe consider the problem of mathematical modeling of oxidation-reduction oscillatory chemical reactions based on the Belousov reaction mechanism. The process of the main components interaction in such a reaction can be interpreted by a “predator – prey” model phenomenologically similar to it. Thereby, we consider a parabolic boundary value problem consisting of three Volterratype equations, which is a mathematical model of this reaction. We carry out a local study of the neighborhood of the system non-trivial equilibrium state, define a critical parameter, at which the stability is lost in this neighborhood in an oscillatory manner. Using standard replacements, we construct the normal form of the considering system and the form of its coefficients defining the qualitative behaviour of the model and show the graphical representation of these coefficients depending on the main system parameters. On the basis of it, we prove a theorem on the existence of an orbitally asymptotically stable limit cycle, which bifurcates from the equilibrium state, and find its asymptotics. To identificate the limits of found asymptotics applicability, we compare the oscillation amplitudes of one periodic solution component obtained on the basis of asymptotic formulas and by numerical integration of the model system. Along with the main case of Andronov–Hopf bifurcation, we consider various combinations of normal form coefficients obtained by changing the parameters of the studied system, and the corresponding to them solutions behaviour near the equilibrium state. In the second part of the paper, we consider the problem of the diffusion loss of stability of a spatially homogeneous cycle obtained in the first part. We find a critical value of diffusion parameter, at which this cycle of distributed system loses the stability. В работе рассматривается задача математического моделирования окислительновосстановительных колебательных химических реакций, в основе которых лежит широко известный механизм реакции Белоусова. Процесс взаимодействия основных компонентов в такой реакции может быть интерпретирован феноменологически близкой к ней моделью «хищник – жертва». В связи с этим рассматривается параболическая краевая задача, состоящая из трех уравнений вольтерровского типа, которая представляет собой математическую модель этой реакции. Сначала проводится локальное исследование окрестности нетривиального состояния равновесия системы, определяется критический параметр, при котором в окрестности нетривиального решения колебательным образом теряется устойчивость. С помощью стандартных замен строится нормальная форма изучаемой системы, приводится вид ее коэффициентов, по которым определяется качественное поведение модели, кроме того, построено их графическое представление в зависимости от параметров задачи. Полученная нормальная форма позволяет доказать теорему о существовании орбитально асимптотически устойчивого предельного цикла, ответвляющегося от состояния равновесия, и найти его асимптотику. Для выяснения границ применимости найденной асимптотики проводится сравнение амплитуд колебаний одной из компонент периодического решения, полученных на основе асимптотических формул и путем численного интегрирования модельной системы. Наряду с основным случаем бифуркации Андронова–Хопфа рассмотрены различные комбинации значений коэффициентов нормальной формы, получающиеся при изменении параметров исследуемой системы, и изучено соответствующее им поведение решений вблизи рассматриваемого состояния равновесия. Далее рассмотрена задача о диффузионной потере устойчивости полученного на первом этапе пространственно однородного цикла. Найдено критическое значение параметра диффузии, при котором этот цикл распределенной системы теряет устойчивость
Динамика распределения популяции по ареалам
Get PDFThe problem of selection by the patch population in the absence of information on the utility of the patch, that is, the volume of its energy resources, is considered. This problem relates to the theory of optimal foraging. U. Dieckman proposed an approach to modeling the population patch distribution. The approach is based on a utility function that takes into account the amount of resources in a patch, the population − patch distance, and the measure of information certainty on patch utility. In this case, the Boltzmann distribution is used to describe the population patch distribution. And U. Dieckman considered a static problem that does not take into account the change in the position of the population with time. In this paper, we propose a dynamic system that describes the population patch distribution, which depends on the utility of the patch. In addition the utility varies with time as a result of distance variations. The Boltzmann distribution is a particular solution of the proposed system of differential equations. The Lyapunov stability condition for the Boltzmann distribution is obtained.The utility functions of the patches, which depend on the population − patch distance and on the measure of the information certainty, are introduced. As a result, in the two-dimensional case, a space R2 is divided into areas of preferred utility. Such a partition is a generalization of the Voronoi diagram.Рассматривается задача выбора популяцией ареала в условиях отсутствия у неё полной информации о полезности ареала, то есть об объеме у него энергетических ресурсов. Данная задача относится к теории оптимального фуражирования. У. Дикман (U. Dieckmann) предложил подход к моделированию распределения популяции по ареалам, основанный на функции полезности, учитывающей количество ресурсов в ареале, расстояние от популяции до него и меру информированности популяции о количестве ресурсов в ареале. При этом используется распределение Больцмана для описания распределения популяции по ареалам. Рассматривается статическая задача, не учитывающая изменение положения популяции с течением времени. В настоящей работе предложена динамическая система, описывающая распределение популяции по ареалам, зависящее от полезности ареалов, которая изменяется со временем вследствие изменения расстояния от популяции до ареала. При этом распределение Больцмана является частным решением полученной системы обыкновенных дифференциальных уравнений. Получено условие устойчивости по Ляпунову распределения Больцмана. Введены функции полезности ареалов, зависящие от расстояния до ареала и меры информированности популяции об ареале. В результате, в двумерном случае, пространство R2 разбивается на области предпочтительной полезности. Такое разбиение является обобщением диаграммы Г.Ф. Вороного
Существование и асимптотическая устойчивость периодического решения с внутренним переходным слоем в задаче со слабой линейной адвекцией
Get PDFIn the paper, we study a singularly perturbed periodic in time problem for the parabolic reaction-advection-diffusion equation with a weak linear advection. The case of the reactive term in the form of a cubic nonlinearity is considered. On the basis of already known results, a more general formulation of the problem is investigated, with weaker sufficient conditions for the existence of a solution with an internal transition layer to be provided than in previous studies. For convenience, the known results are given, which ensure the fulfillment of the existence theorem of the contrast structure. The justification for the existence of a solution with an internal transition layer is based on the use of an asymptotic method of differential inequalities based on the modification of the terms of the constructed asymptotic expansion. Further, sufficient conditions are established to fulfill these requirements, and they have simple and concise formulations in the form of the algebraic equation w(x0,t) = 0 and the condition wx(x0,t) < 0, which is essentially a condition of simplicity of the root x0(t) and ensuring the stability of the solution found. The function w is a function of the known functions appearing in the reactive and advective terms of the original problem. The equation w(x0,t) = 0 is a problem for finding the zero approximation x0(t) to determine the localization region of the inner transition layer. In addition, the asymptotic Lyapunov stability of the found periodic solution is investigated, based on the application of the so-called compressible barrier method. The main result of the paper is formulated as a theorem. Исследована сингулярно возмущенная периодическая по времени задача для параболического уравнения реакция-адвекция-диффузия со слабой линейной адвекцией. Рассмотрен случай реактивного члена в виде кубической нелинейности. На основе уже известных результатов исследуется более общая постановка задачи, причем предоставляются более слабые достаточные условия для существования решения с внутренним переходным слоем, чем в предыдущих работах. Для удобства приводятся уже известные результаты, обеспечивающие выполнение теоремы существования контрастной структуры. Обоснование существования решения с внутренним переходным слоем базируется на использовании асимптотического метода дифференциальных неравенств, основанного на модификации членов построенного асимптотического разложения. Далее устанавливаются достаточные условия для выполнения указанных требований, причем они имеют простые и лаконичные формулировки в виде алгебраического уравнения w(x0,t) = 0 и условия wx(x0,t) < 0, по существу являющегося условием того, что корень x0(t) простой, и обеспечивающего устойчивость найденного решения. Функция w является функцией от известных функций, фигурирующих в реактивном и адвективном членах исходной задачи. Уравнение w(x0,t) = 0 представляет собой задачу для нахождения нулевого приближения x0(t) для определения области локализации внутреннего переходного слоя. Кроме того, исследована асимптотическая устойчивость по Ляпунову найденного периодического решения, основанная на применении метода так называемых сжимающихся барьеров. Основной результат работы сформулирован в виде теоремы.
Коды в диэдральной групповой алгебре
Get PDFRobert McEliece developed an asymmetric encryption algorithm based on the use of binary Goppa codes in 1978 and no effective key attacks has been described yet. Variants of this cryptosystem are known due to the use of different codes types, but most of them were proven to be less secure. Code cryptosystems are considered an alternate to number-theoretical ones in connection with the development of quantum computing. So, the new classes of error-correcting codes are required for building new resistant code cryptosystems. Non-commutative codes, which simply are ideals of finite non-commutative group algebras, are an option. The Artin–Wedderburn theorem implies that a group algebra is isomorphic to a finite direct sum of matrix algebras, when the order of the group and the field characteristics are relatively prime. This theorem is important to study the structure of a non-commutative code, but it gives no information about summands and the isomorphism. In case of a dihedral group these summands and the isomorphism were found by F. E. Brochero Martinez. The purpose of the paper is to study codes in dihedral group algebras as and when the order of a group and a field characteristics are relatively prime. Using the result of F. E. Brochero Martinez, we consider a structure of all dihedral codes in this case and the codes induced by cyclic subgroup codes.В 1978 году Р.Мак-Элисом построена первая асимметричная кодовая криптосистема, основанная на применении помехоустойчивых кодов Гоппы, при этом эффективные атаки на секретный ключ этой криптосистемы до сих пор не найдены. К настоящему врмени известно достаточно много кодовых криптосистем, но их криптографическая стойкость уступает стойкости классической криптосистемы Мак-Элиса. В связи с развитием квантовых вычислений кодовые криптосистемы рассматриваются как альтернатива теоретико-числовым, поэтому актуальной представляется задача поиска перспективных классов кодов для построения новых стойких кодовых криптосистем. Для этого можно использовать некоммутативные коды, т.е. идеалы в групповых алгебрах FqG над конечными некоммутативными группами G. Ранее изучалась стойкость криптосистем на кодах, индуцированных кодами на подгруппах. Важной для исследования некоммутативных кодов является теорема Веддерберна, доказывающая существование изоморфизма групповой алгебры на прямую сумму матричных алгебр, но конкретный вид слагаемых и конструкция изоморфизма этой теоремой не определены, и поэтому для каждой группы остается задача построения представления Веддерберна. Ф.Е.Б. Мартинесом получено полное представление Веддерберна для групповой алгебры FqD2n над диэдральной группой D2n в случае, когда мощность поля и порядок группы взаимно просты. С использованием этих результатов в настоящей работе исследуются коды в групповой алгебре FqD2n. Решена задача о структуре всех кодов и описана структура кодов, которые индуцированы кодами над циклическими подгруппами группы D2n, что представляет интерес для криптографических приложений
О некоторых задачах для симплекса и шара в Rn
Get PDFLet be a convex body and let be a nondegenerate simplex in . Denote by the image of under homothety with a center of homothety in the center of gravity of and the ratio . We mean by the minimal \tau>0 such that is a subset of the simplex . Define as the minimal \tau>0 such that is contained in a translate of . Earlier the author has proved the equalities (if ), Here are the linear functions that are called the basic Lagrange polynomials corresponding to . The numbers are the barycentric coordinates of a point . In his previous papers, the author investigated these formulae in the case when is the -dimensional unit cube . The present paper is related to the case when coincides with the unit Euclidean ball where We establish various relations for and , as well as we give their geometric interpretation. For example, if then . The minimal possible value of each characteristics and for is equal to . This value corresponds to a regular simplex inscribed into . Also we compare our results with those obtained in the case .Пусть --- выпуклое тело, невырожденный симплекс в . Через обозначим образ при гомотетии относительно центра тяжести с коэффициентом . Под понимается минимальное \tau>0, для которого является подмножеством симплекса . По определению, есть минимальное \tau>0, такое что принадлежит трансляту симплекса . Ранее автор доказал, что справедливы равенства (если ), Здесь --- линейные функции, называемые базисными многочленами Лагранжа симплекса . Они таковы, что числа являются барицентрическими координатами точки . В предыдущих работах автора указанные формулы исследовались в ситуации, когда представляет собой -мерный единичный куб . В статье рассматривается случай, когда есть единичный евклидов шар где Устанавливаются различные соотношения для и~, а также приводится их геометрическая интерпретация. Например, если то . Минимальное возможное значение каждой из величин , для равно и соответствует правильному симплексу, вписанному в . Даётся сравнение с результатами, полученными ранее для
О минимальном коэффициенте поглощения для n-мерного симплекса
Get PDFLet and let be the unit cube . For a nondegenerate simplex , by denote the homothetic copy of with center of homothety in the center of gravity of and ratio of homothety Put We call an absorption index of simplex . In the present paper, we give new estimates for the minimal absorption index of the simplex contained in , i.\,e., for the number In particular, this value and its analogues have applications in estimates for the norms of interpolation projectors. Previously the first author proved some general estimates of . Always n\leq\xi_n< n+1. If there exists an Hadamard matrix of order , then . The best known general upper estimate has the form (n>2). There exists a constant c>0 not depending on such that, for any simplex of maximum volume, inequalities take place. It motivates the use of maximum volume simplices in upper estimates of . The set of vertices of such a simplex can be consructed with application of maximum -determinant of order or maximum -determinant of order . In the paper, we compute absorption indices of maximum volume simplices in constructed from known maximum -determinants via a special procedure. For some , this approach makes it possible to lower theoretical upper bounds of . Also we give best known upper estimates of for Пусть , . Для невырожденного симплекса через обозначим образ при гомотетии относительно центра тяжести с коэффициентом Положим Величину будем называть коэффициентом поглощения куба симплексом . В статье приводятся новые оценки для минимального коэффициента поглощения для симплекса, содержащегося в , т.е. величины Эта величина и её аналоги, в частности, имеют приложения при оцениваниинорм интерполяционных проекторов. Общие оценки были ранее получены в работах первого автора.Всегда n\leq\xi_n< n+1. Если существует матрица Адамара порядка , то .Лучшая из известных общих оценок сверху имеет вид (n>2).Cуществует не зависящая от константа c>0, такая что для любого симплекса , имеющего максимальный объём, выполняются неравенства . Это мотивиpует применение для оценивания сверху симплексов максимального объёма в . Для построения набора вершин такого симплекса могут применяться максимальный -определитель порядка или максимальный -определитель порядка . В работе вычисляются коэффициенты поглощения для симплексов максимального объёма, построенных с использованием специальной процедуры из известных максимальных -определителей. Для ряда значений c помощью этого подхода удалось понизить верхние границы , полученные теоретическим путём.Приводятся лучшие известные оценки cверху для