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

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

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

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

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

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

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

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

Пусть \(\Omega = A^{N}\) - пространство правосторонних бесконечных последовательностей символов алфавита \(A = \{0,1\}\), \(N = \{1,2,\dots\}\). Пусть
$$\label{rho}
\rho(\boldsymbol{x},\boldsymbol{y}) =\sum_{k=1}^{\infty}|x_{k} - y_{k}|2^{-k}
$$

- метрика на \(\Omega = A^{N}\), и \(\mu\) - мера Бернулли на \(\Omega\) с вероятностями \(p_0,p_1>0\), \(p_0+p_1=1\). Обозначим через \(B(\boldsymbol{x},\omega)\) открытый шар радиуса \(r\) с центром в точке \(\boldsymbol{\omega}\).Основной результат работы
$$
\mu\left(B(\boldsymbol{\omega},r)\right) =r+\sum_{n=0}^{\infty}\sum_{j=0}^{2^n-1}\mu_{n,j}(\boldsymbol{\omega})\tau(2^nr-j),
$$
где \(tau(x) =2\min\{x,1-x\}\), \(0\leq x \leq 1\), \(tau(x) = 0, if x<0 or x>1\),

$$mu_{n,j}(\boldsymbol{\omega}) = \left(1-p_{\omega_{n+1}}\right)
\prod_{k=1}^n p_{\omega_k\oplus j_k},\ \ j = j_12^{n-1}+j_22^{n-2}+\dots+j_n$$.

Семейство функций \(1,x,\tau(2^nx-j)\), \(j =0,1,\dots,2^n-1\), \(n=0,1,\dots\) является системой Фабера-Шаудера в пространстве \(C([0, 1])\) непрерывных функций на \([0, 1]\).
Также получены разложения в системе Фабера-Шаудера для сингулярной функции Лебега, кривых Чезаро и кривых Коха-Пеано.