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

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

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

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

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

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

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