Индексы в динамической системе двоичных векторов, ассоциированных с ориентациями циклов | ПДМ. 2012. № 2(16).

Индексы в динамической системе двоичных векторов, ассоциированных с ориентациями циклов

Предлагается алгоритм для подсчёта индексов состояний конечной динамической системы двоичных векторов, ассоциированных с ориентациями циклов, в которой эволюционная функция преобразует вектор с помощью одновременного выполнения следующих действий: начальный 0 и конечная 1 заменяются на 1 и 0 соответственно, каждая диграмма 10 - на 01. Определяется максимальный из индексов системы заданной размерности.

Indices in dynamic system of binary vectors associated with cyclesorientations.pdf ВведениеГрафовые модели, в которых отказы процессоров интерпретируются как удале-ние соответствующих вершин, а отказы сетевых каналов - как удаление дуг, зани-мают важное место в задачах, связанных с отказоустойчивостью компьютерных се-тей. Здесь можно выделить следующую конструкцию, получившую самостоятельноезначение в теории графов - бесконтурный граф с заданной структурой источникови стоков [1]. В модели [1] в качестве механизма восстановления работоспособностисети предлагается так называемая SER-динамика бесконтурных графов. Это позво-ляет использовать при изучении модельных графов идеи и методы теории конечныхдинамических систем и, в частности, динамических систем двоичных векторов (см.,например, [2, 3]) - когда имеется естественная двоичная кодировка графов рассмат-риваемого класса.Под конечной динамической системой понимается пара (S, $), где S - конеч-ное непустое множество, элементы которого называются состояниями системы;S ^ S - отображение множества состояний в себя, называемое эволюционной функ-цией системы. Каждой конечной динамической системе сопоставляется карта - ори-ентированный граф с множеством вершин S и дугами, проведенными из каждой вер-шины s G S в вершину $(s). Этот граф является функциональным, то есть из каждойего вершины выходит точно одна дуга. Компоненты связности графа, задающего ди-намическую систему, называются её бассейнами. Каждый бассейн представляет собойконтур с входящими в него деревьями. Контуры называются предельными цикламиили аттракторами.Основными проблемами теории конечных динамических систем являются задачиотыскания эволюционных параметров без проведения динамики. К их числу относитсяиндекс состояния - расстояние до аттрактора того бассейна, которому принадлежитсостояние. Автором составлены программы для ЭВМ, позволяющие вычислять раз-личные параметры динамических систем двоичных векторов, ассоциированных с неко-торыми типами графов, в частности [4].В данной работе предлагается алгоритм для подсчёта индексов состояний в ди-намической системе двоичных векторов, порожденных такими графами, как циклы.Определяется также максимальный из индексов системы заданной размерности.1. Описание динамической системыооНа множестве B = (J Bn , где через Bn, n > 2, обозначается множество всех дво-n=3ичных векторов размерности n, рассмотрим динамическую систему (B,0). Пусть со-стоянием динамической системы в данный момент времени является вектор v G B.Тогда в следующий момент времени она окажется в состоянии 0(v), полученном путемодновременного применения следующих правил:I) если первой компонентой в v является 0 и последней компонентой является 1, топервой компонентой в 0(v) будет 1, а последней компонентой - 0;II) если в составе v имеются диграммы вида 10, то в 0(v) каждая из них заменяетсяна 01;III) других отличий между v и 0(v) нет.Каждое состояние размерности n при динамике переходит в состояние также раз-мерности n. Таким образом, система (B, 0) в зависимости от n разбивается на конечныеподсистемы (Bn , 0), n > 2.Теперь пусть имеется n-звенный цикл с. Выберем в нём какую-либо вершинув качестве начальной и обозначим её через с0, тогда цикл можно записать какс = с 0 с 1 . . . c n - 1 cn, где cn = с0. Придадим каждому ребру цикла произвольную ориен-тацию. Дуги, имеющие направление по часовой стрелке (от вершины с0 к вершине cn ),пометим символом 1, а дуги с противоположной ориентацией - символом 0, и после-довательно выпишем получившуюся последовательность из нулей и единиц.Таким образом, каждой ориентации цикла сопоставляется n-мерный двоичный век-тор. С другой стороны, каждый такой вектор однозначно определяет некоторую ориен-тацию цикла, так что между множеством Cn , n > 2, всевозможных ориентированныхn-звенных циклов указанного вида и множеством Bn , n > 2, устанавливается вза-имно однозначное соответствие. На языке циклов структура динамической системывводится следующим образом: если дан некоторый цикл с G Cn , то его динамическимобразом 0(c) является цикл, получаемый из с одновременным превращением всех сто-ков в источники. Это частный случай динамики бесконтурных графов, введённой в [1].Заметим, что контуры в динамической системе (Cn , 0 ) , n > 2, образуют аттракторыединичной длины. Преобразования ориентаций циклов соответствуют эволюционнымпреобразованиям соотносимых им двоичных векторов в динамической системе (Bn , 0),n > 2, а именно v#(c) = 0^с).Таким образом, динамические системы (Bn , 0 ) и (Cn , 0 ),n > 2, изоморфны. На рис. 1 и 2 изображены карты изоморфных динамических систем(B3 , 0 ) и (C3,0).Рис. 1. Карта динамической системы (B3,9)Рис. 2. Карта динамической системы (Сз,9)2. Индексы состоянийБудем считать два вектора циклически идентичными, если один получается издругого путем циклического сдвига.Т е о р е м а 1. Состояния динамической системы (Bп,в), n > 2, являющиеся цик-лически идентичными, имеют одинаковые индексы.Доказательство. Возьмём два циклически идентичных вектора и и v. На язы-ке ориентаций циклов получаем, что соответствующие им графы cu и cv являютсяизоморфными с точностью до переобозначения вершин. Так как данные изоморфныециклы на следующем шаге динамики переходят также в изоморфные циклы, то есть0(cu) = 0(cv), то они, а значит, и соответствующие им векторы имеют одинаковыйиндекс. Через pc(v) обозначим циклическую плотность вектора v, то есть количество парсовпадающих соседних компонент в нём с учётом циклического сдвига. Например,pc(11001011) = 1 + 3 = 4. Очевидно, что для состояния v системы (Bп , в) выполняет-ся 0 ^ pc(v) ^ n. Под циклическим блоком будем понимать максимальное по вклю-чению множество подряд стоящих нулей (0-блок) или единиц (1-блок) в количествебольше 1 с учётом циклического сдвига. Длина блока - число нулей (единиц) в блоке,уменьшенное на 1. Обозначим через p0, p] суммы длин с учетом циклического сдвигарассматриваемых 0-блоков и 1-блоков соответственно.Под блок-группой будем понимать последовательность компонент вектора, возмож-но при циклическом сдвиге, начинающуюся с 0-блока и заканчивающуюся 1-блоком.Под первичной блок-группой будем понимать блок-группу, в которой сначала идуттолько 0-блоки, затем только 1-блоки.Введем необходимые обозначения: i - индекс состояния; l - длина рассматривае-мой блок-группы.А л г о р и т м в ы ч и с л е н и я и н д е к с а с о с т о я н и я с и с т е м ы (B, в )Индекс i(v) состояния v системы (B, в) вычисляется исходя из его векторного пред-ставления.I. Если p° = 0 или p1 = 0, то i(v) = 0.II. Если p° = 0 и p1 = 0, то выполняем следующие действия.1. Помечаем в векторе все первичные блок-группы; их количество обозначим h.2. В каждой блок-группе подсчитываем суммы длин 0- и 1-блоков. Пусть 0 < j ^ h,тогда считаем p ° j ) , p i j и помечаем блок-группы знаками « - ( ж ) » , « = » и «+(ж)», еслив н и х p°(j) > P ^ ) ' p°(j) = p j p°(j) < p1(j) с о о т в е т с т в е н н о , г д е ж = |p°(j) - p j3. Если в векторе существуют одновременно « -» и « + » блок-группы, то идём в п. 4,иначе идём в п. 5.4. Если в векторе подряд стоят « - ( ж ) » блок-группа и « + ( у ) » блок-группа (безучёта остальных компонент и «=»-групп между ними, если они имеются), то объеди-няем их в одну блок-группу, включая возможно стоящие между ними компоненты и«=»-группы (их количество в данном случае обозначим за h=), и помечаем знаком« - ( ж - у)», « = » или « + ( у - ж)», если ж > у , ж = у, ж < у соответственно. Полагаемh := h - 1 - h= и идём в п. 3.5. Считаем ij, 0 < j ^ h, согласно следующим правилам:- в « -» блок-группе ij = tj /2 - 1, где tj -длина той части блок-группы (если еёрассматривать с конца циклически влево), в которой выполняется равенство p° = p1;- в « = » блок-группе ij = I j /2 - 1;- в « + » блок-группе ij = t j / 2 - 1, где tj -длина той части блок-группы (если еёрассматривать с начала циклически вправо), в которой выполняется равенствоp° = p1.6. Ответ: i(v) = max j.° < K h JТ е о р е м а 2. Предложенный алгоритм вычисления индекса состояния динамиче-ской системы (B, 0) корректен.Доказательство.I. У вектора p° = 0 или p1 = 0. В работе [5] показано, что состояния, для которыхpc° = 0 или pc1 = 0, принадлежат аттрактору, поэтому такие состояния имеют нулевойиндекс.II. У вектора v существуют одновременно 0- и 1-блоки. В данном случае индексвектора равен количеству шагов эволюции, в результате которых получится состояние,содержащее только 0-блоки, только 1-блоки или не содержащее ни 0-, ни 1-блоков.1. Рассмотрим ситуацию, когда в состоянии идут сначала все 0-блоки, затем все1-блоки. Заметим, что в таких состояниях существует единственная блок-группа, аименно первичная блок-группа, которая начинается с первого 0-блока и заканчиваетсяпоследним 1-блоком.а ) p° < p ^Из доказательства критерия принадлежности состояния аттрактору в работе [5]следует: в таком состоянии на каждом шаге эволюции одновременно 0-блоки начина-ют движение вправо, 1-блоки начинают двигаться влево за счёт поглощения компо-нент, стоящих между блоками, с учетом циклического сдвига;когда они оказываютсястоящими рядом, то блоки начинают уменьшаться на единицу каждый за счёт погло-щения компонент друг друга, пока один из блоков полностью не поглотится, послечего опять продолжаются сдвиги блоков навстречу друг другу, пока не поглотитсясамый последний 0-блок, а это означает, что достигнут аттрактор.Таким образом, для вычисления индекса нужно, рассматривая вектор циклическивправо от начала блок-группы, дойти до такой компоненты состояния, чтобы выпол-нялось равенство pc° = pc1 - именно этой компонентой и закончится 1-блок, которыйпоглотит последнюю оставшуюся компоненту 0-блока единичной длины. Тогда дей-ствительно i = t / 2 - 1, где t - длина такой части данной блок-группы. Чётность tпоказана в работе автора [6].б) pc° = pc1.В работе [5] показано, что такая ситуация возможна только для четного n. Из дока-зательства критерия принадлежности состояния аттрактору в [5] следует, что в такомсостоянии при эволюции 0-блоки и 1-блоки начнут движение навстречу друг другу,пока не окажутся рядом, а затем начнут поглощать друг друга с каждым следующимшагом эволюции, пока не поглотится один из блоков. После этого продолжится ана-логичное движение, пока рядом не окажутся последние оставшиеся 0-блок и 1-блок,которые начнут поглощать друг друга с каждым следующим шагом эволюции, пока отних не останется по одной компоненте, что будет означать, что достигнут аттрактор.Таким образом, индекс данного состояния действительно равен i = / / 2 - 1.в) pc° > pc1.Здесь ситуация аналогична случаю II.1 а, только тут поглотятся все 1-блоки. Поэто-му для вычисления индекса нужно, рассматривая вектор циклически влево от началаблок-группы, дойти до такой компоненты состояния, чтобы выполнялось равенствоpc° = pc1 - именно этой компонентой и закончится 0-блок, который поглотит последнююоставшуюся компоненту 1-блока единичной длины. Тогда действительно i = t / 2 - 1.2. Теперь рассмотрим ситуацию, когда в состоянии 0-блоки и 1-блоки расположеныслучайным образом.Из доказательств предыдущих пунктов можно заключить, что при эволюции та-кого состояния 0-блоки будут сдвигаться циклически вправо, при этом если они будутвстречаться с 1-блоками, то длина 0-блока будет уменьшаться с очередным шагомэволюции. То есть если есть подряд стоящие 0-блоки, то они или все поглотятся, ес-ли следующие за ними подряд стоящие 1-блоки в сумме имеют равную или большуюсумму длин; или подряд стоящие 0-блоки поглотят сами следующие за ними подрядстоящие 1-блоки и продолжат циклический сдвиг вправо, встречая очередные 1-блоки,если сумма длин этих 0-блоков больше суммы длин 1-блоков. Для 1-блоков ситуацияаналогична.В таком состоянии существует не менее двух первичных блок-групп, обозначим ихколичество за h. Причём если в первичной блок-группе сумма длин 0-блоковбольше,чем сумма длин 1-блоков, то при эволюции на очередном шаге в блок-группе останутсятолько 0-блоки, которые при последующей эволюции продолжат движение вправо.Если в первичной блок-группе суммы длин 0- и 1-блоков равны, то при эволюции наочередном шаге в блок-группе останутся только чередующиеся нули и единицы. Еслиже в первичной блок-группе сумма длин 0-блоков меньше, чем сумма длин 1-блоков,то при эволюции на очередном шаге в блок-группе останутся только 1-блоки, которыепри последующей эволюции продолжат движение влево.Пометим в состоянии все первичные блок-группы в зависимости от суммы длин0- и 1-блоков. А именно, в каждой первичной блок-группе подсчитываем p ° ( j ) , p 1 ( j ),где 0 < j ^ h, и помечаем блок-группы знаками « - (ж)», « = » и «+(ж)», если в нихp ° ( j ) > pC(j), P°(j ) = p 1 ( j ) , P°(j ) < p 1 ( j ) с о о т в е т с т в е н н о , г д е ж = |p ° ( j ) - PC(j ) 1.Так как на очередном шаге эволюции движение 0- и 1-блоков происходит одновре-менно, то если в состоянии существуют одновременно « - (ж)» и « + ( у ) » блок-группы, тов них при эволюции останутся 0-блоки и 1-блоки соответственно, которые по-прежнемубудут друг друга поглощать. Значит, игнорируя чередующиеся нули и единицы, а так-же « = » блок-группы, которые могут стоять между « - (ж)» и « + ( у ) » блок-группами,объединяем их в одну блок-группу, включая возможно стоящие между ними компо-ненты и «=»-группы (их количество в данном случае обозначим за h=), и помечаемзнаком «< - (x - y)», « = » или « + ( y - x ) » , если x > y, x = y, x < y соответственно. Приэтом количество блок-групп уменьшается, то есть h := h - 1 - h=. Если в состояниипосле этого существуют одновременно « - ( x ) » и « + ( y ) » блок-группы, то повторяемданную процедуру объединения, пока не избавимся от этой ситуации.В результате получим состояние, в котором возможна одна из следующих ситуа-ций по наличию блок-групп: только « -» блок-группы; только « + » блок-группы; толь-ко « = » блок-группы; одновременно « -» и « = » блок-группы; одновременно « = » и« + » блок-группы. При эволюции от этих блок-групп в результате останутся: только0-блоки; только 1-блоки; ни 0-, ни 1-блоков; только 0-блоки или ни 0-, ни 1-блоков;ни 0-, ни 1-блоков или только 1-блоки - это уже состояния, принадлежащие аттракто-ру. Таким образом, для вычисления индекса состояния нужно подсчитать количествошагов эволюции, за которые от исходных блок-групп останутся вышеперечисленныекомпоненты, и выбрать из этих чисел максимальное. Используя формулы, получен-ные в доказательстве (случаи II.1 a-e), считаем j, 0 < j ^ h, согласно следующимправилам:- в « -» блок-группе ij = tj /2 - 1, где tj -длина той части блок-группы (если еёрассматривать с конца циклически влево), в которой выполняется равенство pcc = pc1;- в « = » блок-группе ij = l j / 2 - 1;- в « + » блок-группе ij = t j / 2 - 1, где tj -длина той части блок-группы (если еёрассматривать с начала циклически вправо), в которой выполняется равенство pcc = pc1.Тогда i(v) = max j. c < K h jДля поиска индекса состояния по данному алгоритму вектор сразу разбиваетсяна группы, которые могут быть потом объединены, а затем подсчитываются индексыотдельно для каждой группы и выбирается максимальный из них, поэтому алгоритмимеет линейную сложность O(n), где n - количество компонент в состоянии.П р и м е р 1. Подсчитаем индекс состояния 1l c c010l c c.Считаем индекс состояния согласно п. II алгоритма.1. Помечаем в векторе все первичные блок-группы: 1i c cJ01L0i c c , h = 1.2. Получаем, что в состоянии присутствует единственная « = » блок-группа.3. В векторе не существует одновременно « -» и «+»-группы, значит, идём в п. 5.5. Подсчитываем групповой индекс: i1 = l 1 / 2 - 1 = 200/2 - 1 = 99.6. Таким образом, i(v) = 99, т. е. данное состояние придет к аттрактору за 99 шагов.С л е д с т в и е 1. Система (Bn , e ) , n > 2, имеет максимальный индекс (n - 1)/2 - 1при нечетном n и n / 2 - 1 - при четном n.Доказательство. Все формулы вычисления индекса состояния рассматривают,по сути, такую часть блок-групп, что при pcc < pcl сумма длин 1-блоков равна суммедлин всех 0-блоков этой блок-группы; при pcc > pcl сумма длин 0-блоков равна суммедлин всех 1-блоков этой блок-группы, а при pcc = pcl берётся длина этой блок-группы.Соответственно при чётном n максимальным является индекс у состояния 00(10)п - 411,для которого i(00(10)n - 411) = n / 2 - 1; при нечётном n максимальный индекс у состо-яния 00(10)n - 411x, где x - э т о 0 или 1; для него i(00(10)n - 411x) = (n - 1)/2 - 1. ЗаключениеПредложен алгоритм для подсчёта индексов состояний в динамической системедвоичных векторов, ассоциированных с ориентациями циклов, а также определено,чему равен максимальный индекс подсистемы заданной размерности.

