Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi
Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 321
Статья научная
Представлен подход к оптимизации вычислений, основанный на надстройке PROOF для пакета научных вычислений ROOT. Метод успешно применялся в задачах, возникающих в проекте NICA/MPD, таких как моделирование ridge-эффекта и вычисление радиационных длин детектора MPD. Получены зависимости ускорения от различных параметров.
Бесплатно
Статья научная
В связи со сложностью объекта исследования анализ данных в медицине является основным инструментом поиска закономерностей и проверки гипотез. Прежде всего, это относится к психологии, в том числе, к анализу поведения субъектов в тех или иных ситуациях. Для выявления высокотревожного состояния студентов, анализа склонности к депрессии или суициду ежегодно в Омском промышленно-экономическом колледже проводится исследование психоэмоционального состояния студентов. Традиционно для этого используются стандарные тесты, основанные на методике «Шкалы тревоги» Спилберегера-Ханина. Целью данной работы является снижение трудоемкости стандартных тестов. Значительные и слабо мотивированные усилия приходится прилагать студентам при заполнении тестов, затем преподавателям при обработке и анализе тестов. Для решения указанной проблемы предлагается сделать тест компактным за счет применения стандартных и оригинальных методов анализа данных с минимизацией потери точности тестирования. Основным новым результатом данной работы является диагностическая шкала, положенная в основу экспресс-оценки психоэмоционального состояния студентов. Расчет диагностической шкалы был выполнен с использованием графических процессоров на суперкомпьютере ИМ СО РАН. Исследования ориентированы на старшие классы общеобразовательных школ и младшие курсы учебных заведений среднего профессионального образования.
Бесплатно
Применение третичной структуры алгебраической байесовской сети в задаче апостериорного вывода
Статья научная
В теории алгебраических байесовских сетей существуют алгоритмы, позволяющие проводить глобальный апостериорный вывод с использованием вторичных структур. При этом построение вторичных структур предполагает использование третичной структуры. Следовательно, возникает вопрос об обособленном применении третичной структуры в задаче апостериорного вывода. Этот вопрос рассматривался ранее, но было приведено только общее описание алгоритма, при этом учитывались лишь модели со скалярными оценками вероятности истинности. В данной работе приведен алгоритм, расширяющий вышеупомянутый до возможности его использования в случае интервальных оценок. Помимо этого, важным свойством алгебраической байесовской сети является ацикличность, и корректность работы перечисленных алгоритмов обеспечивается только для ацикличных сетей. Поэтому необходимо также уметь проверять ацикличность алгебраической байесовской сети с применением третичной структуры. Описание этого алгоритма также представлено в работе, в его основе лежит ранее доказанная теорема, которая связывает количество моделей фрагментов знаний в сети с количеством непустых сепараторов и количеством компонент связности сильных сужений в цикличной АБС, а также доказанная в данной статье теорема о принадлежности двух моделей фрагментов знаний к одной компоненте связности сильного сужения. Для всех разработанных алгоритмов доказана корректность работы, а также вычислена их оценка временной сложности.
Бесплатно
Статья научная
Рассматриваются задачи поиска фраз и наборов слов в большом объеме текстов. В результате поиска получаем список документов, содержащих заданные слова, при этом документы, где слова располагаются ближе друг к другу, считаются более релевантными. Поскольку эта задача требует сохранения в индексе информации о каждом вхождении каждого слова в текстах, запросы, включающие часто встречающиеся слова, требуют для своего выполнения длительного времени. В некоторых поисковых системах предлагается ввести список стоп слов, которые не учитываются при поиске, но этот подход снижает качество поиска. В данной работе при поиске обрабатываются все слова и применяются дополнительные индексы. С помощью дополнительных индексов время выполнения поискового запроса, включающего часто встречающиеся слова, может быть снижено в десятки раз. Разработан новый вид индекса с трехкомпонентными ключами. Приведены алгоритмы поиска и результаты экспериментов поиска в сравнении с обычными индексами. Эксперименты показывают, что при применении разработанных индексов для определенного класса запросов, состоящих из самых часто встречающихся слов, скорость поиска возрастает более чем в 90 раз.
Бесплатно
Прогнозирование банкротств предприятий с помощью экстремального градиентного бустинга
Статья научная
Использование моделей прогнозирования банкротства предприятий для управления инвестиционными рисками лежит в основе управленческой деятельности финансовых учреждений. Важным фактором, позволяющим финансовым учреждениям определять объем капитала для покрытия кредитных потерь, является точность прогноза. В большинстве исследований для построения моделей банкротства предприятий используются традиционные методы статистики (например, дискриминантный анализ и логистическая регрессия).Однако точность построенных моделей обычно является достаточно низкой. Это обусловлено несбалансированностью классов обучающих наборов (доля фирм-банкротов составляет несколько процентов от общего числа фирм), которые используются при построении моделей. В настоящее время широкое распространение получают такие методы машинного обучения как метод случайного леса и метод градиентного бустинга. В данном исследовании основной акцент делается на использовании экстремального градиентного бустинга для прогнозирования банкротства. Экстремальный градиентный бустинг, используя LASSO или Ridge регуляризацию, штрафует сложные модели, что помогает избежать переобучения. Также в ходе обучения экстремальный градиентный бустинг заполняет пропущенные значения в наборе данных в зависимости от величины потерь. В статье для повышения эффективности экстремального градиентного бустинга предлагается использовать технологию SMOTE для улучшения сбалансированности классов. Метрики качества решений, полученных улучшенным экстремальным градиентным бустингом, сравниваются с решениями полученными другими методами.
Бесплатно
Статья научная
Описана процедура поиска потенциальных предикторов и создания прогнозных правил нечеткой логики и нечетких нейронных сетей для последующего прогнозирования вспышек численности синезеленой водоросли M. aeruginosa. В результате натурных наблюдений ряда биотических и абиотических параметров водной среды, проведенных на озере Смолино (г. Челябинск) за теплый период 2009 и 2011 года получены временные ряды численности M. aeruginosa и значений сопутствующих параметров. С помощью кросс-корреляционного анализа данных установлено, что потенциальными предикторами квазипериодических колебаний численности M. aeruginosa с периодом 12-20 дней могут выступать численность водоросли P. duplex, температура воды и концентрация нитрат-иона. По результатам кросс-корреляционного анализа заданы прогнозные правила и функции принадлежности в диапазоне изменений предиктанта и предиктора от нуля до 1. Для «автоматического» задания прогнозных правил и функций принадлежности с помощью специально написанной программы произведено обучение нечеткой нейронной сети на данных о значениях предиктанта и отобранных в ходе предварительного анализа параметров-предикторов. Для сравнения результатов дополнительно осуществлена линейная экстраполяция данных о численности предиктанта. Выявлено, что экстраполяционный прогноз хорошо работает на квазилинейных интервалах изменения численности, а алгоритмы нечеткой логики потенциально способны определить время наступления интенсивных вспышек численности предиктанта.
Бесплатно
Программная поддержка модели BSF
Статья научная
В статье описана программная поддержка модели параллельных вычислений BSF (Bulk Synchronous Farm), ориентированной на итерационные алгоритмы с высокой вычислительной сложностью, разрабатываемые для многопроцессорных систем с распределенной памятью экзафлопсного уровня производительности. Программная поддержка включает в себя параллельный BSF-каркас и веб-приложение BSF-Studio. Приведены определение и классификация параллельных программных каркасов. Описан новый BSF-каркас, разработанный согласно BSF-модели: его файловая структура и логика работы. BSF-каркас представляет собой совокупность файлов исходного кода на языке C++, используемых для быстрого создания BSF-программ. Приведено подробное описание проектирования и реализации веб-приложения BSF-Studio, которое представляет собой визуальный конструктор BSF-программ. BSF-Studio обеспечивает поэтапное заполнение проблемно-зависимых частей BSF-каркаса, а также компиляцию и запуск программного кода.
Бесплатно
Программное исследование полурешеток, связанных с автоматом Ватерлоо
Статья научная
Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.
Бесплатно
Статья научная
В CAD/CAM-системах технологической подготовки процессов раскроя встает задача построения маршрута движения режущего инструмента, при котором отрезанная от листа часть не требует дополнительных разрезаний и запрещены пересечения траектории резки (касания допускаются). Формально такая задача может быть сформулирована как задача построения самонепересекающейся цепи в плоском эйлеровом графе, представляющим гомеоморфный образ раскройного плана. В конечном счете задачи построения маршрутов, удовлетворяющих технологическим ограничениям, сводятся к нахождению A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. В статье предложен алгоритм нахождения такой цепи. Выполнение алгоритма состоит из двух этапов. На первом этапе выявляются и расщепляются точки сочленения ранга k. На втором этапе построение цепи начинается из произвольной вершины, инцидентной внешней грани; первым ребром цепи выбирается инцидентное данной вершине ребро максимального ранга; далее организуется итерационный процесс, где в качестве следующего ребра выбирается непройденное ребро максимального ранга, являющееся левым либо правым соседом текущего ребра. Показано, что для плоского связного 4-регулярного графа алгоритм строит маршрут с указанными свойствами за линейное время. Представленные алгоритмы реализованы в виде компьютерной программы. Приведены примеры решения ряда тестовых задач.
Бесплатно
Краткое сообщение
Задачи нахождения маршрутов, удовлетворяющих определенным ограничениям, появились из конкретных практических ситуаций. Например, в задачах раскроя листового материала плоский граф является моделью раскройного плана, а маршрут, покрывающий все ребра, определяет траекторию режущего инструмента. В статье рассматривается алгоритм построения оптимального покрытия произвольного плоского (возможно, многосвязного) графа цепями с упорядоченным охватыванием, позволяющий построить такую траекторию движения режущего инструмента, при которой отрезанная от листа часть не требует дополнительных разрезаний. Показано, что алгоритм имеет полиномиальную сложность.
Бесплатно
Статья научная
В статье описывается оригинальный комплекс высокоуровневого синтеза, преобразующий последовательные программы в схемотехническую конфигурацию специализированных аппаратных средств для реконфигурируемых вычислительных систем. Из исходной последовательной программы строится абсолютно-параллельная форма - информационный граф. Далее, граф преобразуется в ресурсонезависимую параллельно-конвейерную форму - кадровую структуру, которую можно адаптировать к различному аппаратному ресурсу. Преобразование кадровой структуры в информационно-эквивалентную, но занимающую меньший аппаратный ресурс, структуру выполняется с помощью формализованных методов редукции производительности, что позволяет автоматически получить рациональное решение для заданной многокристальной реконфигурируемой вычислительной системы. В отличие от известных средств высокоуровневого синтеза результатом преобразования является не IP-ядро вычислительно-трудоемкого фрагмента, а автоматически синхронизированное решение прикладной задачи для всех кристаллов ПЛИС реконфигурируемой вычислительной системы. По сравнению с распараллеливающими компиляторами, число анализируемых вариантов синтеза рационального решения существенно меньше, что является отличительной особенностью описываемого комплекса. Применение программных средств высокоуровневого синтеза рассматривается на примере задачи решения системы линейных алгебраических уравнений методом Гаусса, содержащей информационно-взаимозависимые вычислительные фрагменты с существенно разной степенью параллелизма.
Бесплатно
Программный комплекс Радуга-Т для моделирования полей нейтронов в ядерно-энергетических установках
Статья научная
При проектировании и сопровождении эксплуатации ядерно-энергетических установок (ЯЭУ) необходимо выполнять моделирование в этих установках потоков нейтронов. При задании геометрии ЯЭУ необходимо учитывать границы разномасштабных конструктивных элементов, состоящих из материалов с существенно различными свойствами. Из-за больших размеров ЯЭУ для расчетов желательно использовать параллельные компьютеры. Для выполнения такого моделирования развиваются алгоритмы и программы численного решения краевой задачи для интегро-дифференциального уравнения переноса нейтронов на неструктурированных сетках. В статье приводится описание реализованных в программном комплексе РАДУГА-Т алгоритмов решения такой задачи. Представлены сетки, сеточные схемы, итерационные методы решения систем сеточных уравнений. Рассмотрены методы распараллеливания вычислений на гибридных компьютерах (используются технологии MPI и OpenMP). Представлены методы работы с пространственными сетками (построение, улучшение качества, декомпозиция, визуализация). Описаны особенности программной реализации. Проведено сравнение используемых в программном комплексе РАДУГА-Т алгоритмов с алгоритмами в других аналогичных программных комплексах. Приведены результаты исследования эффективности распараллеливания вычислений в задаче расчета коэффициента размножения нейтронов в модели легководного реактора. Исследования выполнены на многопроцессорном компьютере МВС-10П (МСЦ РАН). Приведены значения ускорения вычислений каждого из используемых в расчете алгоритмов и суммарного ускорения всего расчета.
Бесплатно
Проектирование оптимальной траектории проведения мониторинга объектов
Статья научная
В статье рассматривается задача разработки системы для моделирования траекторий движения робота, проводящего мониторинг в замкнутой области с земли: осмотр помещений, съемка промышленных объектов, оценка состояния фруктовых деревьев и т.д. Во время мониторинга на пути робота могут возникнуть некоторые препятствия: временно возникшие и устранимые (люди, небольшая мебель, бытовая техника, зона чрезвычайной ситуации) или постоянные (стены, постоянно установленное оборудование, зафиксированная мебель). Управление роботом осуществляется с помощью разработанной авторами программы, в которой хранится база данных маршрутов, успешно преодоленных роботом ранее, для наиболее точного определения траектории движения робота с учетом препятствий, встречающихся вдоль построенного пути. В статье рассматривается алгоритм построения графовой модели области проведения мониторинга для последующего поиска кратчайшего маршрута робота, заключающийся в дискретизации исследуемой области, выявлении возможных путей перемещения робота, анализе имеющихся препятствий и задании расстояний между объектами исследования. Показано, что после построения такого графа возможно применить один из алгоритмов поиска гамильтонова пути. Он соединяет вершины графа, соответствующие точкам проведения мониторинга. Результатом применения алгоритма будет кратчайший маршрут робота, либо сообщение о невозможности проведения мониторинга (частичной или полной неразрешимости задачи), если ряд возникших препятствий не позволяет проложить маршрут, проходящий через некоторые (либо через все) вершины. Выбор наиболее подходящего алгоритма, а также использование методов искусственного интеллекта для классификации препятствий и внесения корректировок в маршруты являются направлениями дальнейших исследований.
Бесплатно
Работа с данными в учебном языке программирования Синхро
Статья научная
Статья является продолжением собственных предыдущих исследований автора в рамках многолетней работы по созданию учебного языка программирования СИНХРО, предназначенного для ознакомления с параллелизмом. Основное направление работ - уточнение понятий, способствующих подготовке небольших многопоточных программ при обучении параллельному программированию. Главный результат последнего года заключается в развитии механизма взаимодействия локальной и общей памяти. Дан приоритет парадигме функционального программирования, популярной при подготовке прототипов многопоточных программ. Это помогло преодолеть зависимость порядка вычислений от последовательности вхождения выражений в текст программы и размещения данных в памяти. Описаны отличия от привычных понятий программирования, сдерживающих решение задач организации параллельных вычислений и предельно распределенных систем из ряда потоков, взаимодействующих в терминах доступа к значениям переменных, возможно расположенных в общей памяти. Повышен базовый уровень воздействий на память. Часть из них укрупнены для предотвращения неожиданностей из-за асинхронности и ослабления императивности элементов распределенных систем. Добавлено понятие команд-двойников для управления императивной синхронизацией взаимодействующих устройств, полезное при решении вопросов освобождения памяти.
Бесплатно
Разномасштабные задачи тепломассообмена в атомной энергетике
Статья научная
Данная статья посвящена обзору результатов, полученных в АО ОКБ «ГИДРОПРЕСС» с учетом наработанного опыта в области численного моделирования тепломассообмена в различных объектах атомной энергетики. Польза от применения CFD-технологий при проектировании реакторных установок заключается в возможности на базе ограниченного количества экспериментальных данных детально исследовать процессы тепломассообмена в установке с целью подтверждения или модернизации конструкторских решений на передовом научно-техническом уровне. Представлен ряд задач, для решения которых были использованы современные численные методы вычислительной гидродинамики с применением высокопроизводительной вычислительной техники. Показаны новые возможности расчетного моделирования при использовании современных суперкомпьютерных вычислительных технологий, а также сопутствующие вычислительные сложности и проблемы анализа результатов. Приведены примеры использования рассматриваемой технологии для моделирования экспериментальных стендов и натурных объектов при различных режимах работы. Показана автоматическая обработка результатов, позволяющая проводить анализ больших задач размерностью до 1 млрд. контрольных объемов по интегральным параметрам, характеризующим работу реакторной установки, таким как распределение расходов на входе и на выходе из активной зоны, распределение подогревов в тепловыделяющих сборках активной зоны, и т.д.
Бесплатно
Статья научная
В работе показано, что одна из проблем систем телекоммуникаций - это неопределенность отношения элемента к определенной подсистеме сети передачи информации, элемент может использоваться как абонентское оборудование и как подсистема управления. В результате затрудняется внедрение ad hoc сетей в структуру систем мобильной связи. Для устранения проблемы разработан метод описания структуры системы инфокоммуникаций. Метод основан на представлении системы как единой логической структуры. Основа структуры - это виртуальные узлы. Совокупность виртуальных узлов образует виртуальную сеть. Пропускная способность виртуальной сети изменяется по вероятностным законам. Вероятностные законы определяются на основе статистики посещения виртуального узла физическими узлами. Область использования для систем связи заключается в повышении эффективности управления за счет прогнозирования альтернативных маршрутов передачи информации и синтеза систем связи различных стандартов. Результаты можно использовать для исследования взаимодействий социальных и экономических систем региона. Для демонстрации результатов проведен эксперимент по прогнозированию количества физических узлов в заданном виртуальном узле. По полученным данным рассчитана вероятность появления в виртуальном узле физических объектов. Результаты расчета позволяют построить карту посещаемости территории физическими узлами и рассчитать маршруты передачи трафика между виртуальными узлами.
Бесплатно
Статья научная
В работе изложены результаты по созданию виртуального стенда и отработке CFD моделей проточных частей беcфланцевых расходомеров на суперкомпьютере «Торнадо ЮУрГУ». Представлена структура виртуального стенда для проведения параметрических расчетов. Представлены результаты численного моделирования течения в проточной части бесфланцевого вихревого расходомера для сжимаемой (воздух) и несжимаемой среды (вода).
Бесплатно
Разработка и реализация группового протокола генерации ключа на базе IKE
Статья научная
В качестве основы информационного взаимодействия участников в недоверенной среде часто выступает протокол выработки общего секретного ключа. С помощью такого ключа в дальнейшем может быть построен защищенный канал или защищенная сеть связи. В настоящее время актуальна задача разработки протоколов генерации общего ключа для группы участников. Одним из способов построения таких протоколов является обобщение протокола для двух участников на случай нескольких участников. В работе строится протокол генерации общего секретного ключа для группы участников (для конференции). В основе разработанного протокола лежит протокол IKE (Internet Key Exchange) из семейства протоколов IPSec для двух участников, обеспечивающий выполнение таких свойств безопасности, как аутентификация субъекта и сообщения, генерация новых ключей, защита от чтения назад, защита от повтора и ряда других. Стойкость разработанного протокола генерации ключа основана на сложности задачи дискретного логарифмирования в циклической группе. В работе исследуются свойства безопасности, обеспечиваемые построенным протоколом, в частности, исследуется стойкость к коалиционным атакам, актуальным для групповых протоколов. Также отмечаются некоторые особенности практического применения построенного протокола.
Бесплатно
Статья научная
В настоящее время важнейшими задачами при исследовании структуры земной коры являются обратные задачи гравиметрии и задачи магнитометрии о нахождении поверхностей раздела сред на основе данных о гравитационном и магнитном поле, измеренном на некоторой площади земной поверхности. В основе методов решения этих задач лежат идеи итеративной регуляризации. После дискретизации эти задачи сводятся к системам нелинейных уравнений большой размерности, решение которых требует большого количества вычислительных ресурсов. Необходимость в повышении точности решения требует дополнительных вычислений, что влечет за собой увеличение времени счета. В работе описывается система удаленных вычислений и интегрированного в нее комплекса программ для графических ускорителей, реализующих наиболее быстрые и экономичные по памяти из разработанных ранее итерационных алгоритмов на основе градиентных методов. Эта система представляет собой веб-портал, являющийся универсальным решением для запуска задач на удаленных кластерах. Важнейшим преимуществом такого портала является его простота использования: при подключении к кластеру для осуществления вычислений более не требуется производить установку дополнительного ПО на самом кластере, также не требуется наличие привилегированной учетной записи для работы с кластером. Все что требуется - действующая учетная запись на исполняемом кластере, остальную работу по коммуникации с центром обработки данных (ЦОД) берет на себя портал. Портал может легко масштабироваться при росте количества пользователей, которые могут загружать необходимые алгоритмы и выполнять вычисления с помощью ЦОД.
Бесплатно
Разработка компьютерных моделей баллистических тканей с поверхностной обработкой
Статья научная
Баллистические ткани на сегодняшний день широко применяются в качестве элементов защитных структур. Актуальными задачами при разработке бронеструктур являются минимизация их массы, уменьшение кинетической энергии пули, передаваемой объекту, расположенному за бронепанелью (снижение величины прогиба тыльной стороны панели). Значительная часть энергии пули рассеивается за счет работы сил трения при вытягивании нитей из ткани. Умение предсказывать работу баллистической ткани при вытягивании нитей позволит проектировать высокоэффективные бронеструктуры. Поэтому были разработаны малопараметрические численные модели вытягивания нити из арамидной ткани Р110 полотняного переплетения, а также для этой ткани с разными типами поверхностной обработки (канифоль, силиконовая смазка) в пакете программ LS-DYNA. Поверхностная обработка ткани позволяет изменять коэффициент трения между нитями с минимальным увеличением веса, и в модели она учитывалась за счет изменения одного параметра - коэффициента сухого трения. Рассмотрено несколько способов распараллеливания задачи вытягивания нити из ткани, получены графики ускорения. Были получены расчетные зависимости нагрузки от перемещения при вытягивании нити из ткани с поверхностной обработкой и без нее. Расчетные результаты лежат в диапазоне разброса экспериментальных данных.
Бесплатно
