Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
Криптосистема на индуцированных групповых кодах
Get PDFThe code C on a group G, induced by the code N on a subgroup H, has the property that for decoding the code C one can use the decoder for the code N. Therefore, if N has an efficient algorithm for decoding, we can build a class of induced codes with known decoding algorithms. This feature is used in this paper to build the code McEliece-type public key cryptosystems on induced group codes. For this cryptosystem we described operations of encryption and decryption, an analysis of the resistance to the attack on the private key is proposed, and also weak keys are highlighted, which is used while breaking McEliece-type cryptosystem on the induced code C is reduced to breaking this cryptosystem on the code N. It is shown that a practically resistant cryptosystem on the induced code C can be built on the code N with small length. Based on the proposed cryptosystem a common protocol for open channel key generation is developed.Код C на группе G, индуцированный кодом N на подгруппе H, обладает тем свойством, что для декодирования кода C может применяться декодер кода N. Поэтому, если для N имеется эффективный алгоритм декодирования, то по N с помощью конструкции индуцирования можно построить класс кодов с известными алгоритмами декодирования. Эта особенность используется в настоящей работе для построения кодовой криптосистемы с открытым ключом типа Мак-Элиса на индуцированных групповых кодах. Для этой криптосистемы описаны операции шифрования и расшифрования, приводится анализ стойкости к атаке на ключ, а также выделены слабые ключи, в случае использования которых взлом криптосистемы типа Мак-Элиса на индуцированном коде C сводится к взлому этой криптосистемы на коде N. Показано, что практически стойкая криптосистема на индуцированном коде C может быть построена на коде N малой длины. На основе предложенной криптосистемы разработан протокол выработки общего ключа по открытому каналу.
Асимптотика, устойчивость и область притяжения периодического решения сингулярно возмущённой параболической задачи с двукратным корнем вырожденного уравнения
Get PDFFor a singularly perturbed parabolic problem with Dirichlet conditions we prove the existence of a solution periodic in time and with boundary layers at both ends of the space interval in the case that the degenerate equation has a double root. We construct the corresponding asymptotic expansion in a small parameter. It turns out that the algorithm of the construction of the boundary layer functions and the behavior of the solution in the boundary layers essentially differ from that ones in case of a simple root. We also investigate the stability of this solution and the corresponding region of attraction.Для сингулярно возмущённой параболической задачи с краевыми условиями Дирихле построено и обосновано асимптотическое разложение периодического по времени решения с пограничными слоями вблизи концов отрезка в случае, когда вырожденное уравнение имеет двукратный корень. Поведение решения в пограничных слоях и сам алгоритм построения асимптотики существенно отличаются от случая однократного корня вырожденного уравнения. Исследован также вопрос об устойчивости периодического решения и области его притяжения
Расслоенное произведение коммутативных алгебр: образующие и соотношения
No full textThe method of direct computation of the universal (fibred) product in the category of commutative associative algebras of finite type with unity over a field is given and proven. The field of coefficients is not supposed to be algebraically closed and can be of any characteristic. Formation of fibred product of commutative associative algebras is an algebraic counterpart of gluing algebraic schemes by means of some equivalence relation in algebraic geometry. If initial algebras are finite-dimensional vector spaces, the dimension of their product obeys a Grassmann-like formula. A finite-dimensional case means geometrically the strict version of adding two collections of points containing a common part.The method involves description of algebras by generators and relations on input and returns similar description of the product algebra. It is "ready-to-eat"\, even for computer realization. The product algebra is well-defined: taking other descriptions of the same algebras leads to isomorphic product algebra. Also it is proven that the product algebra enjoys universal property, i.e. it is indeed a fibred product. The input data are a triple of algebras and a pair of homomorphisms . Algebras and homomorphisms can be described in an arbitrary way. We prove that for computing the fibred product it is enough to restrict to the case when are surjective and describe how to reduce to the surjective case. Also the way of choosing generators and relations for input algebras is considered.Paper is published in the author's wording.В работе дан и обоснован метод прямого вычисления универсального (расслоенного) произведения в категории коммутативных ассоциативных алгебр конечного типа с единицей над полем. Поле коэффициентов не предполагается алгебраически замкнутым и может иметь любую характеристику.Формирование расслоенного произведения коммутативных ассоциативных алгебр составляет алгебраическую сторону процедуры склеивания алгебраических схем по некоторому отношению эквивалентности в алгебраической геометрии. Если исходные алгебры являются конечномерными векторными пространствами, то размерность их расслоенного произведения подчиняется формуле, аналогичной формуле размерности суммы подпространств. Геометрически конечномерный случай поставляет строгую версию объединения двух наборов точек, имеющих общую часть. Метод использует задание алгебр образующими и определяющими соотношениями на входе и выдает аналогичное представление произведения на выходе. Он пригоден для компьютерной реализации.Произведение алгебр определено корректно: выбор иных представлений тех же алгебр приводит к изоморфной алгебре-произведению.Также показано, что алгебра-произведеное обладает свойством универсальности, т.е. является настоящим расслоенным произведением. Входные данные -- это тройка алгебр и пара гомоморфизмов. Алгебры и гомоморфизмы могут быть заданы произвольным образом. Показано, что для вычисления расслоенного произведения достаточно ограничиться случаем, когда гомоморфизмы сюръективны, и описан способ редукции к сюръективному случаю. Также рассмотрено правило выбора образующих и соотношений для исходных алгебр.Статья публикуется в авторской редакции
Построение CFC-программ ПЛК по LTL-спецификации
Get PDFThis article continues a cycle of papers, which describe an approach to construction and verification of discrete PLC-programs by an LTL-specification. The approach provides a possibility of PLC-program correctness analysis by the model checking method. For the specification of the program behavior the linear-time temporal logic LTL is used. The correctness analysis of an LTL specification is performed automatically by the symbolic model checking tool Cadence SMV. Previously it was shown how ST-, LDand IL-programs are constructed by a correct (with verified program properties) LTL-specification. In this article a technology of CFC-program construction by an LTL-specification is described. The language CFC (Continuous Function Chart) is a variation of FBD (Function Block Diagram). FBD is a graphical language for microcircuits. CFC provides a possibility of free allocation of program components and connections on a screen. The approach to construction of CFC-programs is shown by an example. PLC-program representation on CFC within the approach to programming by LTL-specification differs from other representations. It gives the visualisation of a data flow from inputs to outputs. Influence and dependence between variables is explicitly shown during program execution within one PLC working cycle. In fact, CFC-program is a scheme of PLC-program data flow.Статья продолжает серию работ, посвященных подходу к построению и верификации «дискретных» программ логических контроллеров (ПЛК) по LTL-спецификации. Этот подход обеспечивает возможность анализа корректности программ логических контроллеров с помощью метода проверки модели (Model Checking). В рамках подхода в качестве языка спецификации программного поведения используется язык темпоральной логики LTL. Анализ корректности LTL-спецификации относительно программных свойств производится автоматически с помощью программного средства символьной проверки модели Cadence SMV. Ранее было показано, каким образом по корректной (проверенной на корректность относительно программных свойств) LTL-спецификации происходит построение ST-, LDи IL-программ. В этой статье описывается технология построения CFC-программ по LTL-спецификации. Язык непрерывных функциональных схем CFC (Continuous Function Chart) представляет собой разновидность языка FBD (Function Block Diagram) — графического языка диаграмм принципиальных схем электронных устройств на микросхемах. В отличие от FBD язык CFC обеспечивает возможность свободного размещения программных компонентов и их соединений на экране. Технология построения CFC-программ демонстрируется на примере. Представление ПЛК-программы на языке CFC в рамках подхода к программированию по LTL-спецификации в отличие от представлений на других стандартных языках дает возможность наглядного графического изображения потока данных от входных переменных к выходам ПЛК. Явным образом демонстрируется зависимость и влияние значений одних переменных на значения других переменных во время исполнения программы за один проход рабочего цикла ПЛК. Фактически CFC-программа представляет собой схему потоков данных ПЛК-программы.
Об эффективности минимизирующего подхода к оптимизации запросов
Get PDFA standard problem of DBMSs usage is a lack of efficiency and high cost of the access to the stored data. The acceptable level of system performance may be achieved by query optimization technics that determine the most efficient way to execute a given query by its modification and considering possible query execution plans. The goal of this paper is to prove the efficiency of the query minimization algorithms based on minimization of the query restriction by elimination of the redundant conditions. The paper represents minimization algorithms based on the mathematical transformations, which detect and remove redundant conditions from query restriction to simplify it. It includes minimization algorithms based on “condition absorption”, prime implicants, and a set of linear inequalities minimization technics. The paper also includes theoretical justification of the efficiency of minimization approach to the query optimization based on restriction simplification. We also observe experimental results of the implementation of these optimization techniques and their influence on the query processing speed. In the end, we represent an observation of the query minimization impact on the whole optimization process Стандартной проблемой использования СУБД является недостаток эффективности и высокая стоимость доступа к хранимым данным. Допустимый уровень работы системы может достигаться с помощью технологий оптимизации запросов, определяющих наиболее эффективный способ выполнения конкретного запроса с помощью его модификации и определения возможных планов выполнения. Целью данной работы является доказательство эффективности алгоритмов минимизации запроса, основанных на минимизации ограничения запроса и удаления избыточных условий. Статья представляет алгоритмы минимизации, основанные на математических преобразованиях, определяющих и удаляющих избыточные условия из ограничения запроса, чтобы упростить его. Она включает алгоритмы, основанные на технологиях «поглощения условий», первичных импликант и минимизации множеств линейных неравенств. Работа также включает теоретическое доказательство эффективности минимизирующего подхода, основанного на упрощении ограничения. Мы также рассматриваем экспериментальные результаты применения этих технологий оптимизации и их влияния на скорость обработки запроса. В конце мы представляем обзор влияния минимизации запроса на весь процесс оптимизации запроса.
Устойчивые циклы и торы системы из трех и четырех диффузионно связанных осцилляторов
Get PDFWe consider chains of identical diffusive weakly coupled oscillation systems with different conditions on coupling on a chain bound. We suppose that every interacting oscillator undergoes Andronov–Hopf bifurcation, and the coefficient of coupling is proportional to the supercriticality value. For this case on a stable integral manifold of the system a normal form is constructed for which, in case of three oscillators interact, we can study the simplest stationary states and their phase transformations. As the coupling parameter changes, for the uniform stationary state corresponding to the uniform cycle of the problem there can be two cases, in the former case it loses stability with the emergence of two stable nonuniform states, and in the latter one it merges with two unstable nonuniform states and transfers to them its stability. For the stationary state corresponding to oscillations in antiphase two cases can be also distinguished. In the first one, this stationary state becomes stable due to the contraction of a stable limit cycle of the system into it (Andronov–Hopf bifurcation), and in the second case it becomes stable after branching from it an unstable limit cycle. If there are four oscillators in the chain, the system of phase difference for a small coupling coefficient was studied.Рассматриваются цепочки идентичных диффузионно слабо связанных колебательных систем с различными условиями связи на границе цепочки. Предполагается, что с каждым из взаимодействующих осцилляторов происходит бифуркация Андронова – Хопфа, а коэффициент связи пропорционален величине надкритичности. В этой ситуации на устойчивом интегральном многообразии системы построена нормальная форма, для которой в случае трех взаимодействующих осцилляторов удается проанализировать простейшие состояния равновесия и их фазовые перестройки. При изменении параметра связи для однородного состояния равновесия, соответствующего однородному циклу задачи, возможны два случая, в первом из которых оно теряет устойчивость с появлением двух устойчивых неоднородных состояний, а во втором с ним сливаются два неустойчивых неоднородных состояния и отбирают у него устойчивость. Для состояния равновесия, соответствующего колебаниям осцилляторов в противофазе, также можно выделить два случая. В первом из них это состояние равновесия становится устойчивым в результате стягивания к нему устойчивого предельного цикла системы (бифуркация Андронова – Хопфа), а во втором случае оно становится устойчивым после ответвления от него неустойчивого предельного цикла. В случае, когда число осцилляторов в цепочке равно четырем, проанализирована система разностей фаз осцилляторов, получающаяся при достаточно малом коэффициенте связи
Численное решение одной сингулярно возму- щённой задачи в круговой области
No full textWe consider a singularly perturbed elliptic problem, of convection-diffusion type, posed on a circular domain. Using polar coordinates, simple upwinding and a piecewise-uniform Shishkin mesh in the radial direction, we construct a numerical method that is monotone, pointwise accurate and parameter-uniform under certain compatibility constraints. Numerical results are presented to illustrate the performance of the numerical method when these constraints are not imposed on the data.Рассматривается сингулярно возмущенная эллиптическая задача типа конвекция-диффузия в круговой области. С использованием полярных координат, простой схемы с разностями против потока и кусочно-равномерной сетки Шишкина в радиальном направлении для нее строится численный метод, который будет монотонным, поточечно точным и равномерным по параметру при некоторых ограничениях совместности. Приводятся численные эксперименты, иллюстрирующие эффективность данного численного метода в случае, когда эти ограничения ненакладываются на данные задачи
Бифуркации периодических решений уравнения Мэкки–Гласса
Get PDFWe study the bifurcation of the equilibrium states of periodic solutions for the Mackey– Glass equation. This equation is considered as a mathematical model of changes in the density of white blood cells. The equation written in dimensionless variables contains a small parameter at the derivative, which makes it singular. We applied the method of uniform normalization, which allows us to reduce the study of the solutions behavior in the neighborhood of the equilibrium state to the analysis of the countable system of ordinary differential equations. We poot out the equations in ”fast” and ”slow” variables from this system. Equilibrium states of the ”slow” variables equations determine the periodic solutions. The analysis of equilibrium states allows us to study the bifurcation of periodic solutions depending on the parameters of the equation and their stability. The possibility of simultaneous bifurcation of a large number of stable periodic solutions is shown. This situation is called the multistability phenomenon.В работе изучаются бифуркации периодических решений из состояния равновесия известного уравнения Мэкки–Гласса, предложенного в качестве математической модели изменения плотности белых клеток крови. Уравнение, записанное в безразмерных переменных, содержит малый параметр при производной, что делает его сингулярным. К уравнению применяется метод равномерной нормализации, позволяющий свести исследование поведения решений в окрестности состояния равновесия к анализу счетной системы обыкновенных дифференциальных уравнений, из которых выделяются уравнения быстройй и медленныхх переменных. Показано, что состояния равновесия уравнений медленныхх переменных определяют периодические решения. Анализ состояний равновесия позволяет изучить бифуркации периодических решений в зависимости от параметров уравнения и их устойчивость. Показана возможность одновременной бифуркации большого числа устойчивых периодических решений. Это явление носит название бифуркации мультистабильности
Численное исследование начально-краевой задачи Неймана для сингулярно возмущенного параболического уравнения
Get PDFFor a singularly perturbed one-dimensional parabolic equation with a perturbation parameter ε multiplying the highest-order derivative in the equation, ε ∈ (0,1], an initial-boundary value Neumann problem is considered on a segment. In this problem, when the parameter ε tends to zero, boundary layers appear in neighborhoods of the lateral boundary. In the paper, convergence of the problem solution and its regular and singular components are studied. It is shown that standard finite difference schemes on uniform grids used to numerically solve this problem do not converge ε-uniformly. The error in the grid solution grows unboundedly when the parameter ε → 0. The use of a special difference scheme on Shishkin grid which is a piecewise-uniform mesh with respect to x condensing in neighborhoods of boundary layers and a uniform mesh in t, constructed by using monotone grid approximations of the differential problems, allows us to find a numerical solution of this problem convergent in the maximum norm ε-uniformly. The results of the numerical experiments confirm the theoretical results.Для одномерного сингулярно возмущенного параболического уравнения с возмущающим параметром ε при старшей производной, ε ∈ (0, 1], рассматривается начально-краевая задача на отрезке с условием Неймана на границе. В этой задаче, когда параметр ε стремится к нулю, в окрестностях боковой границы появляются пограничные слои. В работе исследуется сходимость решения и его регулярной и сингулярной компонент. Показано, что стандартные разностные схемы на равномерных сетках, используемые для численного решения этой задачи, не сходятся ε-равномерно. Ошибка сеточного решения неограниченно растет, когда параметр ε → 0. Использование специальной разностной схемы на сетке Шишкина — кусочно-равномерной по x сетке, сгущающейся в окрестностях пограничных слоев, и равномерной по t, построенных с использованием монотонных сеточных аппроксимаций дифференциальной задачи — позволяет найти численное решение этой задачи, сходящееся в равномерной норме ε-равномерно. Результаты численных экспериментов подтверждают теоретические результаты
Численное моделирование процессов формирования полос адиабатического сдвига в композитах
Get PDFThe process of plastic flow localization under shear deformations of a composite material consisting from welded steel and copper is studied. A mathematical model describing this physical process is proposed. A new numerical approach based on Courant–Isaacson–Rees scheme is suggested. This algorithm was verified using three benchmark problems. Operability and effectiveness of this algorithm is confirmed. A numerical simulation of plastic flow localization in composite materials is performed. The influence on localization process of boundary conditions, of initial strain rate and materials width is studied. It is shown that at the initial stage the shear velocity of material layers oscillates. Theoretical estimates of frequency and oscillation period is given. Computational results coincide with these estimates. It is found that plastic flow localizes in the copper part of the composite. One or two areas of plastic flow localization appears depending on the width of steel and copper parts, as well as on the initial plastic strain rate and the selected type of a boundary conditions. The areas locate on characteristic distance from borders. The dependence of this distance and initial strain rate is shown and the corresponding estimates are obtained for two types of boundary conditions. When two areas of localization are formed, in one of them the temperature and the deformation increas faster than in another one.В работе рассматривается процесс локализации пластической деформации в композитном материале, состоящем из сваренных стальной и медной пластины при сдвиговых деформациях. Сформулирована математическая модель данного физического процесса. Для проведения вычислительных экспериментов предложен новый численный алгоритм, основанный на схеме Куранта–Изаксона–Риса. Данный алгоритм верифицирован на трех тестовых задачах. Его работоспособность и эффективность подтверждена в результате проведенных тестов. С использованием предложенного алгоритма проведено численное моделирование процессов локализации пластической деформации в композитных материалах. Исследовано влияние граничных условий, начальной скорости пластической деформации и ширины материалов, входящих в композитный блок, на процесс локализации. Показано, что на начальном этапе скорость сдвига слоев материала колеблется. Предложены теоретические оценки частоты и периода колебаний, расчеты по которым полностью согласуются с численным экспериментом. Установлено, что деформация локализуется в медной части композита. В зависимоcти от ширины стальной и медной части, а также начальной скорости пластической деформации и выбранного типа граничных условий, возникает одна или две области локализции, расположенные на характерном расстоянии от границ. Показана зависимость данного расстояния от начальной скорости пластической деформации, и получены соответствующие оценки для двух типов граничных условий. Установлено, что при возникновении двух областей локализации в одной из них температура и деформация растет существенно быстрее, чем в другой, тогда как на начальном этапе данные величины совпадают в этих областях