В данной статье представлено аналитическое исследование особенностей двух типов парсинга, а именно синтаксический анализ составляющих (constituency parsing) и синтаксический анализ зависимостей (dependency parsing). Также в рамках проведенного исследования разработан алгоритм оптимизации извлечения ключевых слов, отличающийся применением функции извлечения именных фраз, предоставляемой парсером, для фильтрации неподходящих фраз. Алгоритм реализован с помощью трех разных парсеров: SpaCy, AllenNLP и Stazna. Эффективность предложенного алгоритма сравнивалась с двумя популярными методами (Yake, Rake) на наборе данных с английскими текстами. Результаты экспериментов показали, что предложенный алгоритм с парсером SpaCy превосходит другие алгоритмы извлечения ключевых слов с точки зрения точности и скорости. Для парсера AllenNLP и Stanza алгоритм так же отличается точностью, но требует гораздо большего времени выполнения. Полученные результаты позволяют более детально оценить преимущества и недостатки изучаемых в работе парсеров, а также определить направления дальнейших исследований. Время работы парсера SpaCy значительно меньше, чем у двух других парсеров, потому что парсеры, которые используют переходы, применяют детерминированный или машинно-обучаемый набор действий для пошагового построения дерева зависимостей. Они обычно работают быстрее и требуют меньше памяти по сравнению с парсерами, основанными на графах, что делает их более эффективными для анализа больших объемов текста. С другой стороны, AllenNLP и Stanza используют модели парсинга на основе графов, которые опираются на миллионы признаков, что ограничивает их способность к обобщению и замедляет скорость анализа по сравнению с парсерами на основе переходов. Задача достижения баланса между точностью и скоростью лингвистического парсера является открытой темой, требующей дальнейших исследований в связи с важностью данной проблемы для повышения эффективности текстового анализа, особенно в приложениях, требующих точности при работе в реальном масштабе времени. С этой целью авторы планируют проведение дальнейших исследований возможных решений для достижения такого баланса.
Гидроцефалия - это заболевание центральной нервной системы, которое чаще всего поражает младенцев и детей ясельного возраста. Оно начинается с аномального накопления спинномозговой жидкости в желудочковой системе головного мозга. Следовательно, жизненно важной становится ранняя диагностика, которая может быть выполнена с помощью компьютерной томографии (КТ), одного из наиболее эффективных методов диагностики гидроцефалии (КТ), при котором становится очевидным увеличение желудочковой системы. Однако большинство оценок прогрессирования заболевания основаны на оценке рентгенолога и физических показателях, которые являются субъективными, отнимающими много времени и неточными. В этой статье разрабатывается автоматическое прогнозирование с использованием фреймворка H-detect для повышения точности прогнозирования гидроцефалии. В этой статье используется этап предварительной обработки для нормализации входного изображения и удаления нежелательных шумов, что может помочь легко извлечь ценные признаки. Выделение признаков осуществляется путем сегментации изображения на основе определения границ с использованием треугольных нечетких правил. Таким образом, выделяется точная информация о природе ликвора внутри мозга. Эти сегментированные изображения сохраняются и снова передаются алгоритму CatBoost. Обработка категориальных признаков позволяет ускорить обучение. При необходимости детектор переобучения останавливает обучение модели и, таким образом, эффективно прогнозирует гидроцефалию. Результаты демонстрируют, что новая стратегия H-detect превосходит традиционные подходы.
Автоматический синтаксический анализ предложения — одна из важных задач компьютерной лингвистики. В настоящее время для русского языка отсутствуют общедоступные и пригодные для практического применения анализаторы синтаксической структуры. Создание таких анализаторов «с нуля» требует составления корпуса деревьев, размеченного в соответствии с заданной формальной грамматикой, что представляет собой крайне трудоёмкую задачу. Однако, поскольку для русского языка существует несколько анализаторов синтаксических связей, представляется полезным использовать результаты их работы для анализа синтаксической структуры предложений. В настоящей работе предлагается алгоритм, позволяющий построить дерево синтаксических единиц русскоязычного предложения по данному дереву синтаксических связей. Алгоритм использует грамматику, сформулированную в соответствии с классическим справочником Д.Э. Розенталя. Приведены результаты экспериментов по оценке качества работы предложенного алгоритма на корпусе из 300 предложений на русском языке. 200 предложений были выбраны из вышеупомянутого справочника и 100 из открытого корпуса публицистических текстов OpenCorpora. В ходе экспериментов предложения подавались на вход анализаторов из состава библиотек Stanza, SpaCy и Natasha, после чего полученные деревья синтаксических связей обрабатывались предложенным алгоритмом. Полученные в результате обработки деревья синтаксических единиц сравнивались с размеченными вручную экспертами-филологами. Наилучшее качество было получено при использовании анализатора синтаксических связей из библиотеки Stanza: F1-мера построения синтаксических единиц составила 0.85, а точность определения членов предложения — 0.93, чего должно быть достаточно для решения многих практических задач в таких областях, как извлечение событий, информационный поиск, анализ тональности.
Многие приложения цифровой обработки сигналов (DSP) и электронные гаджеты сегодня требуют цифровой фильтрации. Для получения быстрых и улучшенных результатов использовались различные алгоритмы оптимизации. Некоторые исследователи использовали Enhanced Slime Mold Algorithm для разработки 2D БИХ-фильтра. Однако было замечено, что данный алгоритм не обеспечил лучшей структуры решения и имел более низкую скорость сходимости. Чтобы решить эту проблему, для разработки 2D БИХ-фильтра используется алгоритм оптимизации Fused ESMA-Pelican Optimization Algorithm (FEPOA), который объединяет Pelican Optimization Algorithm с Enhanced Slime Mould Algorithm (ESMA). Сначала для инициализации популяции используется хаотический подход, который обеспечивает высококачественную популяцию с превосходным разнообразием, после чего позиция членов популяции заключается в идентификации и корректировке особи в граничной области поиска. После этого с помощью тактического подхода пеликана (Pelican Tactical Approach) изучается пространство поиска и исследовательской мощности FEPOA, потом случайным образом вычисляется пригодность, и обновляется лучшее решение, а затем оно перемещается к итерациям. Фазы FEPOA повторяются до тех пор, пока не завершится выполнение. Далее лучшее решение дает оптимальное решение, которое повышает скорость сходимости, точность сходимости и производительность FEPOA. Затем FEPOA реализуется в БИХ-фильтре для улучшения общей конструкции фильтра. Результаты, предоставленные FEPOA, достигают необходимой пригодности и наилучшего решения для 200 итераций, а амплитудная характеристика достигает максимального значения для = 2,4,8, а также время выполнения 3,0158 с, что намного быстрее, чем другие генетические алгоритмы, часто используемые для 2D БИХ-фильтров.
Данная статья посвящена проблеме автоматизации этапа объединения скважин в кусты, рассматриваемого в рамках процесса проектирования разработки нефтяных месторождений. Решение задачи объединения скважин в кусты заключается в определении наилучшего расположения кустовых площадок и распределения скважин по кустам, при которых будут минимизированы затраты на разработку и обслуживание нефтяного месторождения, а ожидаемый дебит максимизирован. Одним из используемых на сегодняшний день подходов является применение оптимизационных алгоритмов. При этом данная задача влечет за собой учет технологических ограничений при поиске оптимального варианта разработки нефтяного месторождения, обоснованным в том числе действующими в отрасли регламентами, а именно минимальное и максимальное допустимое количество скважин в кусте, а также минимально допустимое расстояние между двумя кустовыми площадками. Использование алгоритмов оптимизации не всегда гарантирует оптимальный результат, при котором соблюдаются все заданные ограничения. В рамках данного исследования предложен алгоритм, который позволяет обрабатывать получаемые проектные решения с целью устранения нарушенных ограничений на этапе оптимизации. Алгоритм последовательно решает следующие проблемы: нарушение ограничений на сверхмалое и сверхбольшое количество скважин в кусте; несоответствие числа кустов с заданным; нарушение ограничения на сверхблизкое расположение кустов. Для исследования эффективности разработанного подхода был проведен вычислительный эксперимент на трех сгенерированных синтетических месторождениях с разной геометрией. В рамках эксперимента сравнивалось качество работы оптимизационного метода и предложенного алгоритма, который является надстройкой к оптимизационному. Сравнение проводилось на различных значениях мощности оптимизации, которое обозначает максимальное количество запусков целевой функции. Оценка качества работы сравниваемых подходов определяется величиной штрафа, которая обозначает степень нарушения значений основных ограничений. Критериями эффективности в данной работе являются: среднее значение, среднеквадратичное отклонение, медиана, минимальное и максимальное значения величины штрафа. За счет использования данного алгоритма величина штрафа для первого и третьего месторождений в среднем уменьшается соответственно до 0.04 и 0.03, а для второго месторождения алгоритм позволил получить проектные решения без нарушения ограничений. По результатам проведенного исследования сделано заключение относительно эффективности применения разработанного подхода при решении задачи разработки нефтяных месторождений.
Методы машинного обучения и цифровой обработки сигналов применяются в различных отраслях, в том числе при анализе и классификации сейсмических сигналов поверхностных источников. Разработанный алгоритм анализа типов волн позволяет автоматически идентифицировать и, соответственно, отделять приходящие сейсмические волны на основе их характеристик. Для выделения типов волн используется сейсмический измерительный комплекс, определяющий характеристики граничных волн поверхностных источников с использованием специальных молекулярно-электронных датчиков угловых и линейных колебаний. Представлены результаты работы алгоритма обработки данных, получаемых по методике сейсмических наблюдений, использующей спектральный анализ на основе вейвлета Морле. Также в работе описан алгоритм классификации источников сигнала, определения расстояния и азимута до пункта возбуждения поверхностных волн, рассмотрено использование статистических характеристик и MFCC (Мел-частотные кепстральные коэффициенты) параметров, а также их совместное применение. При этом в качестве статистических характеристик сигнала были использованы следующие: дисперсия, коэффициент эксцесса, энтропия и среднее значение, а в качестве метода машинного обучения был выбран градиентный бустинг; в качестве метода определения расстояния до источника сигнала применен метод машинного обучения на основе градиентного бустинга с применением статистических и MFCC параметров. Обучение проводилось на тестовых данных на основе выделенных особенных параметрах сигналов источников сейсмического возбуждения поверхностных волн. С практической точки зрения, новые методы сейсмических наблюдений и анализа граничных волн позволяют решить проблему обеспечения плотной расстановки датчиков в труднодоступных местах, устранить недостаток знаний в алгоритмах обработки данных сейсмических сенсоров угловых движений, выполнить классификацию и систематизацию источников, повысить точность прогнозирования, реализовать алгоритмы локации и сопровождения источников. Целью работы стало создание алгоритмов обработки сейсмических данных для классификации источников сигнала, определения расстояния и азимута до пункта возбуждения поверхностных волн.
В данной статье предложены алгоритмы планирования и управления движением мобильного робота в двухмерной стационарной среде с препятствиями. Задача состоит в том, чтобы сократить длину запланированного пути, учесть динамические ограничения робота и получить плавную траекторию. Для учета динамических ограничений мобильного робота на карту добавляются виртуальные препятствия, перекрывающие невыполнимые участки движения. Такой способ учета динамических ограничений позволяет использовать картографические методы без увеличения их сложности. В качестве алгоритма глобального планирования используется модифицированная версия алгоритма быстрого исследования случайных деревьев (Multi parent nodes RRT – MPN-RRT). В этом алгоритме, в отличие от оригинальной версии, используется несколько родительских узлов, что уменьшает длину запланированной траектории по сравнению с исходной версией RRT с одним узлом. Кратчайший путь на построенном графе находится с помощью алгоритма оптимизации муравьиной колонии. Методами численного моделирования показано, что использование двух родительских узлов позволяет уменьшить среднюю длину пути для городской среды с низкой плотностью застройки. Для решения проблемы медленной сходимости алгоритмов, основанных на случайном поиске и сглаживании путей, алгоритм RRT дополнен алгоритмом локальной оптимизации. Алгоритм RRT ищет глобальный путь, который сглаживается и оптимизируется итеративным локальным алгоритмом. Алгоритмы управления нижнего уровня, разработанные в этой статье, автоматически уменьшают скорость робота при приближении к препятствиям или повороте. Общая эффективность разработанных алгоритмов продемонстрирована методами численного моделирования с использованием большого количества экспериментов.
Современные методы решения задач планирования выполнения пакетов заданий в многостадийных системах характеризуются наличием ограничений на их размерность, невозможностью гарантированного получения лучших результатов в сравнении с фиксированными пакетами при различных значениях входных параметров задачи. В статье автором решена задача оптимизации составов пакетов заданий, выполняющихся в многостадийных системах, с использованием метода ветвей и границ. Проведены исследования различных способов формирования порядков выполнения пакетов заданий в многостадийных системах (эвристических правил упорядочивания пакетов заданий в последовательностях их выполнения на приборах МС). Определен способ упорядочивания пакетов в последовательностях их выполнения (эвристическое правило), обеспечивающий минимизацию общего времени реализации действий с ними на приборах. На основе полученного правила сформулирован способ упорядочивания типов заданий, в соответствии с которым их пакеты рассматриваются в процедуре метода ветвей и границ. Построена математическая модель процесса реализации действий с пакетами на приборах системы, которая обеспечивает вычисление его параметров. Выполнено построение метода формирования всех возможных решений по составам пакетов заданий для заданного их количества. Решения по составам пакетов заданий разных типов интерпретируются в процедуре метода ветвей и границ с целью построения оптимальной их комбинации. Для реализации метода ветвей и границ сформулирована процедура ветвления (разбиения), предполагающая формирование подмножеств решений, включающих пакеты разных составов заданий одного типа. Построены выражения для вычисления нижних и верхних оценок значений критерия оптимизации составов пакетов для сформированных в процедуре ветвления подмножеств. Процедура отсева предполагает исключение подмножеств, нижняя оценка которых не меньше рекорда. Для поиска оптимальных решений применена стратегия поиска в ширину, предусматривающая исследование всех подмножеств решений, включающих различные пакеты заданий одного типа, полученных в результате процедуры разбиения подмножеств заданий, не исключенных из рассмотрения после реализации процедуры отсева. Разработанные алгоритмы реализованы программно, что позволило получить результаты планирования выполнения пакетов заданий в многостадийной системе, являющиеся в среднем на 30 % лучшими, чем для фиксированных пакетов.
На основе отслеживающей многоконтурной системы координат целевого угла в статье был выбран и предложен интерактивный многомодельный алгоритм адаптивного фильтра для улучшения качества фильтра целевых фазовых координат. Алгоритм интерактивной многомодельной оценки способен адаптироваться к динамике цели по мере продвижения процесса оценки к наиболее подходящей модели. Данный алгоритм имеет 3 модели, выбранные для разработки фильтра координат угла прямой видимости: модель постоянной скорости (CV), модель Зингера и модель постоянного ускорения, характеризующие 3 различных уровня маневренности цели. В результате, качество оценки фазовых координат цели улучшается, поскольку процесс оценки имеет перераспределение вероятностей каждой модели в соответствии с фактическим маневрированием цели. Структура фильтров проста, ошибка оценки мала, а задержка обнаружения маневрирования значительно сокращается. Результаты проверяются посредством моделирования, гарантируя, что во всех случаях цель маневрирует с разной интенсивностью и частотой, фильтр координат угла прямой видимости всегда точно определяет угловые координаты цели. Метод синтеза системы координат цели, использованный в статье, может быть расширен и применен к системам сопровождения целей в РЛС управления огнем, размещенных под землей.
Функционал любой системы может быть представлен в виде совокупности команд, которые приводят к изменению состояния системы. Задача обнаружения атаки для сигнатурных систем обнаружения вторжений эквивалентна сопоставлению последовательностей команд, выполняемых защищаемой системой, с известными сигнатурами атак. Различные мутации в векторах атак (включая замену команд на равносильные, перестановку команд и их блоков, добавление мусорных и пустых команд) снижают эффективность и точность обнаружения вторжений. В статье проанализированы существующие решения в области биоинформатики, рассмотрена их применимость для идентификации мутирующих атак. Предложен новый подход к обнаружению атак на основе технологии суффиксных деревьев, используемой при сборке и проверке схожести геномных последовательностей. Применение алгоритмов биоинформатики позволяет добиться высокой точности обнаружения мутирующих атак на уровне современных систем обнаружения вторжений (более 90%), при этом превосходя их по экономичности использования памяти, быстродействию и устойчивости к изменениям векторов атак. Для улучшения показателей точности проведен ряд модификаций разработанного решения, вследствие которых точность обнаружения атак увеличена до 95% при уровне мутаций в последовательности до 10%. Метод может применяться для обнаружения вторжений как в классических компьютерных сетях, так и в современных реконфигурируемых сетевых инфраструктурах с ограниченными ресурсами (Интернет вещей, сети киберфизических объектов, сенсорные сети).
Эта статья фокусируется на том, чтобы уловить смысл значения текстовых функций понимания естественного языка (NLU) для обнаружения дубликатов неконтролируемых признаков. Особенности NLU сравниваются с лексическими подходами для доказательства подходящей методики классификации. Подход трансфертного обучения используется для обучения извлечению признаков в задаче семантического текстового сходства (STS). Все функции оцениваются с помощью двух типов наборов данных, которые принадлежат отчетам об ошибках Bosch и статьям Википедии. Цель данного исследованияструктурировать последние исследовательские усилия путем сравнения концепций NLU для описания семантики текста и применения их к IR. Основным вкладом данной работы является сравнительное исследование измерений семантического сходства. Экспериментальные результаты демонстрируют результаты функции Term Frequency–Inverse Document Frequency (TF-IDF) для обоих наборов данных с разумным объемом словаря. Это указывает на то, что двунаправленная долговременная кратковременная память (BiLSTM) может изучать структуру предложения для улучшения классификации.
В современных условиях в сфере создания и применения существующих и перспективных космических средств (КСр) приобретают особую актуальность вопросы автономности и живучести при разработке и эксплуатации маломассоразмерных космических аппаратов (МКА) дистанционного зондирования Земли (ДЗЗ). Специфика МКА заключается в том, что к процессу их создания трудно напрямую применить стандартную практику использования системы обеспечения надежности, принятую в ракетно-космической промышленности, из-за отсутствия возможности обеспечить полное структурное резервирование его бортовых систем (БС), связанное с массового-габаритными и другими ограничениями. В этом случае особую актуальность приобретают задачи разработки модельно-алгоритмических способов и подходов к обеспечению требуемого уровня показателей структурной надежности, живучести и, в целом, эффективности функционирования БС МКА. Проблема повышения уровня показателей автономности, живучести, эффективности функционирования сложных технических объектов (СТО), к которым, в частности, относятся МКА, в научной литературе рассматривается в совокупности с решением задач контроля, оценивания и технического диагностирования состояния СТО, проведения реконфигурации (структурной, функциональной, структурно-функциональной) структур СТО, управления ее резервами, альтернативного и многорежимного управления, анализа отказоустойчивости и катастрофоустойчивости СТО. Однако, все перечисленные исследования носят разрозненный и разобщенный характер как на методологическом, так и методическом и технологическом уровнях. В статье приводится обобщенное описание разработанных авторами комбинированных методов и алгоритмов решения задач синтеза технологий и программ управления реконфигурацией БС для повышения живучести МКА. При этом данные задачи и решаются не изолировано, а комплексно в рамках общей проблемы проактивного управления структурной динамикой МКА с использованием, либо без использования средств НКУ, что обеспечивает оперативность, обоснованность, полноту, замкнутость и непротиворечивость синтезируемых управленческих решений. Новизна предложенного в статье подхода состоит в том, что ее авторы, базируясь на сформулированных ими концепциях комплексного (системного) моделирования, проактивного управления структурной динамикой БС МКА, а также интеллектуализации процессов проактивного управления БС МКА, разработали методы и алгоритмы синтеза технологий и программ управления реконфигурацией БС МКА, обеспечивающие, во-первых, ситуационный выбор оптимальной последовательности выполнения операций и распределения ресурсов МКА с использованием и без использования средств НКУ, и, во-вторых, эффективное парирование не только расчетных, но и нерасчетных аварийных полетных ситуаций (АПС), а также оперативное восстановление работоспособности его БС. Конструктивность предложенного подхода иллюстрируется на примере решения задачи гибкого перераспределения задач обработки информации между БС МКА и НКУ МКА.
В условиях текущей четвертой промышленной революции вместе с развитием компьютерных технологий увеличивается и количество текстовых данных. Следует понимать природу и характеристики этих данных, чтобы применять необходимые методологии. Автоматическая обработка текста экономит время и ресурсы существующих систем. Классификация текста является одним из основных приложений обработки естественного языка с использованием таких методов, как анализ тональности текста, разметка данных и так далее. В частности, недавние достижения в области глубокого обучения показывают, что эти методы хорошо подходят для классификации документов. Они продемонстрировали свою эффективность в классификации англоязычных текстов. Однако по проблеме классификации вьетнамских текстов существует не так много исследований. Последние созданные модели глубокого обучения для классификации вьетнамского текста показали заметные улучшения, но тем не менее этого недостаточно. Предлагается автоматическая система на основе длинной краткосрочной памяти и Word2Vec моделей, которая повышает точность классификации текстов. Предлагаемая модель продемонстрировала более высокие результаты классификации вьетнамских текстов по сравнению с другими традиционными методами. При оценке данных вьетнамского текста предлагаемая модель показывает точность классификации более 90%, поэтому может быть использована в реальном приложении.
Проанализированы основные факторы, обуславливающие расширение возможностей и повышение результативности сетевой разведки по идентификации состава и структуры клиент-серверных вычислительных сетей вследствие стационарности их структурно-функциональных характеристик. Вскрытые особенности защиты клиент-серверных вычислительных сетей, основанных на реализации принципов пространственного обеспечения безопасности, а также формализация и внедрение множества запрещающих регламентов обосновывают актуальность задачи динамического управления структурно-функциональными характеристиками клиент-серверных вычислительных сетей, функционирующих в условиях сетевой разведки.
Представлена математическая модель, позволяющая находить оптимальные режимы динамического конфигурирования структурно-функциональных характеристик клиент-серверных вычислительных сетей для различных ситуаций. Приведены результаты расчетов. Представлен алгоритм решения задачи динамической конфигурации структурно-функциональных характеристик клиент-серверной вычислительной сети, обеспечивающий уменьшение времени достоверности добываемых сетевой разведкой данных. Показаны результаты практических испытаний разработанного на основе алгоритма динамического конфигурирования клиент-серверных вычислительных сетей программного обеспечения. Полученные результаты свидетельствуют, что использование представленного решения по динамическому конфигурированию клиент-серверных вычислительных сетей позволяет повысить результативность защиты за счет изменения структурно-функциональных характеристик клиент-серверных вычислительных сетей в рамках нескольких подсетей. При этом достигнуто поддержание критически важных соединений, а интервалы времени изменения структурно-функциональных характеристик адаптивны к условиям функционирования и действиям злоумышленника.
Новизна разработанной модели заключается в применении математического аппарата теории марковских случайных процессов и решении уравнений Колмогорова для обоснования выбора режимов динамического конфигурирования структурно-функциональных характеристик клиент-серверных вычислительных сетей. Новизна разработанного алгоритма состоит в применении модели динамического конфигурирования структурно-функциональных характеристик клиент-серверных вычислительных сетей для динамического управления структурно-функциональными характеристиками клиент-серверной вычислительной сети в условиях сетевой разведки.
Задача редуцирования линейной динамической системы с постоянными коэффициентами рассматривается как задача аппроксимации ее исходной дробно-рациональной передаточной функции аналогичной функцией более низкого порядка. Ошибка аппроксимации определяется как интегральная квадратичная норма отклонения переходных характеристик исходной и редуцированной передаточной функции во временной области. Рассмотрены формулировки двух основных типов аппроксимационных задач: а) традиционная задача минимизации ошибки аппроксимации при заданном порядке редуцированной модели; б) задача минимизации порядка передаточной функции при заданном допуске на погрешность аппроксимации.
Разработаны алгоритмы решения задач аппроксимации, основанные на итерационном процессе Гаусса – Ньютона. На шаге итерации производится линеаризация текущего отклонения переходных характеристик по коэффициентам знаменателя редуцируемой передаточной функции. Линеаризованное отклонение используется для получения новых значений коэффициентов передаточной функции с помощью метода наименьших квадратов в функциональном пространстве на основе ортогонализации Грама – Шмидта. В работе получен общий вид выражений, представляющих линеаризованное отклонение переходных характеристик.
Для решения задачи минимизации порядка передаточной функции в рамках алгоритма метода наименьших квадратов также используется процесс Грама – Шмидта, условием завершения которого является достижение заданной допустимой нормы ошибки. Показано, что последовательность шагов процесса, соответствующая чередованию коэффициентов полиномов числителя и знаменателя передаточной функции, обеспечивает минимальный порядок передаточной функции.
Дается обзор разработанных алгоритмов на случай векторной передаточной функции с общим знаменателем. Представлен алгоритм с заданием ошибки аппроксимации в виде геометрической суммы скалярных ошибок. Обсуждается использование минимаксной формы для оценки ошибки и возможность распространения предложенного подхода на задачу редуцирования нерациональной исходной передаточной функции.
Разработана экспериментальная программа, реализующая предложенные алгоритмы, и получены результаты численных расчетов на тестовых примерах различных типов.
Предложен алгоритм вычисления приближенных значений корней алгебраических уравнений с заданными предельными абсолютными погрешностями. Математическую основу алгоритма составляет аналитически-численный метод решения нелинейных интегрально-дифференциальных уравнений с нестационарными коэффициентами. Аналитически-численный метод относится к классу одношаговых непрерывных методов переменного порядка с адаптивной процедурой выбора шага расчета, формализованной оценкой погрешности производимых вычислений на каждом шаге и погрешности, накапливаемой в ходе расчета. Предлагаемый алгоритм вычисления приближенных значений корней алгебраического уравнения с заданными предельными абсолютными погрешностями состоит из двух этапов. Результатом выполнения первого этапа служат числовые интервалы, содержащие неизвестные точные значения корней алгебраического уравнения. На втором этапе вычисляем приближенные значения этих корней с заданными предельными абсолютными погрешностями. В качестве примера использования предложенного алгоритма приведено нахождение корней алгебраического уравнения пятого порядка с тремя различными значениями предельной абсолютной погрешности.
На основе полученных результатов сделаны следующие выводы. Предложенный алгоритм позволяет выделить числовые интервалы, содержащие неизвестные точные значения корней. Знание этих интервалов дает возможность вычисления приближенных значений корней с любой заданной предельной абсолютной погрешностью. Результативность алгоритма, то есть гарантия достижения поставленной цели не зависит от выбора начальных условий. Алгоритм не итерационный, поэтому число шагов расчета, которое необходимо для выделения числового интервала, содержащего неизвестное точное значение какого-либо из корней алгебраического уравнения, всегда ограничено. Алгоритм при поиске определенного корня алгебраического уравнения вычислительно полностью автономен.
Определение нуклеотидной последовательности ДНК или РНК, содержащих от нескольких сотен до сотен миллионов звеньев мономеров позволяет получить подробную информацию о геноме человека, животных и растений. Расшифровывать структуру нуклеиновых кислот научились достаточно давно, однако первоначально методы расшифровки были низко производительными, неэффективными и дорогими. Методы расшифровки нуклеотидной последовательности нуклеиновых кислот принято называть методами секвенирования. Приборы, предназначенные для реализации методов секвенирования, называются секвенаторами. Секвенирование нового поколения, массовое параллельное секвенирование — это родственные термины, описывающие технологию высокопроизводительного секвенирования ДНК, при котором весь человеческий геном можно секвенировать в течение одного-двух дней. Предыдущая технология, используемая для расшифровки генома человека, потребовала более десяти лет, чтобы получить окончательные результаты.
В Институте аналитического приборостроения РАН разрабатывается аппаратно-программный комплекс для расшифровки последовательности нуклеиновых кислот патогенных микроорганизмов методом массового параллельного секвенирования.
Программное обеспечение, входящее в состав аппаратно-программного комплекса играет существенную роль в решении задач расшифровки генома.
Цель статьи — показать необходимость создания алгоритмов программного обеспечения аппаратно-программного комплекса для обработки сигналов, получающихся в процессе генетического анализа при решении задач расшифровки генома, а также продемонстрировать возможности этих алгоритмов. В работе рассмотрены основные проблемы обработки сигналов и методы их решения. В их числе: автоматическая и полуавтоматическая фокусировка, коррекция изображения фона реакционной ячейки, обнаружение изображений кластеров, оценка координат их положений, создание шаблонов кластеров молекул нуклеиновых кислот на поверхности реакционной ячейки, коррекция влияния интенсивностей соседних оптических каналов и оценка достоверности результатов генетического анализа.
В работе представлены результаты исследований комбинаторно-метрического алгоритма распознавания многомерных групповых точечных объектов (ГТО) в пространстве признаков, имеющих иерархическую организацию. На примере многоуровневых описаний смоделированных и реальных объектов исследован характер изменения показателей достоверности в условиях, когда результаты распознавания, полученные на одном уровне иерархии, используются в качестве исходных данных на следующем. Рассмотрены предпосылки представления распознаваемых объектов или процессов в виде ГТО и источники иерархии. Так, результаты измерений n -мерного процесса в m временных сечениях или в одном сечении, но m независимыми наблюдателями представляются при распознавании n -мерным m -элементным ГТО. В случае распознавания протяженных в пространстве объектов — априорная неопределенность относительно ракурса представления, неполноты состава и координатных шумов элементов обуславливают комбинаторные процедуры количественной оценки меры близости многомерных ГТО, представляющих объект распознавания тому или иному классу. Устойчивость представленного комбинаторно-метрического алгоритма распознавания ГТО достигается возможностью смены стратегии принятия классификационного решения, использующей априорные показатели распознавания на низших уровнях иерархии. В численных экспериментах проводилась классификация геометрии ГТО, представляющего образец, по составу элементов образца или по комплексному априорному показателю достоверности. Для повышения вероятности правильного распознавания предложено использовать перебор результатов распознавания на нижних уровнях иерархии, характеризующихся более низкими априорными показателями достоверности распознавания по первичным признакам. Благодаря использованию процедур поиска комбинаций индексов в окрестности максимума апостериорной вероятности правильного распознавания на нижних уровнях доставляется экстремальное значение критерию качества функционирования системы распознавания на ее верхнем уровне иерархии. Приведены экспериментальные зависимости априорных и апостериорных показателей достоверности при различных условиях проведения измерений и состояний объектов распознавания.
Планирование пути для автономных мобильных устройств является важной задачей в робототехнике. При планировании пути принято использовать один из двух классических подходов: глобальный, когда карта полностью известна, и локальный, в котором устройство по мере движения обнаруживает препятствия с помощью различных бортовых датчиков. На основе этих двух подходов также создаются алгоритмы, сочетающие в себе сильные стороны глобального и локального планирования.
В ходе предыдущих исследований нами был разработан и реализован в среде Matlab прототип многокритериального сплайн-алгоритма глобального построения маршрута. Алгоритм использует граф Вороного при вычислении первой аппроксимации маршрута для запуска итерационного метода, что позволило находить путь во всех конфигурациях карты при условии существования пути от начальной точки до целевой точки. В ходе итеративного поиска использовалась целевая функция, в которой каждому критерию присваивался его вес в целевой функции. Для реализации критериев в том числе использовался метод потенциальных полей.
В данной статье представлена реализация модифицированного сплайн-алгоритма для применения его на реальных автономных мобильных робототехнических системах. Для этого проводится корректирование уравнений характеристических критериев оптимальности пути. Карта препятствий, представленная в ранней версии алгоритма в виде пересечений кругов, в реальных условиях может быть представлена в виде динамически изменяемой вероятностной карты на основе сетки занятости (OccupancyGrid), а робот уже не представляет из себя геометрическую точку.
Для реализации сплайн-алгоритма и дальнейшего использования его в системах управления реальных мобильных робототехнических устройств исходный код прототипа алгоритма был перенесен из среды Matlab в модуль программного обеспечения, написанный на языке программирования С++. Тестирование быстродействия алгоритма и оптимальность многокритериальной целевой функции проводились в среде ROS/Gazebo, являющимся на сегодняшний день де-факто стандартом программирования и моделирования робототехнических устройств.
Полученный в результате сплайн-алгоритм поиска пути можно интегрировать в системы управления наземных колесных и гусеничных робототехнических устройств, оборудованных лазерным дальномером, а также модифицировать предложенный алгоритм для использования шагающими наземными роботами, беспилотными летающими аппаратами и беспилотными судами. Алгоритм работает в режиме реального времени и параметры влияния критериев на целевую функцию доступны для динамических изменений во время движения мобильного робота.
В качестве способа обеспечения секретности сообщений, переданных в зашифрованном виде по открытым каналам связи, при потенциальных атаках с принуждением к раскрытию ключей шифрования предложены алгоритмы и протоколы отрицаемого шифрования, которые разделяются на следующие типы: 1) с открытым ключом; 2) с разделяемым секретным ключом; 3) бесключевые. В статье представлены псевдовероятностные симметричные шифры, представляющие собой специальный вариант реализации алгоритмов отрицаемого шифрования. Обсуждается применение псевдовероятностного шифрования для построения специальных механизмов защиты информации, в том числе стеганографических каналов, носителями которых являются шифртексты. Рассмотрены способы построения поточных и блочных алгоритмов псевдовероятностного шифрования, реализующих совместное шифрование фиктивного и секретного сообщения таким образом, что формируемый шифртекст является вычислительно неразличимым от шифртекста, получаемого в результате вероятностного шифрования фиктивного сообщения. В качестве одного из критериев построения использовано требование неотличимости по шифртексту псевдовероятностного шифрования от вероятностного. Для реализации этого требования в схеме построения псевдоверояностных шифров используется шаг взаимно-однозначного отображения пар блоков промежуточных шифртекстов фиктивного и секретного сообщений в единый расширенный блок выходного шифртекста. Описаны реализации псевдовероятностных блочных шифров, в которых алгоритмы расшифровывания фиктивного и секретного сообщений полностью совпадают. Предложены общие подходы к построению псевдовероятностных протоколов бесключевого шифрования и рандомизированных псевдовероятностных блочных шифров, а также приведены конкретные реализации криптосхем данных типов.
Рассматриваются прикладные аспекты использования предварительного ранжирования вершин ориентированного взвешенного графа. Особое внимание уделяется широкому использованию такого приема в разработке эвристических алгоритмов дискретной оптимизации. Задача ранжирования имеет непосредственное отношение к проблеме определения центральности в социальных сетях, обработке больших массивов данных реального мира, но как показано в статье, явно или косвенно используется при разработке алгоритмов решения прикладных задач в качестве начального этапа построения решения. Приводятся примеры использования предварительного ранжирования, в которых продемонстрировано повышение эффективности решения некоторых прикладных задач, имеющих широкое применение в математических методах оптимизации. Дано описание структуры первой фазы вычислительного эксперимента, которая связана с получением тестовых наборов данных. Полученные данные представлены взвешенными графами, которые соответствуют нескольким группам социальной сети ВКонтакте с числом вершин в диапазоне от 9000 до 24 тысяч участников. Показано, что структурные характеристики полученных графов по числу компонент связности существенно различаются. Продемонстрированы некоторые характеристики центральности (распределения степенных последовательностей), которые имеют экспоненциальный характер. Основное внимание уделяется анализу трех алгоритмов построения иерархии ранжирования вершин графов, предлагаются новые подходы к вычислению рангов вершин с использованием информации об активности пользователей в социальных сетях. Проводится сравнение распределений полученных совокупностей рангов. Вводится понятие сходимости алгоритмов ранжирования вершин графов, а также обсуждаются различия их использования при рассмотрении данных большой размерности и необходимости построения решения в случае учета только локальных изменений.
Главным предназначением сервисных роботов является помощь людям в непромышленных средах, таких как дома или офисы. Для достижения своей цели сервисные роботы должны обладать несколькими навыками, например распознавание и манипулирование объектом, обнаружение и распознавание лиц, распознавание и синтез речи, планирование задач и одним из самых важных навыков — навигация в динамических средах. В статье описывается полностью внедренная система планирования движения, которая учитывает все: начиная от алгоритмов движения и планирования пути до пространственного представления и активной навигации на основе поведения. Предлагаемая система реализована в бытовом сервисном роботе под названием «Юстина», конструкция которого основана на робототехнической архитектуре под названием «ViRBot», использующейся для контроля действий виртуальных и реальных роботов, которая охватывает несколько уровней абстракции от низкоуровневого управления до символьного планирования. Мы оценили наш проект как в симулированной, так и в реальной среде и сравнили его с классическими реализациями. Для тестов мы использовали карты, полученные из реальных сред (Лаборатория биороботов и Robocup@Home arena), и карты, созданные из препятствий со случайными положениями и формами. Для сравнения использовалось несколько параметров: общее пройденное расстояние, количество столкновений, количество достигнутых целей и средняя исполнительная скорость. Наш проект значительно улучшился как в реальных, так и в симуляционных тестах. Представлены экспериментальные результаты успешно протестированной системы в контексте конкурса RoboCup@Home.
Предложен простой быстродействующий алгоритм полногеномного поиска ассоциаций для оценки основного и эпистатического эффекта влияния маркеров или единичных нуклеотидных полиморфизмов (SNP). Основная идея, лежащая в основе алгоритма, заключается в сравнении генотипов пар объектов популяции и сравнении соответствующих значений фенотипа. В алгоритме используется интуитивное предположение, что изменения аллелей, соответствующих важным SNP у пары объектов, приводят к большому различию значений фенотипа этих индивидуумов. Алгоритм основан на рассмотрении пар индивидуумов вместо SNP или пар SNP. Основным преимуществом алгоритма является то, что он слабо зависит от количества SNP в матрице генотипов. В основном он зависит от количества объектов, которое, как правило, очень мало по сравнению с количеством SNP. Другое важное преимущество алгоритма заключается в том, что он позволяет без дополнительных вычислений обнаруживать эпистатический эффект, рассматриваемый как взаимодействие генов. Алгоритм также может использоваться в случае, когда фенотип принимает только два значения (схема случай–контроль). Кроме того, алгоритм может быть достаточно просто расширен с анализа двоичной матрицы генотипов на случай количественного анализа экспрессии генов. Численные эксперименты с реальными наборами данных, состоящими из популяций удвоенных гаплоидных линий ячменя, иллюстрируют преимущество предлагаемого алгоритма по сравнению со стандартными алгоритмами полногеномного поиска ассоциаций с вычислительной точки зрения, особенно для обнаружения эпистатического эффекта. Пути для повышения эффективности предлагаемого алгоритма также обсуждаются в статье.
Решается задача слежения для нелинейного объекта по выходу в условиях внешних ограниченных возмущений, недоступных для измерения. Объект управления описывается гладкими функциями, для которых может быть определена их относительная динамическая степень. Функция возмущений удовлетворяет условию Липшица. Использованы стандартные модельные преобразования для перехода к описанию динамики объекта в ошибках. При синтезе алгоритма используется итеративная процедура с количеством шагов, равных показателю относительной динамической степени объекта. Предложенная система управления представляет собой робастную модификацию алгоритма обратного обхода интегратора и сохраняет его структуру. Ключевые изменения в алгоритме состоят в использовании метода вспомогательного контура для оценки и компенсации сигнала возмущения, а также в модельных преобразованиях, позволяющих уменьшить количество фильтров в системе управления. Метод вспомогательного контура дает возможность на каждом шаге синтеза алгоритма ввести в рассмотрение модель желаемой динамики ошибок слежения, что является основой для оценки величины возмущающего воздействия. Для оценки неизвестных сигналов и их производных используются известные наблюдатели с сильной обратной связью. Доказана сходимость ошибок слежения и наблюдения в замкнутой системе за конечное время с настраиваемой точностью, зависящей от величины возмущающих воздействий и параметров регулятора. Эффективность алгоритма подтверждена результатами компьютерного моделирования. Приведены графики работы предложенного метода и ближайшего аналога в режимах стабилизации и слежения, и представлены количественные показатели, позволяющие оценить качество регулирования. Практическая применимость метода рассмотрена на примере задачи управления лабораторным стендом «Twin Rotor MIMO System», который воспроизводит динамику винтокрылого летательного аппарата.
Обсуждается проблема взаимной реконструкции изображений лиц в соответствующих друг другу парах. Эта проблема была поставлена в предыдущей статье авторов, а предложенные в ней решения обсуждались с приложением к задачам гетерогенного распознавания изображений лиц (Heterogeneous Face Recognition) и кросс-модального мультимедийного поиска (Cross-Modal Multimedia Retrieval). Эти решения основаны на одномерных и двумерных методах анализа главных компонент для двух исходных наборов изображений лиц и проекции их в независимые собственные подпространства, вычислении матриц взаимной трансформации между этими подпространствами и взаимной реконструкции изображений лиц на основе одномерного и двумерного преобразований Карунена — Лоэва.
В настоящей статье предлагаются новые подходы и решения, основанные исключительно на двумерных методах проекции в собственные подпространства и двух вариантах моделей регрессии — множественной линейной регрессии и регрессии частичных наименьших квадратов.
Приведены результаты экспериментов по взаимной реконструкции изображений лиц в парах скетч/фотографии, в парах лиц с возрастными изменениями, а также в парах изображений лиц в формах 2D/3D. Для проведения экспериментов выбраны два варианта реализации предложенного подхода. Первый из них основан на двумерном анализе главных компонент и регрессии частичных наименьших квадратов, второй — на двумерном методе частичных наименьших квадратов и множественной линейной регрессии. Оба варианта показали приемлемые для практики результаты при решении задачи взаимной реконструкции изображений лиц. Кроме того, рассмотрен способ повышения качества реконструируемых изображений лиц при работе со смешанными базами. Он заключается в классификации на основе двумерного линейного дискриминантного анализа и построении регрессионной зависимости в рамках каждого класса.
Показано также, что в общем случае взаимная реконструкция изображений лиц достижима и в условиях, когда исходные изображения не входили в состав обучающих наборов изображений лиц.
На данный момент применение основанного на явлениях в природе алгоритма балансировки нагрузки задач на виртуальных машинах представляет большой исследовательский интерес. Для балансировки нагрузки с максимальной пропускной способностью была введена балансировка нагрузки на основе поведения медоносных пчел в колонии — Honey Bee Behavior Based Load Balancing (HBB-LB). Этот подход также устанавливает приоритеты выполнения задач на виртуальной машине с целью минимизации времени ожидания задач. Однако он рассматривает только один параметр — нагрузку виртуальных машин, что может оказаться недостаточно эффективным для балансировки. В работе предлагается улучшенный подход к балансировке нагрузки на основе пчелиного поведения, в котором дополнительно учитываются такие параметры качества обслуживания (QoS) виртуальных машин, как время отклика службы, доступность, надежность, стоимость и пропускная способность для улучшения балансировки нагрузки. Время отклика является критически важным для определения мгновенной активности виртуальной машины, доступность определяет доступный ресурс и состояние виртуальной машины (пассивное или активное), а надежность определяет уровень доверия к виртуальной машине. Затраты на использование виртуальной машины и пропускная способность виртуальных машин также необходимы для определения их эффективности. Однако включение нескольких параметров качества обслуживания приводит к многоцелевой оптимизации. По мере вычисления нескольких параметров фаззификация значений качества обслуживания выполнялась с помощью генерируемых нечетких правил, и была устранена проблема многоцелевой оптимизации. Эксперименты проводились с точки зрения времени разрешения задач, времени отклика, степени дисбаланса и количества перенесенных задач, а результаты показывают, что балансировка нагрузки на основе пчелиного поведения обеспечивает лучший уровень производительности.
Рассматриваются алгоритмы объективной оценки качества речи, основанные на измерении динамических и статических характеристик речевых сигналов на выходе кодека источника. Обоснована функциональная схема проведения экспериментальных исследований. Приведены результаты анализа корреляции объективной и субъективной оценки качества речи. Предложены модификации показателя объективной оценки качества на основе корреляции возбуждения спектра MESC и модификации показателя на основе вычисления функции ощущения спектральной динамики MFOSD. Предложен алгоритм формирования кривых регрессии, позволяющий выполнить преобразование объективной оценки к шкале субъективной оценки качества речи.
На основании использования наиболее точных модификаций показателей оценки качества речи для восстановленных речевых сигналов предложен комплексный алгоритм объективной аппаратурной оценки качества речи при воздействии на микрофон широкополосных и низкочастотных стационарных и нестационарных акустических помех. Показано, что применение комплексного алгоритма позволяет получить объективную оценку качества речи согласно ГОСТ Р 50840-95 со средней ошибкой не более 0,35 балла при отношениях сигнал-шум от 30 дБ до -10 дБ.
Описан алгоритм автоматического построения деформируемых 3D моделей лица, основанного на использовании метода Active Shape Models, метода восстановления ландшафтных поверхностей Шепарда и набора частных 3D моделей лиц. Предложена альтернативная к EER оценке точности в задаче распознавания личности по изображению лица, основанная на фиксированном значении оценки FAR. Приведены результаты тестирования описанного алгоритма. Продемонстрированы результаты использования полученных моделей в рамках работы алгоритма распознавания на крупной базе из нескольких тысяч изображений (база изображений FERET за 2000 год), содержащей фотографии людей под углами 0, 45 и 90 градусов относительно оптической оси камеры. Анализ результатов показал, что применение деформируемых моделей лица не снижает качества распознавания личности по изображению лица даже при сложных начальных условиях, а в ряде случаев ведет к улучшению результатов распознавания.
Известно, что технология реализации задач распознавания и принятия решений на основе классических нейронных сетей имеет ряд сложностей, среди которых необходимость наличия значительной по объему обучающей выборки; длительность и сложность алгоритмов обучения; сложности с выбором параметров структуры сети, таких как количество нейронов, слоев, связей, а также способа соединения нейронов; возможные сбои и не удачи во время обучения с необходимостью повторных изменений параметров сети и повторного обучения. В данной работе рассматривается возможность создания на основе алгоритмов метрических методов распознавания, в частности на основе алгоритма ближайшего соседа, многослойного персептрона с полной системой связей и с пороговой функцией активации. Такая возможность позволяет в итоге создать полносвязный многослойный персептрон, такие параметры которого, как количество нейронов, слоев, а также значение весов и порогов определяются аналитически. Также рассмотрена закономерность, определяющая распределение весовых и пороговых значений для второго и третьего слоя полученного многослойного персептрона, на основе которого предложен алгоритм вычисления пороговых и весовых значений многослойного персептрона, а также приведен пример, реализующий данный алгоритм. Также рассмотрены возможные применения полученных сетей для разных задач.
Сформулированы инвариантная к системе внешних координат форма задания геометрии пространственного кинематически избыточного манипулятора с последовательно ортогональными некомпланарными осями шарниров вращения. Получены аналитические выражения для определения угловых шарнирных координат из условий принадлежности точек шарниров параметрически заданной гладкой кривой, уравнение для координат положения точек на кривой и неравенства-ограничения на взаимное положение смежных звеньев манипулятора. Предложен алгоритм решения уравнения и метод планирования законов изменения шарнирных координат, обеспечивающий перемещения точек шарниров по пространственной траектории, наращиваемой добавлением целевых точек для головного звена манипулятора. Метод применен для планирования движения гиперизбыточного манипулятора с неподвижным основанием и змеевидного робота при перемещении по траектории, выстраиваемой на основе текущих и прогнозируемых положений шарниров в декартовом пространстве
Представлен алгоритм классификации образцов многомерных групповых точечных объектов. Поиск осуществляется на основе комбинаторного поиска соразмерных фрагментов матриц попарных отношений на множестве шаблонов. Решение об отнесении образца к тому или иному шаблону принимается по критерию минимума евклидового расстояния. Представленный подход к распознаванию позволяет синтезировать инвариантные (относительно вращения, масштабирования или смещения системы координат) описания вторичных признаков, а также использовать достаточно мощный инструментарий теории многомерного и метрического шкалирования в компенсации искажений распознанных образов групповых точечных объектов. В алгоритме реализована процедура статистических испытаний Монте-Карло, в рамках которого каждая точка случайным образом размещенная в предполагаемой окрестности искомых координат проверяется по условию минимума квадратического показателя сходства. Приведены пример и результаты использования алгоритма для идентификации и восстановления искаженных и подвергнутых воздействию координатных шумов радиоизображений, представленных выборкой шаблонов "блестящих" точек.
Задача восстановления динамической системы по ее функционированию является актуальной в теории управляющих систем. Ранее были получены псевдополиномиальные алгоритмы восстановления дискретных динамических систем с аддитивными и мультипликативными функциями. Такие системы моделируют поведение регуляторного контура генной сети, а соответствующие функции отвечают за увеличение или уменьшения концентрации веществ. В настоящей статье рассматривается обобщение на случай произвольных пороговых функций. Приведены алгоритмы восстановления существенных переменных и алгоритм упорядочивания весов пороговых функций, имеющие псевдополиномиальную сложность тестирования. Эти алгоритмы позволяют либо полностью восстановить систему, либо уменьшить размерность пороговых функций.
Представлен алгоритм классификации групповых точечных объектов (ГТО), основанный на сравнительном анализе фрагментов искаженных образов и шаблонов ГТО. В качестве фрагментов использованы последовательности элементов ГТО различной длины. В качестве признаков классификации выступают попарные и угловые межточечные расстояния. При решении задачи классификации используется вероятностная мера близости, задаваемая экспертом с помощью функции принадлежности и закона распределения вероятности дискретных значений признаков классифицируемых объектов. Алгоритм включает следующие этапы: поиск и сравнение состава фрагментов искаженных образов и шаблонов ГТО; формирование вероятностной оценки близости искаженного образа ГТО и каждого шаблона в пространстве рассматриваемых признаков по результатам анализа каждого фрагмента; накопление полученных вероятностей по результатам анализа всех фрагментов искаженного образа; ранжирование полученных вероятностей отнесения искаженного образа к шаблонам ГТО; определение наиболее вероятного шаблона. В алгоритме предусмотрена возможность уточнения класса искаженного образа ГТО за счет использования логических правил и аналитических выражений рассматриваемой предметной области. Приведены пример и результаты применения данного алгоритма для решения задачи классификации реальных ГТО на основе анализа их фрагментов в виде последовательностей из двух и трех элементов.
Задача оценивания защищённости речевой информации конфиденциального характера в настоящее время является крайне актуальной. Но в условиях применения средств акустической защиты, то есть в условиях сильных шумов, существующие инструментально-расчётные методы дают большую погрешность при сравнении с крайне трудозатратными артикуляционными методами.
В работе исследован метод оценки показателя защищённости речевой информации на основе корреляционного коэффициента Пирсона, но данный коэффициент обладает плохой чувствительностью к спектральным свойствам акустических сигналов. Поэтому автором предложен подход к определению показателя защищённости речевой информации на основе математического аппарата функции когерентности исходного и зашумлённого сигнала.
В статье предлагается весь речевой частотный диапазон функции когерентности разбить на отдельные октавы. Посчитать математическое ожидание составляющих функции когерентности в октавах и на основе функции свёртки получить выражение для расчёта показателя защищённости речи.
Предложенный алгоритм к определению показателя защищённости речевой информации позволяет повысить точность проводимой оценки.
В настоящее время задачи ускорения вычислений и/или их оптимизация является достаточно актуальной задачей. Среди направлений решения вышеприведенной задачи в статье рассматривается применение подхода распараллеливания и асинхронизации алгоритма сортировки. Предлагается метод сортировки, основанный на принципе разбиения всего массива на множество независимых пар чисел и их параллельное и асинхронное сравнение, что отличает предлагаемый алгоритм от традиционных алгоритмов сортировки (таких как быстрая сортировка, сортировка слиянием, вставками и другие). Алгоритм реализован с использованием сетей Петри как наиболее подходящего инструмента для описания асинхронных систем, а также приведен пример его работы. В статье выполнена оценка быстродействия алгоритма для наилучшего и наихудших случаев. В наилучшем случае алгоритм выполняется за 2 или 3 условных такта в зависимости от разбиения массива на пары соседних элементов. В наихудшем случае – за n или за 3n/2, где n – число элементов. Принципы распараллеливания и асинхронизации, использованные при построении алгоритма, также могут быть применены для других алгоритмов.
Улучшены существующие навигационные алгоритмы для плоского шарнирного многоугольника общего вида. Представленный алгоритм строит путь между двумя произвольными конфигурациями шарнирного многоугольника, состоящий из не более чем восьми шагов.
В работе предложен адаптивный алгоритм прогнозирования временного ряда на основе выбора периода-аналога. Особенностью алгоритма является использование обучающей выборки прогнозов для автоматического выбора оптимальных параметров его работы. Алгоритм применялся для прогнозирования гидрологических временных рядов притока воды в Новосибирское водохранилище (река Обь). Показана эффективность его применения (повышение точности прогнозирования) по сравнению с базовым алгоритмом.
В работе предложен алгоритм вычисления координат автономного необитаемого подводного аппарата на базе триангуляционного метода и посттриангуляционной коррекции. Особенностью алгоритма является использование в качестве входных параметров нескольких наборов дальностей аппарат-маяк, вычисленных с разными значениями скорости звука в воде. Проведены исследования, которые показали, что разработанный алгоритм в среднем превосходит триангуляционный метод по точности в два раза.
Рассматривается задача управления расходом ресурсов в процессе развертывания систем информационного обеспечения сложных технических комплексов (СТК). Применение СТК по целевому назначению, как и процесс соответствующего информационного обеспечения, обычно ограничено жесткими директивными сроками, поэтому любая задержка недопустима. Ее устранение может быть реализовано часто только за счет привлечения дополнительных информационных ресурсов на последующих этапах. Разработанный алгоритм базируется на принципе оптимальности Р. Беллмана, позволяющем определять не окончательный план корректировки, а разрабатывать гибкую программу управляющих воздействий, зависящих от конкретного исхода каждого этапа, длительность которого превысила заданный норматив. Данная программа может быть реализована в соответствующих системах поддержки принятия решений, а также включена в имитационные модели процессов развертывания и применения СТК. В статье описывается детальный алгоритм оптимальной корректировки, соответствующий нормальному распределению продолжительности каждого из этапов.
Предлагается подход к автоматической рубрикации текстовых документов на основе совместного применения метода латентно-семантического анализа (ЛСА) и алгоритма нечёткого вывода Мамдани. Метод ЛСА используется для смыслового анализа информации в системах электронного документооборота путем выявления семантических зависимостей между термами документов и получения коэффициента соответствия сравниваемых векторов.
Предлагается база правил для алгоритма нечёткого вывода Мамдани, реализующего автоматическую рубрикацию документов по множеству заданных тематик с возможностью автоматизированного контроля за распределением документов не соответствующим заданным тематикам или имеющим сходство сразу по нескольким тематическим категориям на основе результатов латентно-семантического анализа.
Рассматривается задача объединения графов с общей частью, которые были получены в результате серии моделирований сети Петри с использованием программного пакета Colored Petri Nets Tools, в котором адресное пространство процесса ограничено 232 байтами, начиная с различных вершин и при различных начальных условиях. Для ее решения необходимо определить общую часть графов, выполнить разрез таким образом, чтобы их общая часть осталась только в одном из начальных графов, и составить таблицу соответствия (переходов) между вершинами графов для возможности осуществления переходов между ними. Изначально предполагается, что графы представлены в виде списков смежности, но в процессе работы алгоритма они преобразовываются в хеш-таблицы для быстрого определения общей части графов, которое реализуется при помощи обхода одного из графов и проверки наличия вершин во втором. Составление таблицы переходов между графами осуществляется при помощи обхода графа по парам «родительская-дочерняя» вершины, в ходе которого проверяются условия добавления узлов в таблицу переходов. Предлагается алгоритм решения задачи объединения частей ориентированного графа и приведен пример его использования.
Рассмотрены методы бесконтактного определения величин угловых и линейных геометрических параметров в структурах текстильных материалов. Разработаны алгоритм моделирования изображений дифракционных картин с использованием быстрого преобразования Фурье, алгоритм измерения угла кручения нити по цифровой фотографии её структуры, алгоритм измерения перекоса нитей в ткани и алгоритм измерения расстояния между соседними элементами структуры с использованием метода двойного преобразования Фурье.
В настоящей работе рассматривается проблема автоматизированного поиска уязвимостей в исполняемом коде. В работе проводится анализ проблематики, и выделяются недостатки существующих решений, в части отсутствия возможности обнаружения уязвимостей с учётом тех угроз, которые они несут для защищаемой информации, которая обрабатывается в ПО. Для решения этой проблемы предлагается оригинальная модель автоматизированного поиска уязвимостей в трассе программы, её алгоритмическое обеспечение и программная реализация. В рамках модели приводятся формальные критерии отнесения ошибки к уязвимости с учётом распределения защищаемой информации в памяти программы. Для выделения участков памяти с защищаемой информацией в работе используется методика анализа помеченных данных. Кроме того приводится экспериментальная оценка эффективности разработанного программного комплекса, которая показала, что разработанное решение позволяет детектировать на 5 типов уязвимостей больше в ОС Windows и на 4 типа уязвимостей больше в Linux по сравнению с существующими аналогами. Все модули разработанного комплекса были опубликованы как ПО с открытым исходным кодом, могут свободно использоваться в других проектах и доступны для скачивания в Интернете.
Стремительное развитие информационных технологий в последние десятилетия стало причиной значительного увеличения объема исходных текстов программного обеспечения, а также его сложности. Данный факт обусловливает высокую сложность анализа программного обеспечения с целью понимания логики его функционирования, необходимость выполнения которого является важным моментом при проведении судебной компьютерно - технической экспертизы. В статье раскрывается один из подходов к автоматизации процесса идентификации стандартизированных алгоритмов преобразования данных в исполняемых модулях в условиях отсутствия исходных текстов за счет учета их внутренних информационных связей с целью упрощения понимания программ.
Предлагается алгоритм построения гибкой программы диагностирования технического объекта по критерию ценности получаемой информации. Рассматриваются диагностические признаки, которые имеют непрерывную форму представления. Приводится числовой пример реализации алгоритма.
Статья посвящена исследованию управляемых подстановочно-перестановочных сетей на основе управляемых элементов F 4/2 в качестве примитива блочных алгоритмов шифрования. Актуальность исследований связана с их ориентацией на проектирование скоростных аппаратных шифров. Научная и практическая значимость полученных результатов заключается в повышении эффективности аппаратной реализации скоростных алгоритмов шифрования, предназначенных для защиты информации в информационно-телекоммуникационных системах и сетях.
Описан оригинальный алгоритм кластеризации разнотипных данных, основанный на комплексном применении набора мер расстояний и методов кластеризации и многоэтапной кластеризации. В рамках алгоритма реализовано ранжирование признаков объекта по их значимости для группировки и выбор оптимального набора признаков, ансамблевый подход для получения более устойчивого итогового кластерного решения. Алгоритм реализован в программной системе MixDC (Mixed Data Clustering). Приведены методика и результаты решения реальной задачи кластеризации медицинских данных средствами программной системы.
В данной работе рассматривается влияние параметров алгоритма многоитерационного хеширования с несколькими модификаторами на его криптостойкость. Обоснована актуальность применения алгоритма многоитерационного хеширования с несколькими модификаторами и необходимость исследования его параметров, приводится описание алгоритма. Стойкость хеш-функции к атакам, не зависящим от алгоритма, обусловливается ее разрядностью, т.е. фактически – количеством уникальных значений, которое способна генерировать данная хеш-функция. Для оценки стойкости алгоритма к атакам методами «грубой силы», «дней рождения» и словарным атакам алгоритм многоитерационного хеширования с несколькими модификаторами рассматривается как самостоятельная хеш-функция. Оценку стойкости алгоритма при заданном количестве итераций предлагается производить путем вычисления средней разрядности эквивалентно стойкой хеш-функции для алгоритма. Приводится описание метода оценки стойкости алгоритма. Эксперименты производятся с использованием усеченной криптостойкой хеш-функции. Приводятся результаты экспериментов, позволяющие сравнить между собой показатели стойкости алгоритма при различных значениях его параметров. Кроме того, результаты экспериментов позволяют понять, как значения тех или иных параметров, а также сочетания значений этих параметров влияют на криптостойкость алгоритма к атакам методами «грубой силы», «дней рождения» и словарным атакам. На основании полученных результатов можно сделать выводы о значениях параметров, рекомендуемых для практического применения данного алгоритма. В заключении представлены основные результаты работы. Авторы статьи полагают, что алгоритм может найти применение в подсистемах аутентификации информационных систем, а также в системах, в которых наиболее важным требованием является стойкость в течение длительного времени.
Создание модели языка является одним из этапов обучения системы распознавания слитной речи. В статье описаны алгоритм и разработанные программные средства для создания синтаксическо-статистической модели русского языка по текстовому корпусу. Основными этапами в работе алгоритма являются предварительная обработка текстового материала, создание статистической n-граммной модели языка, дополнение статистической модели n-граммами, полученными в результате синтаксического анализа. Синтаксический анализ позволяет увеличить количество создаваемых в результате обработки текста различных биграмм и тем самым повысить качество модели языка за счет выявления грамматически связанных пар слов. Приводятся результаты тестирования созданных с помощью программного модуля моделей языка по показателям информационной энтропии, коэффициента неопределенности, относительного количества внесловарных слов и совпадений n-грамм.
В работе предлагается оригинальный алгоритм решения прикладной задачи теории графов о нахождении k максимальных потоков между двумя заданными вершинами графа. Описываемый подход представляет собой комплексное применение в едином оптимизационном цикле алгоритма Форда-Фалкерсона (Эдмондса-Карпа или Диница) и алгоритма построения усеченного дерева состояний в ширину.
В статье рассматриваются новые подходы к оценке состояния здоровья человека на основе интегрального показателя. Описана математическая модель для расчета введенного показателя. Проведена апробация модели и показателя на пациентах лечебного учреждения здравоохранения
В статье показаны достоинства и недостатки прямых и итерационных методов решения систем линейных алгебраических уравнений (СЛАУ) большой размерности (БР). Предложен новый «прямой» метод (алгоритм) решения СЛАУ с варьируемыми параметрами для матриц БР на основе учета разреженности матрицы и информации о решении базовой СЛАУ. Это позволяет существенно повысить быстродействие расчетных алгоритмов за счет уменьшения количества вычислительных операций; снизить требования к объемам оперативной памяти ЭВМ.
Рассматривается задача управления телематическими сервисами в гетерогенной виртуальной сети кибер-объектов, к которым относятся различные технические устройства со встроенными средствами организации процессов информационного взаимодействия. Предложенная модель использует технологию виртуализации для организации транспортного уровня мультипротокольных сетей обмена данными. Представленные результаты моделирования процессов, связанных с организацией телематических сервисов, подтверждают возможность создания виртуальных каналов связи, толерантных к задержкам при передаче данных с использованием технологии пакетной коммутации.
Оптимизация работы с мультимедийными ресурсами с целью сокращения передаваемого объема данных между пользователями является одной из проблем приложений видеоконференцсвязи. В статье описаны алгоритмы и программные средства, позволившие провести оптимизацию разработанного кроссплатформенного приложения видеоконференцсвязи. Основными этапами работы средств видеоконференцсвязи являются: создание и удаление аудио- и видеопотоков данных, их передача от сервера к клиенту и обратно, создание цепочек потоков и их поиск на сервере. Вышеперечисленные этапы присутствуют в любом приложении видеоконференцсвязи и требуют оптимизации в связи с присутствием в них главных процессов и сложностью архитектуры самого приложения. Поэтому в ходе работы было выполнено упрощение клиентской части приложения и реорганизация структуры серверной части приложения. В режиме приема-передачи данных разработанное приложение после проведенной оптимизации по сравнению с программой «Skype» стало потреблять почти в 10 раз меньше оперативной памяти и в 2 раза меньше процессорного времени.
При автоматической обработке спонтанной речи возникает ряд трудностей, таких как вариативность речи или присутствие речевых сбоев различной природы. В статье рассматриваются различные виды речевых сбоев и причины их возникновения, а также представлен алгоритм их автоматического определения, основанный на анализе акустических параметров. Для выделения звонких хезитационных явлений использовался кросскорреляционный метод, а для выделения глухих хезитационных явлений – метод полосовой спектральной фильтрации. Эксперименты проводились на специально собранном корпусе спонтанной русской речи, состоящем из диалогов по описанию маршрута по карте и нахождению общего свободного времени по расписанию. Проведенные эксперименты показали, что звонкие хезитационные явления выделяются с точностью 80%, глухие хезитационные явления и дыхание - с точностью 66%.
Целью работы является создание алгоритма генерации тезауруса синонимов для названий продуктов. Такие тезаурусы используются в современных поисковых машинах для расширения пользовательского запроса и улучшения качества поиска. При этом подходе из поискового индекса выбираются документы, включающие в себя не только слова, содержащиеся в запросе, но и близкие по смыслу термины. В ходе работы был реализован полуавтоматический метод обучения распознавателя именованных сущностей. Для валидации извлеченных сущностей был предложен метод полуавтоматической валидации.
В статье рассматривается задача коррекции планов работы информационной системы наземно-космического мониторинга с учетом текущей информации, приводится обобщенный алгоритм программно-позиционного управления и результаты его работы на численном примере.
Одним из подходов к обнаружению сетевых аномалий является анализ рядов показателей функционирования сети. Характеристики, рассчитанные по вейвлет-коэффициентам, действительно, более чувствительны к изменениям ряда, чем характеристики, рассчитанные непосредственно по ряду, но при этом требуют большего объема вычислений, поэтому спектрально-временные алгоритмы, безусловно, подлежат оптимизации для применения в системах реального времени. Кроме того, существуют различные подходы к выполнению вейвлет-разложений, каждый из которых занимает свое место по информативности (по количеству уточняющих коэффициентов), области достоверных значений, вычислительной сложности преобразований. В статье предлагается обоснованный подход к выполнению таких алгоритмов для применения в режиме реального времени в системах обнаружения аномалий телекоммуникационных данных.
Предложена двухэтапная схема синтеза подмножеств минимальных графов смежности, предполагающая построение трех множеств (стереосепараторов, их владений и обязательных ребер) по множеству подалфавитов и построение по этим четырем множествам множеств жил определенного вида для каждого стереосепаратора. Систематизированы алгоритмы, реализующие оба этапа, и дана оценка их сложности.
В теории алгебраических байесовских сетей (логико-вероятностных графических моделей, использующих для представления знаний с неопределенностью интервальные оценки вероятности истинности пропозициональных формул), формализовано понятие непротиворечивости содержащихся в системе знаний. В работе проанализирован алгоритм обработки поступивших свидетельств с точки зрения сохранения в процессе его выполнения непротиворечивости сети. Предложено улучшение существующего алгоритма, обеспечивающее непротиворечивость результата.
В теории алгебраических байесовских сетей стоит задача построения вторичной структуры сети по известной первичной структуре. Для осуществления логико-вероятностного вывода в качестве вторичной структуры может выступать только минимальный граф смежности. В статье сформирован алгоритм рандомизированного синтеза минимального графа смежности. Доказана теорема о том, что выбор любого возможного для заданной первичной структуры алгебраической байесовской сети минимального графа смежности алгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиимеет положительную вероятность.
Способность приложений анализировать текущие условия эксплуатации, в том числе, текущее состояние пользователя, физического окружения, вычислительных ресурсов, и динамически адаптировать сценарий взаимодействия с пользователем является одним из главных требований при разработке прототипов интеллектуальных пространств. С увеличением решаемых задач и числа обслуживаемых пользователей становится затруднительным держать под контролем множество программных и аппаратных модулей, задействованных в интеллектуальном пространстве, поэтому необходимо математическое обеспечение и программные средства, реализующие контроль совместной работы распределенных модулей. В статье описывается разработанная структура модели управления распределенными модулями интеллектуального зала и используемые многомодальные интерфейсы для обеспечения естественности человеко-машинного взаимодействия.
Условием работы алгоритмов глобального логико-вероятностного вывода в алгебраической байесовской сети (АБС) является отсутствие циклов в ее вторичной структуре. Первичная структура, над которой можно построить ациклическую вторичную, называется ациклической. Цель работы — предложить алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в ее вторичной структуре без непосредственного построения вторичной структуры, а также оценка сложности этого алгоритма. В работе сформулирован алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в минимальном графе смежности полным перебором, доказана его корректность, оценена его сложность, предложено улучшение скорости работы этого алгоритма, доказана корректность и оценено время работы улучшенного алгоритма. Также рассмотрены возможности улучшения скорости работы этого алгоритма за счет использования алгоритмов построения элементов третичной полиструктуры АБС.
В статье рассматривается обобщенная динамическая модель управления корпоративной информационной системой (КИС), предлагается для коррекции планов ее работы использовать позиционные управления, построенные с использованием метода позиционной оптимизации, приводится обобщенный алгоритм программно-позиционного управления КИС.
В данной работе для непрерывных сплайнов первого порядка лагранжева типа построено вэйвлетное разложение (уточнение) на неравномерной сетке и соответствующие алгоритмы декомпозиции и реконструкции в случаях бесконечного потока (с сеткой на открытом интервале) и конечного потока (с сеткой на отрезке).
Статья посвящена получению оценок числа шагов логико-предметных алгоритмов распознавания сложных изображений на экране дисплея. Доказана полиномиальность задачи выделения и распознавания эталонного изображения на сложной сцене. Для задачи выделения и распознавания объекта из класса, описание которого содержит только характерные признаки этого класса, доказана её принадлежность классу. Для уменьшения числа шагов работы алгоритма предложено понятие размытого изображения. Рассмотрена задача инвариантного (относительно изменения масштаба) распознавания изображения
Алгебраические байесовские сети (АБС) относятся к классу логиковероятностных графических моделей систем знаний с неопределенностью, которые позволяются использовать интервальные оценки вероятности для представления неопределенности в знаниях. Одним из наиболее важных условий работы АБС является отсутствие циклов в их вторичной структуре. Первичная структура, над которой можно построить ациклическую АБС, называется ациклической. Цель работы — предложить алгоритм выявления ацикличности первичной структуры на основе анализа четвертичной структуры АБС, а также оценка сложности этого алгоритма. В работе сформулирован алгоритм выявления ацикличности, доказана его корректность, оценена его сложность и предложен ряд способов, направленных на ускорение работы этого алгоритма.
Роль третичной полиструктуры алгебраической байесовской сети (АБС) заметно возросла. Вводимая изначально в качестве вспомогательного объекта для построения вторичной структуры, третичная полиструктура нашла свое применение в анализе цикличности вторичной структуры без ее непосредственного построения и предполагается к использованию для глобального вывода в АБС. Цель работы — выделение (с последующей систематизацией и оценкой сложности) существующих алгоритмов построения элементов третичной полиструктуры из алгоритмов построения вторичной структуры. В работе рассмотрены существующие алгоритмы построения элементов третичной полиструктуры и оценено время их работы. Приводятся четыре алгоритма построения пустого графа над подмножествами значимых клик и два алгоритма построения родительского графа над множеством стереоклик.
В статье рассматривается локальный апостериорный вывод в алгебраических байесовских сетях. Для трёх видов свидетельств (детерминированного, стохастического и неточного) описывается способ проведения вывода и доказываются оценки сложности предлагаемых вычислений. В случае, когда вывод сводится к решению задач линейного программирования, оценка сложности даётся в виде числа таких задач, а также оценки числа переменных и ограничений в них. В остальных случаях сложность описывается в числе арифметических операций.
Третичная структура алгебраической байесовской сети (АБС), представляемая в виде графа клик, важна для построения и анализа вторичной структуры АБС, а также для анализа ее первичной структуры. В статье предложены два алгоритма построения третичной структуры: алгоритм построения графа клик при помощи потомков и алгоритм построения графа клик снизу—вверх, доказана их корректность и оценено время работы. Оба алгоритма по заданному набору максимальных фрагментов знаний строят два упорядоченных множества, содержащие множества вершин и множества сыновей каждой клики. Приведены примеры первичных структур АБС, на которых первый алгоритм работает быстрее второго и, наоборот, второй — быстрее первого. Также установлены существование и единственность третичной структуры АБС для каждой первичной структуры АБС.
Статья носит научно-методический характер и посвящена формализованной постановке задачи оценивания торговой ситуации на рынках капитала в интересах проведения эффективных торговых операций. Представлены основные факторы, определяющие высокий уровень неопределенности при формировании оценки состояния рынков финансовых активов. Рассмотрен традиционный подход к анализу состояния рынка на основе методов статистического системного синтеза. Приведены основные технологии к построению статистически устойчивых алгоритмов оценивания состояния торговых ситуаций.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи самоуправляемых клик), а также два улучшения, каждое из которых реализуется в отдельном алгоритме; однако нет алгоритма, который бы реализовал оба улучшения. Цельюданной работы является создание такого алгоритма, который бы реализовывал одновременно ряд улучшений базового алгоритма, вследствие чего он был бы более эффективным, чем существующие.Такой алгоритм был предложен, его корректность доказана.
Рассматриваются вопросы проверки и поддержания непротиворечивости алгебраических байесовских сетей. Даются формальные описания алгоритмов, доказывается их корректность и приводятся оценки вычислительной сложности.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи само-управляемых клик), однако он может быть улучшен путем привлечения результатов активно разрабатывающейся теории глобальной структуры алгебраической байесовской сети. Целью данной работы является разработать улучшенную версию этого алгоритма за счет усовершенствованного построения множества вершин, входящих в клики: вместо полного перебора всех весов клик и вершин производить поиск для каждой клики ее потомков среди других клик. Предложенное улучшение легко в основу нового алгоритма построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников, корректность которого также была доказана.
При построении сценариев тестирования программ может возникнуть потребность анализа их свойств. Для формального задания сценариев можно применить левоконтекстные терминальные грамматики. В работе доказывается эквивалентность порождающей мощности левоконтекстных терминальных грамматик и контекстно-свободных грамматик и рассматриваются алгоритмы анализа левоконтекстных грамматик, которые могут быть использованы для анализа свойств сценариев тестирования.
Известен эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов знаний (при помощи самоуправляемых клик), однако этот алгоритм может быть улучшен путем привлечения разработанной теории глобальной структуры алгебраической байесовской сети. Цель работы — улучшить работу этого алгоритма за счет усовершенствованного построения владений (компонент связности строгих сужений) — ключевых объектов в построении данного множество: строить их не прямым поиском, а путем анализа пересечений множеств вершин детей соответствующих клик. Был предложен алгоритм, реализующий предложенные улучшения, и доказана его корректность.
В статье предложено полимодельное описание функционирования наземного комплекса управления (НКУ) орбитальной системой (ОрС) космических аппаратов (КА), в основе которого лежит динамическая интерпретация соответствующих процессов. Данный подход открывает широкие перспективы использования достижений современной теории управления для решения прикладных задач, при исследовании которых указанная теория ранее не применялась. В частности, в статье показано, как задачу комплексного планирования работы наземных технических средств (НТСр), входящих в состав НКУ, с помощью метода локальных сечений удается свести к двухточечной краевой задаче. Традиционно задачи данного класса (задачи теории расписаний) решаются с использованием методов математического программирования. Однако в случае большой размерности задач планирования приходится отказываться от точных методов оптимизации решений и прибегать к эвристическим приемам. В статье предлагается оригинальный подход к решению задач теории расписаний большой размерности, основанный на использовании моделей и методов теории оптимального управления.
Известна схема алгоритма, которая позволяет строить множество минимальных графов смежности по заданному набору максимальных фрагментов знаний (МФЗ), однако алгоритм может быть улучшен путем привлечения разработанной теории глобальной структуры алгебраической байесовской сети. Цель исследования — улучшить работу это алгоритма. Были выдвинуты и обоснованы три улучшения известного алгоритма: 1) исключение незначимых сужений, 2) исключение клик с единственным владением и 3) априорный учет однореберных бездетных клик. Предложен алгоритм, реализующий предложенные улучшения и доказана его корректность.
Предлагается алгоритм формирования вторичной структуры алгебраической байесовской сети (АБС) на основе ее первичной структуры. Вторичная структура АБС представляет собой граф смежности с минимальным числом ребер. Приведено доказательство корректности работы алгоритма.
Задача поиска образца в изображении в той или иной форме является одной из базовых задач в области компьютерного зрения. Она возникает в задачах определения оптического потока, стереозрения, сопровождения. Один из классических подходов, предложенный Б. Лукасом и Т. Канаде, основывается на оптимизации некоторого функционала качества. В работе предлагается алгоритм поиска образца в изображении (алгоритм случайной выборки), основанный на подходе Лукаса–Канаде и показывающий высокие результаты по производительности.
Проведение априорного логико-вероятностного вывода является одной из важных операций в работе интеллектуальных систем поддержки принятия решений. Данная статья описывает комплекс алгоритмов локального априорного вывода в рамках парадигмы алгебраических байесовских сетей: алгоритм разбора логических формул и алгоритмы построения задач линейного программирования, соответствующих разным случаям локального априорного вывода.
Приводится и обосновывается алгоритм распознавания цепных и циклических правил для контекстно-свободной грамматики.
В статье рассматриваются основные алгоритмы интеллектуального анализа данных (Data Mining, DM), лежащие в основе нового типа автоматизированного управления многомерными динамическими процессами — аналитического. Существенным отличием аналитического управления является сочетание оперативных управленческих решений, формируемых должностными лицами на основе данных мониторинга текущей ситуации, с результатами глубокого количественного анализа ретроспективных данных (накопленного опыта), реализуемого средствами DM. Сформулированы концептуальные основы аналитического управления, позволяющие выделить DM в качестве самостоятельного подкласса информационных технологий.
Статья посвящена вопросам применения методологии прогностического управления (Advanced Process Control, APC) в задачах управления технологическими процес сами. В качестве базового инструментария предлагается использовать разработанный авторами программно-алгоритмический комплекс «Матрица», позволяющий на основе пред варительного анализа статистических и динамических характеристик ретроспективных данных формировать прогностические модели управления. Использование прогностических моделей дает возможность, в свою очередь, оптимизировать процесс многопараметриче ского управления в соответствии с выбранным критерием эффективности и имеющимися ограничениями.
В настоящее время в рамках интенсивно развиваемой теории управления структурной динамики (УСД) информационных систем (ИС) особую актуальность приобретают задачи расчета и анализа показателей целевых и информационно-технологических возможностей указанных систем, задачи анализа устойчивости их функционирования. Проведенные исследования показали, что для эффективного решения данных задач целесообразно использовать множества достижимости (МД), которые ставятся в соответствие тем динамическим моделям, с помощью которых описывается структурная динамика ИС. В статье предлагаются оригинальные методы и алгоритмы построения и аппроксимации МД, позволяющие повысить оперативность расчета и анализа различных показателей, характеризующих УСД ИС.
В статье рассматривается реализация в графическом редакторе операторов слияния и разлияния, широко используемых в практике построения моделей на основе алгоритмических сетей. В предыдущей версии графического редактора эти операторы были реализованы в упрощенной форме. Рассматриваются сложности при программной реализации операторов в полном варианте и возможные их решения.
Приводится и обосновывается алгоритм распознавания бесконечных правил для контекстно-свободной грамматики.
Под коллективным распознаванием понимается задача использования множества классификаторов, каждый из которых принимает решение о классе одной и той же сущности, ситуации, образа и т.п., с последующим объединением и согласованием решений отдельных классификаторов с помощью того или иного алгоритма. В настоящее время это направление в области распознавания образов и классификации, которое, с одной стороны, зарекомендовало себя как новый шаг в данной области, и которое, с другой стороны, находит все более и более широкое применение в решении сложных крупномасштабных прикладных задач, является предметом активных теоретических и прикладных исследований. Данная работа посвящена обзору состояния исследований в упомянутой области начиная с первых работ, которые относятся еще к 1950-м годам, и заканчивая самыми новыми результатами.
В пространстве состояний (ПС) нелинейных нестационарных динамических объектов исследуются численные алгоритмы их оптимального управления при наличии ограничений. Управляющие воздействия ограничиваются классом кусочно-постоянных функций, в виде положительных и отрицательных импульсов, порождающих в ПС бинарные деревья. Динамический процесс интерпретируется как рост бинарного дерева. По мере роста бинарного дерева, его узлы попадают в различные области ПС (кластеры). Целью управления является попадание, в процессе роста бинарного дерева, одного или нескольких узлов в заданный кластер. В работе рассматривается новый численный метод поиска оптимального управления при адаптации к ограничениям внешней среды, названный методом бинарных деревьев.
Предлагается расширение возможностей аппарата алгоритмических сетей путем сравнения его с классическими языками программирования.
Определяются задачи, решаемые в ходе выполнения проекта разработки программного изделия с помощью математических моделей. Приводятся схемы технологического и информационного взаимодействия моделей. Определяются основные характеристики проекта. Дается описание моделей, входящих в комплекс (модели оценивания и отслеживания).
В статье приводится алгоритм вычисления площади многоугольника по координатам его вершин для многоугольников с непересекающимися ребрами.
Предлагаются новые программные решения, учитывающие реальные возможности создания обучающихся и аналитических систем. Обсуждаются возможности создания интеллектуальной поддержки принятия решений на основе использования предикатных построений.
Представлен результат исследований Многофазного метода и робастного алгоритма управления нечеткой логики, основанных на Модели памяти формы с визуальным наведением для сборочных роботов применительно к задаче измерения координат для автономных и сборочных роботов и космических манипуляторов. Также, представлены разработанное программное обеспечение и аппаратура оптической телевизионной системы, используемой в том числе для 6-ти координатной задающей перчатки управления роботом в режиме реального времени, и результаты экспериментальных исследований динамических параметров и оценки точности оптико телевизионной системы, а также, экспериментов по использованию метода обучения показом для сборочного манипулятора. Данная работа поддержана Проектом INTAS № 96-049 «Сборочная робототехника, робастное сило-моментное управление, оптимальное планирование, основанное на нечеткой логике».
В работе рассматривается возможность использования формализма алгоритмических сетей для автоматизации распараллеливания программ.
Рассматриваются методы структурного синтеза и общие принципы инвариантного анализа сложных нелинейных математических моделей. Аналитическая форма представления моделей имеет вид многопараметрических дифференциальных уравнений или динамических систем с управлением. Вводятся понятия о формальных моделях полиномиального типа, формальных интегральных многообразиях и дифференциальных комплексах. Приводятся примеры алгоритмов. Рассматриваются модели полиномиального и сингулярного типа, обратимые и управляемые, экологические минимального типа. Приводятся примеры компьютерных математических справочных систем.
В интернете «фейковые новости» - это распространенное явление, которое часто беспокоит общество, поскольку содержит заведомо ложную информацию. Проблема активно исследовалась с использованием обучения с учителем для автоматического обнаружения фейковых новостей. Хотя точность растет, она по-прежнему ограничивается идентификацией ложной информации через каналы на социальных платформах. Это исследование направлено на повышение надежности обнаружения фейковых новостей на платформах социальных сетей путем изучения новостей с неизвестных доменов. Особенно трудно обнаружить и предотвратить распространение информации в социальных сетях во Вьетнаме, потому что все имеют равные права на использование интернета для разных целей. Эти люди имеют доступ к нескольким платформам социальных сетей. Любой пользователь может публиковать или распространять новости через онлайн-платформы. Эти платформы не пытаются проверять пользователей, их местоположение или содержимое их новостей. В результате некоторые пользователи пытаются распространять через эти платформы фейковые новости для пропаганды против отдельного лица, общества, организации или политической партии. Мы предложили проанализировать и разработать модель распознавания фейковых новостей с использованием глубокого обучения (называемого AAFNDL). Метод выполнения работы: 1) во-первых, анализируем существующие методы, такие как представление двунаправленного кодировщика от преобразователя (BERT); 2) приступаем к построению модели для оценки; 3) подходим к применению некоторых современных методов к модели, таких как метод глубокого обучения, метод классификатора и т.д., для классификации ложной информации. Эксперименты показывают, что наш метод может улучшить результаты на 8,72% по сравнению с другими методами.
Применение моделей машинного обучения обуславливает необходимость создания методов, направленных на повышение качественных показателей обработки информации. В большинстве практических случаев диапазоны значений целевых переменных и предикторов формируются под воздействием внешних и внутренних факторов. Такие явления, как дрейф концепций, приводят к тому, что модель со временем понижает показатели полноты и точности результатов. Целью работы является повышение качества анализа выборок и информационных последовательностей на основе многоуровневых моделей для задач классификации и регрессии. Предлагается двухуровневая архитектура обработки данных. На нижнем уровне происходит анализ поступающих на вход информационных потоков и последовательностей, осуществляется решение задач классификации или регрессии. На верхнем уровне выполняется разделения выборок на сегменты, определяются текущие свойства данных в подвыборках и назначаются наиболее подходящие по достигаемым качественным показателям модели нижнего уровня. Приведено формальное описание двухуровневой архитектуры. В целях повышения показателей качества решения задач классификации и регрессии производится предварительная обработка выборки данных, вычисляются качественные показатели моделей, определяются классификаторы, имеющие лучшие результаты. Предложенное решение позволяет реализовывать постоянно обучающиеся системы обработки данных. Оно направлено на снижение затрат на переобучение моделей в случае трансформации свойств данных. Проведены экспериментальные исследования на ряде наборов данных. Численные эксперименты показали, что предложенное решение позволяет повысить качественные показатели обработки. Модель может быть рассмотрена как совершенствование ансамблевых методов обработки информационных потоков и выборок данных. Обучение отдельного классификатора, а не группы сложных классификационных моделей дает возможность уменьшить вычислительные затраты.
В работе рассмотрено применение модели машинного обучения для определения оптимальной стратегии пользователя для победы в аукционе на покупку товара/услуги с использованием задачи наилучшего выбора. Применение модели наилучшего выбора позволяет участникам аукциона определить стратегию, которая минимизирует ожидаемую стоимость товара/услуги на основе функции распределения его цен. На практике наиболее часто цены на товар, услугу или ресурс имеют распределение, близкое к нормальному или к смеси нормальных распределений. Возникают задачи определения числа компонент смеси нормальных распределений и определения ее параметров. Одним из распространенных методов для определения числа компонент смеси распределений является BIC критерий. Оценить неизвестные параметры смеси нормальных распределений при фиксированном числе компонент можно с помощью EM-алгоритма, однако временные затраты на оценку параметров данным методом возрастают как при увеличении объёма выборки, так и при увеличении числа рассматриваемых компонент смеси. Разработана классификационная модель машинного обучения на основе сверточной нейронной сети для автоматизации и ускорения процесса определения числа компонент смеси нормальных распределений и оценки ее параметров. Приведены результаты тренировки и тестирования модели машинного обучения. Проведено сравнение применения разработанной модели с другими алгоритмами, не использующими нейронные сети. Результаты показывают, что предложенная модель позволяет эффективно определить наиболее подходящее число компонент для смеси нормальных распределений и уменьшает скорость вычисления параметров распределения при применении EM-алгоритма. Модель машинного обучения может быть применена в различных областях, например, в финансовом анализе или для определения оптимальной стратегии в аукционе на аренду вычислительного ресурса.
Рассматривается использование различных типов эвристических алгоритмов на основе технологий мягких вычислений для распределения задач в группах мобильных роботов, выполняющих односложные операции в едином рабочем пространстве: генетические алгоритмы, муравьиные алгоритмы и искусственные нейронные сети. Показано, что данная задача является NP-сложной и ее решение прямым перебором для большого числа заданий невозможно. Исходная задача сведена к типовым NP-полным задачам: обобщенной задаче поиска оптимальной группы замкнутых маршрутов от одного депо и задаче коммивояжера. Представлены описание каждого из выбранных алгоритмов и сравнение их характеристик. Приводится пошаговый алгоритм работы с учетом выбранных генетических операторов и их параметров при заданном объеме популяции. Представлена общая структура разработанного алгоритма, позволяющего достаточно эффективно решить многокритериальную оптимизационную задачу с учетом временных затрат и интегрального критерия эффективности роботов, учитывающего энергетические затраты, функциональную насыщенность каждого агента группы и т.д. Показана возможность решения исходной задачи с использованием муравьиного алгоритма и обобщенного поиска оптимальной группы замкнутых маршрутов. Для многокритериальной оптимизации показана возможность линейной свертки полученного векторного критерия оптимальности за счет введения дополнительных параметров, характеризующих групповое управление: общее КПД функционирования всех роботов, затраты энергии на функционирование группы поддержки и энергия на размещение одного робота на рабочем поле. Для решения задачи распределения заданий с использованием нейронной сети Хопфилда произведено ее представление в виде графа, полученного в ходе перехода от обобщенной задачи поиска оптимальной группы замкнутых маршрутов от одного депо к задаче коммивояжера. Показателем качества выбран суммарный путь, пройденный каждым из роботов группы.
Накопление данных о процессах управления проектами и типовых решениях сделало актуальными исследования, связанные с применением методов инженерии знаний для многокритериального поиска вариантов, которые задают оптимальные настройки параметров проектной среды. Цель: разработка методики поиска и визуализации групп проектов, которые могут быть оценены на основе концепции доминирования и интерпретироваться в терминах проектных переменных и показателей эффективности. Методы: обогащение выборки с сохранением неявной связи между проектными переменными и показателями эффективности осуществляется с помощью прогнозирующей нейросетевой модели. Для обнаружения фронта Парето в многомерном критериальном пространстве используется набор генетических алгоритмов. Онтология проектов определяется после кластеризации вариантов в пространстве решений и преобразования кластерной структуры в критериальное пространство. Автоматизация поиска в многомерном пространстве зоны наибольшей кривизны фронта Парето, определяющей равновесные проектные решения, их визуализация и интерпретация осуществляются с помощью плоского дерева решений. Результаты: плоское дерево строится при любой размерности критериального пространства и имеет структуру, которая имеет топологическое соответствие с проекциями разделяемых образов кластеров из многомерного пространства на плоскость. Для различных видов преобразований и корреляций между показателями эффективности и проектными переменными показано, что участки наибольшей кривизны фронта Парето определяются либо содержимым целого кластера, либо частью вариантов, представляющих “лучший” кластер. Если на плоском дереве к правому верхнему углу примыкает неразделенный прямоугольник кластера, то его представители в критериальном пространстве хорошо отделены от остальных кластеров и при максимизации показателей эффективности наиболее приближены к идеальной точке. Все представители такого кластера являются эффективными решениями. Если кластер-победитель содержит внутри дерева решений доминируемые варианты, то “лучший” кластер представляют оставшиеся варианты, которые задают оптимальные настройки проектных переменных. Практическая значимость: предложенная методика поиска и визуализации групп проектов может найти применение при выборе условий ресурсного и организационно-экономического моделирования проектной среды, обеспечивающих оптимизацию рисков, стоимостных, функциональных и временных критериев.
Рассматривается вопрос моделирования поведенческих функций животных, в частности, моделирование и реализация условного рефлекса. Производится анализ современного состояния нейронных сетей с возможностью структурного реконфигурирования. Моделирование осуществляется посредством нейронных сетей, которые строятся на основе сегментной спайковой модели нейрона с возможностью структурной адаптации к входному паттерну импульсов. Сегментная спайковая модель нейрона способна изменять свою структуру (размер тела клетки, количество и длина дендритов, количество синапсов) в зависимости от поступающего на её входы паттерна импульсов. Приведено краткое описание сегментной спайковой модели нейрона, отмечены её основные особенности с точки зрения возможности её структурного реконфигурирования. Описывается способ структурной адаптации сегментной спайковой модели нейрона к входному паттерну импульсов. Для исследования работы предложенной модели нейрона в сети, в качестве примера обосновывается выбор условного рефлекса, как частного случая формирования ассоциативных связей. Приведено описание структурной схемы и алгоритма формирования условного рефлекса как с положительным, так и с отрицательным подкреплением. Представлено пошаговое описание экспериментов по формированию ассоциативных связей вообще и условного рефлекса (как с положительным, так и с отрицательным подкреплением), в частности. Сделан вывод о перспективности применения спайковых сегментных моделей нейронов для повышения эффективности реализации поведенческих функций в нейроморфных системах управления. Рассмотрены дальнейшие перспективные направления развития нейроморфных систем, основанных на спайковых сегментных моделях нейрона.
Современные информационные технологии с высокой эффективностью обеспечивают процессы манипулирования текстами. В первую очередь это хранение, редактирование и форматирование текстов и их составляющих. Добившись значительных успехов в разработке средств бессодержательной компьютерной обработки текстов, исследователи столкнулись с проблемами их содержательной обработки. Поэтому дальнейшие шаги в этом направлении связаны с созданием, в том числе, методов автоматизированного целенаправленного манипулирования текстами с учетом заложенного в них содержания. Проведен анализ работ, посвященных исследованию проблем формального представления текстов и их последующего использования. Несмотря на ряд успешных проектов, задачи по разрешению проблемы соотношений между содержанием текста и его смыслом остаются актуальными. По-видимому, формализация текста общего назначения при сохранении его семантики на данном этапе развития науки не осуществима. Вместе с тем существуют типы текстов, для которых формализация с сохранением существенной части их семантики представляется возможной. Одним из них является регулятивный тип текста, который по существу представляет собой словесно выраженный алгоритм последовательности целенаправленных действий. Его отличают логичность и точность (отсутствие иносказаний), связность и цельность, ясность, понятность (за счет отсутствия эмоциональной окраски и образных средств), доступность (за счет использования специфической терминологии). Иначе говоря, при разработке регулятивных текстов обычно стараются как можно понятнее отображать механизмы описываемых действий. Цель: разработка метода формализации регулятивного текста с сохранением его семантики. Методы: структурная лингвистика, представление объектов в виде онтологии, конструктивные алгоритмы. Использование данного метода демонстрируется на примере описания решения системы алгебраических уравнений. Результаты: метод построения математической модели регулятивного текста. Практическая значимость: применение разработанного метода обеспечивает возможность разработки программных комплексов для построения библиотек отдельных предметных областей, разработки средств оценки регулятивных текстов на предмет их определенности, полноты, связности и других характеристик, а также тренажеров и средств самообучения.
Рассматривается фазовое укрупнение полумарковских систем, не требующее определения стационарного распределения вложенной цепи Маркова. Под фазовым укрупнением понимается эквивалентная замена полумарковской системы с общим фазовым пространством состояний системой с дискретным пространством состояний. Нахождение стационарного распределения вложенной цепи Маркова для системы с непрерывным фазовым пространством состояний является одним из наиболее трудоемких и не всегда разрешимым этапом, так как в ряде случаев приводит к решению интегральных уравнений с ядрами, содержащими сумму и разность переменных. Для таких уравнений известно только частное решение, а общих решений на сегодняшний день не существует. Для этой цели используется лемма о виде функции распределения разности двух случайных величин, при условии, что первая величина больше вычитаемой. Показано, что вид функции распределения разности двух случайных величин при указанном условии зависит от одной константы, которая определяется численным методом решения уравнения, приведенного в лемме. На основе леммы строится теорема о разности случайной величины и непростого потока восстановления. Использование данного метода демонстрируется на примере моделирования технической системы, состоящей из двух последовательно соединенных технологических ячеек, при условии, что одновременно отказать обе ячейки не могут. Определяются функции распределения времен пребывания системы в укрупненных состояниях, а также в подмножестве работоспособных и неработоспособных состояний. Сравнение результатов моделирования рассматриваемым и классическим методами показало полное совпадение искомых величин.
В результате анализа выявлено, что социальные сети (Вконтакте, Facebook), тематические сообщества в сетях микроблогинга (Twitter), ресурсы для путешественников (TripAdvisor), транспортные порталы (Autostrada) являются источником актуальной и оперативной информации о дорожно-транспортной обстановке, качестве предоставляемых транспортных услуг и степени удовлетворенности пассажиров уровнем транспортного обслуживания. Однако существующие системы транспортного мониторинга не содержат программных инструментов, способных осуществлять сбор и анализ дорожно-транспортной информации в среде Интернет. В настоящей работе рассматривается задача построения системы автоматического извлечения и классификации дорожно-транспортной информации с транспортных интернет-порталов и апробация разработанной системы для анализа транспортных сетей Крыма и города Севастополя. Для решения этой задачи проанализированы библиотеки с открытым исходным кодом для тематического сбора и исследования данных. Разработан алгоритм для извлечения и анализа текстов. Осуществлена разработка краулера с использованием пакета Scrapy на языке Python3 и собраны отзывы пользователей с портала http://autostrada.info/ru о состоянии транспортной системы Крыма и города Севастополя. Для лемматизации текстов и векторного преобразования текстов были рассмотрены методы tf, idf, tf-idf и их реализация в библиотеке Scikit-Learn: CountVectorizer и TF-IDF Vectorizer. Для обработки текстов были рассмотрены методы Bag-of-Words и n-gram. В ходе разработки модели классификатора рассмотрены наивный байесовский алгоритм (MultinomialNB) и модель линейного классификатора с оптимизацией стохастического градиентного спуска (SGDClassifier). В качестве обучающей выборки использовался корпус объемом 225 тысяч размеченных текстов с ресурса Twitter. Проведено обучение классификатора, в ходе которого использовалась стратегия кросс-валидации и метод ShuffleSplit. Проведено тестирование и сравнение результатов тоновой классификации. По результатам валидации лучшей оказалась линейная модель со схемой n-грамм [1, 3] и векторизатором TF-IDF. В ходе апробации разработанной системы был проведен сбор и анализ отзывов, относящихся к качеству транспортных сетей республики Крым и города Севастополя. Сделаны выводы и определены перспективы дальнейшего функционального развития разрабатываемого инструментария.
Применение скоординированных групп автономных подводных роботов представляется наиболее перспективной и многообещающей технологией, обеспечивающей решение самого широкого спектра океанографических задач. Групповое выполнение комплексных широкомасштабных миссий, как правило, связано с длительным пребыванием роботов в заданной акватории, что в условиях ограниченной энергоемкости аккумуляторных батарей возможно только при наличии специализированных док-станций для ее пополнения. С целью обеспечения высокого уровня работоспособности действующей группировки возникают две параллельные задачи: эффективно распределить задания миссии между членами группы и определить порядок подзарядки роботов на длительном промежутке времени. При этом необходимо учитывать, что реальные робототехнические системы функционируют в динамической подводной среде, а значит, могут подвергаться влиянию непредвиденных событий и различного рода неполадок.
В данной статье предлагается двухуровневый подход к динамическому планированию групповой стратегии, основанный на декомпозиции миссии на последовательность рабочих периодов с обязательным сбором действующей группировки по окончанию каждого из них. Задача планировщика на верхнем уровне заключается в составлении такого расписания циклов зарядки для всех аппаратов в группе, которое обеспечивало бы своевременное пополнение батарей при недопущении одновременной зарядки большого количества роботов. На основе выбранного расписания осуществляется декомпозиция миссии таким образом, чтобы каждый сбор группы сопровождался либо выходом робота из группы для осуществления подзарядки, либо возвращением в группу уже заряженного аппарата. Такая схема позволяет отслеживать статус группы и осуществлять оперативное перепланирование при изменении ее состава. Маршрутизация группы на каждом рабочем периоде осуществляется низкоуровневым планировщиком, работающим на графе целей и учитывающим технические возможности всех аппаратов в группе, а также все действующие ограничения и требования к выполнению конкретных задач. В статье предлагается эволюционный подход к децентрализованной реализации обоих планировщиков с применением специализированных эвристик, процедур улучшения решений и оригинальных схем кодирования и оценки решений; приводятся результаты вычислительных экспериментов.
В статье рассматривается оптимизация процедуры тоновой аппроксимации полутоновых (например, в палитре серого цвета) изображений. Процедура тоновой аппроксимации подразумевает сокращение в палитре аппроксимированного изображения количества используемых тонов по сравнению с количеством тонов в палитре исходного изображения. Оптимизация этой процедуры заключается в минимизации потери качества передачи графической информации, которая оценивается суммарным или усредненным по изображению отклонением тонов координатно-идентичных пикселей аппроксимированного изображения от тонов исходного. В качестве инструмента оптимизации предлагается гибридный алгоритм, который совмещает эвристический и детерминированный алгоритмы поиска наилучшей по критерию минимизации ошибки аппроксимации структуры аппроксимирующей палитры. Эвристический алгоритм реализован на основе эволюционно-генетической парадигмы. Его задачей является поиск области тоновых структур аппроксимирующей палитры, максимально близких к оптимальной. Цель детерминированного алгоритма направленного перебора — найти ближайший к полученному предыдущим поиском результату экстремум критерия качества аппроксимации. Эвристический алгоритм, как более быстродействующий, нацелен на оперативное сокращение области поиска, а детерминированный, как более затратный, — на нахождение хотя бы локального экстремума (а, возможно, и глобального) по максимально сокращенному предыдущим алгоритмом пути. Совместная работа этих алгоритмов позволяет обеспечить процессу тоновой аппроксимации эффект оптимизации, названный в статье дуальной. Под этим термином подразумевается получение результата, при котором достигается экстремум критерия качества аппроксимации при минимизации времени его достижения. Описываемое в статье исследование посвящено повышению результативности гибридного алгоритма на эвристическом этапе, в качестве которого используется модифицированный эволюционно-генетический алгоритм. Рассматриваются перспективы разработки и оценки эффективности внедрения модели параллельного использования алгоритмов с различными параметрами настройки. Обсуждаются первичные эксперименты, а их результаты сравниваются с известным алгоритмом решения поставленной задачи.
Современные стандарты кодирования видеоданных имеют высокую эффективность кодирования, но скорость кодирования может быть улучшена для удовлетворения растущих потребностей мультимедийных приложений. В статье рассматриваются методы и алгоритмы энтропийного кодирования в стандартах кодирования видеоданных H.264/AVC и H.265/HEVC. Контекстно-зависимое адаптивное кодирование с переменной длиной кодового слова CAVLC (Context-based Adaptive Variable Length) для стандарта H.264/AVC изначально предназначалось для ко-дирования с потерями и как таковое не давало адекватной производительности для кодирования без потерь. Контекстно-зависимое адаптивное бинарное арифметиче-ское кодирование CABAC (Context-Adaptive Binary Arithmetic Coding) — это метод энтропийного кодирования, впервые введенный в H.264/AVC и используемый в стандарте H.265/HEVC. Хотя он обеспечивает высокую эффективность кодирования, зависимости данных в H.264/AVC CABAC затрудняют распараллеливание и, таким образом, ограничивают его пропускную способность. Соответственно, во время стандартизации энтропийного кодирования для HEVC были рассмотрены как эффективность кодирования, так и пропускная способность. На основе анализа их достоинств и недостатков предложен метод энтропийного кодирования с последующим применением нумерационного иерархического кодирования. Он состоит из алгоритма САВАС и алгоритма нумерационного кодирования с применением иерархического подхода. Предложенный метод протестирован в среде разработки Visual C++ на различных тестовых видеопоследовательностях. Результаты экспериментов показали большую эффективность кодирования мультимедийных данных (уменьшает в среднем до 15% объема памяти хранения по сравнению с традиционным методом CABAC), но при этом метод требует большее время кодирования (примерно в два раза). Предложенный метод можно рекомендовать для применения в телекоммуни-кационных системах для решения задач хранения, передачи и обработки мультимедийных данных, где в первую очередь требуется большая степень сжатия.
Предлагается алгебраический подход к конструированию системы множественного управления для нелинейных многомерных объектов с хаотическими режимами с целью вывода объекта в аналитически заданное устойчивое состояние. Рассмотрены непрерывные и дискретные объекты управления, представленные системами нелинейных дифференциальных или разностных уравнений, соответственно, часть описания которых не определена. Предлагаемый алгоритм управления реализован на совместном применении методов нелинейного управления на многообразиях, функций Ляпунова и алгебраическом подходе к синтезу корректных алгоритмов. Рассмотрены две прикладные задачи экономической направленности с непрерывной и дискретной моделями описания. Численное моделирование осуществлено на реальных данных малых предприятий. Результаты работы предполагается использовать в системе поддержки принятия экономических решений.
Данная статья посвящена отбору и оценке речевых признаков, используемых в задаче автоматической текстонезависимой верификации диктора. Для решения поставленной задачи была использована система верификации диктора, основанная на модели Гауссовых смесей и универсальной фоновой модели (GMM-UBM система).
Рассмотрены область применения и проблемы современных систем автоматической идентификации диктора. Произведен обзор современных методов идентификации диктора, основных речевых признаков, используемых при решении задачи идентификации диктора, а также рассмотрен процесс извлечения признаков, использованных далее. К рассмотренным признакам относятся мел-кепстральные коэффициенты (MFCC), пары линейного спектра (LSP), кепстральные коэффициенты перцептивного линейного предсказания (PLP), кратковременная энергия, формантные частоты, частота основного тона, вероятность вокализации (voicing probability), частота пересечения нуля (ZCR), джиттер и шиммер.
Произведена экспериментальная оценка GMM-UBM системы с применением различных наборов речевых признаков на речевом корпусе, включающем в себя записи 50 дикторов. Признаки отобраны с помощью генетического алгоритма и алгоритма жадного добавления-удаления.
Используя 256-компонентные Гауссовы смеси и полученный вектор из 28 признаков, была получена равная ошибка 1-го и 2-го рода (EER), составляющая 0,579 %. По сравнению со стандартным вектором, состоящим из 14 мел-кепстральных коэффициентов, ошибка EER была уменьшена на 42,1 %.
Целью работы является построение алгоритма аналитического конструирования последовательного компенсатора в задаче управления техническим объектом с запаздыванием на основе модификации типовых полиномиальных моделей. Получена аналитическая связь характеристической частоты и частоты среза передаточной функции прямой ветви желаемой типовой полиномиальной модели. На основе данной связи произведена модификация типовых полиномиальных моделей с учетом величины запаздывания технического объекта.
Управление техническим объектом с запаздыванием с помощью последовательного компенсатора обладает рядом преимуществ. К ним относятся: минимальный объем измерительной информации для его реализации, представляемый сигналом ошибки воспроизведения системой задающего воздействия, что снимает необходимость введения в состав системы динамического наблюдателя для формирования сигналов оценки компонентов вектора состояния объекта; отсутствие проблемы ненулевых начальных условий, которые могут возникнуть при кратковременных нарушениях нормального функционирования системы, порождаемых наличием в составе системы динамического наблюдателя; простота процедуры конструирования последовательного компенсатора, а также единообразие этой процедуры для технических объектов типа «одномерный вход-одномерный выход» и типа «многомерный вход-многомерный выход».
При управлении системами с переменным временем задержки традиционный предиктор Смита обладает плохой устойчивостью. Предлагается разработка усовершенствованного адаптивного ПИД-Смит предиктора, который использует ПИД-регулятор в качестве основного контроллера и, кроме того, блок оценки неизвестного времени задержки. Цель состоит в том, чтобы гарантировать стабильность работы системы и устойчивость к ошибкам моделирования.
Рассматриваются два варианта организации блока оценки: на базе нейронной сети и на базе нечеткого регулятора. В первом варианте генетический алгоритм применяется для поиска оптимальных параметров блока оценки в автономном режиме. Во втором варианте нечеткий регулятор типа Такаги — Сугено использует множество моделей с различным временем задержки. В каждый момент времени вычисляется ошибка выхода для каждой модели. Выходной сигнал блока оценки рассчитывается по правилу дефаззификации. Результаты моделирования показывают эффективность предложенного метода.
Цель работы: показать связь чисел, принадлежащих известным после-довательностям, и квазиортогональных матриц, существующих на порядках, равных этим числам, а также взаимосвязь таких матриц через алгоритмы вычисления. Методы: анализ последовательностей квазиортогональных матриц абсолютного и локального максимумов детерминанта, выделение в матрицах структурных инвариантов, сопоставление алгоритмов вычисления таких матриц. Результаты: рассмотрены известные последовательности натуральных чисел, сформулировано определение матрицы, ассоциированной с натуральным числом. Приведены последовательности чисел, для которых доказано существование ассоциированных с ними квазиортогональных матриц. Высказано предположение, что ассоциированные матрицы существуют для всех натуральных чисел. Рассмотрены свойства типов таких матриц, их взаимосвязи через алгоритмы вычисления. Приведены модифицированные алгоритмы и основные цепочки матриц Эйлера и Мерсенна, последовательности порядков которых являются системообразующими. Практическая значимость: квазиортогональные матрицы абсолютного и локального максимумов детерминанта имеют непосредственное практическое значение для задач помехоустойчивого кодирования, сжатия и маскирования видеоинформации. Их разнообразие позволяет разработчикам технических систем значительно облегчить выбор матрицы, оптимальной для конкретной задачи.
Чтобы снизить сложность задач структурного синтеза, его делят на этапы, на каждом из которых исследователем при помощи систем поддержки принятия решений производится синтез и анализ моделей систем по заданным входным требованиям и ограничениям. Структурная оптимизация в данном контексте сводится к поиску экстремума некоторой целевой функции, значением которой управляют заданные конструктивные параметры, зависящие от вида задачи.
Для демонстрации работы имитационной модели рассматривается функциональный синтез структуры информационной системы управления предприятием, при этом функциональными элементами выступают автоматизируемые бизнес-процессы, а структурными — средства автоматизации. Разработан тестовый пример, в котором в качестве функциональных элементов описаны типовые процессы бюджета, маркетинга, закупок и продаж, производства, кадров.
Использование разработанной модели функционального синтеза продемонстрировано на примере задачи выбора программных продуктов при проектировании корпоративных информационных систем. На основании ряда экспериментов определено множество вариантов решения с наибольшим значением функции приспособленности. Установлено, что на значение функции влияет количество избыточных функций, которые содержат выбранные структурные элементы.
В данной статье исследуются проблемы применимости и выбора криптографических стандартов с учетом предпочтений и требований потенциального пользователя. Профили пользователя формируются с помощью онтологических методов. На основе профилей пользователей и характеристик документов формируется набор документов, которые могут подойти конкретному пользователю, и элементы этого набора ранжируются по вероятности соответствия его требованиям. При формировании набора документов используются различные методы фильтрации: коллаборативная фильтрация, анализ и фильтрация контента, а также гибридные методы, совмещающие оба подхода. Таким образом, создается рекомендующая система выбора криптографических стандартов и алгоритмов. При наличии нескольких пользовательских критериев выбора объекта целесообразно использовать интегральный показатель соответствия объекта, который вычисляется в виде взвешенной суммы показателей.
Рассматривается задача формирования траекторий движения группы подвижных объектов, функционирующих в двумерной среде с неподвижными препятствиями. Эта задача решалась графоаналитическими методами, основанными на алгоритмах Дейкстры, Беллмана-Форда и A*. Поставлен эксперимент, включающий компьютерное моделирование, результатами которого явились данные о времени движения группы подвижных объектов по траекториям. На основании данных результатов моделирования произведено их сравнение, которое позволило сделать вывод об эффективности различных методов решения задачи, и помогло выявить наиболее оптимальный.
В статье рассмотрены модель и особенности реализации программной оболочки распараллеливания вычислений. Приведены результаты сравнительной оценки производительности решения задачи восстановления доступа к данным на различных аппаратных средствах, используя для этих целей, как последовательный алгоритм вычислений, так и реализацию на основе программной оболочки распараллеливания.
Цель данной работы – предложить алгоритм, использующий свойства семантической близости и позволяющий автоматически определить, употреблено ли слово с иронией или в прямом смысле. Сделан обзор предыдущих подходов к данной проблеме. Сформулировано определение понятию «ирония». Собраны две коллекции, одна из которых содержит высказывания со словами, употребленными с иронией, а вторая – с теми же словами, употребленными в буквальном смысле. Исследованы и проведены эксперименты над разными способами измерения семантической близости. Предложен алгоритм для обнаружения иронии, позволяющий автоматически определить, употреблено ли слово с иронией или в прямом смысле.
Результаты массового оптического распознавания архивных документов необходимо подвергать корректировке с целью сокращения количества ошибок. В работе описывается алгоритм корректировки, учитывающий особенности русского языка и позволяющий обрабатывать корпуса текстов больших объемов в полностью автоматическом режиме. Процесс корректировки разделяется на этапы анализа всего корпуса текстов, подготовки структур данных, отбора слов-кандидатов и их финального ранжирование. Использование рейтинго-ранговой модели текста для генерации корректировок позволяет обрабатывать тексты, содержащие узкоспециализированную терминологию, различных предметных областей.
Рассматриваются и анализируются некоторые из известных способов и методик разработки программного обеспечения (ПО), в частности этапа проектирования, как одного из важнейших. Описывается методика, в которой используются UML диаграммы для моделирования свойств и динамики работы системы, а также сети Петри для анализа динамических свойств спроектированных поведенческих диаграмм. Приводится усовершенствованная методика взаимного использования UML диаграмм и сетей Петри. Предлагаемая методика демонстрируется на примере системы АСУ ТП насосной станции, а именно, проектирования диаграммы прецедентов, диаграмма классов и диаграмма объектов, а также диаграмма деятельности, преобразование которой реализуется по формальным правилам. При анализе сети Петри, транслированной из диаграммы деятельности, были выявлены некорректные состояния, в которых оказывалась система при включении и выключении насосов оператором. После устранения данной ситуации, ошибок в динамике работы системы не осталось. В результате анализа получено представление о размере дерева достижимости системы, составляющее величину порядка 10 6 .
Рассматривается задача построения многоуровневого описания классов, объекты которых характеризуются свойствами своих элементов и отношениями между ними. Задачи распознавания и анализа таких объектов являются NP-трудными, но при наличии достаточно коротких и часто встречающихся подформул в описаниях классов можно построить многоуровневое описание классов, существенно понижающее значение показателя степени в оценках числа шагов алгоритмов, решающих эти задачи. До сих пор выделение таких подформул оставлялось на усмотрение разработчика системы распознавания. В работе предлагается подход к их автоматическому выделению.
Потребность в эффективных алгоритмах обработки строк возникает во многих практических задачах. Одним из наиболее универсальных подходов является применение суффиксных деревьев. Однако, данная структура имеет высокие требования к памяти, что ограничивает область её применения. В данной статье на примере задачи о максимальной симметричной подстроке рассматривается способ, позволяющий частично устранить данный недостаток. Описанный способ может быть использован и для других задач.
Фундаментальное свойство пространственно-угловой симметрии полей излучения плоского однородного слоя конечной оптической толщины используется для усовершенствования численно-аналитических методов и упрощения соответствующих алгоритмов классической теории переноса излучения. Вводится новое понятие этой теории (фотометрические инварианты), с помощью которого формулируется принцип зеркального отображения (симметрии) полей излучения природных сред. Для применения этого принципа модифицируется основная краевая задача теории переноса излучения для плоских однородных сред в терминах введенных величин. Упрощения алгоритмов численного моделирования скалярных полей излучения таких сред проведено для хорошо известных методов сферических гармоник, дискретных ординат, а также методов Гаусса-Зайделя, Кейза и Ханта-Гранта. Показано, что использование фотометрических инвариантов скалярных полей излучения существенно повышает эффективность их численного моделирования.
В статье предлагается метод ускорения алгоритмов сегментации изображения для класса алгоритмов наращивания областей в случае, когда функционал, определяющий необходимость слияния сегментов, не требует пересчёта признаков сегмента на каждой итерации.
В настоящее время в арктическом регионе отмечается резкое изменение климата. Это связано со значительными изменениями, происходящими в окружающей среде – в атмосфере, океане, ледовом покрове. Научные учреждения Росгидромета, территориальные управления и региональные центры приема и обработки данных, системы мониторинга различных видов обстановки, в том числе ледовой, регулярно осуществляют наблюдения за состоянием окружающей среды арктического региона. Полученные измерения нуждаются в эффективной обработке и анализе для изучения, контроля и прогнозирования состояний окружающей среды. В статье рассматриваются методы адаптивной обработки метеорологических и океанографических данных в рамках двух этапов – верификации и регуляризации данных. Приводится описание алгоритмов обработки для этих этапов.
В статье рассматривается смена парадигмы: от традиционных математических моделей теории управления к алгоритмической теории информатики А.Н. Колмогорова. Проводится сопоставление между идентифицируемой объектной информацией и ансамблевой (энтропийной) информацией по Шеннону. Предложенные алгоритмические модели основаны на соответствующих приближениях ЗПК, рассматриваемых как самоподобные рекурсивные структуры (фрактальный подход).
Обсуждается смысл терминов «биоинформатика», «медицинская информатика», «биомедицинская информатика» применительно к целям, задачам и методам последней. Обосновывается наиболее полное на наш взгляд определение биомедицинской информатики. Приводятся вехи истории биомедицинской информатики в России и основные научные школы по этому направлению, возглавляемые лидерами отечественной науки. Рассматриваются деятельность лаборатории биомедицинской информатики и особенности решения задач биомедицинской информатики в СПИИРАН
Статья посвящена исследованию возможностей языков семейства Prolog для их использования при решении задач распознавания изображений на экране дисплея. Отмечены трудности, возникшие при реализации подхода на языках семейства Prolog. Показано, как использование оценок числа шагов работы алгоритма поиска вывода для рассматриваемой задачи позволило преодолеть возникшие трудности. Приведены примеры применения написанных программ к выделению эталонного изображения на сложном изображении. Проанализированы особенности использования различных форматов изображения, предъявленного к распознаванию.
В статье рассматриваются ключевые элементы програмной реализации фрагмента знаний алгебраической байесовской сети на языке С++. Фрагмент знаний реализован в виде отдельного класса, обеспечивающего хранение оценок истинности и имеющего ряд методов реализующих алгоритмы обработки фрагмента знаний, таких как поддержания непротиворечивости и апостериорный вывод.
В статье предложен метод построения модального регулятора по передаточной функции замкнутой системы при наличии внешнего возмущающего и задающего воздействий. Метод отличается простотой и позволяет выразить коэффициенты передаточной функции регулятора через коэффициенты желаемого полинома замкнутой системы. На основании этой особенности приводится алгоритм оптимизации системы по этим коэффициентам по критерию максимальной робастности.
Рассматривается задача группировки векторных объектов относительно возможных центров с учетом ограничений на состав групп. Предлагается способ представления специфических векторных ограничений в виде ограничений эквивалентной задачи целочисленного программирования и полиномиальные алгоритмы для некоторых частных случаев.
Ряд задач искусственного интеллекта, включающих в себя такие задачи как распознавание образов, медицинская диагностика, анализ рынка, сведены к доказательству выполнимости формул исчисления предикатов, имеющих простую структуру. Рассмотрены некоторые алгоритмы решения этих задач и доказаны верхние оценки числа шагов этих алгоритмов.