Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 316
Помехоустойчивый алгоритм построения поля потоков изображений отпечатков пальцев
Статья научная
Поле потоков отпечатков пальцев является одной из наиболее важных характеристик узора и оказывает большое влияние на всю процедуру дактилоскопической идентификации. Методы для построения поля потоков, основанные на градиенте, весьма популярны, однако, слишком чувствительны к различным шумам и дефектам, которые тем или иным образом проявляются на многих изображениях отпечатков. В данной статье предлагается новый метод построения поля потоков для цифровых изображений отпечатков пальцев. Он позволяет улучшить решение ряда ключевых задач обработки изображений. Среди таких задач прогноз направлений линий в области складок кожи, шрамов и других дефектов поверхности пальца. Метод опирается на такие подходы, как обработка изображения на субпиксельном уровне, на кластерный анализ поля градиентов изображения и заключатся в последовательном применении нескольких алгоритмов. Это интерполяция изображения и оценка значений градиента на нем, свертка поля градиента с заданным шаблоном для борьбы с шумами на субпиксельном уровне, выделение опорных областей на основе построения локальных оценок качества узора, прогнозирование поля направлений от опорных областей на всё изображение с адаптацией прогнозируемых значений под результаты измерений. Верификация результатов работы предлагаемого метода выполнена с помощью веб-фреймворка, созданного на базе Болонского университета в Италии. Новые результаты верификации сравниваются с результатами верификации предшествующего метода, развитого в данной статье, и с другими опубликованными алгоритмами на том же веб-фреймворке.
Бесплатно
Статья научная
Статья посвящена краткому обзору истории и авторской оценке состояния реализации проектов сбора и распределенной обработки данных, основанной на использовании Грид-технологий. Особое внимание уделяется этапам реализации и областям их применений в рамках панЕвропейского проекта EGI (European Grid Initiative), а также перспектив его развития для возможной реализации проекта типа WGI (Wordlewide Grid Initiative).
Бесплатно
Построение самонепересекающихся OE-маршрутов в плоском эйлеровом графе
Статья научная
В статье предложен полиномиальный алгоритм построения самонепересекающегося маршрута с упорядоченным охватыванием в плоском эйлеровом графе. Предложенный подход состоит в расщеплении всех вершин исходного графа степени выше 4 и введении фиктивных вершин и ребер, сводя, таким образом, исходную задачу к решенной ранее автором задаче построения A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. Приведенный алгоритм сведения решает поставленную задачу за полиномиальное время. Рассмотрен тестовый пример построения самонепересекающейся цепи с упорядоченным охватыванием. Данная задача возникает при технологической подготовке процесса раскроя, когда требуется определить маршрут движения режущего инструмента, при котором отсутствуют самопересечения траектории резки и отрезанная от листа часть не требует разрезаний. Раскройный план представлен в виде плоского графа, являющегося его гомеоморфным образом. Предложенный в статье алгоритм решает проблему маршрутизации при вырезании деталей, когда на маршрут движения режущего инструмента одновременно наложены такие технологические ограничения.
Бесплатно
Правда, искажающая истину. Как следует анализировать Top500?
Статья научная
После каждого выпуска рейтинга Top500 выполняются подсчеты и публикуются суждения, вида: «Подавляющее большинство суперкомпьютеров списка Top500 используется в промышленности». Появляются и другие подобные подсчеты и суждения о долях в списке Top500 разных типов процессоров, различных типов интерконнекта, производителей суперкомпьютеров, стран и т.п. Часто на базе подобных суждений принимаются серьезные решения, в том числе и на правительственном уровне. В данной работе показано: все, что фиксируется в подобных суждениях — правда, однако эта правда серьезно искажает истину и не отражает истинное положение дел в суперкомпьютерной отрасли. Кроме того, дается анализ причины серьезного отличия «правды» от «истины», приводятся методика корректного анализа данных Top500 и результаты такого анализа.
Бесплатно
Статья научная
Рассматривается применение задачи сильной отделимости для получения решений о покупке или продаже финансовых активов, таких как акции, иностранная валюта, фьючерсы и т.д. на биржевом рынке. Для этого выполнено построение двух систем линейных неравенств, задающих области в n-мерном пространстве, которые описывают экспертные торговые сигналы на основе адаптивной скользящей средней Кауфмана.
Бесплатно
Статья научная
Данная статья продолжает цикл работ автора, посвященных проблеме возраста информации (Age of Information, AoI) - метрики, используемой в информационных системах для мониторинга и управления удаленными источниками информации со стороны центра управления. Теоретический анализ систем передачи информации требует количественной оценки «свежести» информации, доставляемой в центр управления. В данной работе рассматривается модель двухузловой группы передачи, состоящей из источника информации (узла-отправителя), центра управления (узла-получателя) и нескольких каналов связи между ними. Предполагается, что пропускные способности каналов могут быть различными. При этом, сетевой протокол требует, чтобы информация, поступающая в узел-получатель считывалась в той же последовательности, в какой она была передана из узла-отправителя. В результате пакеты, нарушившие установленный порядок, задерживаются в узле-отправителе на время, требуемое для восстановления порядка. В данной работе процесс передачи информации моделируется с помощью многоканальной системы массового обслуживания с ограниченным накопителем, пуассоновским потоком заявок, экспоненциальным обслуживанием и переупорядочиванием заявок. При этом заявки моделируют пакеты передаваемой информации, накопитель системы - очередь пакетов на передачу, обслуживание заявок на приборах различной интенсивности - процесс передачи пакетов по каналам связи. Данная модель для оценки возраста информации использовалась впервые. В результате проведенного исследования получены выражения для преобразования Лапласа-Стилтьеса стационарной функции распределения и начальных моментов максимального значения возраста информации, называемого пиковым возрастом. Проведено численное исследование показателей производительности системы, включающее анализ пикового возраста информации при различных загрузках системы. Корректность аналитических результатов подтверждена результатами имитационного моделирования.
Бесплатно
Статья научная
Статья посвящена поиску троек взаимно частично ортогональных диагональных латинских квадратов порядка 10. Для каждой известной пары ортогональных диагональных латинских квадратов порядка 10 достраивается третий диагональный латинский квадрат таким образом, чтобы условие ортогональности между ним и квадратами из рассматриваемой пары нарушалось в как можно меньшем количестве ячеек. Используются два подхода: первый основан на сведении исходной задачи к задаче о булевой выполнимости, а второй - на использовании метода грубой силы. Построено несколько троек указанного вида с рекордными характеристиками. Эксперименты были проведены в проекте добровольных распределенных вычислений SAT@home, а также на вычислительном кластере.
Бесплатно
Применение вычислительных схем повышенной точности в проектировании антенных систем
Статья научная
Предложены эффективные вычислительные методы для исследования математических моделей антенных систем. Для построения математических моделей используются строгие электродинамические принципы и уравнения. Применение квадратурных формул повышенной точности для решения интегрального уравнения Поклингтона и специальной регуляризирующей процедуры для интегрального уравнения II рода позволяет получить устойчивые результаты моделирования с заданной точностью и высокими динамическими характеристиками.
Бесплатно
Применение гибридной вычислительной системы к решению прикладных задач аэрогазодинамики
Статья научная
Использованию графических ускорителей при решении прикладных задач уделяется большое внимание. В работе рассмотрены возможности использования гибридной вычислительной системы, основу которой составляют универсальные и графические процессоры.
Бесплатно
Статья научная
Работа посвящена вопросам применения графических процессоров для обработки запросов в параллельных системах баз данных. Целью данной работы является оценка эффективности выполнения запросов к сжатой базе данных без предварительной распаковки с использованием графических ускорителей, поддерживающих технологию CUDA. Объем внутренней памяти ГПУ на порядки меньше, чем объем оперативной памяти современных вычислительных систем. Это ограничивает размер базы данных, которую можно загрузить в память ГПУ и как следствие не позволяет раскрыть весь вычислительный потенциал графического процессора. Предлагается подход для обработки запросов над сжатыми данными на ГПУ. На основе предложенного подхода реализован эмулятор параллельной СУБД. Аналогичный эмулятор разработан для ЦПУ. Приведены результаты вычислительных экспериментов и произведена оценка эффективности данного подхода.
Бесплатно
Статья научная
Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье продемонстрировано применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Любой численный алгоритм имеет Q-детерминант. Q-детерминант состоит из Q-термов. Их число равно числу выходных данных алгоритма. Каждый Q-терм описывает все возможные способы вычисления одного из выходных данных на основе входных данных. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве применения метода проектирования Q-эффективных программ описано проектирование программ для реализации метода сопряженных градиентов на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ».
Бесплатно
Применение концепции активных хранилищ в задачах обработки данных сейсмических наблюдений
Статья научная
Предложен подход для организации распределенной обработки сейсмических данных на базе свободно распространяемого пакета Seismic Un*x и системы активного хранения данных с использованием TSim и ФС Lustre. В работе рассмотрены ключевые проблемы обработки сейсмических данных, и для каждой предложено и обосновано использование соответствующего инструмента из арсенала системы активного хранения данных. Обработка данных непосредственно на узлах хранения позволяет продемонстрировать значительную эффективность за счет минимизации количества дорогостоящих операций передачи данных по сети. Проведено исследование производительности разработанного программного прототипа по обработке сейсмических данных в системе активного хранения для оценки перспектив полноценной интеграции.
Бесплатно
Применение математического моделирования для выбора инвестиционной программы предприятия
Статья научная
В статье представлены три экономико-математические модели для формирования инвестиционной программы предприятия: (1) на основе принципа гарантированного результата (т.е. принципа максимина); (2) на основе принципа максимизации ожидаемого в дисконтированного дохода при заданном ограничении сверху на его дисперсию; (3) на основе принципа максимизации ожидаемого в дисконтированного дохода при ограничении сверху вероятности его недостижимости. Последние две модели дают не гарантированные, а средние оценки доходности в уловиях риска и неопределенности. Решения предложенных задач позволяют дать системную оценку инвестиционной привлекательности предприятия, которую можно использовать при выборе эффективного инвестиционного портфеля с учетом склонности к риску лица принимающего решение.
Бесплатно
Применение метода проектирования q-эффективных программ для алгоритма Дейкстры
Статья научная
Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье впервые продемонстрировано применение концепции Q-детерминанта для эффективной реализации алгоритма на графах. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве первого применения метода проектирования Q-эффективных программ для алгоритмов на графах описано проектирование программ для реализации алгоритма Дейкстры на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ». На основе анализа результатов экспериментального исследования определяются динамические характеристики разработанных программ и выявляются особенности их выполнения. Проведенные в статье исследования дают возможность сделать вывод, что применение концепции Q-детерминанта с целью разработки эффективных программ возможно не только для численных алгоритмов, но и для алгоритмов на графах.
Бесплатно
Применение многомерной квантильной функции в задаче пептид-белок докинг
Статья научная
Настоящая работа посвящена исследованию применения стохастических эволюционных алгоритмов оптимизации к задаче пептид-белок докинга. В статье продемонстрированы основные положения, сводящие докинг к задаче непрерывной глобальной оптимизации. Представлены основные особенности рассматриваемой задачи и возникающие трудности применения эволюционных алгоритмов оптимизации. Предложен способ применения эволюционных алгоритмов, включающий использование эмпирической квантильной функции. Приведено краткое «рекурсивное» определение структуры многомерной квантильной функции с использованием одномерного квантильного преобразования. Представлен сеточный подход применения квантильной функции и указаны его недостатки. Предложен детерминированный алгоритм построения выборки, приведена схема его распараллеливания и получаемое ускорение. Для квантильной функции описана схема использования параллельных вычислений, включающая вычисления на графических ускорителях. Предложено несколько способов параллелизации с использованием выборки в явном виде. Продемонстрирована их производительность в зависимости от размера выборки. Представлены результаты докинга с использованием эволюционного алгоритма и его модификации с применением квантильной функции. Выполнено сравнение с актуальным методом докинга в рамках одного силового поля. Проведен анализ результатов вычислительных экспериментов.
Бесплатно
Применение параллельных вычислений для аннотирования сенсорных данных
Статья научная
Аннотирование сенсорных данных предполагает автоматизированную разметку временного ряда показаний, снятых с сенсора, которая выделяет различные активности, заданные указанным рядом. Разметка активностей имеет широкий спектр практического применения: предиктивное техническое обслуживание, умное управление системами жизнеобеспечения, моделирование климата и др. Ранее нами разработан параллельный алгоритм PSF для аннотирования данных сенсоров с помощью графического процессора на основе концепции сниппетов. Сниппет представляет собой подпоследовательность, на которую похожи многие другие подпоследовательности данного ряда в смысле специализированной меры схожести, основанной на евклидовом расстоянии. В данной статье описаны два тематических исследования, выполненные с помощью алгоритма PSF: аннотирование показаний носимого виброакселерометра, закрепленного на человеке, и стационарного виброакселерометра, установленного на малогабаритной дробильной установке. В рамках исследований были проведены вычислительные эксперименты для оценки быстродействия и точности разработанного алгоритма. Также была исследована зависимость эффективности работы алгоритма от значений входных параметров: количества искомых сниппетов и длины подпоследовательности.
Бесплатно
Статья научная
Представлен подход к оптимизации вычислений, основанный на надстройке PROOF для пакета научных вычислений ROOT. Метод успешно применялся в задачах, возникающих в проекте NICA/MPD, таких как моделирование ridge-эффекта и вычисление радиационных длин детектора MPD. Получены зависимости ускорения от различных параметров.
Бесплатно
Статья научная
В связи со сложностью объекта исследования анализ данных в медицине является основным инструментом поиска закономерностей и проверки гипотез. Прежде всего, это относится к психологии, в том числе, к анализу поведения субъектов в тех или иных ситуациях. Для выявления высокотревожного состояния студентов, анализа склонности к депрессии или суициду ежегодно в Омском промышленно-экономическом колледже проводится исследование психоэмоционального состояния студентов. Традиционно для этого используются стандарные тесты, основанные на методике «Шкалы тревоги» Спилберегера-Ханина. Целью данной работы является снижение трудоемкости стандартных тестов. Значительные и слабо мотивированные усилия приходится прилагать студентам при заполнении тестов, затем преподавателям при обработке и анализе тестов. Для решения указанной проблемы предлагается сделать тест компактным за счет применения стандартных и оригинальных методов анализа данных с минимизацией потери точности тестирования. Основным новым результатом данной работы является диагностическая шкала, положенная в основу экспресс-оценки психоэмоционального состояния студентов. Расчет диагностической шкалы был выполнен с использованием графических процессоров на суперкомпьютере ИМ СО РАН. Исследования ориентированы на старшие классы общеобразовательных школ и младшие курсы учебных заведений среднего профессионального образования.
Бесплатно
Применение третичной структуры алгебраической байесовской сети в задаче апостериорного вывода
Статья научная
В теории алгебраических байесовских сетей существуют алгоритмы, позволяющие проводить глобальный апостериорный вывод с использованием вторичных структур. При этом построение вторичных структур предполагает использование третичной структуры. Следовательно, возникает вопрос об обособленном применении третичной структуры в задаче апостериорного вывода. Этот вопрос рассматривался ранее, но было приведено только общее описание алгоритма, при этом учитывались лишь модели со скалярными оценками вероятности истинности. В данной работе приведен алгоритм, расширяющий вышеупомянутый до возможности его использования в случае интервальных оценок. Помимо этого, важным свойством алгебраической байесовской сети является ацикличность, и корректность работы перечисленных алгоритмов обеспечивается только для ацикличных сетей. Поэтому необходимо также уметь проверять ацикличность алгебраической байесовской сети с применением третичной структуры. Описание этого алгоритма также представлено в работе, в его основе лежит ранее доказанная теорема, которая связывает количество моделей фрагментов знаний в сети с количеством непустых сепараторов и количеством компонент связности сильных сужений в цикличной АБС, а также доказанная в данной статье теорема о принадлежности двух моделей фрагментов знаний к одной компоненте связности сильного сужения. Для всех разработанных алгоритмов доказана корректность работы, а также вычислена их оценка временной сложности.
Бесплатно
