Эвристические алгоритмы и распределённые вычисления - аннотации статей

Журнал «Эвристические алгоритмы и распределённые вычисления»

На главную страницу журнала

Аннотации статей

Том 1, № 1 (2014) стр. 6–15
А. С. Андреев, О. А. Перегудова, К. В. Пахомов (Ульяновский государственный университет)
emails: AndreevAS@ulsu.ru, peregudovaoa@gmail.com, pahomovkv@yandex.ru
Моделирование управляемого движения трехколёсного робота с двумя степенями свободы
В работе на примере построения стабилизирующего управления движением мобильного трехколёсного робота с двумя степенями свободы обосновывается методика решения задачи о стабилизации нелинейных нестационарных систем с кусочно-постоянным управлением на основе дискретизации системы и применения метода бэкстеппинга. Данный метод основан на представлении всей системы в виде каскадного соединения подсистем и синтезе нелинейного закона управления на основе построения функций Ляпунова для каждой подсистемы. Эффективность построенного закона управления состоит в том, что, во-первых, он применим для широкого класса программных движений, во-вторых, легко реализуется программно, в-третьих, позволяет определять для каждого конкретного случая наиболее подходящий набор параметров управления. Новизна данной методики состоит в применении функций Ляпунова вида векторных норм и разностных уравнений сравнения, эффективных в построении законов дискретных управлений рассматриваемых систем, обеспечивающих более высокую скорость сходимости, расширение области притяжения решений, упрощение структуры управления по сравнению с известными результатами. Рассмотрена электромеханическая модель мобильного робота, движущегося по горизонтальной поверхности без проскальзывания, с двумя ведущими задними колесами, управляемыми при помощи двух независимых электроприводов постоянного тока, и передним рояльным колесом. К задаче синтеза кусочно-постоянного управления непрерывной системы применен подход, основанный на дискретизации системы с использованием аппроксимации Эйлера и построении стабилизирующих дискретных законов управления дискретной моделью. На основе рекуррентной процедуры метода бэкстеппинга, состоящей в переходе от задачи синтеза управления для кинематической модели к задаче построения управляющих сигналов динамической моделью робота, найден кусочно-постоянный закон управления, обеспечивающий практическую стабилизацию заданного нестационарного движения робота. Представлены результаты численного моделирования, подтверждающие эффективность предложенного закона управления.
Ключевые слова и фразы: стабилизация; мобильный колёсный робот; функция Ляпунова; метод бэкстеппинга.

Том 1, № 1 (2014) стр. 16–24
О. И. Горбанёва, Г. А. Угольницкий (Южный федеральный университет)
emails: gorbaneva@mail.ru, ougoln@mail.ru
Теоретико-игровые модели распределения ресурсов при управлении качеством речной воды в условиях коррупции. Часть I
Рассматривается задача распределения ресурсов в иерархических системах управления качеством водных ресурсов. Эта задача разбивается на две подзадачи: задача распределения ресурсов в иерархической системе и задача управления качеством речной воды. Обе полученные задачи решаются нахождением равновесия по Штакельбергу. При решении задачи распределения ресурсов учитывается наличие двух механизмов коррупции: связанные с величиной распределения ресурсов и с величиной контроля над использованием ресурсов, причём в качестве функций зависимости данных величин от взятки брались линейные. В каждом случае рассматривались как «жёсткая», так и «мягкая» коррупция. Введение фактора коррупции заключается в том, что Ведомый отдаёт некоторую долю полученного ресурса в качестве взятки Ведущему. Целью взятки для Ведомого является получение различных льгот от Ведущего. Задача рассматривалась также при помощи аппарата кооперативных игр. Найдены доходы и кооперативные эффекты всех коалиций, вычислены векторы Шепли и пропорционального распределения. Задача управления качеством речной воды решается с учётом трёх случаев. В первом случае количество загрязняющих веществ, сброшенных Ведомым в сточные воды, меньше первого порогового значения. В этом случае есть только задача Ведомого, Экологический Центр не участвует в игре. Во втором случае количество загрязняющих веществ, сброшенных Ведомым в сточные воды, больше первого, но меньше второго пороговых значений. В этом случае Экологический Центр назначает штраф Ведомому за каждую единицу сброшенного вещества выше первого порогового значения. В третьем случае количество сброшенных Ведомым загрязняющих веществ выше второго порогового значения. В этом случае Экологический Центр дополнительно к предыдущему штрафу назначает штраф за превышение второго порогового значения.
Ключевые слова и фразы: задача распределения ресурсов; управление качеством водных ресурсов; попустительство; вымогательство; иерархическая система управления.

Том 1, № 1 (2014) стр. 25–39
А. В. Нагорнов, А. В. Кац (Тольяттинский государственный университет)
emails: nagornovys@yandex.ru, elfsage@mail.ru
О методе молекулярной динамики с параметрическим температурно-зависимым потенциалом
В работе предлагается новый подход к выбору межатомных сил взаимодействия при моделировании свойств конденсированных сред методом молекулярной динамики, заключающийся в выборе парных потенциалов в виде медленно меняющихся функций температуры. Метод классической молекулярной динамики основан на уравнениях классической механики, численные методы ab initio основаны на уравнениях квантовой механики. Квантовая молекулярная динамика совмещает уравнения классической механики для атомов и квантовой механики для электронов. Предложенный метод молекулярной динамики с температурно-зависимым потенциалом основан на квазиклассическом приближении и представляет собой измененный метод классической молекулярной динамики. Квантово-механическое обоснование предложенного метода производится на основе теоремы Эренфеста и квантового уравнения Ньютона. Для подтверждения эффективности метода молекулярной динамики с температурно-зависимым потенциалом проводились расчеты термодинамических параметров стехиометрического диоксида урана. Диоксид урана был выбран как модельный материал с высокой температурой плавления (3120 K), что позволило продемонстрировать преимущества квазиклассического подхода по сравнению с классической механикой.
Сравнение результатов при использовании температурно-зависимого потенциала Борна-Майера с расчётами других авторов показывает небольшой выигрыш в точности при невысоких температурах (до 1100К). Однако особый интерес представляет более широкий температурный диапазон (до 3120 K), в котором преимущества расчётов в рамках предложенного подхода становятся особенно заметны. В работе были проведены расчёты постоянной решётки, энтальпии, теплоёмкостей при постоянном объёме и давлении, а также отношение теплоёмкостей. Совпадение расчётов с экспериментальными данными для всех рассмотренных температур составляет не более 0.5% – в то время как потенциалы без учёта температурных изменений в кристалле дают расхождение с экспериментальными данными от 2%, увеличивающееся с ростом температуры до 90%.

