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

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

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

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

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

Исследуются вопросы построения автоматизированной обучающей системы «Множества», которая позволит учащемуся освоить одну из важных тем дисциплины «Дискретная математика» и развить логико-математическое мышление в этом направлении. Соответствующая тема 1-й части проекта включает материал, связанный с понятием множества, операциями над множествами, алгеброй множеств, доказательствами утверждений для множеств, выводом формул для количества элементов множества. В основе системы лежит построение с целью использования для обучения редактора доказательства утверждений для множества и редактора вывода формул для количества элементов множества. Первый из них позволяет студенту разбить исходное утверждение на ряд более простых утверждений, в совокупности эквивалентных исходному утверждению, выбрать метод доказательства каждого простого утверждения и провести их пошаговое доказательство. Второй редактор позволяет, используя формулу включения и исключения и формулу количества элементов дополнения, вывести пошагово формулу для количества элементов множества через заданные количества элементов, связанных с ним множеств. Важной частью системы является контроль правильности всех действий студента, и на этой основе разработана вся система обучения. Логический контроль правильности выбранного действия в первом редакторе осуществляется созданием системой булевой функции, соответствующей этому действию, и проверкой ее на тождественную истинность. Во втором редакторе для контроля используются такие инварианты, как характеристическая строка множества и характеристическая строка количества элементов множества. Остальная часть системы связана с обучением алгебре множеств и подготовке к использованию редакторов. При этом основное внимание уделяется стратегии обучения, при которой проверка понимания усвоенного материала является довольно строгой, исключающей случайный выбор ответов. Разбиение материала на секции с контролем успешности обучения не только тестами, но и упражнениями и задачами, позволяет студенту овладеть сложным логико-математическим аппаратом доказательства утверждений для множеств и вывода формулы для количества элементов множества.

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