On attractors in one discrete binary dynamic system with bipartite dependency graph.pdf Система, использующая модель безопасности с полным перекрытием, должна иметь, по крайней мере, одно средство для обеспечения безопасности на каждом возможном пути проникновения в систему. Множество отношений «объект-угроза» образует двудольный граф, в котором ребро (u, v) существует тогда и только тогда, когда u является средством получения доступа к объекту v. Графовые модели, в которых отказы процессоров интерпретируются как удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг, занимают важное место в задачах, связанных с отказоустойчивостью компьютерных сетей. При изучении модельных графов можно применять идеи и методы теории конечных динамических систем. В данной работе рассматривается дискретная двоичная динамическая система с двудольным графом зависимостей. Важная проблема в теории конечных динамических систем состоит в том, чтобы связать структуру системы с её динамикой. Под конечной Динамической системой понимается пара (S, 5), где S - конечное непустое множество, элементы которого называются состояниями системы, 5 : S S - отображение множества состояний в себя, называемое эволюционной функцией системы. Каждой конечной динамической системе сопоставляется карта, представляющая собой орграф с множеством вершин S и дугами, проведёнными из каждой вершины s G S в вершину 5(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Каждый бассейн представляет собой контур с входящими в него деревьями. Контуры, в свою очередь, называются предельными циклами, или аттракторами. Основными проблемами теории конечных динамических систем являются задачи отыскания эволюционных параметров без проведения динамики [1]. К их числу относятся аттракторы, их вид, количество. Например, в работе [2] подсчитано количество аттракторов в конечных динамических системах ориентаций полных графов. В данной работе определяется вид и количество аттракторов в одной дискретной двоичной динамической системе с двудольным графом зависимостей. Рассмотрим, согласно [3], дискретную двоичную динамическую систему (Sn, f), n > 1, состояниями которой являются все возможные двоичные векторы длины n, с эволюционной функцией f = (f1, . . . , fn), где двоичные функции имеют вид - ГМ rp£ni i i 1 n где а, G {0,1} и Ej, G {0,1}. Если а, = 0, то все Ej, = 0. C f ассоциируется ориентированный граф зависимостей X с множеством вершин {а1,...,ап,е}, в котором существует дуга из а, в aj, если а, = 1 и Xj -множитель f, (то есть Ej, = 1), а также существует дуга из а, в е, если а, = 0 (то есть f, = 0). В работе рассматриваются данные динамические системы с двудольными графами зависимостей и функциями вида f = (xn, 0,..., 0,х1), при n = 2 получаем f = (xn, х1). На рис. 1 изображена карта дискретной двоичной динамической системы (S3, f) с эволюционной функцией f = (х3, 0, х1) и её двудольный граф зависимостей. В результате исследований сформулирована следующая Теорема 1. Дискретная двоичная динамическая система (Sn, f), n > 1, с эволюционной функцией f = (xn, 0,... , 0,х1) имеет три бассейна и три аттрактора видов рис. 2, и только их.

Скачать электронную версию публикации