Ключевые слова и фразы: молекулярная динамика; температурно-зависимый потенциал; диоксид урана.

Том 1, № 1 (2014) стр. 40–52
А. В. Соколов (Институт прикладных математических исследований Карельского научного центра РАН)
А. В. Драц (Петрозаводский государственный университет)
emails: avs@krc.karelia.ru, adeon88@mail.ru
Моделирование некоторых методов представления n FIFO-очередей в памяти одного уровня
Во многих приложениях требуется работа с несколькими FIFO-очередями, расположенными в общем пространстве памяти. Для этого применяют различные программные или аппаратные решения. В данной работе предлагаются математические модели для последовательного циклического и связанного способов представления n FIFO-очередей в общей памяти. В обоих способах представления для каждой очереди нужны два указателя на начало и конец, но для первого способа элементы равных длин располагаются циклически в последовательных адресах выделенного очереди участка памяти, а во втором каждая очередь представлена в виде односвязного списка элементов, и переполнение памяти наступает тогда, когда список свободных элементов пуст и требуется включить элемент в какую-либо очередь. В этих способах представления операции включения и исключения элементов выполняются за время О(1). В последовательном способе мы имеем потери, в случае когда одна очередь переполнилась, а в других остаётся свободное место. В связном способе потерь нет до тех пор, пока не исчерпана вся свободная память в выделенном для очередей участке памяти, но требуется дополнительная память на связи в каждом элементе списка.
В статье решается задача нахождения оптимального разделения памяти между очередями в случае последовательного циклического представления очередей и задача анализа метода представления очередей в виде связных списков. В качестве математических моделей предложены случайные блуждания по целочисленным решёткам в различных областях n-мерного пространства. В качестве критерия оптимальности рассматривается минимальная средняя доля времени, которое системы проводит в состояниях «сброса хвоста». Это эквивалентно минимизации средней доли потерянных элементов. Эту величину разумно минимизировать, когда переполнение очереди является не аварийной, а стандартной ситуацией. В некоторых приложениях при переполнении очереди работа программы заканчивается, и тогда в качестве критерия оптимальности надо рассматривать максимальное среднее время до переполнения памяти. То есть если очередь занимает всю предоставленную ей память, то все последующие элементы, поступающие в неё, отбрасываются до тех пор, пока не появится свободная память (т.е. до тех пор, пока не произойдёт исключение элемента из очереди). Эта схема работы применяется, например, в работе сетевых маршрутизаторов в том случае, когда по мере увеличения трафика очередь на исходящем интерфейсе маршрутизатора заполняется пакетами. Такое поведение маршрутизатора называется «сбросом хвоста». Потери пакетов приводят к нежелательному результату, поэтому число таких ситуаций необходимо свести к минимуму. Для решения задач используется аппарат регулярных цепей Маркова.

Ключевые слова и фразы: FIFO-очереди; случайные блуждания; цепи Маркова; оптимальные динамические структуры данных.

Том 1, № 1 (2014) стр. 53–63
Д. В. Иванов (Самарский государственный университет путей сообщения)
email: dvi85@list.ru
Численный алгоритм оценивания параметров линейных динамических систем дробного порядка с помехой в выходном сигнале
Хорошо известно, что метод наименьших квадратов даёт смещённые оценки параметров для динамических систем с помехами наблюдения в выходных сигналах. В настоящее время активно развиваются методы нелинейного оценивания параметров динамических систем. Разработаны критерии оценивания параметров на основе минимизации нелинейных функции и доказана сильная состоятельность получаемых оценок параметров для линейных динамических систем дробного порядка с различными моделями шума. Проблема отыскания глобального экстремума нелинейной функции сопряжена с известными трудностями. В работе предложен численный алгоритм, позволяющий решить задачу оценивания параметров динамической системы дробного порядка с помехой в выходном сигнале, не применяя прямых методов отыскания глобального экстремума нелинейной функции, а только решая системы линейных уравнений.
На основании доказанной теоремы предлагается численный алгоритм, который позволяет:
1) ответить на вопрос, существует ли единственная оценка параметров;
2) определить начальное приближение, гарантирующее сходимость итерационного процесса к единственной оценке;
3) вычислить с любой наперёд заданной точностью оценку.
Предложенный алгоритм был реализован в среде Matlab, было проведено сравнение с методом наименьших квадратов. Результаты моделирования подтвердили высокую точность оценок параметров, получаемую с помощью предложенного алгоритма.
Дальнейшие направления исследований могут быть связаны с обобщением предложенных алгоритмов на многомерные и многосвязные системы. А также – обобщением результатов структурно-параметрических методов идентификации на случай линейных динамических систем дробного порядка.

Ключевые слова и фразы: метод наименьших квадратов; помеха в выходном сигнале; состоятельные оценки; разность дробного порядка.

Том 1, № 1 (2014) стр. 64–73
Ш. Т. Ишмухаметов, Б. Г. Мубараков (Казанский (Приволжский) федеральный университет)
emails: ishm@nextmail.ru, mubbulat@mail.ru
Об одном классе строго псевдопростых чисел
Одной из наиболее важных проблем в криптографии и теории чисел является проблема определения по заданному натуральному числу n, является ли оно простым или составным. Процедура, решающая такую задачу, называется тестом простоты. Известно множество различных тестов простоты, среди которых наиболее распространенным является тест простоты Миллера-Рабина. Этот тест является вероятностным, причем вероятность ошибки уменьшается при росте числа итераций, в ходе каждой из которых выполняется ряд вычислений, называемых раундом, с натуральным числом a, меньшим тестируемого числа n, называемым базой.
Составные числа, успешно проходящие тест Миллера-Рабина с какой-нибудь базой или набором баз, называются строго псевдопростыми по этому набору. Пусть \psi_k - это наименьшее строго псевдопростое число по набору баз, состоящему из первых k простых чисел. Числа \psi_k для k=1,2,3,... образуют возрастающую последовательность. Если тестируемое число n меньше какого-то \psi_k, то для точного определения, является ли n простым или составным, достаточно выполнить k раундов теста Миллера-Рабина с первыми k простыми числами в качестве баз. Следовательно, вероятностный тест превращается в детерминированный, что повышает его достоверность и сферу использования.
В этой статье мы рассмотрим разные алгоритмы построения строго псевдопростых чисел и оценим их вычислительную сложность. Наши результаты показывают, что существующие на сегодняшний день алгоритмы нахождения строго псевдопростых чисел являются недостаточно эффективными для использования в криптографии.

