Архив статей журнала
Рассматривается система из трех связанных в кольцо генераторов с несимметричной нелинейностью и специальной нелинейной связью. Исследуемая система моделирует электрическую цепь, в которой каждый из трех идентичных генераторов представляет собой колебательный контур с нелинейным элементом. Вольт-амперная характеристика этого элемента имеет S-образный характер. Нелинейная связь между генераторами организована так, что имеет близкий к единичному коэффициент передачи в прямом направлении и близкий к нулевому в обратном. Асимптотическими методами сначала изучается задача о решениях, ветвящихся от состояний равновесия, а затем численными методами исследуется исходная система. Изучена зависимость динамики системы от степени несимметричности кубической нелинейности, описывающей характеристику нелинейного элемента.
Выражения со смешанной булевой и целочисленной арифметикой (далее - MBA-выражения, от англ. Mixed Boolean-Arithmetic) от t целочисленных n-битных переменных часто находят применение при обфускации (запутывании) программного кода. Запутывание заключается в замене коротких выражений более длинными эквивалентными выражениями, на исследование которых, как представляется, аналитиком может быть затрачено больше времени. В работе показано, что для упрощения линейных MBA-выражений (сокращения количества слагаемых) может быть применена техника, аналогичная технике декодирования линейных кодов по информационным совокупностям. На основе этой техники в работе построены алгоритмы упрощения линейных MBA-выражений: алгоритм нахождения выражения с минимальным числом слагаемых и алгоритм сокращения числа слагаемых. На основе алгоритма сокращения числа слагаемых построен алгоритм, позволяющий оценить стойкость MBA“=выражения к упрощению. В работе экспериментально оценена зависимость среднего числа слагаемых в линейном MBA-выражении, возвращаемом алгоритмами упрощения, от разрядности n, числа итераций декодирования и мощности набора булевых функций, по которому ищется линейная комбинация с минимальным числом ненулевых коэффициентов. Результаты экспериментов для всех рассмотренных t и n показывают, что если до обфускации линейное MBA-выражение содержало r=1,2,3 слагаемых, то разработанные алгоритмы упрощения с вероятностью, близкой к единице, позволяют по обфусцированному варианту этого выражения найти эквивалентное с числом слагаемых не более r. В этом заключается главное отличие техники декодирования по информационным совокупностям от известных техник упрощения линейных MBA-выражений, в которых целью является сокращение числа слагаемых до не более чем 2t. В работе также установлено, что для случайно сгенерированных линейных MBA-выражений с ростом n среднее число слагаемых в возвращаемом выражении стремится к 2t и не отличается от среднего числа слагаемых в линейном выражении, возвращаемом известными алгоритмами упрощения. Полученные результаты, в частности, позволяют определить t и n, для которых количество слагаемых в упрощенном линейном MBA-выражении в среднем будет не менее заданного.
В работе предложен алгоритм решения задачи нахождении максимального общего подграфа. Описаны последовательный и параллельный вариант алгоритма, их программная реализация и произведено экспериментальное исследование их эффективности. Данная задача является одной из самых известных NP“=полных задач. Ее решение может потребоваться при решении многих практических задач, связанных с исследованием сложных структур. Мы решаем ее в постановке, в которой требуется найти все возможные изоморфизмы найденного общего подграфа. Ввиду чрезвычайно высокой трудоемкости задачи желание ускорить ее решение за счет распараллеливания алгоритма является вполне естественным. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Целью численного эксперимента было исследование ускорения, достигаемого за счет рекурсивно“=параллельной организации вычислений. Для эксперимента автором было разработано специальное приложение на языке C#, предназначенное для генерации различных наборов исходных данных с заданными параметрами. В работе описаны характеристики сгенерированных исходных пар графов, а также результаты, полученные в ходе эксперимента.
Среди полных систем булевых функций особый интерес представляют самодостаточные операторы. Они обладают широкой областью применимости и не ограничиваются двухместным случаем. В данной работе формулируются условия, накладываемые на коэффициенты полинома Жегалкина, необходимые и достаточные для того, чтобы полином соответствовал самодостаточному оператору. Рассмотрено полиномиальное представление булевых функций, сохраняющих константу. Показано, что свойства монотонности и линейности не требуют специального рассмотрения при описании самодостаточного оператора. Вводится понятие полинома двойственного остатка, значение которого позволяет определить самодвойственность булевой функции. Доказано, что сохраняющая 0 и 1 или не сохраняющая ни 0, ни 1 булева функция является самодвойственной тогда и только тогда, когда двойственный остаток соответствующего ей полинома Жегалкина равен 0 для любых наборов значений переменных функции. На основании этого факта получена система ведущих коэффициентов. Решение данной системы позволило сформулировать критерий самодвойственности булевой функции, представленной полиномом Жегалкина, накладывающий необходимые и достаточные условия на коэффициенты полинома. Таким образом, показано, что полиномы Жегалкина являются достаточно удобным инструментом при исследовании предполных классов булевых функций.
Статья посвящена построению корпуса предложений, размеченных по общей тональности на 4 класса (положительный, отрицательный, нейтральный, смешанный), корпуса фразеологизмов, размеченных по тональности на 3 класса (положительный, отрицательный, нейтральный), и корпуса предложений, размеченных по наличию или отсутствию иронии. Разметку проводили волонтёры в рамках проекта «Готовим тексты алгоритмам» на портале«Люди науки».На основе имеющихся знаний о предметной области для каждой из задач были составлены инструкции для разметчиков. Также была выработана методика статистической обработки результатов разметки, основанная на анализе распределений и показателей согласия оценок, выставленных разными разметчиками. Для разметки предложений по наличию иронии и фразеологизмов по тональности показатели согласия оказались достаточно высокими (доля полного совпадения 0.60-0.99), при разметке предложений по общей тональности согласие оказалось слабым (доля полного совпадения 0.40), по-видимому, из-за более высокой сложности задачи. Также было показано, что результаты работы автоматических алгоритмов анализа тональности предложений улучшаются на 12-13 % при использовании корпуса, относительно предложений которого сошлись мнения всех разметчиков (3-5 человек), по сравнению с корпусом с разметкой только одним волонтёром.
Задача распознавания именованных сущностей (named entity recognition, NER) состоит в выделении и классификации слов и словосочетаний, обозначающих именованные объекты, таких как люди, организации, географические названия, даты, события, обозначения терминов предметных областей. В поисках лучшего решения исследователи проводят широкий спектр экспериментов с разными технологиями и исходными данными. Сравнение результатов этих экспериментов показывает значительное расхождение качества NER и ставит проблему определения условий и границ применения используемых технологий, а также поиска новых путей решения. Важным звеном в ответах на эти вопросы является систематизация и анализ актуальных исследований и публикация соответствующих обзоров. В области распознавания именованных сущностей авторы аналитических статей в первую очередь рассматривают математические методы выделения и классификации и не уделяют внимание специфике самой задачи. В предлагаемом обзоре область распознавания именованных сущностей рассмотрена с точки зрения отдельных категорий задач. Авторы выделили пять категорий: классическая задача NER, подзадачи NER, NER в социальных сетях, NER в предметных областях, NER в задачах обработки естественного языка (natural language processing, NLP). Для каждой категории обсуждается качество решения, особенности методов, проблемы и ограничения. Информация об актуальных научных работах каждой категории для наглядности приводится в виде таблицы, содержащей информацию об исследованиях: ссылку на работу, язык использованного корпуса текстов и его название, базовый метод решения задачи, оценку качества решения в виде стандартной статистической характеристики F-меры, которая является средним гармоническим между точностью и полнотой решения. Обзор позволяет сделать ряд выводов. В качестве базовых технологий лидируют методы глубокого обучения. Основными проблемами являются дефицит эталонных наборов данных, высокие требования к вычислительным ресурсам, отсутствие анализа ошибок. Перспективным направлением исследований в области NER является развитие методов на основе обучения без учителя или на основе правил. Возможной базой предобработки текста для таких методов могут служить интенсивно развивающиеся модели языков в существующих инструментах NLP. Завершают статью описание и результаты экспериментов с инструментами NER для русскоязычных текстов.
Разработка программного обеспечения зачастую связана с расширением функциональности. Для повышения надежности в этом случае необходимо минимизировать изменение ранее написанного кода. Для инструментальной поддержки эволюционной разработки программ была предложена процедурно-параметрическая парадигма программирования, что позволило повысить возможности процедурного подхода. Это обеспечивает безболезненное расширение как данных, так функций, используя при этом статическую типизацию. В работе рассматривается включение процедурно-параметрического программирования в язык C. Предлагаются дополнительные синтаксические конструкции, ориентированные на поддержку предлагаемого подхода. К ним относятся: параметрические обобщения, специализации обобщений, обобщающие функции, обработчики специализаций. Описываются их семантика, возможности и особенности технической реализации. Для проверки возможностей использования данного подхода построены модели процедурно-параметрических конструкций на языке программирования C. Приведенный пример демонстрирует гибкое расширение программы и поддержку множественного полиморфизма.
Численное исследование различных процессов приводит к необходимости уточнения (расширения) границ применимости вычислительных конструкций и инструментов моделирования. В настоящей статье изучается дифференцируемость в пространстве интегрируемых по Лебегу функций и рассматривается согласованность этого понятия с основополагающими вычислительными построениями такими, как разложение Тейлора и конечные разности. Функцию f из L1[a;b] назовём (k,L)-дифференцируемой в точке x0 из (a;b), если существует алгебраический многочлен P, степени не выше k, такой, что интеграл по отрезку от x0 до x0+h для f−P есть o(hk+1). Найдены формулы для вычисления коэффициентов такого P, представляющие собой предел отношения интегральных модификаций конечных разностей Δmh(f,x) к hm,m=1,⋯,k. Получается, что если f∈Wl1[a;b], и f(l) является (k,L)-диффе\-ренци\-руемой в точке x0, то f приближается тейлоровским многочленом с точностью o((x−x0)l+k), а коэффициенты разложения могут быть найдены указанным выше способом. Для исследования функций из L1 на множестве применяется дискретная <<глобальная>> конструкция разностного выражения: на основе частного Δmh(f,⋅) и hm строится последовательность {Λmn[f]} кусочно-постоянных функций, подчинённых разбиениям полуинтервала [a;b) на n равных частей. Показано, что для (k,L)-диффе\-ренци\-руемой в точке x0 функции f последовательности {Λmn[f]},m=1,⋯,k, сходятся при n→∞ в этой точке к коэффициентам приближающего в ней функцию многочлена. С помощью {Λkn[f]} устанавливается теорема: {\it <<f из L1[a;b] принадлежит Ck[a;b]⟺ f равномерно (k,L)-диффе\-рен\-цируе\-ма на [a;b]>>.} Отдельное место занимает изучение построений, соответствующих случаю m=0. Их рассматриваем в L1[Q0], где Q0 -- куб в пространстве Rd. По заданной функции f∈L1 и разбиению τn полузамкнутого куба Q0 на nd равных полузамкнутых кубов построим кусочно-постоянную функцию Θn[f], определяемую как интегральное среднее f на каждом кубе Q∈τn. Данная вычислительная конструкция приводит к следующим теоретическим фактам: {\it \,1)\,f из L1 принадлежит Lp,1≤p<∞,⟺{Θn[f]} сходится в Lp; ограниченность {Θn[f]}⟺f∈L∞; 2)\,последовательности {Θn[⋅]} определяют на классах эквивалентности оператор-проектор Θ в пространстве L1; 3)\,для функции f∈L∞ получаем Θ[f]¯¯¯¯¯¯∈B, где B -- это пространство ограниченных функций, а Θ[f]¯¯¯¯¯¯ -- доопределённая на множестве меры ноль функция Θ[f](x), и выполняется равенство ∥∥Θ[f]¯¯¯¯¯¯∥∥B=∥f∥∞. } Таким образом, в семействе пространств Lp можно заменить L∞[Q0] на B[Q0].
В работе рассмотрена задача моделирования информационного обмена адаптивной системы управления движением группы беспилотных летательных аппаратов (БЛА). Движение группы БЛА осуществляется в соответствии с адаптивным алгоритмом оптимального управления пространственной перестройкой. Оптимальные управления строятся обеспечивающими минимум общей затрачиваемой энергии. Параметры математической модели движения группы БЛА уточняются в процессе полета в соответствии с изменяющимися внешними условиями. В соответствии с этим уточняются управляющие воздействия. Это требует значительных вычислительных ресурсов и накладывает особые требования на систему информационного обмена между БЛА и пунктом управления. Предложена схема информационного обмена между БЛА и пунктом управления, позволяющая рассчитать оптимальные параметры передающих устройств.
В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности k > 1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или (k + 1) вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом k связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра.Как и для обычного графа, для кратного графа можно ввести целочисленную функцию длины ребра и поставить задачу о кратчайшем пути между двумя вершинами. Кратный путь является объединением k обычных путей, согласованных на связанных ребрах кратных и мультиребер. В статье оптимизирован полученный ранее алгоритм поиска кратчайшего пути в произвольном кратном графе. Показано, что оптимизированный алгоритм полиномиален. Таким образом, задача о кратчайшем пути является полиномиальной для любого кратного графа.