Программирование. Рубрика в журнале - Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование
Методы типа Адамса для решения вырожденных интегро-дифференциальных уравнений
Статья научная
В статье рассмотрены линейные интегро-дифференциальные системы уравнений первого порядка с тождественно вырожденной матрицей перед производной. Для данных систем задано начальное условие, которое предполагается согласованным с правой частью. Рассматриваемые в статье постановки задач возникают при математическом моделировании сложных электрических цепей. Используя аппарат матричных полиномов, выделен класс задач, имеющих единственное решение. Обсуждаются трудности численного решения таких задач, в частности неустойчивость многих неявных методов. Для численного решения такого класса задач предложены многошаговые методы, которые основаны на явной квадратурной формуле Адамса для интегрального слагаемого и на экстраполяционных формулах. Сформулированы достаточные условия сходимости таких алгоритмов к точному решению. Приведены результаты численных расчетов, которые хорошо согласуются с теоретическими выкладками.
Бесплатно
Многостороннее защищенное вычисление полиномов от нескольких переменных
Статья научная
Целью децентрализации вычислений, выполняемых участниками протоколов информационного взаимодействия, обычно является повышение надежности и защищенности информационных систем. Основу децентрализованных вычислений составляют протоколы многосторонних защищенных вычислений (ПМЗВ), которые обычно не являются универсальными, а строятся для конкретных вычисляемых функций. В настоящей работе строится ПМЗВ для вычисления значений полиномов от нескольких переменных над конечным полем. Построенные протоколы основаны на линейных схемах разделения секрета, а их характеристики, такие как мощность правомочных и неправомочных коалиций, могут быть описаны в терминах характеристик линейных кодов и их степеней Шура - Адамара. В работе приводятся некоторые коды и кодовые конструкции, для которых удается такие характеристики найти аналитически.
Бесплатно
Моделирование и оценивание траектории движущегося объекта
Статья научная
Построена линейная дискретная модель кругового движения влево/вправо с заданным радиусом. Сформулирован и реализован новый алгоритм математического моделирования траектории движущегося объекта, состоящей из отрезков прямолинейного и кругового движения в условиях неполных зашумленных измерений. Показано, как применять алгоритмы оптимальной дискретной фильтрации для оценивания такой траектории. Разработан программный комплекс Моделирование и оценивание траектории подвижного объекта v1.0 для моделирования и линейного оценивания траектории движущегося объекта на основе дискретных моделей равномерного прямолинейного и кругового движения. Результаты работы могут найти применение при решении практических задач судовождения, робототехники, обработки сигналов со сканирующих дальномеров и др.
Бесплатно
Статья научная
В основу решения прямой задачи положены две основные идеи: сведение системы уравнений Максвелла, записанных в цилиндрической системе координат, к системе обыкновенных дифференциальных уравнений первого порядка с использованием интегралов Ломмеля для преобразования Фурье - Бесселя и учет конечных размеров геометрических параметров модели. Это позволяет решать прямые задачи для осесимметричных радиально неоднородных слоистых сред с учетом анизотропии как по удельной электропроводности, так и по магнитной проницаемости, в том числе для их дисперсий как функций частоты. Все это имеет важное значение при изучении околоскважинного пространства в методах геофизических исследований скважин.
Бесплатно
Статья научная
В настоящее время осуществляется переход системы российского образования на государственные образовательные стандарты третьего поколения, в которых требования к дисциплинам определяются с помощью компетенций. В данной статье представлена электронная модель федерального государственного образовательного стандарта высшего профессионального образования третьего поколения эГОС-3 (электронный Государственный Образовательный Стандарт третьего поколения), кратко описана ее реализация в рамках универсальной среды электронного обучения UniCST. Так же приведен пример использования при обучении современным параллельным вычислительным технологиям.
Бесплатно
Модификация алгоритма случайного леса для классификации нестационарных потоковых данных
Статья научная
Предложен метод классификации нестационарных потоковых данных. К таким данным относятся характеристики поведения сложных систем, процессы, обладающие высокой степенью стохастичности, такие как скорость ветра. В данной работе предложена эффективная модификация алгоритма случайного леса, позволяющая повысить точность классификации состояния путем взвешивания ответов отдельных классификаторов композиции. Опираясь на метод Accuracy Weighted Ensemble (AWE), взвешивание производится в соответствии с оценкой ошибки каждого классификатора на новых данных. Такая оценка производится с использованием метода k ближайших соседей и внутренней структуры случайного леса. В качестве стратегии обновления композиции используется замена классификаторов с низкой точностью на новых данных. Приводятся результаты тестирования предложенного метода и сравнение с другими современными методами.
Бесплатно
Статья научная
Развивается предложенный нами ранее подход построения разностных схем для решения жестких задач ударно-волновых течений гетерогенных сред с использованием неявного безытерационного алгоритма расчета межфазных взаимодействий. Метод крупных частиц модифицирован до схемы второго порядка точности по времени и пространству на гладких решениях. На первом этапе используются центральные разности с искусственной вязкостью TVD типа. На втором - TVD-реконструкция путем взвешенной линейной комбинации противопоточной и центральной аппроксимаций с ограничителями потоков. Схема дополнена двухшаговым методом Рунге - Кутта по времени. Схема является K-устойчивой - шаг по времени не зависит от интенсивности межфазных взаимодействий, а определяется числом Куранта для однородной системы уравнений (без источниковых членов). На тестовых задачах подтверждена монотонность, малая диссипативность, высокая устойчивость схемы и сходимость численных результатов к точным автомодельным равновесным решениям в газовзвеси. Показаны возможности схемы для численного моделирования физической неустойчивости и турбулентности. Метод может быть рекомендован для структурно-сложных течений газовзвесей.
Бесплатно
Некоторые обобщения теории Шеннона о совершенных шифрах
Статья научная
К. Шеннон в 40-х годах XX века ввел понятие совершенного шифра, обеспечивающего наилучшую защиту открытых текстов. Такой шифр не дает криптоаналитику никакой дополнительной информации об открытом тексте на основе перехваченной криптограммы. При этом хорошо известный шифр гаммирования с равновероятной гаммой является совершенным, но максимально уязвимым к попыткам имитации и подмены. Это происходит потому, что в шифре гаммирования алфавиты для записи открытых и шифрованных текстов равномощны. Также в данном шифре должны использоваться равновероятные гаммы, что не всегда достигается на практике. В данной обзорной работе рассматриваются задачи построения совершенных и (k|y)-совершенных шифров по заданному набору параметров, приводятся необходимые и достаточные условия данных шифров, рассматриваются совершенные и (k|y)-совершенные шифры замены с неограниченным ключом, а также совершенные шифры, стойкие к имитации и подмене шифрованных сообщений с необязательно равномерным распределением на множестве ключей.
Бесплатно
Новый алгоритм вычисления аппроксимаций Паде и его реализация в MATLAB
Статья научная
В работе предложен алгоритм вычисления аппроксимации Паде, основанный на выборе ее знаменателя с минимальной степенью. Показано, что новый алгоритм не приводит к появлению дуплетов Фруассара, в отличие от имеющихся в Maple и Mathematica процедур вычисления аппроксимаций Паде.
Бесплатно
О вычислении функциональной производной для одной задачи оптимального управления
Статья научная
Задача синтеза многослойной дифракционной решетки формулируется как задача оптимального управления и заключается в минимизации целевого функционала, зависящего от геометрических параметров профиля решетки. Градиентный метод является наиболее надежным и стабильным методом решения этой задачи. В статье представлен метод вычисления функциональной производной (градиента) целевого функционала, который выполняется путем решения сопряженной задачи со специальными граничными условиями. Кроме того, в статье обсуждается численная реализация этого решения и расчет градиента. Также представлены результаты вычислительного эксперимента.
Бесплатно
О сложности стратегии параллельного построения изображении для систем визуализации
Статья научная
В работе рассматриваются различные стратегии параллельного построения изображений и видеопоследовательностей на суперкомпьютерах для систем визуализации научных данных. Анализируется их вычислительная сложность. Приводятся оценки эффективности и масштабируемости стратегии для различных входных параметров задачи. Практическая апробация предложенных методов проведена на суперкомпьютере BlueGene /P.
Бесплатно
Об автоматизации применения размещения данных с перекрытиями в распределенной памяти
Статья научная
В статье рассматриваются блочно-аффинные размещения данных с перекрытиями для оптимизации параллельных вычислений в вычислительной системе с распределенной памятью. Примерами целевых вычислительных систем являются высокопроизводительные кластеры и перспективные системы на кристалле с большим количеством вычислительных ядер. Предлагается описывать размещение массива с перекрытиями как новый массив немного большей длины, у которого дополнительные элементы имеют значения некоторых элементов исходного массива. Рассматривается возможность разработки автоматического преобразования (компилятором) обычного размещения массива в распределенной памяти в новый массив, содержащий перекрытия. Предлагаемый метод иллюстрируется на известном численном алгоритме решения задачи теплопроводности.
Бесплатно
Определение локации в корпоративных Wi-Fi сетях
Статья научная
В статье рассмотрены существующие алгоритмы расчета локации, модели распространения радиосигнала внутри помещений, а также существующие ограничения, связанные с их применением для решения задачи локализации внутри помещений. Предложен способ для расчета локации в корпоративных Wi-Fi сетях с динамически меняющимися характеристиками на основе данных об уровне сигнала, регистрируемого базовыми станциями. Данный способ не требует предварительной настройки и калибровки мобильных устройств, что позволяет использовать его при отсутвии сервисов локации. Такая особенность предлагаемого способа решения не накладывает каких-либо ограничений на его применение в любой Wi-Fi сети, где базовые станции способны регистрировать данные об уровне сигнала мобильных устройств. Локация мобильного устройства определяется относительно отрезка, соединяющего две базовые станции. Количество базовых станций для расчета локации должно быть не менее двух. Критерии выбора соответствующего отрезка также описаны в данной работе. В основу предложенного метода положена модель, рекомендованная Международным союзом электросвязи (ITU-R 1238) для определения потерь мощности сигнала внутри зданий и помещений. В статье приведены результаты экспериментов по расчету локации мобильных устрйств.
Бесплатно
Оценка точки схода отрезков методом максимального правдоподобия
Статья научная
В работе представлен метод оценки положения точки схода набора сходящихся зашумленных отрезков. В качестве модели зашумления отрезка используется нормальный шум, накладываемый на его концевые точки. Точка схода определяется как точка, в которой достигает минимума функционал, зависящий от положения рассматриваемых отрезков. Для задания такого функционала в работе используется метод максимального правдоподобия. Полученный функционал позволяет как ставить задачу численной минимизации, так и задавать функцию соответствия отрезка пучку при необходимости отсеивания отрезков-выбросов из исходного набора. Применение предложенного метода иллюстрируется на примере исправления проективных искажений и последующей локализации страниц паспорта Российской Федерации на изображениях его разворотов. В рамках данной задачи предполагается, что выделенные на изображении отрезки соответствуют нескольким пучкам и содержат выбросы. Для обеспечения устойчивости и возможности оценки множества точек схода предложен алгоритм, основанный на схеме RANSAC. Применение метода проективной нормализации позволило сократить количество ошибок локализации страниц с 6,4% до 1,8%.
Бесплатно
Параллельные реализации симплекс-метода для безошибочного решения задач линейного программирования
Статья научная
В работе рассмотрены подходы к решению задачи линейного программирования с абсолютной точностью, достигаемой применением в алгоритмах симплекс-метода дробно-рациональных вычислений без округления. Если при этом m - минимальная из размерностей задачи, 1 - число бит, необходимых под один численный элемент исходных данных, то пространственная сложность алгоритма не превосходит 41m4 + o(m3), при этом вычислительная сложность одной итерации симплекс-метода не превосходит O(lm4), а эффективность распараллеливания (т.е. отношение ускорения к числу процессоров) в предложенной реализации параллельного алгоритма составляет в асимптотике 100%.
Бесплатно
Статья научная
Предлагается модификация метода декомпозиции Шварца для дифференциальных уравнений переноса, содержащих производные дробного порядка. Доказывается сходимость метода. Приводятся описание численной схемы и схемы распараллеливания, а также оценка эффективности предлагаемого параллельного алгоритма.
Бесплатно
Статья научная
Данная статья посвящена проблеме подбора параметров при моделировании надежности программного обеспечения. В статье рассматривается процесс подбора параметров S-образной модели роста надежности ПО на основе данных об отказах в предыдущих релизах, проводится сравнение точности модели при разных способах подбора параметров. В качестве базовой модели, описанной в данной статье, используется модель Goel-Okumoto. Данная модель строится на основе данных об отказах в программе за определенный промежуток времени. Для того, чтобы получить адекватные оценки при помощи данной модели требуется определенное количество данных об отказах, которые недоступны до тех пор, пока система не была протестирована в течение достаточно долгого периода времени. В качестве экспериментальных данных используются статистические данные, собранные в течение трех последовательных релизов программного продукта промышленного масштаба. Оценка параметров модели была выполнена при помощи функции максимального правдоподобия.
Бесплатно
Статья научная
Рассматривается система линейных алгебраических уравнений с интервальной матрицей коэффициентов и интервальной правой частью. Для данных систем вводится понятие псевдорешения. Доказано существование псевдорешения для любых интервальных систем линейных уравнений, предложен способ поиска псевдорешения с помощью решения соответствующей задачи линейного программирования. Вследствие вырожденности полученной задачи для ее решения необходимо использовать вычисления, обеспечивающие точность, намного превышающую возможности стандартных типов данных языков программирования. Симплекс-метод в сочетании с безошибочными дробно-рациональными вычислениями дает решение задачи. Для реализации используется крупнозернистый параллелизм в распределенных системах на основе MPI. Для реализации безошибочных дробно-рациональных вычислений на GPU используется CUDA C.
Бесплатно
Статья научная
Проведено исследование влияния неопределенности в кинетических параметрах на результаты решения прямой и обратной задач химической кинетики. Кинетические данные представлены интервалами и рассматриваются как объекты интервального анализа. Разработан алгоритм решения прямой задачи методом интервального анализа чувствительности и алгоритм решения обратной задачи по вычислению областей неопределенности параметров. Проведен вычислительный эксперимент по поиску интервального вектора параметров на примере промышленно значимой реакции. Показано, что интервальное решение прямой задачи, полученное для математической модели реакции, удовлетворяет заданному предельно допустимому значению погрешности в экспериментальных замерах концентраций участвующих веществ.
Бесплатно
Статья научная
Задача планирования выполнения пакетов заданий в многостадийных системах при наличии ограничения на длительность интервалов времени ее функционирования является комплексной. Ее решение предполагает (с учетом требования формирования комплектов из результатов) определение составов пакетов, составов групп пакетов, выполняемых в течение временных интервалов заданной длительности, расписаний выполнения пакетов на приборах многостадийной системы. Для определения комплексных решений применен аппарат теории иерархических игр. Реализуется построение модели иерархической игры для принятия решений по составам пакетов, групп пакетов и расписаниям выполнения пакетов. В модели учтено требование формирования комплектов из результатов выполнения пакетов заданий. Задача определения составов групп пакетов является NP-трудной, поэтому для ее решения требуется применение приближенных методов оптимизации. Формулируются метод построения начального решения по составам групп пакетов и метод распределения результатов выполнения пакетов заданий по комплектам. Сформулирован способ построения новых решений по составам групп пакетов заданий. Введены условия, позволяющие определять исключаемые из групп пакеты на основе количества результатов выполнения заданий каждого типа, не включаемых в комплекты. Предложен метод локальной оптимизации решений по составам групп пакетов.
Бесплатно