Ключевые слова и фразы: простые числа; тест простоты Миллера-Рабина; строго псевдопростые числа; алгоритм Джаешке.

Том 1, № 1 (2014) стр. 74–87
Б. Ф. Мельников (Самарский государственный университет)
email: bormel@rambler.ru
О звёздной высоте регулярного языка. Часть I: Основные определения
Проблема звёздной высоты была поставлена в 1963 г., а решена в 1988 г.; до настоящего времени опубликовано всего 2 решения этой проблемы. Первое из этих решений (принадлежащее К. Хашигучи) в литературе было названо экстремально сложным; второе (принадлежащее Д. Кирстену) существенно проще.
В настоящей статье рассматривается новый подход к данной проблеме; краткое описание этого подхода таково. Мы определяем звёздную высоту некоторого конечного автомата: рассматривая все возможные перестановки его состояний; обычным образом строя регулярные выражения, получаемые по каждой из этих перестановок с помощью теоремы Клини; и выбирая минимально возможное значение их звёздной высоты. Далее мы показываем возможность построить по любому заданному регулярному выражению такого недетерминированного конечного автомата, звёздная высота которого совпадает со звёздной высотой исходного регулярного выражения.
Следовательно, мы можем рассматривать такой гипотетический недетерминированный конечный автомат, который соответствует регулярному выражению, определяющему заданный регулярный язык и имеющему минимально возможную звёздную высоту; пусть это автомат K. Вместе с этим K мы будем также рассматривать конкретный порядок τ на множестве его состояний, соответствующий регулярному выражению, имеющему минимально возможную звёздную высоту.
Рассматривая состояния автомата K в порядке τ, мы для очередного выбираемого состояния получаем одну из следующих трёх возможностей. Либо для каждого цикла, проходящего через это состояние, существует эквивалентный, не проходящий через него. Либо существует некоторое иное состояние автомата, которое имеет меньшее значение функции порядка τ и определяет те же самые циклы, которые определяет рассматриваемое нами состояние. Либо мы можем добавить к автомату K некоторые дуги – получая при этом один из предыдущих вариантов.
С помощью конечной последовательности таких операций мы получаем автомат, эквивалентный заданному, – причём такой, у которого мы можем априори ограничить сверху число состояний. Таким образом, описываемая последовательность действий доказывает существование недетерминированного конечного автомата, определяющего заданный регулярный язык и имеющему минимально возможную звёздную высоту, с заранее ограниченным числом состояний.

Ключевые слова и фразы: недетерминированный конечный автомат; регулярный язык; звёздная высота.

Том 1, № 1 (2014) стр. 88–96
И. И. Газизов, А. В. Юлдашев (Уфимский государственный авиационный технический университет)
emails: igpooh@gmail.com, arthur@mail.rb.ru
Разработка параллельного линейного решателя для задачи гидродинамического моделирования нефтегазовых месторождений
Настоящая работа нацелена на разработку параллельных алгоритмов и программ решения систем линейных алгебраических уравнений (СЛАУ) на современных вычислительных системах с целью сокращения временных затрат при проведении гидродинамического моделирования нефтегазовых месторождений. Создание цифровых моделей нефтегазовых месторождений и их практическое применение является ресурсоёмкой вычислительной задачей, поэтому в практике нефтедобывающих компаний используются высокопроизводительные вычислительные системы, а также специализированные программные комплексы с поддержкой параллельных вычислений. В последнее время широкое распространение получили гибридные системы, в которые наряду с центральными процессорами устанавливаются массивно-параллельные ускорители, в частности графические процессоры NVIDIA, обладающие высокими характеристиками производительности и энергоэффективности. Нами разрабатывается параллельный линейный решатель, предназначенный для решения разрежённых СЛАУ, возникающих при моделировании многофазных фильтрационных потоков углеводородов в пористой среде. Для решения СЛАУ используется предобусловленный итерационный метод бисопряжённых градиентов со стабилизацией с параллельными модификациями неполного LU-разложения ILU(0) в качестве предобуславливателей. Программа реализована на языке C с использованием технологий OpenMP и CUDA. Ключевые вычислительные операции базируются на функциях библиотек Intel MKL, NVIDIA cuBLAS и cuSPARSE. Эффективность разработанной программы исследована на современной гибридной вычислительной системе (2 x Intel Xeon E5-2680 и 2 x NVIDIA K20X) при решении тестовых СЛАУ, полученных при гидродинамическом моделировании реальных нефтегазовых месторождений. В результате максимальное ускорение при параллельном решении СЛАУ на центральных процессорах составило до 4,8 раз, а использование графических процессоров позволило получить дополнительное ускорение до 2,7 раз.
Ключевые слова и фразы: графические процессоры; гидродинамическое моделирование; многоядерные системы; разрежённые матрицы.

