Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика

Алгоритм соединения циклов для метрической задачи коммивояжера на максимум

Панюков Анатолий Васильевич, Леонова Юлия Федоровна

Статья научная

Задача коммивояжера на максимум имеет ряд практических приложений, например, при сжатии произвольных данных и анализе последовательностей ДНК. При том, что задача коммивояжера на максимум является менее разработанной, чем задача коммивояжера на минимум, для ее решения существуют эффективные приближенные алгоритмы. В статье приведены оценки точности лучших на сегодняшний день алгоритмов для приближенного решения метрической задачи коммивояжера на максимум, и предлагается еще один алгоритм приближенного решения задачи коммивояжера на максимум, состоящий из поиска 2-фактора максимального веса в заданном графе, а затем применения операции оптимального соединения циклов в один гамильтонов цикл. Приведено доказательство, что для метрической задачи коммивояжера на максимум отношение длины найденного алгоритмом гамильтонова цикла к максимально возможной длине гамильтонова цикла не менее 5/6. Вычислительная сложность алгоритма не превышает O(|V|3). Проведено тестирование качества алгоритма на случайно сгенерированных матрицах стоимостей с евклидовой метрикой. Аналитическое и численное исследование алгоритма объединения циклов позволило выдвинуть гипотезу об асимптотической точности алгоритма на классе метрических задач коммивояжера на максимум.

Бесплатно

Об одном методе восстановления пропущенных значений потокового временного ряда в режиме реального времени

Цымблер Михаил Леонидович, Полонский Вячеслав Александрович, Юртин Алексей Артемьевич

Статья научная

Проблема восстановления пропущенных значений потокового временного ряда в режиме реального времени возникает в широком спектре практических приложений цифровой индустрии и интернета вещей.В статье предложен новый метод восстановления на основе совместного применения технологий интеллектуального анализа временных рядов и искусственных нейронных сетей. Метод предполагает три этапавосстановления: предварительная обработка данных, распознавание и реконструкция. Предварительнаяобработка предполагает однократную предварительную подготовку обучающих выборок данных. Распознавание и реконструкция реализуются с помощью нейронных сетей, обучаемых на указанных выборках. Предварительной обработке подвергается заранее сохраненный фрагмент потокового временного ряда безпропусков, в котором выполняется поиск набора типичных подпоследовательностей (сниппетов). Распознавание реализуется с помощью сверточной нейронной сети, на вход которой подается вектор из элементоввременного ряда, предшествующих пропуску. Распознаватель выдает сниппет, на который более всего похожа входная подпоследовательность. Реконструкция реализуется с помощью рекуррентной нейронной сети,на вход которой подается конкатенация вывода распознавателя и вектора элементов ряда, предшествующих пропуску. Реконструктор выдает восстановленное значение. Представлены результаты экспериментов,показывающих высокую точность восстановления и преимущество предложенного метода перед аналогами. Ключевые слова: временной ряд, восстановление пропущенных значений, режим реального времени, сверточная нейронная сеть, рекуррентная нейронная сеть, типичные подпоследовательности.

Бесплатно

Организация обмена данными в рамках платформы мобильной медицины

Волков Иван Алексеевич, Радченко Глеб Игоревич, Черных Андрей Николаевич

Статья научная

Мобильная медицина является важной составляющей для реализации постоянного мониторинга здоровья, который открывает для врачей, пациентов и исследователей новые возможности. Экспоненциальныйрост сферы привел к увеличению скорости появления новых решений на рынке здравоохранения и, соответственно, к увеличению количества информации о здоровье населения. Однако сегодня практически всясобираемая сервисами мобильной медицины информация изолирована друг от друга, так как распределенапо разным сайтам и мобильным приложениям. Отсутствие у пользователя возможности удобно управлятьсвоими медицинскими данными и делиться ими является существенной проблемой на текущий момент.Создание платформы мобильной медицины позволит решить данную проблему, предлагая механизмы наоснове которых сторонние разработчики могут размещать свои сервисы и организовывать межсервисныйобмен данными пользователей. В рамках нашей работы мы провели анализ существующих решений нарынке мобильной медицины, описали варианты использования сервисов в сфере мобильной медицины. Нами предложена концепция платформы мобильной медицины и проведено сравнение способов организацииобмена медицинскими данными. На основе проведенного анализа нами был выбран и реализован прототипсистемы обмена медицинскими данными между мобильными клиентами на основе однорангового (peer-to-peer) соединения.

