Discrete Mathematics in Relation to Computer Science
В статье представлена графовая модель функционирования сети с адаптивной топологией, где узлы сети представляют собой вершины графа, а обмен данными между узлами представлен в виде ребер. Динамический характер сетевого взаимодействия осложняет решение задачи мониторинга и контроля функционирования сети с адаптивной топологией, которую необходимо выполнять для обеспечения гарантированно корректного сетевого взаимодействия. Значимость решения такой задачи обосновывается созданием современных информационных и киберфизических систем, в основе которых лежат сети с адаптивной топологией. Динамический характер связей между узлами, с одной стороны, позволяет обеспечивать саморегуляцию сети, с другой стороны, существенно осложняет контроль за работой сети в связи с невозможностью выделения единого шаблона сетевого взаимодействия. На базе разработанной модели функционирования сети с адаптивной топологией предложен графовый алгоритм предсказания связей, распространенный на случай с одноранговыми сетями. В основу алгоритма положены значимые параметры узлов сети, харатеризующие как их физические характеристики (уровень сигнала, заряд батареи), так и их характеристики как объектов сетевого взаимодействия (характеристики центральности вершин графа). Корректность и адекватность разработанного алгоритма подтверждена экспериментальными результатами по моделированию одноранговой сети с адаптивной топологией и ее саморегуляции при удалении различных узлов.
Theory of Software
Настоящая работа продолжает цикл статей по разработке и верификации управляющих программ на основе LTL"=спецификации. Суть подхода заключается в описании поведения программ с помощью формул линейной темпоральной логики LTL специального вида. Полученная LTL"=спецификация может быть непосредственно верифицирована с помощью инструмента проверки модели. Далее по LTL"=спецификации однозначно строится код программы на императивном языке программирования. Перевод спецификации в программу осуществляется по шаблону. Новизна работы состоит в предложении двух LTL"=спецификаций нового вида — декларативной и императивной, а также в более строгом формальном обосновании данного подхода к разработке и верификации программ. Выполнен переход на более современный инструмент верификации конечных и бесконечных систем — nuXmv. Предлагается описывать поведение управляющих программ в декларативном стиле. Для этого предназначена декларативная LTL"=спецификация, которая задаёт размеченную систему переходов как формальную модель поведения программы. Данный способ описания поведения является достаточно выразительным — доказана теорема о Тьюринг"=полноте декларативной LTL"=спецификации. Далее для построения кода программы на императивном языке декларативная LTL"=спецификация преобразуется в эквивалентную императивную LTL"=спецификацию. Доказана теорема об эквивалентности, которая гарантирует, что обе спецификации задают одно и то же поведение. Императивная LTL"=спецификация транслируется в императивный код программы по представленному шаблону. Декларативная LTL"=спецификация, которая подвергается верификации, и построенная по ней управляющая программа гарантированно задают одно и то же поведение в виде соответствующей системы переходов. Таким образом, при верификации используется модель, адекватная реальному поведению управляющей программы.
Algorithms in Computer Science
Картографическая генерализация включает выбор отображаемых на карте объектов и явлений и их упрощение (обобщение) с сохранением основных типичных черт и характерных особенностей, а также взаимосвязей в соответствии с критериями, задаваемыми в запросе пользователем, в том числе решаемой задачей и масштабом отображаемой карты. Различные преобразования карт могут изменить отношения между объектами, тем более что общепринятой является практика упрощения каждого типа пространственных объектов независимо (сначала административные границы, потом дорожная сеть, населенные пункты, гидрографическая сеть и т. д.). Разрешение топологических конфликтов — одна из важнейших задач цифровой генерализации карт, решению которой уделяется особое внимание с начала исследований в этой области. Рассмотрение покрытий и сеточных структур позволяет свести более общую проблему коррекции топологических конфликтов к задаче разрешения топологических конфликтов внутри одной ячейки сетки. В настоящей работе предлагается новый алгоритм геометрического упрощения. Его особенностью является совместное упрощение множества пространственных объектов различного типа с сохранением их топологических отношений. Предлагаемый алгоритм имеет единственный параметр минимальный размер отображаемой на карте детали (обычно он равен одному миллиметру в целевом масштабе карты). Первым шагом алгоритма является построение специальной сеточной структуры данных. На ее основе для каждого пространственного объекта формируется последовательность ячеек, которым принадлежат точки данного объекта. Если в ячейке находятся точки только одного объекта, то его геометрическое упрощение происходит в рамках ограничивающей ячейки по алгоритму sleeve-fitting. Если в ячейке содержатся точки нескольких объектов, то геометрическое упрощение осуществляется с помощью специальной, сохраняющей топологию, процедуры.
Theory of Data
Разработка быстрых алгоритмов генерации ключей, шифрования и дешифрования не только повышает эффективность соответствующих операций. Такие быстрые алгоритмы, например, для асимметричных криптосистем на квазициклических кодах, позволяют экспериментально исследовать зависимость вероятности ошибочного расшифрования от параметров кода для малых параметров безопасности и экстраполировать эти результаты на большие значения параметров безопасности. В этой статье мы исследуем эффективные алгоритмы циклической свертки, специально разработанные, в том числе, для использования в алгоритмах кодирования и декодирования квазициклических LDPC и MDPC кодов. Соответствующие свертки работают с двоичными векторами, которые могут быть как разреженными, так и плотными. Предлагаемые алгоритмы достигают высокой скорости за счет компактного хранения разреженных векторов, использования аппаратно поддерживаемых инструкций XOR и замены операций по модулю специализированными преобразованиями цикла. Эти быстрые алгоритмы имеют потенциальное применение не только в криптографии, но и в других областях, где используются свертки.
Computing Methodologies and Applications
В данной статье проводится описание серии экспериментов в симуляционной среде Gazebo, направленных на исследование влияния внешних погодных условий на автоматическую посадку беспилотного летательного аппарата (БпЛА) на движущуюся платформу с использованием компьютерного зрения и разработанной ранее системы управления, основанной на ПИД и полиномиальных регуляторах. В рамках исследования разработаны методы моделирования внешних погодных условий, и проведены тесты посадки с имитацией таких погодных условий, как ветер, освещенность, туман и осадки, включая их комбинации. Во всех экспериментах была достигнута успешная посадка на платформу, в ходе экспериментов измерялось время посадки и ее точность. Проведенный графический и статистический анализ полученных результатов выявил влияние освещенности, осадков и ветра на время посадки БпЛА, а введение ветра в симуляцию при любых других внешних условиях привело к наиболее значительному увеличению времени посадки. При этом в ходе исследования не удалось выявить системного негативного влияния внешних условий на точность посадки. Полученные результаты представляют ценную информацию для дальнейшего совершенствования систем автономной автоматической посадки БпЛА без использования спутниковых систем навигации.
Artificial Intelligence
Данная работа посвящена решению задачи распознавания именованных сущностей для русскоязычных текстов на основе модели CRF. Рассмотрены два набора данных: документы о рефинансировании с хорошей структурой документа, слабоструктурированные тексты судебных протоколов. Было проведено тестирование модели при различных наборах текстовых признаков и параметрах CRF (алгоритмов оптимизации). В среднем по всем сущностям лучшее значение F"=меры для структурированных документов составило 0.99, а для слабоструктурированных 0.86.
Статья посвящена задаче определения тональности предложения на русском языке, понимаемой как отношение автора предложения к его теме, выраженное с помощью языковых средств. В настоящий момент большинство исследований по этой теме проводятся на текстах разговорного стиля речи, что ограничивает применимость их результатов для других стилей, в частности, публицистического. Для того, чтобы заполнить этот пробел, авторами был разработан алгоритм определения тональности, ориентированный на применение к предложениям публицистического стиля речи. Алгоритм рекурсивно применяет подходящие правила к составным частям предложения, представленным в виде дерева синтаксических единиц. Большинство правил было построено на основе знаний эксперта-филолога относительно средств выражения тональности, известных русской лингвистике, и выбора тех из них, которые достаточно формализованы для того, чтобы их можно было алгоритмизировать с использованием генерируемых в рамках алгоритма деревьев синтаксических единиц. Также применялись дерево решений и тональный словарь. В статье приведены результаты эксперимента по апробации предложенного алгоритма на корпусе предложений публицистического стиля OpenSentimentCorpus, F-мера составила 0.80, а также результаты анализа ошибок алгоритма.
Авторами предлагается подход к генерации ключевых слов для русскоязычных научных текстов с помощью модели mT5 (multilingual text-to-text transformer), дообученнной на материале текстового корпуса Keyphrases CS&Math Russian. Автоматический подбор ключевых слов является актуальной задачей обработки естественного языка, поскольку ключевые слова помогают читателям осуществлять поиск статей и облегчают систематизацию научных текстов. В данной работе задача подбора ключевых слов рассматривается как задача автоматического реферирования текстов. Дообучение mT5 осуществлялась на текстах аннотаций русскоязычных научных статей. В качестве входных и выходных данных выступали тексты аннотаций и списки ключевых слов, разделенных запятыми, соответственно. Результаты, полученные с помощью mT5, были сравнены с результатами нескольких базовых методов: TopicRank, YAKE!, RuTermExtract, и KeyBERT. Для представления результатов использовались следующие метрики: F-мера, ROUGE-1, BERTScore. Лучшие результаты на тестовой выборке были получены с помощью mT5 и RuTermExtract. Наиболее высокое значение F-меры продемонстрировала модель mT5 (11.24 %), превзойдя RuTermExtract на 0.22 %. RuTermExtract показал лучший результат по метрике ROUGE-1 (15.12 %). Лучшие результаты по BERTScore также были достигнуты этими двумя методами: mT5 — 76.89 % (BERTScore, использующая модель mBERT), RuTermExtract — 75.8 % (BERTScore на основе ruSciBERT). Также авторами была оценена возможность mT5 генерировать ключевые слова, отсутствующие в исходном тексте. К ограничениям предложенного подхода относятся необходимость формирования обучающей выборки для дообучения модели и, вероятно, ограниченная применимость дообученной модели для текстов других предметных областей. Преимущества генерации ключевых слов с помощью mT5 — отсутствие необходимости задавать фиксированные значения длины и количества ключевых слов, необходимости проводить нормализацию, что особенно важно для флективных языков, и возможность генерировать ключевые слова, в явном виде отсутствующие в тексте.
ISSN 2313-5417 (Online)