Том 1, № 2 (2014) стр. 6–20
П. А. Вельмисов, Ю. В. Покладова, Е. С. Серебрянникова (Ульяновский государственный технический университет)
emails: velmisov@ulstu.ru, pokladovau@inbox.ru, serebr_k@mail.ru
Математическое моделирование систем контроля над изменением давления
Авторами разработаны математические модели механической системы, включающей в себя трубопровод с рабочей средой и датчик, составной частью которого является упругий элемент. Модели позволяют исследовать динамику упругого элемента датчика давления (в зависимости от закона изменения давления в камере сгорания) с учетом взаимодействия его с рабочей средой в трубопроводе, по которому эта среда передается от камеры сгорания двигателя к датчику. Датчик закреплен либо на торцевой, либо на боковой стенке трубопровода, который имеет прямолинейные стенки или содержит полость, и предназначен для измерения давления рабочей среды (например, на выходе из камеры сгорания двигателя), закон изменения которого считается заданным.
Задачи решались в линейной постановке, соответствующей малым прогибам упругого элемента (пластины) и малым возмущениям потенциала скорости среды. Также приведены новые нелинейные математические модели механической системы «трубопровод – датчик давления» и усовершенствованы разработанные ранее модели этой системы – за счет уточнения уравнений, описывающих динамику упругого элемента датчика.
Под рабочей средой понимается идеальная несжимаемая жидкость. Аэрогидродинамическое воздействие на элементы определялось из асимптотических уравнений, полученных на основе анализа точных уравнений аэрогидромеханики. Предполагалось, что элементы сжаты (растянуты) продольными силами и связаны с основаниями.
Проведен численный эксперимент по исследованию динамики упругого элемента датчика на основе предложенных моделей – в зависимости от закона изменения давления в двигателе. Исследовалась деформация элемента как функция времени (в фиксированных точках элемента) и как функция координаты (в фиксированные моменты времени) для различных параметров механической системы. Проведен сравнительный анализ разработанных моделей: линейных, нелинейных одностепенных и нелинейных двухстепенных.

Ключевые слова и фразы: трубопровод; датчик давления; деформация; упругий элемент; интегро-дифференциальные уравнения; динамика.

Том 1, № 2 (2014) стр. 21–29
О. И. Горбанёва, Г. А. Угольницкий (Южный федеральный университет)
emails: gorbaneva@mail.ru, ougoln@mail.ru
Теоретико-игровые модели распределения ресурсов при управлении качеством речной воды в условиях коррупции. Часть II
Рассматривается задача распределения ресурсов в иерархических системах управления качеством водных ресурсов. Эта задача разбивается на две подзадачи: задача распределения ресурсов в иерархической системе и задача управления качеством речной воды. Обе полученные задачи решаются нахождением равновесия по Штакельбергу. При решении задачи распределения ресурсов учитывается наличие двух механизмов коррупции: связанные с величиной распределения ресурсов и с величиной контроля над использованием ресурсов, причём в качестве функций зависимости данных величин от взятки брались линейные. В каждом случае рассматривались как «жёсткая», так и «мягкая» коррупция. Введение фактора коррупции заключается в том, что Ведомый отдаёт некоторую долю полученного ресурса в качестве взятки Ведущему. Целью взятки для Ведомого является получение различных льгот от Ведущего. Задача рассматривалась также при помощи аппарата кооперативных игр. Найдены доходы и кооперативные эффекты всех коалиций, вычислены векторы Шепли и пропорционального распределения. Задача управления качеством речной воды решается с учётом трёх случаев. В первом случае количество загрязняющих веществ, сброшенных Ведомым в сточные воды, меньше первого порогового значения. В этом случае есть только задача Ведомого, Экологический Центр не участвует в игре. Во втором случае количество загрязняющих веществ, сброшенных Ведомым в сточные воды, больше первого, но меньше второго пороговых значений. В этом случае Экологический Центр назначает штраф Ведомому за каждую единицу сброшенного вещества выше первого порогового значения. В третьем случае количество сброшенных Ведомым загрязняющих веществ выше второго порогового значения. В этом случае Экологический Центр дополнительно к предыдущему штрафу назначает штраф за превышение второго порогового значения.
Ключевые слова и фразы: задача распределения ресурсов; управление качеством водных ресурсов; попустительство; вымогательство; иерархическая система управления.

Том 1, № 2 (2014) стр. 30–42
Ю. Громкович (Швейцария, Цюрих, Технический университет – Eidgenössische Technische Hochschule)
email: jhromkov@inf.ethz.ch
Детерминированные подходы к алгоритмизации труднорешаемых задач. Часть I: Основные понятия
Данная статья является обзорной – в ней приведены обобщения работ автора, изданных за последние несколько лет в качестве научных и учебных статей и монографий. В текст статьи добавлена информация о самых новых достижениях в данной области теоретической информатики – разработке алгоритмов для труднорешаемых задач.
Подробно рассматривая в данной статье процесс разработки алгоритмов, мы не сводим рассмотрение трудных задач, а также нашу интерпретацию трудности, к так называемой NP-трудности. Более того, наибольшее внимание мы уделяем тем проблемам, для которых пока не доказаны ни NP-трудность, ни полиномиальная разрешимость – т.е. неизвестно, существуют ли алгоритмы, решающие эту задачу за полиномиальное время. Для частных случаев этих проблем, имеющих большую размерность, использовать алгоритмы экспоненциальной сложности на практике нельзя – поскольку при этом может получаться очень большой объём вычислений. Например, может потребоваться $2^{100}$ элементарных операций – а это лежит за границами физических возможностей компьютера. Однако, кроме того, мы считаем трудными и такие задачи, для которых полиномиальная разрешимость уже доказана – но пока неизвестны полиномиальные алгоритмы небольших степеней.
Несколько разных подходов к алгоритмизации труднорешаемых задач, рассматриваемых в данной обзорной статье, могут быть названы детерминированными. В первом из этих подходов мы допускаем, что в худшем случае разрабатываемые нами алгоритмы всё же будут иметь экспоненциальную сложность – но при этом они достаточно эффективны для большинства частных случаев проблемы, появляющихся в конкретных практических приложениях. Во втором подходе мы соглашаемся даже с тем, что усреднённая временна́я сложность разрабатываемых алгоритмов решения трудных проблем экспоненциальна – однако возрастает достаточно медленно. А в третьем подходе мы снимаем требование о том, чтобы алгоритм обязательно находил точное решение рассматриваемой проблемы. И, как обычно в подобных случаях, мы часто рассматриваем комбинации этих трёх подходов.
В части I данной статьи мы рассмотрим основные понятия алгоритмизации как теоретической науки, а также приведём формальное описание нескольких проблем принадлежности.

Ключевые слова и фразы: труднорешаемые задачи; эвристические алгоритмы; детерминированные подходы.

