Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
МКЭ-анализ на адаптированных к слою сетках в задачах с точкой по- ворота, имеющих внутренний слой
No full textWe consider singularly perturbed turning point problems whose solutions exhibit an interior layer. Two suitable layer-adapted mesh-types are presented. For both types we give uniform error estimates in the ε-weighted energy norm for finite elements of higher order. Numerical experiments are used to compare the meshes and to confirm the theoretical findings.Рассматриваются сингулярно возмущенные задачи с точкой поворота, решения которых имеют внутренний слой. Представлены подходящие для таких задач два типа адаптированных к слою сеток. Для обоих типов даны равномерные оценки погрешности в ε-весовой энергетической норме для конечных элементов высокого порядка. В целях сравнения этих сеток и подтверждения теоретических выводов использованы численные эксперименты.Статья публикуется в авторской редакции
Коллективные потоковые вычисления: реляционные модели и алгоритмы
Get PDFRecently, microtask crowdsourcing has become a popular approach for addressing various data mining problems. Crowdsourcing workflows for approaching such problems are composed of several data processing stages which require consistent representation for making the work reproducible. This paper is devoted to the problem of reproducibility and formalization of the microtask crowdsourcing process. A computational model for microtask crowdsourcing based on an extended relational model and a dataflow computational model has been proposed. The proposed collaborative dataflow computational model is designed for processing the input data sources by executing annotation stages and automatic synchronization stages simultaneously. Data processing stages and connections between them are expressed by using collaborative computation workflows represented as loosely connected directed acyclic graphs. A synchronous algorithm for executing such workflows has been described. The computational model has been evaluated by applying it to two tasks from the computational linguistics field: concept lexicalization refining in electronic thesauri and establishing hierarchical relations between such concepts. The “Add–Remove–Confirm” procedure is designed for adding the missing lexemes to the concepts while removing the odd ones. The “Genus–Species–Match” procedure is designed for establishing “is-a” relations between the concepts provided with the corresponding word pairs. The experiments involving both volunteers from popular online social networks and paid workers from crowdsourcing marketplaces confirm applicability of these procedures for enhancing lexical resources. В последнее время краудсорсинг на основе выполения микрозадач получил широкое применение в области анализа неструктурированных данных. Разрабатываются специализированные методики, состоящие из множества этапов обработки исходных данных, требующих согласованности их представления для обеспечения воспроизводимости работы. Данная статья посвящена решению проблемы воспроизводимости и формализации процесса краудсорсинга микрозадачами. Предложена модель коллективных потоковых вычислений на основе расширенной реляционной модели и потоковой модели вычислений. Модель предназначена для обработки исходных данных в виде реляционных отношений путем параллельного выполнения этапов разметки микрозадачами и этапов автоматической синхронизации. Этапы обработки данных и связи между ними записываются с использованием схемы коллективных вычислений, представляющей собой слабо связный ориентированный ациклический граф. Описан синхронный алгоритм выполнения схем коллективных вычислений. Продемонстрированы приложения модели в области компьютерной лингвистики для уточнения лексикализации понятий в электронных тезаурусах и построения родо-видовых отношений между понятиями при помощи краудсорсинга. Процедура «добавить–удалить–подтвердить» позволяет внести в лексикализацию понятий недостающие лексемы и исключить посторонние. Процедура «род–вид–сопоставить» позволяет сформировать гипо-гиперонимические отношения между понятиями на основе соответствующих родо-видовых пар слов. Результаты экспериментов на материалах открытого электронного тезауруса русского языка подтверждают применимость разработанных процедур для развития лексических ресурсов. В экспериментах приняли участие как волонтеры из популярных социальных сетей, так и пользователи бирж краудсорсинга (за вознаграждение в форме микроплатежей).
Метод синтеза тестов с гарантированной полнотой по модели расширенного автомата
Get PDFExtended Finite State Machines (EFSMs) are widely used when deriving tests for checking functional requirements for software implementations. However, the fault coverage of tests covering appropriate paths, variables, etc. of the specification EFSM, remains rather obscure and such tests do not detect many functional faults in EFSM implementations. In this paper, an approach is proposed for deriving complete tests with respect to functional faults of a proper Java EFSM implementation. First, an initial test suite derived against the specification EFSM is checked with respect to faults generated by a µJava tool. Since the EFSM software implementation is template based, each undetected fault can be easily mapped into a mutant EFSM of the specification machine. Thus, a distinguishing sequence is derived for two Finite State Machines modeling two EFSMs instead of deriving such a sequence for two programs. If the corresponding FSMs are too complex or cannot be completely derived, a test suite can be incomplete. However, the performed experiments clearly show that a test suite extended by such distinguishing sequences detects much more functional faults in software implementations of a system whose behaviour is described by the given EFSM.Расширенные автоматы активно используются при построении тестов для программного обеспечения на основе формальных моделей. Однако полнота тестов, построенных по расширенному автомату на основе покрытия путей, переменных и т.п., остается практически неизвестной; более того, как известно, такие тесты не обнаруживают большое количество часто встречающихся функциональных ошибок в программных реализациях системы, поведение которой описано таким расширенным автоматом. В данной работе для построения тестовых последовательностей мы предлагаем использовать шаблонную реализацию расширенного автомата в языке Java. Поскольку программа составлена по шаблону, то ошибки в программе напрямую переносятся на ошибки в расширенном автомате. В работе предлагается метод построения множества тестовых последовательностей, обнаруживающих функциональные ошибки в шаблонной реализации расширенного автомата. На первом шаге тест, построенный по расширенному автомату одним из известных методов, проверяется на полноту относительно ошибок, сгенерированных инструментом µJava в шаблонной программной реализации. После этого для каждого необнаруженного тестом программного мутанта строится мутант эталонного расширенного автомата; на следующем шаге по некоторой конечно-автоматной абстракции генерируется последовательность, различающая два расширенных автомата (если такая последовательность существует), которая добавляется в строящийся тест. Построенный таким образом тест является полным относительно ошибок, сгенерированных инструментом µJava. Если соответствующий конечный автомат, построенный посредством моделирования расширенного автомата, получается слишком сложным, или построить такой конечный автомат не представляется возможным, то полнота построенного теста не гарантируется. Однако экспериментально показывается, что исходный тест, расширенный такими различающими последовательностями, обнаруживает значительно больше функциональных ошибок в программных реализациях системы, для которой расширенный автомат используется в качестве спецификаци
Об оптимизации и распараллеливании алгоритма Литтла для решения задачи коммивояжера
Get PDFThe paper describes some ways to accelerate solving the NP-complete Traveling Salesman Problem. The classic Little algorithm belonging to the category of ”branch and bound methods” can solve it both for directed and undirected graphs. However, for undirected graphs its operation can be accelerated by eliminating the consideration of branches examined earlier. The paper proposes changes to be made in the key operations of the algorithm to speed up its execution. It also describes the results of an experiment that demonstrated a significant acceleration of solving the problem by using an advanced algorithm. Another way to speed up the work is to parallelize the algorithm. For problems of this kind it is difficult to break the task into a sufficient number of subtasks having comparable complexity. Their parallelism arises dynamically during the execution. For such problems, it seems reasonable to use parallel-recursive algorithms. In our case the use of the library RPM ParLib developed by the author was a good choice. It allows us to develop effective applications for parallel computing on a local network using any .NET-compatible programming language. We used C# to develop the programs. Parallel applications were developed as for basic and modified algorithms, the comparing of their speed was made. Experiments were performed for the graphs with the number of vertexes up to 45 and with the number of network computers up to 16. We also investigated the acceleration that can be achieved by parallelizing the basic Little algorithm for directed graphs. The results of these experiments are also presented in the paper. В данной работе рассматриваются способы ускорения решения NP-полной задачи коммивояжера. Классический алгоритм Литтла, относящийся к категории "методов ветвей и границ" , позволяет ее решать как для ориентированных, так и для неориентированных графов. Однако для неориентированных графов его работу можно ускорить за счет исключения рассмотрения фактически ранее рассмотренных вариантов. В работе предлагаются изменения, которые следует внести в ключевые операции алгоритма для ускорения его работы. Приводятся результаты численного эксперимента, показавшего значительное ускорение решения задачи с использованием усовершенствованного алгоритма. Другой ресурс для ускорения – это разработка параллельного алгоритма. Для задач подобного рода весьма сложно сразу разбить вычисления на достаточное количество сравнимых по трудоемкости подзадач. Параллелизм у них выявляется динамически во время вычислений. Для таких задач разумным представляется использование рекурсивно-параллельной организации вычислений. В нашем случае хорошим выбором оказалась разработанная автором библиотека RPM_ParLib, позволяющая создавать эффективные параллельные программы для вычислений на локальной сети в среде .NET Framework на любом поддерживаемом ею языке программирования. Мы при разработке программы использовали язык C#. Были написаны параллельные программы для реализации как исходного, так и модифицированного алгоритмов, проведено их сравнение. Эксперименты проводились для графов с количеством вершин до 45 с количеством компьютеров в сети до 16. Дополнительно исследовалось ускорение, которого можно достичь за счет распараллеливания базового алгоритма Литтла для ориентированных графов. Результаты этих серий экспериментов также приводятся в работе.
Моделирование неизотермического течения аномально вязкой жидкости в каналах с различной геометрией границ
Get PDFIn this paper, we analyzed the flat non-isothermal stationary flow of abnormally viscous fluid in the channels with asymmetric boundary conditions and an unknown output boundary. The geometry of the channels in which the problem is considered, is such regions, that at the transition to bipolar a system of coordinates map into rectangles. This greatly simplifies the boundary conditions, since it is possible to use an orthogonal grid and boundary conditions are given in its nodes. Fields of this type are often found in applications. The boundary conditions are set as follows: the liquid sticks to the boundaries of the channels, which rotate at different speeds and have different radius and temperature; moreover, temperature at the entrance to deformation is known, while on the boundary with the surface the material has the surface temperature; the pressure on the enter and exit of the region becomes zero. The rheological model only takes into account the anomaly of viscosity. The material is not compressible. This process can be described by a system consisting of continuity equations, the equations of conservation of momentum and an energy equation: ∇В данной работе проведен анализ плоского неизотермического стационарного течения аномально вязкой жидкости в каналах с несимметричными граничными условиями и неизвестной границей выхода. Геометрия каналов, в которых рассматривается задача, – это такие области, которые при переходе в биполярную систему координат отображаются в прямоугольники. Это существенно упрощает граничные условия, т.к. появляется возможность использовать ортогональную сетку и граничные условия задаются в ее узлах. Области такого типа часто встречаются в прикладных задачах. Граничные условия задаются следующим образом: жидкость прилипает к границам каналов, которые вращаются с разной скоростью и имеют разный радиус и температуру; кроме того, известна температура при входе в область деформации, а на границе с поверхностью материал имеет температуру поверхности; давление на входе и выходе из области обращается в нуль. Реологическая модель учитывает только аномалию вязкости. Материал несжимаемый. Данный процесс описывается системой, состоящей из уравнений неразрывности, уравнения сохранения импульса и уравнения энергии:
Метод конечных разностей во временной области для кусочно-однородных диэлектрических сред
Get PDFIn this paper, we consider a numerical solution of Maxwell’s curl equations for piecewise uniform dielectric medium by the example of a one-dimensional problem. For obtaining the second order accuracy, the electric field grid node is placed into the permittivity discontinuity point of the medium. If the dielectric permittivity is large, the problem becomes singularly perturbed and a contrast structure appears. We propose a piecewise quasi-uniform mesh which resolves all characteristic solution parts of the problem (regular part, boundary layer and transition zone placed between them) in detail. The features of the mesh are discussed. В данной статье рассматривается численное решение системы вихревых уравнений Максвелла для кусочно-однородной диэлектрической среды на примере одномерной задачи. Для обеспечения второго порядка точности необходимо поставить узел сетки электрического поля в точку разрыва диэлектрической проницаемости. Если скачок проницаемости велик, то задача становится сингулярно возмущенной и возникает контрастная структура. Построена кусочная квазиравномерная сетка, детально передающая все характерные участки решения этой задачи (регулярную область, пограничный слой и переходную зону между ними). Обсуждаются свойства этой сетки
Сингулярно возмущенная эллиптическая задача Дирихле с кратным корнем вырожденного уравнения
Get PDFA singularly perturbed elliptic problem with Dirichlet boundary conditions is considered in the case of multiple roots of the degenerate equation. A complete asymptotic expansion of the solution is constructed and justified. It is qualitatively different from the known expansion in the case where the root of the degenerate equation is simple: the asymptotic expansion of the solution being in fractional powers of the small parameter, boundary-layer variables have a different scale, boundary-layer series is constructed using a non-standard algorithm, the boundary layer in the vicinity of the domain boundary consists of three zones with different behavior of the solution in different zones.Рассматривается сингулярно возмущенная эллиптическая задача с граничными условиями Дирихле в случае кратного корня вырожденного уравнения. Построено и обосновано полное асимптотическое разложение решения задачи. Оно качественно отличается от известного разложения в случае, когда корень вырожденного уравнения – простой: асимптотическое разложение решения ведется по дробным степеням малого параметра, погранслойные переменные имеют другой масштаб, погранслойный ряд строится с помощью нестандартного алгоритма, пограничный слой вблизи границы области состоит из трех зон с различным поведением решения в разных зонах
Асимптотические разложения собственных чисел первой краевой задачи для сингулярно возмущенного дифференциального уравнения второго порядка с точками поворота
Get PDFFor singularly perturbed second order equations the dependence of eigenvalues of the first boundary problem on a small parameter at the highest derivative is studied. The main assumption is that the coefficient at the first derivative in the equation is the sign of the variable. This leads to the emerging of so-called turning points. Asymptotic expansions on the small parameter are obtained for all eigenvalues of the considered boundary problem. It turns out that the expansions are defined by the behavior of coefficients in a neighborhood of turning points onlyДля сингулярно возмущенных уравнений второго порядка исследована зависимость от малого параметра при старшей производной собственных значений первой краевой задачи. Основное предположение состоит в том, что коэффициент при первой производной уравнения является знаком переменной. Это приводит к появлению так называемых точек поворота. В этом случае удалось построить асимптотические разложения по малому параметру всех собственных значений рассматриваемой краевой задачи. Оказалось, что эти разложения определяются поведением коэффициентов только в окрестности точек поворот
Генерация графа социальной сети с использованием Apache Spark
Get PDFWe plan to create a method of clustering a social network graph. For testing the method there is a need to generate a graph similar in structure to existing social networks. The article presents an algorithm for the graph distributed generation. We took into account basic properties such as power-law distribution of the users communities number, dense intersections of the social networks and others. This algorithm also considers the problems that are present in similar works of other authors, for example, the multiple edges problem in the generation process. A special feature of the created algorithm is the implementation depending on the communities number parameter rather than on the connected users number as it is done in other works. It is connected with a peculiarity of progressing the existing social network structure. There are properties of its graph in the paper. We described a table containing the variables needed for the algorithm. A step-by-step generation algorithm was compiled. Appropriate mathematical parameters were calculated for it. A generation is performed in a distributed way by Apache Spark framework. It was described in detail how the tasks division with the help of this framework runs. The Erdos-Renyi model for random graphs is used in the algorithm. It is the most suitable and easy one to implement. The main advantages of the created method are the small amount of resources in comparison with other similar generators and execution speed. Speed is achieved through distributed work and the fact that in any time network users have their own unique numbers and are ordered by these numbers, so there is no need to sort them out. The designed algorithm will promote not only the efficient clustering method creation. It can be useful in other development areas connected, for example, with the social networks search engines.Планируется создать метод кластеризации графа социальной сети. Для тестирования будущего метода возникла необходимость в генерации графа, по своей структуре схожего с лежащими в основе существующих социальных сетей. В статье представлен алгоритм для распределенной генерации такого графа. Учитываются основные свойства социальной сети: степенное распределение количества сообществ для пользователей, плотные пересечения сообществ и другие. В данном алгоритме учтены проблемы, присутствующие в подобных работах других авторов, например, проблема кратных ребер при генерации. Особенностью созданного алгоритма стала реализация, зависящая от такого параметра как количество сообществ, а не от количества пользователей, как это делается в других работах. Это связано с особенностью развития структуры реальной существующей социальной сети. В работе перечислены свойства ее графа. Описана таблица, содержащая необходимые для алгоритма переменные. Составлен пошаговый алгоритм генерации. Для него определены соответствующие математические параметры. Генерация происходит распределенно с помощью фреймворка Apache Spark. Подробно описано, каким образом происходит разделение задач с помощью данного фреймворка. В алгоритме используется модель Эрдеша–Реньи для случайных графов как наиболее подходящая и достаточно простая для реализации. Основными преимуществами созданного метода являются использование малого количества ресурсов, по сравнению с другими подобными генераторами, и скорость выполнения. Быстрота достигается за счет распределенной работы и того, что при распределенной работе алгоритма в любой момент пользователи сети имеют свои уникальные номера и упорядочены по этим номерам, поэтому не требуется их сортировка. Разработанный алгоритм будет способствовать не только созданию эффективного метода кластеризации. Он может быть полезен в других областях, связанных, например, с поисковыми системами социальных сетей