Search

Одной из самых известных задач комбинаторной оптимизации является задача коммивояжера. Эта задача является важной и вместе с тем трудноразрешимой, что связано с экспоненциальной сложностью точных методов решения. Она возникает в обширном классе приложений: в построении оптимальных схем движения, распознавании траекторий и образов. Однако, целый ряд научных исследований, в частности, вопросы генетики и биоинформатики, требуют получения точного решения. На основе классической реализации метода ветвей и границ в работе проводится исследование влияния асимметрии на сложность решения. Поскольку проводимое исследование требует анализа большого числа экспериментально полученных данных, возникает необходимость повышения скорости проведения расчетов. Выбранный для работы метод ветвей и границ допускает получение большей скорости перебора решений за счет хранения в памяти состояний активных листовых вершин дерева решений. На эффективность реализации алгоритма влияет также выбор структур данных для быстрого нахождения следующей рассматриваемой вершины. На основании полученных результатов и проведенного анализа установлена зависимость сложности решения задачи от асимметричности матрицы. Некоторые из вариантов внесения асимметрии приводят к сокращению сложности решения. Изучение влияния асимметрии на сложность задачи коммивояжера на примере классического алгоритма решения – метода ветвей и границ – представляет интерес для дальнейшего предиктивного анализа сложности индивидуальных задач., The traveling salesman problem is the one of the most famous combinatorial optimization problems. This problem is important and at the same time difficult to solve, due to the exponential complexity of the exact methods of solution. It occurs in an extensive class of applications: in the construction of optimal motion schemes, recognition of tracks and images. However, a number of scientific studies, in particular, genetics and bioinformatics, require an accurate solution. This study is concerned with the problem of asymmetry influence on the complexity of the solution, which obtained with the classical implementation of branches and bounds method. Since the study requires the analysis of numerous experimental data, there is a need to increase the speed of calculations. The selected approach using branch and bounds method allows gaining an extra speed of search in decision tree by maintaining in-memory state of the active list nodes of the tree. The efficiency of the implementation of the algorithm is also affected by the choice of data structures for the rapid finding of the next vertex under consideration. Based on the results and the analysis, the dependence of the complexity of the problem solution on the asymmetry of the matrix is established. Some asymmetry options reduce the complexity of the solution. The study of the influence of asymmetry on the traveling salesman problem’s complexity on the example of the classical solution algorithm – the method of branches and bounds – is of interest to further predictive analysis of the complexity of individual problems., №1 (2019)

Лазерное сканирование – современный и активно развивающийся метод дистанционного зондирования. Результат лазерного сканирования представляет собой облако точек, которое кроме координат каждой точки может содержать цвет точки и другие атрибуты. Одной из особенностей технологии лазерного сканирования, обусловившей её популярность, является возможность получения достаточно плотного облака точек, что определяет высокую точность цифрового представления геометрии объекта сканирования. В некоторых случаях облака точек могут содержать миллиарды точек, для хранения которых необходимы сотни гигабайт. Загрузка и обработка таких колоссальных объёмов данных требует больших временных и вычислительных ресурсов. Распространенным подходом является построение октодерева для ускорения операций пространственного поиска и группировки близких в пространстве точек. Использование такого октодерева совместно с внешней памятью открывает возможность ограничения объёма потребляемой оперативной памяти. В статье представлен метод построения октодерева с использованием двухуровневой системы кеширования участков облака точек. Предложены способ организации процесса построения структуры данных и способ анализа эффективности метода с помощью вычислительного эксперимента. Приведены результаты анализа эффективности предложенного метода., Laser scanning is a modern and actively developing remote sensing method. Laser scanning results are represented by point clouds, which can contain not only the coordinates of each point, but also the color of the points and other attributes. One of laser scanning technology features, which caused its popularity, is the ability to obtain a sufficiently dense cloud of points. Thanks to this function, laser scanning allows you to determine the digital representation of the geometry of the scanned object with high accuracy. In some cases, point clouds can contain billions of points that require hundreds of gigabytes of data storage. Loading and processing such enormous amounts of data requires significant time and computational resources. A common approach is to build an octree to speed up the spatial search operations and group points close in space. Using such an octree together with external memory opens the possibility of limiting the amount of RAM consumed. This article presents the method of an octree generating using a two-tier cache system for caching sections of the point cloud. The method of organizing the process of data structure building is proposed, and the approach to the analysis of the proposed method efficiency on the basis of a computational experiment is given. The results of the proposed method efficiency analysis are presented.