Том 1, № 2 (2014) стр. 43–57
Е. Ф. Сайфуллина, Р. И. Семенов (Тольяттинский государственный университет)
emails: elena-fairy@yandex.ru, romansemenov3@gmail.com
Об алгоритмах восстановления графа по вектору степеней второго порядка
В работе предлагается универсальный алгоритм восстановления графа по его вектору степеней второго порядка, а также ведется подробное рассмотрение вариантов данного алгоритма для решения различных прикладных задач (например, для получения случайного графа с некоторыми известными характеристиками). Данный алгоритм тесно связан с наблюдением сетей и работой с ними
также в различных прикладных задачах. Среди многих примеров отметим задачу распределения проводных связей в локализованной сети, а также связанную с ней задачу частичного восстановления некоторых утерянных данных на основе уцелевших.
Основная проблема, с которой пришлось столкнуться при разработке универсального алгоритма, – это неоднозначность решения задачи восстановления графа по вектору степеней второго порядка, заставляющая рассматривать множество допустимых решений как результат работы эвристических алгоритмов, обеспечивающих близкие к минимальным временны́е затраты.
Для достижения обозначенной цели предлагаемые алгоритмы разбиты на две специализированные части, выполняющие задачи различной сложности: оптимизатор, способный частично восстанавливать граф по упрощенному быстрому алгоритму, и построитель, способный по сложному долгому алгоритму вернуть правильный ответ любой сложности. Алгоритм построителя представлен в двух вариациях – для задачи построения случайного графа и для задачи построения определенного графа соответственно. Построитель определенного графа был получен на основе построителя случайного графа и является его усложненной вариацией с расширенными возможностями, в которые входит относительно несложная интеграция многочисленных проверок получаемых результатов и возможность выбора режима работы (получение всех правильных вариантов ответа и получение первого правильного варианта ответа).
Наиболее подробно в работе представлены способы восстановления графа с такими характеристиками, как отсутствие петель и наличие связности – так как именно они требовали от разработчиков создание наиболее разностороннего и универсального алгоритма. Также в работе наглядно описаны два способа получения вектора степеней второго порядка на основе существующих графов, представленных в виде чертежа или матрицы смежности. Не меньше внимания было уделено и самой реализации предлагаемого алгоритма, и в статье представлены результаты работы однопоточной реализации алгоритма с заметками о его поведении в различных ситуациях, а также представлена таблица, демонстрирующая зависимость затраченного на восстановление времени от степени поддержки оптимизатором. При этом в работе не ставилась задача точной оценки сложности описываемых алгоритмов.

Ключевые слова и фразы: восстановление графа; вектор степеней второго порядка; эвристические алгоритмы.

Том 1, № 2 (2014) стр. 58–68
В. В. Энгельгардт, О. А. Кацюба (Самарский государственный университет путей сообщения)
emails: hexware@gmail.com, katsyuba@samgups.ru
Применение генетического алгоритма для осуществления структурно-параметрической идентификации линейных динамических систем
В работе рассматривается подход, основанный на использовании генетического алгоритма для решения задачи структурной идентификации линейной динамической системы, содержащей помехи на входе и выходе. В предложенном методе структурно-параметрическая идентификация проходит в 2 этапа.
На первом этапе структура модели кодируется в виде вектора, и задача структурной идентификации сводится к NP-трудной проблеме целочисленного линейного программирования. Для нахождения решения генетическим алгоримом в рамках целочисленного программирования в работе рассматривается соответствующая модификация алгоритма. Предложенный численный алгоритм был реализован в среде Matlab в качестве модификации для библиотеки Genetic Algorithm Solver.
На втором этапе происходит параметрическая идентификация полученной структуры модели. Для осуществления нахождения устойчивого решения в рамках параметрической идентификации структуры модели на параметры накладываются ограничения в виде критерия устойчивости Рауса-Гурвица, достаточности данных и физической реализуемости системы. При численном моделировании было проведено сравнение критериев для параметрической идентификации с методом наименьших квадратов и методом инструментальных переменных, а также был предложен свой критерий, который даёт более состоятельные оценки. Данные сравнения были произведены при различных начальных условиях работы алгоритма, таких как: нарастающее увеличение сложности модели, прекращение идентификации в случае незначительного уменьшения ошибки при увеличении сложности модели.
Моделирование проводилось при различном отношении сигнал/шум на входе и выходе динамической системы. Результаты подтвердили высокую точность оценок параметров и структуры модели, получаемых с помощью предложенного алгоритма.

Ключевые слова и фразы: структурно-параметрическая идентификация; линейные динамические системы; эволюционные вычисления; генетический алгоритм; целочисленное программирование.

Том 1, № 2 (2014) стр. 69–81
Б. Ф. Мельников (Самарский государственный университет)
email: bormel@rambler.ru
О звёздной высоте регулярного языка. Часть II: Вспомогательные конструкции
Во второй части настоящей статьи мы продолжаем рассматривать предлагаемый нами новый подход к проблеме звёздной высоты регулярного языка; краткое описание этого подхода таково. Мы определяем звёздную высоту некоторого конечного автомата: рассматривая все возможные перестановки его состояний; обычным образом строя регулярные выражения, получаемые по каждой из этих перестановок с помощью теоремы Клини; и выбирая минимально возможное значение их звёздной высоты. Далее мы показываем возможность построить по любому заданному регулярному выражению такого недетерминированного конечного автомата, звёздная высота которого совпадает со звёздной высотой исходного регулярного выражения.
Следовательно, мы можем рассматривать такой гипотетический недетерминированный конечный автомат, который соответствует регулярному выражению, определяющему заданный регулярный язык и имеющему минимально возможную звёздную высоту; пусть это автомат K. Вместе с этим K мы будем также рассматривать конкретный порядок τ на множестве его состояний, соответствующий регулярному выражению, имеющему минимально возможную звёздную высоту.
Рассматривая состояния автомата K в порядке τ, мы для очередного выбираемого состояния получаем одну из следующих трёх возможностей. Либо для каждого цикла, проходящего через это состояние, существует эквивалентный, не проходящий через него. Либо существует некоторое иное состояние автомата, которое имеет меньшее значение функции порядка τ и определяет те же самые циклы, которые определяет рассматриваемое нами состояние. Либо мы можем добавить к автомату K некоторые дуги – получая при этом один из предыдущих вариантов.
С помощью конечной последовательности таких операций мы получаем автомат, эквивалентный заданному, – причём такой, у которого мы можем априори ограничить сверху число состояний. Таким образом, описываемая последовательность действий доказывает существование недетерминированного конечного автомата, определяющего заданный регулярный язык и имеющему минимально возможную звёздную высоту, с заранее ограниченным числом состояний.

Ключевые слова и фразы: недетерминированный конечный автомат; регулярный язык; звёздная высота.