Бесплатно

Система учета посещаемости студентов на основе распознавания лиц

Иванова Елена Владимировна, Струева Анастасия Юрьевна

Статья научная

В настоящее время одним из значимых факторов для повышения качества подготовки специалистов является учет посещаемости студентов. Данный процесс может быть автоматизирован. В статье предлагается подход к построению системы учета посещаемости студентов на основе технологии распознаваниялиц, которая позволяет идентифицировать множество людей одновременно без прямого контакта с ними ибез использования дорогостоящего оборудования. Данный подход основан на сверточных нейронных сетях RetinaFace и ResNet, выбранных на основе обзора современных методов распознавания лиц, представленного в статье. Архитектура нашей системы учета посещаемости дополнена процедурами предобработкиизображений, которые по предложенной нами методике, основанной на мере BREN, проверяют качествоизображения и при необходимости применяют к изображению алгоритмы для уменьшения шума, повышения резкости, увеличения яркости и выравнивания цветов. Представлены результаты вычислительныхэкспериментов, показавшие более высокую эффективность предложенного подхода по сравнению с аналогами.

Бесплатно

Unified approach for provision of supercomputer center resources

Paokin A.V., Nikitenko D.A.

Статья научная

Within one supercomputer center, there may be several computing systems with different architectures and principles of work with the end user. When organizing user access, it is necessary to fully describe the systems for the coordinated choice of tasks, software packages and hardware by the user, as well as to take into account the details of quotas, authentication, and launching applications on each of the individual machines within a single workflow. In this paper, we propose an approach to the provision of resources of a supercomputer center, where a user, using a complete description of computing systems, creates requests for access with desirable quotas. The approach describes the life cycle of access. When an access state transition occurs, it is supposed to interact with computing systems through their interfaces without deep integration. An overview of widely used approaches to quoting and organizing access is given, and the proposed approach is implemented as a software module for the Octoshell supercomputer center support system and tested on a computing system managed by the OpenNebula cloud computing platform.

Бесплатно

Высокопроизводительные вычислительные ресурсы Южно-Уральского государственного университета

Биленко Роман Владимирович, Долганина Наталья Юрьевна, Иванова Елена Владимировна, Рекачинский Александр Игоревич

Статья научная

В настоящее время в Южно-Уральском государственном университете достигнуты значительные результаты в области суперкомпьютерного моделирования, искусственного интеллекта и больших данных. ЮУрГУ обладает энергоэффективным суперкомпьютером «Торнадо ЮУрГУ», который занимает 15е место в рейтинге самых мощных суперкомпьютеров СНГ ТОП50 (сентябрь 2021). Для исследований в области искусственных нейронных сетей в ЮУрГУ был установлен специализированный многопроцессорный комплекс «Нейрокомпьютер». «Нейрокомпьютер» использует мощные передовые графические ускорители для обучения нейронных сетей. Суперкомпьютер «Торнадо ЮУрГУ» и комплекс «Нейрокомпьютер» находятся в центре научной жизни Университета, позволяя производить сложнейшие вычисления для расчетов в области инжиниринга, естественных наук, наук о человеке и искусственного интеллекта. Вычислительные ресурсы ЮУрГУ используются в образовании и в коммерческих целях для расчетов задач партнеров Университета. В работе описываются характеристики высокопроизводительного оборудованияЮУрГУ, доступное системное и прикладное параллельное программное обеспечение, приведены сведения о решенных научных и инженерных задачах.

Бесплатно