+
ПРОГРАММНОЕ ИССЛЕДОВАНИЕ ПОЛУРЕШЕТОК, СВЯЗАННЫХ С АВТОМАТОМ ВАТЕРЛОО
стр.5-21
Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.
Загружаем данные из библиотечной системы...
Ключевые слова
+
РАСПРЕДЕЛЕНИЕ КВАДРАТОВ И ПРОВЕРКА ГИПОТЕЗ В НЕЧЕТНЫХ РАЗБИЕНИЯХ ЧИСЕЛ
стр.22-37
В статье рассматриваются разбиения натурального числа n, части которого различны, нечетны и их произведение не является квадратом. Такие разбиения применимы для определения ранга группы центральных единиц целочисленного группового кольца знакопеременной группы. Количество разбиений растет экспоненциально, следовательно, задача перебора является вычислительно затратной. В статье предложен параллельный алгоритм в общей памяти для нахождения количества разбиений числа n с дополнительными условиями. Алгоритм основан на концепции распараллеливания по данным и использовании вложенного параллелизма. Выделяется множество длин K разбиения числа n, элементы которого обрабатываются параллельно. Во время обработки длины k разбиения числа n выделяется множество уровней L, рассмотрение которого также выполняется параллельно. Приемлемые значения ускорения и параллельной эффективности предложенного алгоритма получаются при использовании двух нитей на параллельный регион по длинам и двух - по уровням. Таким образом, ускорение при разных n превышает 2.1, а параллельная эффективность не опускается ниже 50 %. Полученные результаты использованы для проверки гипотез Каргаполова и анализа распределения значений нечетных разбиений на некоторых диапазонах. Предложен алгоритм поиска оптимального коэффициента c. С помощью этого алгоритма получена асимптотическая формула количества разбиения числа n, в котором части различны и нечетны, а их произведение является квадратом. Эта формула основана на экспериментальных данных и сформулирована как гипотеза.
Загружаем данные из библиотечной системы...
Ключевые слова
+
О НЕСУЩЕСТВОВАНИИ ПРОСТОГО ВАРИАНТА ПОЛИНОМИАЛЬНОГО АЛГОРИТМА ИЗВЛЕЧЕНИЯ КОРНЯ ИЗ ЯЗЫКА
стр.38-56
Для стандартной операции конкатенации слов, рассматриваемой как умножение, естественным образом определяется конкатенация языков, а на основе последней операции - степень языка и, при наличии, корень заданной степени. При описании алгоритмов построения языка, являющегося корнем степени M из заданного языка, большое значение имеют так называемые потенциальные корни: это такие слова (не языки), рассматриваемая M-я степень которых входит в заданный язык. Несложно показать, что все потенциальные корни для заданного языка строятся с помощью полиномиального алгоритма. Эта задача, по-видимому, не упрощается при рассмотрении слов и языков над 1-буквенным алфавитом - что и делается в настоящей статье. Табуированная пара потенциальных корней - это такая пара, конкатенация слов которой в язык не входит. В предыдущих публикациях на тему описания алгоритмов извлечения корней из языка возникала гипотеза, что полиномиальный алгоритм извлечения корня из языка может быть описан на основе рассмотрения только множества табуированных пар - путем перебора специально описываемых подмножеств множества потенциальных корней. В настоящей статье показывается, что подобный алгоритм (называемый «простым») невозможен, т.е. если и существует полиномиальный алгоритм извлечения корня из языка, то он (алгоритм) должен использовать некоторую дополнительную информацию.
Загружаем данные из библиотечной системы...
Ключевые слова
+
ПРЕОБРАЗОВАНИЕ ЛАПЛАСА-СТИЛТЬЕСА ФУНКЦИИ РАСПРЕДЕЛЕНИЯ ПИКОВОГО ВОЗРАСТА ИНФОРМАЦИИ В МНОГОКАНАЛЬНОЙ ГРУППЕ ПЕРЕДАЧИ
стр.57-73
Данная статья продолжает цикл работ автора, посвященных проблеме возраста информации (Age of Information, AoI) - метрики, используемой в информационных системах для мониторинга и управления удаленными источниками информации со стороны центра управления. Теоретический анализ систем передачи информации требует количественной оценки «свежести» информации, доставляемой в центр управления. В данной работе рассматривается модель двухузловой группы передачи, состоящей из источника информации (узла-отправителя), центра управления (узла-получателя) и нескольких каналов связи между ними. Предполагается, что пропускные способности каналов могут быть различными. При этом, сетевой протокол требует, чтобы информация, поступающая в узел-получатель считывалась в той же последовательности, в какой она была передана из узла-отправителя. В результате пакеты, нарушившие установленный порядок, задерживаются в узле-отправителе на время, требуемое для восстановления порядка. В данной работе процесс передачи информации моделируется с помощью многоканальной системы массового обслуживания с ограниченным накопителем, пуассоновским потоком заявок, экспоненциальным обслуживанием и переупорядочиванием заявок. При этом заявки моделируют пакеты передаваемой информации, накопитель системы - очередь пакетов на передачу, обслуживание заявок на приборах различной интенсивности - процесс передачи пакетов по каналам связи. Данная модель для оценки возраста информации использовалась впервые. В результате проведенного исследования получены выражения для преобразования Лапласа-Стилтьеса стационарной функции распределения и начальных моментов максимального значения возраста информации, называемого пиковым возрастом. Проведено численное исследование показателей производительности системы, включающее анализ пикового возраста информации при различных загрузках системы. Корректность аналитических результатов подтверждена результатами имитационного моделирования.
Загружаем данные из библиотечной системы...
Ключевые слова
+
КЛАССИФИКАЦИЯ МУЛЬТИМОДАЛЬНЫХ ДАННЫХ О ЗАБОЛЕВАНИЯХ ЛЕГКИХ НА ОСНОВЕ ПОЗДНЕГО СЛИЯНИЯ МОДАЛЬНОСТЕЙ
стр.74-86
Иванова О.Н., Кумар С., Цымблер М.Л., Иванова Е.В.
С развитием аппаратных технологий высококачественные рентгеновские снимки стали доступны для диагностики заболеваний легких с помощью специалистов-радиологов. Однако процесс диагностики занимает много времени и зависит от наличия в медицинском учреждении специалистов соответствующего профиля. В то же время информация о пациенте может включать не только рентгеновские снимки грудной клетки разного качества, а также результаты медицинских анализов, записи и предписания врача, сведения о приеме лекарств и другие. В данном исследовании предложена модель классификации легочных заболеваний на основе мультимодальных данных о клинических исследованиях пациентов и рентгенографических изображений. При подготовке данных использованы различные методы генерации искусственных образцов как для изображений, так и для табличных данных о результатах лабораторных исследований. Предложен метод установления соответствия для сгенерированных образцов между модальностями. Предложенная мультимодальная модель имеет архитектуру позднего слияния. Проведены эксперименты на наборах данных с одной и двумя модальностями. Предложенная модель показала точность на 5.5% выше, чем модели, основанные на одной модальности (91.3% против 86.11% на наборе данных из 1 156 пациентов).
Загружаем данные из библиотечной системы...
Ключевые слова