Том 1, № 2 (2014) стр. 82–94
И. Н. Попов (Северный (Арктический) федеральный университет им. М. В. Ломоносова)
email: popovivannik@yandex.ru
Алгоритмизация определения принадлежности элемента группы её подгруппе (на примере группы RC)
Матрицы в математике играют большую роль – как теоретическую, так и практическую. Матрицы имеют особое значение и в абстрактной алгебре, в частности, в теории групп. Среди всех групп можно выделить матричные группы, элементами которых являются квадратные матрицы. Такие группы исследуются на строение, в них выделяются особые подгруппы и элементы. Зафиксировав подгруппу в матричной группе и выбрав произвольную матрицу из группы, можно поставить вопрос о принадлежности её данной подгруппе. Этот вопрос является основным вопросом данной работы.
Ясно, что в решении этого вопроса играет роль определение подгруппы, которое, в частности, может основываться на определяющих соотношениях или порождающих матрицах. Во втором случае подгруппа задаётся как линейная оболочка определённых матриц, то есть каждый элемент подгруппы равен линейной комбинации некоторых матриц из заранее определённого множества матриц. К такому виду подгрупп относится и группа RC, являющаяся подгруппой группы квадратных матриц над кольцом классов вычетов по модулю 2 при фиксированном размере матриц. Более того, матричная группа RC является конечнопорождённой.
Но это свойство группы RC для большой размерности матриц не является, на наш взгляд, основополагающим для построения алгоритма распознавания принадлежности произвольной матрицы группе RC. Основываясь только на этом свойстве группы RC, при условии небольшого количества порождающих матриц, нахождение ответа на основной вопрос работы сводится к решению матричных уравнений. Одним из факторов, влияющим на сложность вычислений, при таком подходе является размерность матриц.
Другой подход к построению алгоритмов для решения основного вопроса работы для группы RC, что можно использовать для решения основного вопроса и в общем случае, может основываться на внутреннем строении подгруппы, на особых свойствах матриц, входящих в группу RC. Следует обнаружить свойства такие, что, с одной стороны, на основе их можно однозначно дать ответ на поставленный вопрос, а с другой стороны, алгоритмы, построенные на этих свойствах, более просты в реализации.
Умение определять принадлежность произвольной матрицы группы фиксированной её подгруппе имеет и практическое значение. Матрицы, как известно, могут играть роль преобразований отдельных элементов или множеств элементов.
Преобразования могут быть разного вида. В общей теории групп исследуется вопрос о возможности получения элемента группы из другого элемента этой же группы, используя определённый класс преобразований элементов группы. Если один элемент группы можно получить из другого, используя конечную комбинацию преобразований из данного класса преобразований, то элементы называются эквивалентными.
Вопрос об определении эквивалентности элементов группы возникает, например, в теории кодирования (в исследовании и построении групповых кодов), в исследовании ассоциативных алгебр (проблема эквивалентности (равенства) слов), в теории игр (в определении возможности достижения цели игры, исходя из её правил).
Возвращаясь к группе RC, под преобразованиями матрицы можем считать изменение всех нулей и единиц строки или столбца на единицы и нули соответственно. С точки зрения матричных действий это означает, что к данной матрице прибавляются матрицы из группы RC. Если даны две матрицы и ставится вопрос об их эквивалентности, то вопрос сводится к определению принадлежности их разности группе RC. Наличие эффективного алгоритма принадлежности матрицы группе RC ускоряет процесс получения ответа на вопрос об эквивалентности выбранных матриц.

Ключевые слова и фразы: матрицы; группа; подгруппа; характеристическое свойство элементов группы.

Том 1, № 3 (2014) стр. 6–19
Ю. С. Нагорнов (Тольяттинский государственный университет)
email: Nagornov.Yuri@gmail.com
И. В. Жиляев (Южный федеральный университет)
email: Zhilyaev@mail.com
О методе оптимизации расчётов морфофункциональных свойств эритроцита и определения его внутриклеточного давления
В настоящей работе применяется теория упругости и метод оптимизации с численным подбором параметров модели к моделированию морфофункциональных свойств эритроцита. Модель эритроцита необходима для того, чтобы дать ответы на фундаментальные вопросы: почему эритроцит приобретает форму двояковогнутого диска при условии однородности содержимого эритроцита? какие факторы влияют на форму эритроцита и его упругие свойства? как на основе физической модели померить внутриклеточное давление? В последнее время наиболее интересные и полные экспериментальные данные о структуре эритроцита и строении цитоскелета были получены методами атомно-силовой микроскопии, где указывалось, что коэффициент упругости мембраны эритроцитов в норме равен 1,4–1,7 кПа, при этом ригидность в центре и на краю эритроцита отличается на 25–40%.
В работе предложены модель эритроцита, а также метод оптимизации расчётов его морфофункциональных и упругих свойств в зависимости от внутриклеточного давления. Модель представляет эритроцит в виде однородного упругого тела с упругостью, зависящей от расстояния до центра симметрии эритроцита. Данные для моделирования взяты из экспериментального исследования, в котором был применён метод атомно-силовой микроскопии; проводилось измерение упругости мембраны эритроцитов и морфологии.
В настоящей работе были решены следующие задачи: 1) разработана модель упругости мембраны, которая изменялась в зависимости от расстояния до центра в пределах 1–1,6 кПа; 2) проведён расчёт упругих свойств модели эритроцита методом конечных элементов; 3) выполнен подбор параметров мембраны методом оптимизации; 4) в рамках модели получена зависимость морфологии эритроцита от давления на мембрану; 5) проведено сравнение расчётных данных с данными атомно-силовой микроскопии, что позволило определить давление на мембрану для различных морфологических форм эритроцитов; 6) предложен подход к измерению внутриклеточного давления эритроцита.

Ключевые слова и фразы: модель эритроцита; атомно-силовая микроскопия; геометрические характеристики эритроцита; моделирование упругих свойств; внутриклеточное давление.