В данной работе осуществляется развитие идей, изложенных в работе [1] относительно методики обучения студентов направления «Прикладная информатика» по дисциплине «Структуры данных в предметной области» (СДвПО). Выделены междисциплинарные связи с дисциплинами «Информатика и программирование», «Базы данных», «Объектно-ориентированное программирование» и «Высокоуровневые методы информатики и программирования». Кроме этого, обозначены направления дальнейшей работы по обновлению учебно-методического обеспечением дисциплины «СДвПО».

При распараллеливании решения трехмерных краевых задач, особенно в областях со сложной геометрией, важными являются технологии проведения вычислений и структуры данных. От них зависит объем хранимой информации и время решения. В статье предлагаются технологии распараллеливания метода декомпозиции расчетной области на подобласти, сопрягаемые без наложения, на квазиструктурированных сетках. Разработаны параллельные сеточные структуры данных, ориентированные преимущественно на работу со структурированными массивами данных. Приведен иллюстративный пример, показывающий основные положения предлагаемого подхода., When parallelizing the solution of three-dimensional boundary value problems, especially in domains with complex geometry, the сomputational technologies and data structureы are important. The amount of stored information and the computational time depend on them. In this paper we propose the technologies for parallelizing the method of decomposition of the computational domain into subdomains conjugated without overlapping on a quasistructured grid. Parallel grid data structures oriented mainly to work with structured data arrays are developed. An illustrative example clarifying the fundamentals of the proposed approach is discussed., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 4 2018

Рассматриваются алгебраические, геометрические и информационные аспекты параллельных методов декомпозиции для решения больших систем линейных уравнений с разреженными матрицами, возникающими при аппроксимации многомерных краевых задач на неструктурированных сетках. Алгоритмы базируются на разбиении сеточной расчетной области на подобласти с параметризованной величиной пересечений и различными интерфейсными условиями на смежных границах. Рассматриваются вопросы, возникающие при алгебраической декомпозиции исходной матрицы. Применяются различные двухуровневые итерационные процессы, включающие в себя предобусловленные крыловские методы с использованием грубосеточной коррекции, а также синхронное решение вспомогательных систем в подобластях с помощью прямых или итерационных алгоритмов. Распараллеливание алгоритмов реализуется средствами гибридного программирования с формированием MPI-процессов для каждой подобласти и использованием в них многопотоковых вычислений над общей памятью. Информационные коммуникации между соседними подобластями осуществляются на каждой внешней итерации путем предварительной организации буферов обмена и применения неблокирующих операций с возможностями проведения арифметических действий на фоне передачи данных., Algebraic, geometric, and informational aspects of parallel decomposition methods are considered to solve large systems of linear equations with sparse matrices arising after approximation of multidimensional boundary value problems on unstructured grids. Algorithms are based on partitioning a grid computational domain into its subdomains with a parameterized value of overlapping and various interface conditions on the adjacent boundaries. Some questions arising in algebraic decomposition of the original matrix are discussed. Various two-level iterative processes are used. They include both preconditioned Krylov methods with a coarse grid correction and the parallel solution of auxiliary subsystems in subdomains by direct or iterative algorithms. Parallelization of algorithms is implemented by means of hybrid programming with separate MPI processes for each subdomain and by multithreaded computations over shared memory in each of the subdomains. Communications between adjacent subdomains are performed on each external iteration via the preliminary creation of some exchange buffers and using non-blocking operations, which makes it possible to combine both the arithmetic operations and data transfer., ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ: НОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ, Выпуск 2 2016