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

В работе рассматривается верификация программ со взаимной рекурсией для языка функционально-потокового параллельного программирования Пифагор. В языке используется модель представления программы в виде графа потока данных (информационного графа), в котором нет дополнительных управляющих связей, а присутствуют только информационные зависимости. Это позволяет упростить процесс верификации, так как не требует анализа возникающих в традиционных архитектурах дополнительных ресурсных конфликтов. Доказательство корректности программы опирается на удаление взаимных рекурсий посредством преобразования программы. Универсальным способом удаления взаимной рекурсии произвольного количества функций является построение универсальной рекурсивной функции, которая выполняет работу всех исходных функций и принимает, кроме аргумента выполняемой функции, натуральное число, являющееся номером выполняемой функции. В ряде случаев, когда присутствует косвенная рекурсия, можно использовать более простой способ преобразования — объединение кода функций, при котором происходит объединение тел вызывающих друг друга функций. Для преобразования произвольной рекурсии в прямую предлагается построение графа всех связанных функций и последующая трансформация данного графа путём удаления функций, не связанных с рассматриваемой, объединения косвенно рекурсивных функций и построения универсальной рекурсивной функции. Доказывается, что изменение функции на языке Пифагор при объединении кода и построении универсальной рекурсивной функции не влияет на корректность исходной программы. Приводится пример доказательства частичной корректности программы на языке Пифагор, осуществляющей синтаксический разбор простого арифметического выражения. После построения графа всех связанных функций рассматриваются два способа доказательства: с использованием объединения кода функций и с построением универсальной рекурсивной функции.

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

В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности k > 1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или k + 1 вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом k связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Особое внимание уделяется классу делимых кратных графов, которые отличаются возможностью выделения k частей, согласованных на всех связанных ребрах и не содержащих общих ребер. Каждая из частей является обычным графом. Вводится понятие кратного дерева, определяюся его основные свойства. В отличие от обычных деревьев количество ребер в кратных деревьях не фиксировано. Для делимых деревьев в работе приводится и обосновывается оценка минимального и максимального количества ребер. Далее определяются понятия остовного дерева и полного остовного дерева. Для делимых графов доказывается критерий полноты остовного дерева. Также доказано, что полное остовное дерево всегда существует в делимом графе. Если кратный граф является взвешенным, то для него можно поставить задачу о минимальном остовном дереве, а также о минимальном полном остовном дереве. В работе предложен эвристический алгоритм поиска минимального полного остовного дерева в делимом графе.

Технология блокчейн основана на принципе доказательства работой «Proof-ofwork». Суть данного принципа состоит в том, что некоторое событие (например, перевод денежных средств с одного счета на другой) становится значимым только после того, как оно подтверждено определенным объемом вычислительной работы. Соответственно возникает потребность в вычислительных задачах, над которыми такую работу можно производить, причем на решение этих задач будет тратиться практически вся вычислительная мощность блокчейн-сети. На сегодня в качестве таких задач получили распространение «хэш-головоломки» – задачи поиска битовой строки с хэшем, удовлетворяющим определенным условиям. Существенным недостатком хэш-головоломок является отсутствие у них какого-либо полезного применения за пределами технологии блокчейн. В работе описываются подходы к решению задачи «Useful Proof-of-work for blockchains», а именно предлагается рассматривать в качестве вычислительных задач для доказательства работой возникающие на практике индивидуальные представители NP-полных задач, которые могут решаться, например, SAT- или LLL-решателями. Отдельной проработки требует вопрос об использовании FPT-задач. Предлагаемый подход позволяет обеспечить следующие свойства вычислительных задач для доказательства работой: полезность, управляемость сложностью задач (через изменение размерности, выбор задач определенного вида, указание точности необходимого решения), массовость. При этом допускается, что не каждая решенная задача может оказаться полезной, однако предоставляется возможность решать с помощью технологии блокчейн задачи, возникающие на практике. Кроме прочего, таким образом становится возможным сопоставить стоимость виртуальной криптовалюты через затраты электроэнергии при ее генерации с практическим результатом от решения вычислительных задач. Наиболее трудными вопросами в контексте рассматриваемого подхода являются реализация связи событий и задач, обеспечивающих эти события вычислительной работой, и реализация системы анализа сложности задач. Статью следует воспринимать как программу исследований, поскольку многие технические детали требуют отдельной проработки.

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

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

В работе выполнен обзор существующих электронных русскоязычных тезаурусов и методов их автоматического построения и применения. Авторы провели анализ основных характеристик тезаурусов, находящихся в открытом доступе, для научных исследований, оценили динамику их развития и эффективность в решении задач по обработке естественного языка. Были исследованы статистические и лингвистические методы построения тезаурусов, которые позволяют автоматизировать разработку и уменьшить затраты на труд экспертов-лингвистов. В частности, рассматривались алгоритмы выделения ключевых терминов из текстов и семантических тезаурусных связей всех типов, а также качество применения получившихся в результате их работы тезаурусов. Для наглядной иллюстрации особенностей различных методов построения тезаурусных связей был разработан комбинированный метод, генерирующий специализированный тезаурус полностью автоматически на основе корпуса текстов предметной области и нескольких существующих лингвистических ресурсов. С использованием предложенного метода были проведены эксперименты с русскоязычными корпусами текстов из двух предметных областей: статьи о мигрантах и твиты. Для анализа полученных тезаурусов использовалась комплексная оценка, разработанная авторами в предыдущем исследовании, которая позволяет определить различные аспекты тезауруса и качество методов его генерации. Проведённый анализ выявил основные достоинства и недостатки различных подходов к построению тезаурусов и выделению семантических связей различных типов, а также позволил определить потенциальные направления будущих исследований.