Том 2, № 1 (2015) стр. 11–20
И. Е. Воронина, Т. Ю. Харченко (Воронежский государственный университет)
emails: irina.voronina@gmail.com, harchenko-tatyan@mail.ru
Разработка количественного подхода и метода экспертного оценивания для модели определения зависимостей и оценки результатов судебных решений
В статье рассматриваются подходы к вычислению итогового наказания в уголовных делах. Количественный подход используется для видов наказаний, измеряющихся в числовых значениях. Качественный подход используется для остальных видов наказаний. Для качественного подхода определены направления работы для разработки метода экспертных оценок. Также рассмотрен по-этапный подход к вычислению коэффициентов смягчающих и отягчающих обстоятельств по уголовным делам. Представлена сводная таблица коэффициентов для одного вида наказания – лишение свободы. Представлена формула для вычисления итогового наказания и коэффициентов. Формула состоит из двух частей: формальная оценка и субъективная составляющая. В связи с этим предложено свести формулу только к формальной оценке. Сформулировано определение субъективной составляющей в судебных делах, проведен ее анализ, предложены пути решения для её минимизации. Даны определения зависимой и независимой переменной в формуле вычисления итогового наказания и коэффициентов. Рассмотрены факторы, влияющие на зависимую переменную. Проведена классификация уголовных наказаний. Очерчен круг задач для продолжения исследования. Указаны достоинства и недостатки описанных подходов. Подчеркнуто, что предложенные подходы применяются к уголовным делам с минимальным количеством обстоятельств. Также описаны случаи, в которых необходимо сочетать количественный и качественный подходы. Все подходы будут использованы для разработки модели определения зависимостей и оценки результатов судебных решений. Разрабатываемая модель послужит основой для создания формальной процедуры поддержки принятия решений в уголовном праве. Результаты исследования предполагается использовать при разработке процедур для задач обучения профессиональной деятельности.
Ключевые слова и фразы: уголовное право; экспертная информация; принятие решений; зависимый фактор; независимый фактор.

Том 2, № 1 (2015) стр. 21–32
С. В. Еремеев (Муромский институт им. В. К. Зворыкина – филиал Владимирского государственного университета им. А. Г. и Н. Г. Столетовых)
email: sv-eremeev@yandex.ru
Моделирование и алгоритмы выполнения пространственно-временных запросов в геоинформационных системах
В статье поставлена и реализована задача получения состояния карты по запросу пользователя за определённый период времени. Рассмотрены существующие аналоги систем и модели данных по пространственно-временному анализу данных. Эта задача является особенно актуальной для муниципальных геоинформационных систем, т.к. объекты городской инфраструктуры могут достраиваться, изменяться и даже исчезать с карты в связи с удалением старого жилья или перепланировкой местности. Для решения проблемы предложен метод хранения изменений геометрии картографических объектов в пространственных регистрах, которые представляют собой структуру данных из двух полей: даты и геометрической формы объекта на эту дату. Это даёт возможность одному и тому же объекту участвовать в различных кадастровых документах. При оформлении документа информация о геометрии объекта записывается в пространственный регистр. Приведено формальное описание пространственно-временно го представления объекта, где каждый пространственный объект содержит одну из возможных операций над ним на конкретную дату. Показана структура и схема взаимодействия модулей программной системы. В качестве базовой геоинформационной системы выбрана система ИнГео. Центральным модулем системы является модуль построения пространственно-временных запросов. Разработан алгоритм выполнения пространственно-временных запросов для выбранного набора объектов или слоёв за указанный промежуток. Создана база данных, которая содержит журнал изменений для каждого пространственного объекта. Продемонстрирован пример SQL запроса, содержащий в качестве параметров начальную и конечную дату, которые используются для выбора только тех пространственных объектов, операции над которыми удовлетворяют этому промежутку. Приведены примеры использования разработанных алгоритмов.
Ключевые слова и фразы: пространственно-временные запросы; геоинформационные системы; пространственные регистры; геометрия объекта.

Том 2, № 1 (2015) стр. 33–44
С. Ю. Корабельщикова (Северный (Арктический) федеральный университет им. М. В. Ломоносова)
email: kmv@atnet.ru
А. И. Чесноков (Северный (Арктический) федеральный университет им. М. В. Ломоносова)
email: cleric_air@mail.ru
К. П. Бутин (Северный (Арктический) федеральный университет им. М. В. Ломоносова)
email: k.butin@narfu.ru
Об одном алгоритме подсчета корневых деревьев с заданными числом листьев и порядком ветвления
В статье решается задача подсчёта корневых деревьев специального вида. Рассматриваются корневые деревья с фиксированным числом листьев и порядком ветвления. Такие деревья часто встречаются в прикладных задачах дискретной математики. К примеру, при алфавитном кодировании преимущественно используются префиксные коды, так как свойство префикса гарантирует однозначную декодируемость кода. Максимальные префиксные коды обладают рядом дополнительных свойств, в частности, все вершины кодового дерева, соответствующего такому коду, являются насыщенными, и число рёбер в каждом пучке равно мощности кодирующего алфавита. В данной статье нами получена и обоснована формула подсчёта корневых деревьев такого вида с фиксированным числом листьев. Для организации подсчётов использовались комбинаторные методы, в частности индукция по числу ярусов, распределение пучков рёбер по ярусам, нахождение всех возможных вариантов распределения при фиксированном числе пучков. Из приведённых примеров видно, что вычисления даже при малых значениях довольно трудоёмки. Авторами разработан эффективный алгоритм решения данной задачи и написана программа на языке Си++, которая производит требуемые вычисления; в статье приведён программный код. Для вычислений применяется динамическое программирование, в статье описаны два возможных алгоритма для его реализации. Асимптотическая сложность более оптимального из них равна O(R^3), где R – количество концевых вершин. Деревья рассматриваемого вида существуют при условии, что R–1 делится нацело на Q–1, где Q – порядок ветвления. Полученные результаты можно использовать не только для подсчёта корневых деревьев специального вида, но также для оценки числа максимальных префиксных кодов и кодов с минимальной избыточностью.
Ключевые слова и фразы: корневое дерево; порядок ветвления; распределения пучков по ярусам; алгоритм подсчёта.

