ВЕСТНИК ЮЖНО-УРАЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. СЕРИЯ: ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И ИНФОРМАТИКА

Данная статья продолжает цикл работ автора, посвященных проблеме возраста информации (Age of Information, AoI) - метрики, используемой в информационных системах для мониторинга и управления удаленными источниками информации со стороны центра управления. Теоретический анализ систем передачи информации требует количественной оценки «свежести» информации, доставляемой в центр управления. В данной работе рассматривается модель двухузловой группы передачи, состоящей из источника информации (узла-отправителя), центра управления (узла-получателя) и нескольких каналов связи между ними. Предполагается, что пропускные способности каналов могут быть различными. При этом, сетевой протокол требует, чтобы информация, поступающая в узел-получатель считывалась в той же последовательности, в какой она была передана из узла-отправителя. В результате пакеты, нарушившие установленный порядок, задерживаются в узле-отправителе на время, требуемое для восстановления порядка. В данной работе процесс передачи информации моделируется с помощью многоканальной системы массового обслуживания с ограниченным накопителем, пуассоновским потоком заявок, экспоненциальным обслуживанием и переупорядочиванием заявок. При этом заявки моделируют пакеты передаваемой информации, накопитель системы - очередь пакетов на передачу, обслуживание заявок на приборах различной интенсивности - процесс передачи пакетов по каналам связи. Данная модель для оценки возраста информации использовалась впервые. В результате проведенного исследования получены выражения для преобразования Лапласа-Стилтьеса стационарной функции распределения и начальных моментов максимального значения возраста информации, называемого пиковым возрастом. Проведено численное исследование показателей производительности системы, включающее анализ пикового возраста информации при различных загрузках системы. Корректность аналитических результатов подтверждена результатами имитационного моделирования.

Для стандартной операции конкатенации слов, рассматриваемой как умножение, естественным образом определяется конкатенация языков, а на основе последней операции - степень языка и, при наличии, корень заданной степени. При описании алгоритмов построения языка, являющегося корнем степени M из заданного языка, большое значение имеют так называемые потенциальные корни: это такие слова (не языки), рассматриваемая M-я степень которых входит в заданный язык. Несложно показать, что все потенциальные корни для заданного языка строятся с помощью полиномиального алгоритма. Эта задача, по-видимому, не упрощается при рассмотрении слов и языков над 1-буквенным алфавитом - что и делается в настоящей статье. Табуированная пара потенциальных корней - это такая пара, конкатенация слов которой в язык не входит. В предыдущих публикациях на тему описания алгоритмов извлечения корней из языка возникала гипотеза, что полиномиальный алгоритм извлечения корня из языка может быть описан на основе рассмотрения только множества табуированных пар - путем перебора специально описываемых подмножеств множества потенциальных корней. В настоящей статье показывается, что подобный алгоритм (называемый «простым») невозможен, т.е. если и существует полиномиальный алгоритм извлечения корня из языка, то он (алгоритм) должен использовать некоторую дополнительную информацию.

В статье рассматриваются разбиения натурального числа n, части которого различны, нечетны и их произведение не является квадратом. Такие разбиения применимы для определения ранга группы центральных единиц целочисленного группового кольца знакопеременной группы. Количество разбиений растет экспоненциально, следовательно, задача перебора является вычислительно затратной. В статье предложен параллельный алгоритм в общей памяти для нахождения количества разбиений числа n с дополнительными условиями. Алгоритм основан на концепции распараллеливания по данным и использовании вложенного параллелизма. Выделяется множество длин K разбиения числа n, элементы которого обрабатываются параллельно. Во время обработки длины k разбиения числа n выделяется множество уровней L, рассмотрение которого также выполняется параллельно. Приемлемые значения ускорения и параллельной эффективности предложенного алгоритма получаются при использовании двух нитей на параллельный регион по длинам и двух - по уровням. Таким образом, ускорение при разных n превышает 2.1, а параллельная эффективность не опускается ниже 50 %. Полученные результаты использованы для проверки гипотез Каргаполова и анализа распределения значений нечетных разбиений на некоторых диапазонах. Предложен алгоритм поиска оптимального коэффициента c. С помощью этого алгоритма получена асимптотическая формула количества разбиения числа n, в котором части различны и нечетны, а их произведение является квадратом. Эта формула основана на экспериментальных данных и сформулирована как гипотеза.

Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.