В работе строится эффективный ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после удаления одной дуги из ориентированного взвешенного графа. С этой целью вначале описывается используемая структура данных и ее построение, а также приводится STAR–машина, которая моделирует работу ассоциативных (контекстно–адресуемых) параллельных систем с простыми процессорными элементами и вертикальной обработкой информации. На этой модели ассоциативный параллельный алгоритм представляется в виде главной процедуры DeleteArcSPT, использующей группу вспомогательных процедур для выполнения его отдельных частей. Доказана корректность процедуры DeleteArcSPT и показано, что на STAR-машине она выполняется за время O(hk), где h – число битов, которое требуется для кодирования длины максимального кратчайшего пути, а k – число вершин, для которых вычисляются новые кратчайшие пути после удаления одной дуги из исходного графа.

Рассмотрена задача оценки параметров авторегрессионной модели элементарных речевых единиц типа фонем. Предложен итерационный алгоритм поиска авторегрессионной модели фонемы, заданной множеством ее реализаций, в основе которого лежит метод Ньютона, предназначенный для численной минимизации функций. Для этого были получены аналитические выражения для градиента и гессиана величины информационного рассогласования Кульбака–Лейблера между моделями авторегрессии. В ходе экспериментальных исследований на наборе фонем английского языка показано, что разработанный алгоритм, по сравнению с алгоритмом выбора эталона фонемы на основе критерия минимума суммы информационных рассогласований, требует меньших вычислительных затрат на больших объемах данных, а число необходимых итераций слабо зависит от объема входных данных. Кроме того, предложенный алгоритм позволяет находить такие модели фонем, которые обеспечивают более высокую вероятность правильного распознавания.

В статье изучается следующая мультиагентная алгоритмическая задача о роботах в пространстве (Robot in Space — RinS): В пространстве есть n ≥ 2 автономных робота, которым необходимо самостоятельно договориться о выборе индивидуальных укрытий так, чтобы прямолинейные маршруты к этим укрытиям не пересекались. Эта задача имеет отношение к задаче о назначениях в теории графов, задаче построения выпуклой оболочки в ком- бинаторной геометрии и задаче планирования перемещений в искусственном интеллекте. Предлагаемый в статье мультиагентный алгоритм (протокол) ос- нован на централизованном локальном алгоритме Э.В. Дейкстры. Наш алго- ритм обладает свойствами анонимности и масштабируемости, мы доказываем его корректность и верхнюю оценку сложности. Кроме того, мы исследуем два коммуникационных аспекта задачи о роботах в пространстве — инфор- мационный и криптографический. В статье показано, что (1) не существует протокола, решающего задачу RinS, передающего ограниченное число битов, но (2) существует протокол для решения этой задачи, который позволяет ро- ботам не раскрывать информацию о своём положении относительно укрытий. Настоящая статья является продолжением исследований, представленных в статье Е.В. Бодина, Н.О. Гараниной и Н.В. Шилова "Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры)" опубликованной в № 2 за 2011 г. журнала "Моделирование и анализ информационных систем".

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

В данной работе предлагается новый подход к извлечению оценочных слов для различных предметных областей. В рамках этого подхода была разработана модель, включающая набор характеристик и комбинацию алгоритмов, которые позволяют извлекать оценочные слова в конкретной предметной области. Данная модель была обучена в предметной области о фильмах и затем применена в четырёх других областях. Качество работы метода оценивалось на основании разметки экспертов и оставалось на высоком уровне при переносе модели на различные предметные области. Кроме того, созданная модель была использована в предметной области о фильмах на английском языке и продемонстрировала высокое качество извлечения оценочных слов.

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

Сеть Петри называется элементарной, если каждое ее место может содержать не более одной фишки. В работе изучаются топологические свойства элементарной сети Петри конвейера, состоящего из n функциональных устройств. Если рассматривать работу функциональных устройств как непрерывную, то можно прийти к некоторому топологическому пространству “промежуточных” состояний. В работе вычислены группы гомологий этого топологического пространства. С помощью индукции по n, с применением аддиционной последовательности для групп гомологий полукубических множеств, доказано, что в размерностях 0 и 1 целочисленные группы гомологий этих сетей равны группе целых чисел, а в остальных размерностях равны нулю. Исследуются направленные группы гомологий. Установлена связь этих групп с тупиками и рассылками. Эта связь помогает доказать, что все направленные группы гомологий элементарной сети Петри конвейера равны нулю.

Предлагается новый подход к построению надежных «дискретных» ПЛК-программ с таймерами — программирование исходя из задач спецификации и верификации. Для спецификации программного поведения используется язык темпоральной логики LTL. Программирование осуществляется на языке ST по LTL-спецификации. Проводится дискретное моделирование таймера. Новый подход к программированию ПЛК демонстрируется на примере.

Предлагаемый подход к программированию ПЛК обеспечивает возможность анализа корректности ПЛК-программ с помощью метода проверки модели. При программировании требуется соблюдение следующих двух условий:

1) значение каждой переменной должно изменяться не более одного раза за одно полное выполнение программы при прохождении рабочего цикла ПЛК;

2) значение каждой переменной должно изменяться только в одном месте про- граммы ПЛК.

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

Для решения бисингулярной начально-краевой задачи для системы параболических уравнений, содержащей малый параметр ε² при второй производной по пространственной переменной и √ ε при первой производной, обоснована асимптотика произвольного порядка по малому параметру без использования процедуры согласования асимптотических разложений. Для обоснования асимптотики применен асимптотический метод дифференциальных неравенств. Суть его состоит в том, что при построении нижнего и верхнего решений исходной задачи используется формальная асимптотика решения (она построена в предыдущей работе). Модифицируя определенным образом последние члены (порядка εⁿ⁄² ) частичной суммы формальной асимптотики, удается построить нижнее и верхнее решения, между которыми и заключено точное решение исходной задачи.

В данной статье авторами рассматривается понятие дополненной реальности, а также возможные методы её создания. Вначале даётся короткая историческая справка о том, откуда пошло понятие "дополненная реальность кем оно было введено и что означает. Выделяются два принципа её построения: на основе маркера и без него. В статье мы уделяем основное внимание первому подходу. Для анализа видеопотока и поиска на нём объектов определённого типа используются методы и алгоритмы научной дисциплины под названием "компьютерное зрение". В рамках статьи авторы приводят короткое описание и характеристику только двух из них: генетические алгоритмы и feature detection & description. Для программной реализации описываемых алгоритмов может быть использована одна из приведённых библиотек компьютерного зрения: OpenCV или AForge.NET. Обе они дают широкие функциональные возможности в области обработки изображений и поиска объектов. В качестве завершения приводится пример построения дополненной реальности при помощи OpenCV. Основное внимание уделяется вопросам проецирования 3D модели на изображение-маркер. Данный пример может быть взят за основу создания собственного фреймворка дополненной реальности.

Вводится и исследуется специфический формализм счетчиковых автоматов с одним неограниченным счетчиком без проверки на ноль, обладающий достаточно простым почти периодическим поведением и удобным графическим представлением.

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

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

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

Рассматриваются изображения, построенные на основе прямоугольной и гексагональной решеток. Для изображений на прямоугольной решетке предложена формула, дающая приближенные значения компонент характеристического набора коэффициентов при повороте на произвольный угол по методу ближайшего соседа. Характеристические наборы представлены в виде дигарамм, произведена экспериментальная оценка погрешностей. Подтверждено хорошее соответствие предсказанных значений компонент характеристических наборов и полученных экспериментально. Для изображений, построенных на основе гексагональной решетки, предложена аналогичная формула для приближения компонент характеристического набора для поворота на произвольный угол, при этом была применена модификация метода ближайшего соседа для сохранения связности, так как обнаружилось ее нарушение в некоторых случаях на гексагональной решетке. На основе четырехпиксельных фрагментов строятся диаграммы, которые демонстрируют хорошее согласование предсказанных значений и полученных в эксперименте. Определена система трехпиксельных гексагональных фрагментов, для которой доказана теорема об эйлеровой характеристике и предложены аналитические выражения, которые позволяют избежать экспериментального нахождения характеристических наборов коэффициентов для всех возможных опорных углов. Их использование требует производить только один такой эксперимент.

В работе рассматривается вариант построения универсального линеаризованного графа потока управления, архитектурно-независимого и пригодного для описания программы любого языка программирования высокого уровня. Практическая польза данного графа заключается в возможности быстрого и оптимального поиска уникальных путей исполнения, что может быть особенно ценно в методах статического анализа кода алгоритмов с целью поиска в них состояния гонки («race condition»). В качестве технического средства для построения линеаризованного графа управления используется оптимизирующий компилятор CLANG&LLVM. В работе проводится анализ попроцедурных оптимизаций компилятора LLVM, трансформация промежуточного представления которых приводит как к сокращению количества инструкций условного и безусловного перехода в коде, так и к удалению или упрощению целых циклов и условных конструкций. Результат анализа, приведенный в работе, позволил выявить наиболее эффективную линейку оптимизаций компилятора LLVM, которая приводит к существенной линеаризации графа потока управления, что было продемонстрировано на примере кода взаимоисключающего алгоритма Петерсона для 2 потоков.

Рассматривается задача непараметрического оценивания энтропии стационарного эргодического процесса. Применяется подход, основанный на нахождении рас- стояний до ближайших точек. Предложен довольно большой класс метрик на пространстве Ω = A^N правосторонних бесконечных последовательностей над конечным алфавитом A. Новая метрика имеет параметр – невозрастающую функцию. Доказано, что при некоторых ограничениях предлагаемая оценка имеет малую дисперсию. Показано, что специальный выбор параметров позволяет уменьшить смещение. Описан алгоритм для выбора таких параметров. Статья публикуется в авторской редакции.