Том 2, № 1 (2015) стр. 45–56
А. В. Смагличенко (ЗАО РТСофт)
email: asmaglichenko@dev.rtsoft.ru
Т. А. Смагличенко (Институт проблем нефти и газа РАН)
email: tasmaglich@gmail.com
М. К. Саянкина (Институт проблем нефти и газа РАН)
email: msayankina@gmail.com
Подход к разработке жадных алгоритмов выделения неискажённых данных в задачах сейсмической разведки
В процессе работы с сейсмическими данными часто возникают функции, которые создают изображения характеристик сейсмических сигналов на ограниченном множестве цифровых строк. Не все изображения могут быть адекватными с точки зрения присутствия в данных сейсмического шума. Часть изображений содержит значительные искажения и должна быть исключена из рассмотрения.
В настоящей статье представлена одна из схем метода ветвей и границ, которая была разработана в процессе работы с сейсмическими данными, имеющими формат матрицы цифровых строк определённой длины. При предположении, что норма разницы между двумя любыми строками не превышает некоторой граничной оценки, решалась задача по поиску экстремума функции спектра сейсмического сигнала на подмножестве пар сходных строк. Схема метода проиллюстрирована для простого случая нескольких пар. Алгоритм распознавания пар сходных строк протестирован на численном примере с подробным представлением численных результатов для каждого шага алгоритма.
Предлагаемая схема метода ветвей и границ была применена для поиска спектра сейсмического сигнала, который минимально отличается от выделенной группы сигналов, сходных по своим спектральным характеристикам, и, следовательно, обладает свойством устойчивости по отношению к сейсмическому шуму. Изображения примеров исходных спектров и найденного оптимума согласно разработанной схеме иллюстрируют её эффективность.
При этом алгоритм распознавания пар сходных строк, а также сама схема в целом, могут быть также применены в любой области, где возникает проблема определения точного решения системы линейных уравнений. Некоторый интерес может быть для применения схемы в некоторых этапах эволюционных алгоритмов, достаточно популярных в настоящее время для задач дискретной оптимизации.

Ключевые слова и фразы: обработка цифровых строк; сходные строки; допустимое множество; минимальная оценка.

Том 2, № 1 (2015) стр. 71–81
Р. О. Евстигнеев Пензенский государственный университет
email: Roman_cezar@mail.ru
М. Ю. Медведик Пензенский государственный университет
email: _medv@mail.ru
А. А. Шмелёв ОАО НПП «Рубин»
email: shmel.offf@yandex.ru
Итерационный метод решения прямых и обратных двумерных задач акустики с применением параллельных алгоритмов
Интерес к прямым и обратным задачам дифракции вызван активным развитием радиоэлектронной аппаратуры и техники. Особый интерес представляют задачи в резонансном диапазоне частот, когда обычные методы решения не работают. В этом случае, применяют методы объёмных сингулярных интегральных уравнений. Целью данной работы является изучение задачи дифракции акустической волны на плоскости, а именно – нахождения приближённого решения уравнения Гельмгольца для полного поля акустической волны и разработка алгоритма восстановления волнового параметра материала. Также для обеих задач строятся параллельные алгоритмы для ускорения расчётов.
С помощью функции Грина рассматриваемая краевая задача из дифференциальной постановки сводится к объёмному сингулярному интегральному уравнению. В отличие от дифференциальной постановки задачи, где решение производится на бесконечной области, интегральное уравнение будет решаться только на фигуре. Строится параллельный алгоритм, позволяющий добиться ускорения решения обеих задач, а также обеспечивающий высокую устойчивость. Представлены результаты решения прямой задачи для разных размерностей расчётных сеток и разных значений волновых чисел k, для которых были применены параллельные алгоритмы для ускорения решения. Также получены результаты восстановления волнового числа k по известному значению акустического поля.
В статье также представлен метод восстановления волнового параметра материала. Метод был проверен на различных частотах и для различных материалов. Результаты проверки показывают хорошую скорость решения и устойчивость при восстановлении акустических параметров тела.

Ключевые слова и фразы: интегральное уравнение; краевая задача; уравнение Гельмгольца; метод сопряжённых градиентов; численное решение; задача дифракции.

Том 2, № 1 (2015) стр. 82–100
Н. Г. Баранец, А. Б. Верёвкин, С. Е. Марасова (Ульяновский государственный университет)
emails: n_baranetz@mail.ru, a_verevkin@mail.ru, marasova@list.ru
Идеология в науке – «особое мнение» математиков
В статье рассмотрены представления математиков о роли идеологии в науке. Идеология, отвечающая за социально-групповую идентичность человека и выражающая систему ценностей, обеспечивающих стремление к удовлетворению потребностей, в отношении к науке выступает в трёх формах. Во-первых, очевидно влияние на науку различных политических идеологий, внешних по отношению к ней, что было названо «идеологизацией науки». Во-вторых, существует внутренняя идеология научного сообщества, созданная и поддерживаемая самими учёными – сциентизм. В-третьих, присутствуют личные концептуальные и методологические предпочтения учёных в науке, их представления о предмете, целях и задачах дисциплинарной области. В соответствии с этим в статье исследуется отношение математиков к влиянию на научную жизнь внешней политической идеологии и к феномену идеологизации науки, анализируется представленность в мировом математическом сообществе идеологии сциентизма и её влияние на развитие науки, проясняется смысл концепта идеологии в понимании некоторых математиков России (А.Д.Александрова, Н.А.Вавилова, Е.С.Вентцель, С.С.Кутателадзе, С.П.Новикова, И.Р.Шафаревича) и зарубежья (Р.Брауна, Д.Даубена, Д.Рюэля). В результате сравнительного анализа представлений математиков об идеологии в науке, сделаны следующие выводы. Есть общность взглядов в различных национальных математических сообществах относительно понимания доктринальных различий как имеющих идеологическую природу, и несомненное следование сциентистской идеологии. Причины этого лежат в интеграции национальных математических сообществ в единое мировой научное пространство. Одним из проявлений этой тенденции является становление прочной российской диаспоры в западных странах, а также групп учёных, одновременно работающих в России и за рубежом, обеспечивающих проникновение в российское научное сообщество глобальных идей. Вместе с тем сохраняются различия образов науки в российском и западном научных сообществах. В западной традиции акцент делается на понимании социальной компоненты науки и её ориентированности на практику в широком смысле слова – экономическую, социально-культурную, политическую. Российские математики больше внимания уделяют доктринальным, концептуально-содержательным моментам в позициях научных групп.
Ключевые слова и фразы: математическое сообщество; рефлексия учёного; идеология; идеологизация; сциентизм; философия математики; доктрина; стиль мышления; ценностные установки учёного; образ науки.

На главную страницу журнала