Ключевые слова

конечная динамическая система, эволюционная функция, двоичные векторы, циклы, индекс, nite dynamic system, evolutionary function, binary vectors, index, cycles

Авторы

ФИООрганизацияДополнительноE-mail
Жаркова Анастасия ВладимировнаСаратовский государственный университет им. Н. Г. ЧернышевскогоаспиранткаVAnastasiyaV@gmail.com
Всего: 1

Ссылки

Barbosa V. C. An atlas of edge-reversal dynamics. London: Chapman&Hall/CRC, 2001. 372 p.
Салий В. Н. Об одном классе конечных динамических систем // Вестник Томского госуниверситета. Приложение. 2005. №14. С. 23-26.
Colon-Reyes O., Laubenbacher R., and Pareigis B. Boolean monomial dynamical systems // Ann. Combinator. 2004. V. 8. P. 425-439.
Власова А. В. Исследование эволюционных параметров в динамических системах двоичных векторов // Свидет. РОСПАТЕНТа №2009614409, зарегистр. 20 августа 2009.
Власова А. В. Аттракторы динамических систем, ассоциированных с циклами // Прикладная дискретная математика. 2011. №2(12). С. 90-95.
Власова А. В. Индексы в динамической системе (B, 5) двоичных векторов // Изв. Сарат. ун-та. Нов. сер. 2011. Т. 11. Сер. Математика. Механика. Информатика. Вып.3. Ч. 1. С.116-122.
 Индексы в динамической системе двоичных векторов, ассоциированных с ориентациями циклов | ПДМ. 2012. № 2(16).

Индексы в динамической системе двоичных векторов, ассоциированных с ориентациями циклов | ПДМ. 2012. № 2(16).

Полнотекстовая версия