On indices in dynamic system of binary vectors associated with cycles orientations.pdf Под конечной динамической системой понимается пара (S, 8), где S - конеч-ное непустое множество, элементы которого называются состояниями системы,8 : S ^ S - отображение множества состояний в себя, называемое эволюционнойфункцией системы. Каждой конечной динамической системе сопоставляется карта -ориентированный граф с множеством вершин S и дугами, проведенными из каждойвершины s Е S в вершину 8(s). Компоненты связности графа, задающего динамиче-скую систему, называются её бассейнами. Каждый бассейн представляет собой контурс входящими в него деревьями. Контуры называются предельными циклами или ат-тракторами.Основными проблемами теории конечных динамических систем являются задачиотыскания эволюционных параметров без проведения динамики. К их числу относитсяиндекс состояния - расстояние до аттрактора того бассейна, которому принадлежитсостояние. Программа [1] позволяет вычислять различные параметры динамическихсистем двоичных векторов, ассоциированных с некоторыми типами графов.В данной работе предлагается алгоритм для подсчёта индексов состояний в ди-намической системе двоичных векторов, порожденных такими графами, как циклы.Определяется также максимальный из индексов системы заданной размерности.ооНа множестве B = (J Bn, где через Bn, n > 2, обозначается множество всех двоич-n=3ных векторов длины n, рассмотрим динамическую систему (B,0). Пусть состояниемдинамической системы в данный момент времени является вектор v Е B. Тогда в сле-дующий момент времени она окажется в состоянии 0(v), полученном путем одновре-менного применения следующих правил: I) если первой компонентой в v является 0и последней компонентой - 1, то первой компонентой в 0(v) будет 1, а последней - 0;II) если в составе v имеются диграммы вида 10, то в 0(v) каждая из них заменяетсяна 01; III) других отличий между v и 0(v) нет.Каждое состояние размерности n при динамике переходит в состояние той же раз-мерности. Таким образом, система (B, 0) разбивается на конечные подсистемы (Bn, 0),n > 2.Динамическая система (Bn,0), n > 2, изоморфна динамической системе (Cn,0),которая вводится следующим образом: её состояниями являются всевозможные ори-ентации цикла длины n, а эволюционная функция у данного ориентированного циклапереориентирует все дуги, входящие в стоки (вершины с нулевой степенью исхода),а все остальные дуги оставляет без изменения. Динамическая система, состояниямикоторой являются бесконтурные ориентированные графы, с определенной таким об-разом эволюционной функцией введена в [2].Будем считать два вектора циклически идентичными, если один получается издругого циклическим сдвигом.Теорема 1. Состояния динамической системы (Bn,0), n > 2, являющиеся цик-лически идентичными, имеют одинаковые индексы.Через pc(v) обозначим циклическую плотность вектора v, то есть количество парсовпадающих соседних компонент в нем с учётом циклического сдвига. Например,pc(11001011) = 1 + 3 = 4. Очевидно, что для состояния v системы (Bn,0), n > 2, име-ет место 0 ^ pc(v) ^ n. Под циклическим блоком будем понимать максимальное повключению множество подряд стоящих нулей (0-блок) или единиц (1-блок) в количе-стве >1 с учетом циклического сдвига. Длина блока - число нулей (единиц) в блоке,уменьшенное на 1. Обозначим через p0, p1 суммы длин с учетом циклического сдвигарассматриваемых 0-блоков и 1-блоков соответственно.Под блок-группой будем понимать последовательность компонент вектора, возмож-но при циклическом сдвиге, начинающуюся с 0-блока и заканчивающуюся 1-блоком.Под первичной блок-группой будем понимать блок-группу, в которой сначала идуттолько 0-блоки, затем только 1-блоки.Алгоритм вычисления индекса состояния системы (B,0)Индекс i(v) состояния v системы (B,0) вычисляется исходя из его представленияв виде вектора.I. Если p0 = 0 или p1 = 0, то i(v) = 0.II. Если p0 = 0 и p1 = 0, то выполняем следующие действия.1. Помечаем в векторе все первичные блок-группы. Их количество обозначаемчерез h.2. В каждой блок-группе подсчитываем суммы длин 0- и 1-блоков. Пусть0 < j ^ h, тогда считаем p0j), p1(j) и помечаем блок-группы знаками « -(х)»,« = » и «+(х)», если в них p0( j ) > pj p0( j ) = pj p0( j ) < p^ соответственно, г д е x = |p0(j) - p j3. Если в векторе существуют одновременно «-» и «+» блок-группы, то идёмв п. 4, иначе идём в п. 5.4. Если в векторе подряд стоят « -(х)» блок-группа и «+(у)» блок-группа (безучёта остальных компонент и «=»-групп между ними, если они имеются), тообъединяем их в одну блок-группу, включая возможно стоящие между нимикомпоненты и «=»-группы (их количество в данном случае обозначим за h=),и помечаем знаком « -(х - у)», « = » или «+(у - х)», если х > у, х = y, x < yсоответственно. Полагаем h := h - 1 - h= и идём в п. 3.5. Считаем ij, 0 < j ^ h, согласно следующим правилам:- в « -» блок-группе ij = tj /2 - 1, где tj -длина той части данной блок-группы(если её рассматривать с конца циклически влево), в которой выполняется ра-венство p0 = p1;- в « = » блок-группе ij = / j /2 - 1, где /j -длина рассматриваемой блок-группы;- в « + » блок-группе ij = tj/2 - 1, где tj -длина той части данной блок-группы(если её рассматривать с начала циклически вправо), в которой выполняетсяравенство p0 = pi.6. i(v) = max j .Теорема 2. Предложенный алгоритм вычисления индекса состояния динамиче-ской системы (B, 0) корректен.Следствие 1. Система (Bn,0), n > 2, имеет максимальный индекс, равный(n - 1)/2 - 1 при нечетном n и n/2 - 1 при четном n.Подробное изложение представленных результатов можно найти в [3].

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