МОДЕЛИРОВАНИЕ И АНАЛИЗ ИНФОРМАЦИОННЫХ СИСТЕМ

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

Приводятся оценки для минимальной нормы проектора при линейной интерполяции на компакте в Rn. Пусть Π1(Rn) - пространство многочленов от n переменных степени не выше 1, Ω - компакт в Rn, K=conv(E). Будем предполагать, что vol(K)>0. Пусть точки x(j)∈Ω, 1≤j≤n+1, являются вершинами n-мерного невырожденного симплекса. Интерполяционный проектор P:C(Ω)→Π1(Rn) с узлами x(j) определяется равенствами Pf(x(j))=f(x(j)). Под ∥P∥Ω будем понимать норму P как оператора из C(Ω) в C(Ω. Через θn(Ω) обозначим минимальную норму ∥P∥Ω из всех операторов P с узлами, принадлежащими Ω. Через simp(Ω) обозначим максимальный объём симплекса с вершинами в Ω. Устанавливаются неравенства χ−1n(vol(K)simp(Ω))≤θn(Ω)≤n+1. Здесь χn - стандартизованный многочлен Лежандра степени n. Нижняя оценка доказывается с применением полученной характеризации многочленов Лежандра через объёмы выпуклых многогранников. Именно, мы показываем, что при γ≥1 объём многогранника \left{x=(x_1,...,x_n)\in{\mathbb R}^n : \sum |x_j| +\left|1- \sum x_j\right|\le\gamma\right} равен χn(γ)/n!. В случае, когда Ω - n-мерный куб или n-мерный шар, нижняя оценка даёт возможность получить неравенства вида θn(Ω)⩾cn√. Формулируются некоторые открытые вопросы.Приводятся оценки для минимальной нормы проектора при линейной интерполяции на компакте в Rn. Пусть Π1(Rn) - пространство многочленов от n переменных степени не выше 1, Ω - компакт в Rn, K=conv(E). Будем предполагать, что vol(K)>0. Пусть точки x(j)∈Ω, 1≤j≤n+1, являются вершинами n-мерного невырожденного симплекса. Интерполяционный проектор P:C(Ω)→Π1(Rn) с узлами x(j) определяется равенствами Pf(x(j))=f(x(j)). Под ∥P∥Ω будем понимать норму P как оператора из C(Ω) в C(Ω. Через θn(Ω) обозначим минимальную норму ∥P∥Ω из всех операторов P с узлами, принадлежащими Ω. Через simp(Ω) обозначим максимальный объём симплекса с вершинами в Ω. Устанавливаются неравенства χ−1n(vol(K)simp(Ω))≤θn(Ω)≤n+1. Здесь χn - стандартизованный многочлен Лежандра степени n. Нижняя оценка доказывается с применением полученной характеризации многочленов Лежандра через объёмы выпуклых многогранников. Именно, мы показываем, что при γ≥1 объём многогранника \left{x=(x_1,...,x_n)\in{\mathbb R}^n : \sum |x_j| +\left|1- \sum x_j\right|\le\gamma\right} равен χn(γ)/n!. В случае, когда Ω - n-мерный куб или n-мерный шар, нижняя оценка даёт возможность получить неравенства вида θn(Ω)⩾cn√. Формулируются некоторые открытые вопросы.

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

Статья продолжает цикл публикаций по разработке и верификации управляющих программ на основе LTL-спецификаций специального вида. Ранее для описания строго детерминированного поведения программ была предложена декларативная LTL-спецификация, проработаны способы её верификации и трансляции: для верификации используется инструмент проверки модели nuXmv, трансляция осуществляется в императивный язык программирования ST для программируемых логических контроллеров. При верификации декларативной LTL-спецификации поведения программ может возникнуть необходимость в моделировании поведения её окружения. В общем случае требуется обеспечить возможность построения замкнутых систем «программа-окружение». В настоящей работе для описания поведения окружения программ логического управления предложена LTL-спецификация ограниченно недетерминированного поведения булевой переменной. Данная спецификация позволяет задавать поведение булевых сигналов обратной связи, а также условия справедливости для исключения нереалистичных сценариев поведения. В статье предлагается подход к разработке и верификации программ логического управления, в рамках которого модель поведения окружения программы описывается в виде ограничений на поведение её входных сигналов, что позволяет избежать отдельного детального представления процессов функционирования окружения. В результате полученная модель поведения замкнутой системы «программа-окружение» даёт ряд преимуществ: упрощение процесса моделирования, сокращение пространства состояний проверяемой модели, снижение времени верификации. При невозможности сведения поведения окружения к поведению имеющихся входных сигналов данный подход предполагает применение «мнимых» датчиков - дополнительных булевых переменных, использующихся как вспомогательное средство для описания поведения входных сигналов. Цель введения мнимых датчиков состоит в компенсации недостающих датчиков для отслеживания специфического поведения отдельных элементов окружения, которое необходимо учесть при задании реалистичного поведения входов программы логического управления. Предложенный подход к разработке и верификации программ с учётом поведения окружения (объекта управления) демонстрируется на примере промышленной установки для литья пластмасс.