Preview

Моделирование и анализ информационных систем

Расширенный поиск
Том 28, № 2 (2021)
Скачать выпуск PDF

Algorithms 

126-135 33
Аннотация
Современные сетевые системы (группы БПЛА, социальные сети, сетевые производственные цепочки, транспортно-логистические сети, сети связи, криптовалютные сети) отличаются многоэлементностью и динамикой связей между ее элементами. Ряд дискретных задач по построению оптимальных подструктур сетевых систем, описываемых в виде различных классов графов относятся к NP-полным задачам. При этом изменчивость и динамичность структур сетевых систем приводит к «дополнительному» усложнению поиска решения задач дискретной оптимизации. Вместе с тем для некоторых подклассов динамических графов, которыми моделируются структуры сетевых систем, можно выделить условия разрешимости ряда NP-полных задач. К такому подклассу динамических графов относятся предфрактальные графы. В статье исследованы NP-полные задачи на предфрактальных графах: гамильтонов цикл, остов с максимальным числом висячих вершин, монохроматический треугольник, клика, независимое множество. Выделены условия, при которых для некоторых задач возможно получить ответ о существовании и построить полиномиальные (при фиксировании числа вершин затравки) алгоритмы поиска решений.
136-145 72
Аннотация

Пусть $G_{k} = \langle a, b;\ a^{-1}ba = b^{k} \rangle$, где $k \ne 0$. Известно, что если $p$ - некоторое простое число, то группа $G_{k}$ аппроксимируется конечными $p$-группами тогда и только тогда, когда $p \mid k - 1$. Известно также, что если $p$ и $q$ - простые числа, не делящие $k - 1$, $p < q$ и $\pi = \{p,\,q\}$, то группа $G_{k}$ аппроксимируется конечными $\pi$-группами тогда и только тогда, когда $(k,q) = 1$, $p \mid q - 1$ и порядок числа $k$ в мультипликативной группе поля $\mathbb{Z}_{q}$ является $p$-числом. В настоящей статье исследуется вопрос о количестве двухэлементных множеств простых чисел, удовлетворяющих условиям последнего критерия. Более точно, пусть $f_{k}(x)$ - количество множеств $\{p,\,q\}$ таких, что $p < q$, $p \nmid k - 1$, $q \nmid k - 1$, $(k, q) = 1$, $p \mid q - 1$, порядок $k$ по модулю $q$ является $p$-числом и $p$, $q$ выбираются среди первых $x$ простых чисел. Установлено, что если $2 \leq |k| \leq 10000$ и $1 \leq x \leq 50000$, то почти для всех рассматриваемых $k$ функция $f_{k}(x)$ может быть достаточно точно приближена функцией $\alpha_{k}x^{0,85}$, где коэффициент $\alpha_{k}$ - свой для каждого $k$ и $\{\alpha_{k} \mid 2 \leq |k| \leq 10000\} \subseteq (0,28;\,0,31]$. Также исследована зависимость величины $f_{k}(50000)$ от $k$ и предложен эффективный алгоритм проверки двухэлементного множества простых чисел на соответствие условиям последнего критерия. Полученные результаты могут иметь приложения в теории сложности вычислений и алгебраической криптографии.

Computer System Organization 

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

Computing Methodologies and Applications 

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

Discrete mathematics in relation to computer science 

186-197 41
Аннотация

Пусть  $B$ - евклидов шар в ${\mathbb R}^n$, $C(B)$ - пространство непрерывных функций $f:B\to{\mathbb R}$ с равномерной нормой $\|f\|_{C(B)}:=\max_{x\in B}|f(x)|.$ Под $\Pi_1\left({\mathbb R}^n\right)$ понимается совокупность многочленов от $n$ переменных степени $\leq 1$, то есть линейных функций на  ${\mathbb R}^n$. Интерполяционный проектор $P:C(B)\to \Pi_1({\mathbb R}^n)$ c узлами $x^{(j)}\in B$ определяется равенствами $Pf\left(x^{(j)}\right)=f\left(x^{(j)}\right)$,  $j=1,\ldots, n+1$. Норма $P$ как оператора из $C(B)$ в~$C(B)$ вычисляется по формуле $\|P\|_B=\max_{x\in B}\sum |\lambda_j(x)|,$ где $\lambda_j$ - базисные многочлены Лагранжа невырожденного $n$-мерного симплекса с вершинами $x^{(j)}$. Пусть $P^\prime$ - проектор, узлы которого совпадают с вершинами правильного симплекса, вписанного в шар. В статье найдены точки $y\in B$, для которых $\|P^\prime\|_B=\sum |\lambda_j(y)|$. Формулируется геометрическая гипотеза, из справедливости которой следует, что $\|P^\prime\|_B$ есть минимальное значение нормы интерполяционного проектора, узлы которого принадлежат $B$.  Доказывается, что эта гипотеза справедлива по крайней мере для $n=1,2,3,4$. 

Theory of Computing 

198-214 31
Аннотация
Функционально-потоковая парадигма параллельного программирования ориентирована на разработку параллельных переносимых программ. Исходный код функционально-потоковых программ транслируется в набор графов, отражающих информационные и управляющие зависимости. Основным способом их исполнения является интерпретация, что не позволяет эффективно выполнять вычисления на реальных параллельных вычислительных системах и ведет к низкой производительности. Для непосредственного выполнения программ на существующих вычислительных системах требуется использование специфических методов оптимизации и трансформации, учитывающих особенности как языка программирования, так и архитектуры исполнителя. В настоящее время наиболее распространенной является архитектура Фон-Неймана, параллельное программирование для которой в большинстве случаев осуществляется с использованием языков, поддерживающих императивный стиль и ориентированных на статическую систему типов. Для различных архитектур параллельных вычислительных систем существуют разнообразные подходы к написанию параллельных программ. Трансформация функционально-потоковых параллельных программ в императивные позволяет сформировать общий каркас из фрагментов императивного кода, непосредственно отображающих последовательные вычисления, который в дальнейшем может быть адаптирован к конкретной параллельной архитектуре. В работе рассматривается подход к выполнению такого типа трансформации, заключающийся в выделении фрагментов функционально-потоковых параллельных программ в качестве шаблонов, заменяемых впоследствии на эквивалентные фрагменты императивных языков. Предлагаемые методы трансформации позволяют порождать программный код, к которому в дальнейшем можно применять различные оптимизирующие преобразования, включая распараллеливание с учетом целевой архитектуры.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)