Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 316
Статья научная
Рассматриваются задачи поиска фраз и наборов слов в большом объеме текстов. В результате поиска получаем список документов, содержащих заданные слова, при этом документы, где слова располагаются ближе друг к другу, считаются более релевантными. Поскольку эта задача требует сохранения в индексе информации о каждом вхождении каждого слова в текстах, запросы, включающие часто встречающиеся слова, требуют для своего выполнения длительного времени. В некоторых поисковых системах предлагается ввести список стоп слов, которые не учитываются при поиске, но этот подход снижает качество поиска. В данной работе при поиске обрабатываются все слова и применяются дополнительные индексы. С помощью дополнительных индексов время выполнения поискового запроса, включающего часто встречающиеся слова, может быть снижено в десятки раз. Разработан новый вид индекса с трехкомпонентными ключами. Приведены алгоритмы поиска и результаты экспериментов поиска в сравнении с обычными индексами. Эксперименты показывают, что при применении разработанных индексов для определенного класса запросов, состоящих из самых часто встречающихся слов, скорость поиска возрастает более чем в 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. Поверхностная обработка ткани позволяет изменять коэффициент трения между нитями с минимальным увеличением веса, и в модели она учитывалась за счет изменения одного параметра - коэффициента сухого трения. Рассмотрено несколько способов распараллеливания задачи вытягивания нити из ткани, получены графики ускорения. Были получены расчетные зависимости нагрузки от перемещения при вытягивании нити из ткани с поверхностной обработкой и без нее. Расчетные результаты лежат в диапазоне разброса экспериментальных данных.
Бесплатно
Разработка компьютерных моделей войлочных материалов, применяемых в бронезащитных элементах
Статья научная
Статья посвящена разработке численными методами моделей войлочных материалов, применяемых в бронезащитных элементах. Для создания сетки конечных элементов войлочных материалов разработан программный комплекс на языке С++, спроектирован и реализован, проведено тестирование. Программный комплекс позволяет создавать численные модели войлочного материала с прямолинейными волокнами, либо с искривленными волокнами по ломаной линии. Были созданы модели войлочных материалов, проведено суперкомпьютерное моделирование ударного нагружения войлочного материала из высокопрочных высокомодульных волокон в пакете программ LS-DYNA, проведено сравнение полученных данных с экспериментальными, получены графики ускорений.
Бесплатно
Разработка компьютерных моделей модифицированных арамидных тканей
Статья научная
Статья посвящена разработке численными методами моделей модифицированных арамидных тканей (арамидных тканей с поверхностной обработкой), применяемых в бронезащитных элементах. На сегодняшний день актуальными задачами при разработке бронезащитных элементов (бронежилетов) являются минимизация их массы, снижение величины прогиба тыльной стороны бронепанели (уменьшение уровня травмирования тела человека). Большая часть энергии пули рассеивается за счет работы сил трения во время вытягивания нитей из баллистических (арамидных) тканей в бронежилете. Поверхностная обработка тканей позволяет увеличить фрикционное взаимодействие нитей и снизить прогиб тканевых преград при локальном ударе с минимальным утяжелением. Для создания сетки конечных элементов тканей с поверхностной обработкой разработано приложение, спроектировано и реализовано, проведено тестирование. Приложение позволяет создавать численные модели модифицированных арамидных тканей со сплошной поверхностной обработкой и частичной (полосами вдоль осей X и Y в плоскости ткани). В работе рассмотрена арамидная ткань полотняного переплетения P110 с поверхностной обработкой ПВА. Была создана модель ткани со сплошной поверхностной обработкой. Поверхностную обработку строили оболочечными элементами, которые соединяли нити основы и утка с наружной стороны. Проведено суперкомпьютерное моделирование ударного нагружения модифицированной арамидной ткани, расположенной на регистрирующей среде (техническом пластилине) в пакете программ LS-DYNA. Проведено сравнение полученных расчетных данных с экспериментальными, получен график ускорения.
Бесплатно
Разработка программного комплекса для анализа энергоэффективности программного обеспечения
Статья научная
В работе рассмотрена задача разработки энергоэффективного программного обеспечения. Основное внимание уделено программированию для мобильных устройств. Предложен новый программный инструмент для анализа энергоэффективности приложений для мобильных устройств. Инструмент позволяет собирать и обрабатывать экспериментальную информацию, характеризующую энергоэффективность приложений на используемой платформе. Приведено сравнение аналогичных инструментов. Описаны основная функциональность, метод использования и результаты применения на примере задачи матричного умножения. Проведен анализ энергоэффективности реализаций алгоритма с использованием набора команд SSE, а также технологий параллельного программирования OpenMP и Cilk Plus. Исследованы зависимость энергоэффективности от числа использованных потоков, количества кэш-промахов, количества переходов между C-State-состояниями процессора. Сформулированы выводы по результатам проведенного анализа. Приведены планы по дальнейшему развитию функциональности инструмента.
Бесплатно
Разработка системы динамического изменения контента видеоигр на основе эволюционного моделирования
Статья научная
Темой данного исследования является применение методов эволюционного моделирования (ЭМ) для автоматического создания и динамического изменения мультимедийных данных в рамках процедурной генерации контента (ПГК) видеоигр. Использование таких методов ЭМ, как генетические алгоритмы, позволяет решить проблемы персонализации и адаптируемости контента, имеющую большую значимость в индустрии видеоигр. В работе приведен обзор существующих систем ПГК на основе ЭМ и предложен новый универсальный метод представления персонажей в подобных системах. В рамках исследования реализована система эволюционного моделирования, основанная на предложенном методе; в отличие от существующих решений, разработанная система является универсальной и может использоваться в различных коммерческих и научных проектах.
Бесплатно
