Конечные динамические системы

Жаркова, Анастасия Владимировна

Конечные динамические системы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Жаркова, Анастасия Владимировна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Саратов МЕСТО ЗАЩИТЫ

2012 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Конечные динамические системы»

Автореферат диссертации на тему "Конечные динамические системы"

На правах рукописи

Жаркова Анастасия Владимировна КОНЕЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ

01.01.09 - дискретная математика и математическая

кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

3 МАЙ 2012

005016119

Саратов - 2012

005016119

Работа выполнена в Саратовском государственном университете имени Н.Г. Чернышевского.

Научный руководитель

кандидат физико-математических наук, доцент, профессор Саратовского государственного университета имени Н.Г. Чернышевского

Салий Вячеслав Николаевич

Официальные оппоненты:

Бредихин Дмитрий Александрович, доктор физико-математических наук, профессор, профессор Саратовского государственного технического университета имени Гагарина Ю.А.

Богомолов Сергей Анатольевич, кандидат физико-математических наук, доцент, доцент Саратовского государственного социально-экономического университета

Ведущая организация

Национальный исследовательский Томский

государственный университет

Защита состоится «21» мая 2012 г. в 17 ч. 00 мин. на заседании диссертационного совета ДМ 212.243.15 на базе Саратовского государственного университета имени Н.Г. Чернышевского по адресу: 410012, г. Саратов, ул. Астраханская, 83, механико-математический факультет СГУ имени Н.Г. Чернышевского.

С диссертацией можно ознакомиться в Зональной научной библиотеке имени В. А. Артисевич Саратовского государственного университета имени Н.Г. Чернышевского.

Автореферат разослан « // » апреля 2012 г.

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Так, в задачах, связанных с отказоустойчивостью компьютерных сетей, заметное место занимают графовые модели, в которых отказы процессоров интерпретируются как удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг. Здесь можно выделить следующие три основные конструкции, получившие и самостоятельное значение в теории графов: минимальное расширение графа (см. [1], [3], [12]), Т-неприводимое расширение графа [4], бесконтурный связный ориентированный граф с заданной структурой источников и стоков [9]. В модели [9] в качестве механизма восстановления работоспособности сети предлагается так называемая БЕЯ-динамика бесконтурных связных ориентированных графов. Это позволяет использовать при изучении модельных графов идеи и методы теории конечных динамических систем, и в частности динамических систем двоичных векторов (см., например, [5], [И]) - когда имеется естественная двоичная кодировка графов рассматриваемого класса.

Под динамической системой понимается пара (5, где 5 - непустое множество, элементы которого называются состояниями системы, д: 5 -* 5 - отображение множества состояний в себя, называемое эволюционной функцией. Различные интерпретации этого понятия вместе с возникающими конкретными конструкциями и проблематикой составляют предмет общей теории динамических систем, с которой связаны многие теоретические и прикладные исследования как в математике, так и в других естественных науках ([2], [8]).

Заметим, что приведенному определению динамической системы удовлетворяют также такие известные объекты как моноунарная алгебра (унар) и автономный (то есть с одним входным сигналом) автомат без выхода. Они интенсивно изучались различными авторами соответственно в теории алгебраических систем и в теории автоматов. Отметим, например, работы [6], [7], [10], [13].

эволюцию состояний. Так, натуральные числа являются состояниями широко известной динамической системы «Зх + 1», с которой связаны многочисленные работы в теории чисел, теории динамических систем, эргодической теории, математической логике и теории алгоритмов (см. [15]). Натуральные числа с фиксированным числом цифр образуют систему Капрекара [14], обобщения которой [16] используются в теоретико-числовых исследованиях. В математической генетике находят приложения булевы динамические системы, состояниями которых являются двоичные векторы заданной размерности [11]. В задачах об отказоустойчивости компьютерных сетей применяется упомянутая БЕЯ-динамика, действующая на бесконтурных связных ориентированных графах [9]. Подробнее об этих динамических системах говорится в первой главе.

Динамическая система называется конечной, когда множество 5 состояний системы является конечным. Каждой конечной динамической системе сопоставляется карта, представляющая собой ориентированный граф с множеством вершин 5 и дугами, проведенными из каждой вершины 5 £5в вершину <5(5). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Каждый бассейн представляет собой контур с входящими в него деревьями. Контуры в свою очередь называются предельными циклами, или аттракторами.

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

Цель работы. Изучение конечных динамических систем двоичных векторов, ассоциированных с цепями и циклами, исследование вида и основных характеристик таких систем, отыскание различных параметров динамических систем без проведения динамики.

Методы исследования. При выполнении работы применялись различные методы исследования теории графов, теории динамических систем, теории дискретных систем, комбинаторики, теории алгоритмов.

Научная новизна и выносимые на защиту положения. Основные результаты диссертации, выносимые на защиту:

1. Доказана теорема о ветвлении в конечных динамических системах, ассоциированных с графами, показано, какие именно существуют непосредственные предшественники у данного состояния системы, описано свойство недостижимости состояния системы.

2. Введена динамическая система двоичных векторов, ассоциированных с ориентациями циклов.

3. Описаны аттракторы, их количество, размерность и вид, в динамических системах двоичных векторов, ассоциированных с цепями и циклами, а также определены свойства принадлежности состояния аттрактору в данных системах.

4. Предложены и обоснованы эффективные алгоритмы для подсчёта индексов состояний в динамических системах двоичных векторов, ассоциированных с цепями и циклами. Определены максимальные индексы в подсистемах заданной размерности указанных динамических систем.

5. Описаны недостижимые состояния динамической системы двоичных векторов, ассоциированных с ориентациями циклов. Подсчитаны количества недостижимых состояний в подсистемах заданной размерности динамических систем двоичных векторов, ассоциированных с цепями и циклами.

6. Получены различные статистические данные с помощью написанных автором программ для ЭВМ, в частности [А4].

7. Приведены карты динамических систем двоичных векторов, ассоциированных с цепями и циклами начальных размерностей.

Все вышеназванные результаты являются новыми.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные в диссертационной работе результаты могут быть использованы при построении и анализе различных дискретных систем, моделируемых графами.

Апробация работы. Результаты представляемой работы обсуждались на научных семинарах кафедры теоретических основ компьютерной безопасности и криптографии Саратовского государственного университета имени Н.Г. Чернышевского (г. Саратов, 2007, 2010-2012 года) и на объединенном семинаре по дискретной математике и математической кибернетике Саратовского государственного университета имени Н.Г. Чернышевского (г. Саратов, 2012 год). Результаты исследований также докладывались на следующих научных мероприятиях: Научные студенческие конференции Саратовского государственного университета (г. Саратов, 2005, 2006,

2008 годы); I Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых (г. Нальчик, 2008 год); Научная конференция «Компьютерные науки и информационные технологии» (г. Саратов, 2010 год); XVIII и XIX Международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов - 2011» и «Ломоносов - 2012» (г. Москва, 2011 и 2012 год соответственно); VIII Всероссийская межвузовская конференция молодых ученых (г. Санкт-Петербург, 2011 год); XVI Международная конференция «Проблемы теоретической кибернетики» (г. Нижний Новгород, 2011 год); X Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT' 11 (г. Томск, 2011 год).

Публикации. Основные результаты опубликованы в работах автора [А1-А14]. Работы автора [А10], [А12], [А13] опубликованы в изданиях, включенных в «Перечень ведущих рецензируемых научных журналов и изданий» ВАК, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёных степеней доктора и кандидата наук.

Структура и объем работы. Диссертационная работа состоит из введения, трёх глав, заключения, списка использованных источников, включающего 43 наименования, и двух приложений. Диссертация изложена на 119 листах.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Введение. Во введении обосновывается актуальность темы диссертации, формулируется цель работы, приводится перечень задач, решаемых для достижения поставленной цели, даётся характеристика методов исследования, приводится краткое содержание работы по главам, перечень новых научных результатов, содержащихся в работе и выносимых на защиту, характеристика практической ценности и полезности работы, сведения об апробации результатов работы.

Глава I. В первом параграфе вводятся основные определения теории графов, используемые в работе. Так, под ориентированным графом (или орграфом) понимается пара G = (V, а) , где V - конечное непустое множество (вершины орграфа), а а <= V х V - отношение на множестве V.

Во втором параграфе главы вводятся основные определения теории конечных динамических систем, различные способы их задания, приводятся примеры наиболее известных динамических систем и задачи, которые возникают в данной области.

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

Для динамической системы, состояниями которой являются всевозможные ориентации данного графа, а эволюционная функция представляет собой процесс одновременного превращения всех стоков в источники у данной ориентации графа (для бесконтурных связных ориентированных графов данная динамика введена в [9]), доказывается следующая теорема о ветвлении и следствия из неё, в которых описывается, какие именно непосредственные предшественники существуют у данного состояния, и определяется свойство недостижимости состояния.

Выделим заранее состояния, в которых нет стоков (например, контуры): они образуют аттракторы единичной длины и соответственно имеют по крайней мере одного непосредственного предшественника -самого себя, и, значит, их ветвление > 1.

Множество источников ориентированного графа назовем допустимым, если из него в каждый сток этого графа есть дуга.

Теорема 1.1. Ветвление данного состояния 5 равно количеству допустимых множеств источников в орграфе, представляющем состояние б.

Следствие 1.1. Для неначального состояния 5 все его непосредственные предшественники определяются всеми различными допустимыми множествами источников в орграфе, представляющем состояние 5 , следующим образом: все дуги, исходящие из всех источников данного допустимого множества, переориентируются, а все остальные дуги остаются без изменения.

Следствие 1.2. Состояние х динамической системы, ассоциированной с графом, недостижимо тогда и только тогда, когда нет ни одного допустимого множества источников в орграфе, представляющем состояние б, или, другими словами, когда существует хотя бы один сток, не соседствующий с источниками.

Глава II. Во второй главе рассматриваются конечные динамические системы двоичных векторов, ассоциированных с цепями. В первом

параграфе главы вводится их описание. Пусть В = 11^=1 Вп, где через Вп, п > О, обозначим множество всех двоичных векторов размерности п. Пусть состоянием динамической системы в данный момент времени является вектор V £ В . Тогда в следующий момент времени она окажется в состоянии 5(и) , полученном путем одновременного применения следующих правил:

I) если первой компонентой в V является 0, то первой компонентой в 8 (у) будет 1;

II) если в составе V имеются диграммы (две соседние компоненты) вида 10, то в 8(р) каждая из них заменяется на 01;

III) если последней компонентой в V является 1, то последней компонентой в 8 (у) будет 0;

IV) других отличий между V и 8 (у) нет.

Каждое состояние размерности п при динамике переходит в состояние также размерности п. Таким образом, система (В , 8) в зависимости от п разбивается на конечные подсистемы (В71, 8). Данная динамика для системы (Вп, 8), п > 0, двоичных векторов определена в

[5].

Также в [5] вводится динамическая система ( Рп , 8 ), п > 0 , состояниями которой являются ориентации цепи длины п , а эволюционная функция преобразует данную ориентацию цепи путём переориентации всех дуг, входящих в стоки. Показывается, что динамические системы (Вп, 8) и (Рп, 5), п > 0, являются изоморфными, в результате чего различные задачи можно рассматривать как на языке двоичных векторов, так и на языке ориентаций цепей. Замечается, что динамическая система (Рп, 8), п > 0, представляет собой частный случай общей конструкции, введенной в [9].

Во втором параграфе главы описываются аттракторы данной динамической системы, тем самым также определено свойство принадлежности состояния аттрактору.

Теорема 2.3. При любом п > 0 система ( Вп , 8 ) имеет единственный бассейн и единственный аттрактор, представляющий

п-1

собой двухэлементный контур, образуемый состояниями (01) 2 0 и

п-1 п п

(10) 2 1 при нечётном п и состояниями (01)2 и (10)2 при чётном п.

В третьем параграфе главы предлагается эффективный алгоритм для подсчета индекса состояния данной динамической системы, доказывается корректность этого алгоритма (теорема 2.4) и вычисляется глубина бассейна (максимальный из индексов состояний бассейна).

Следствие 2.1 (О глубине бассейна динамической системы, ассоциированной с цепью). При любом п> 0 система (Вп, S) имеет глубину бассейна, равную п — 1.

В четвертом параграфе главы описываются недостижимые состояния на языке двоичных векторов и подсчитывается их количество в подсистеме заданной размерности.

В работе [5] показывается, что состояние (вектор) v динамической системы (Вп, S), п > 0, недостижимо из других состояний тогда и только тогда, когда в составе v имеется хотя бы один из следующих фрагментов:

1) начальная диграмма 00,

2) тетраграмма 1100,

3) финальная диграмма 11.

Очевидно, что эти три условия на языке векторов выражают факт существования стока, требуемого следствием 1.2.

Теорема 2.5 (Количество недостижимых состояний в динамической системе (Вп, 5)). Количество недостижимых состояний в динамической системе (Вп, 8), ассоциированной с цепью длины п > 0, равно

КНС(П,5) = 2 • 2"-2 - 2П-4 + £1(0) - 2 • П(2) + £1(4),

где

га

ОД = £ (-1)£+1 • 2"-*-4£ • С\_х_ъ[, (2-2)

i=i

причём если коэффициенты или степени принимают отрицательные значения, то соответствующие выражения принимают значение 0.

В пятом параграфе главы приводятся различные статистические данные для динамических систем двоичных векторов, порожденных цепями.

Глава III. В этой главе вводятся и рассматриваются динамические системы двоичных векторов, порожденные такими графами, как циклы.

В первом параграфе главы вводится описание системы на языке двоичных векторов и на языке ориентаций циклов. На множестве В = Un=3 Вп> гДе через Вп , п > 2 , обозначается множество всех двоичных векторов размерности п , рассмотрим следующую динамическую систему (В, в). Пусть состоянием динамической системы в данный момент времени является вектор v £ В. Тогда в следующий момент времени она окажется в состоянии в (у) , полученном путем одновременного применения следующими правил:

I) если первой компонентой в V является 0 и последней компонентой является 1, то первой компонентой в в (у) будет 1, а последней компонентой - 0;

II) если в составе V имеются диграммы вида 10, то в в (у) каждая из них заменяется на 01;

III) других отличий между V и в (у) нет.

Каждое состояние размерности п при динамике переходит в состояние также размерности п. Таким образом, система (В, в) в зависимости от п разбивается на конечные подсистемы (Вп, в), п > 2.

Заметим, что состояния 0П и 1п динамической системы (Вп, в), п > 2, под воздействием эволюционной функции переходят сами в себя, тем самым образуя аттракторы единичной длины.

Динамическая система (Сп, в), п > 2, вводится следующим образом. Её состояниями являются всевозможные ориентации цикла длины п, а эволюционная функция преобразует данный ориентированный цикл путём переориентации всех дуг, входящих в стоки, в результате чего получается новое состояние системы. Заметим, что контуры эволюционируют в себя, образуя аттракторы единичной длины. В данном параграфе показывается, что динамические системы (Вп, в) и (Сп, в), п > 2, изоморфны.

Во втором параграфе главы описываются аттракторы в подсистемах заданной размерности данной динамической системы, в частности их вид, размерность и количество, а также определяется свойство принадлежности состояния аттрактору.

Через рс(и) обозначим циклическую плотность вектора V, то есть количество пар совпадающих соседних компонент в нем с учётом циклического сдвига. Например, рс(111111) = 6 , рс(101010) = 0 , рс(111011) = 4. Очевидно, что для состояния V системы (Вп, в), п > 2, будут выполняться неравенства 0 < рс (у) < п. Под циклическим блоком будем понимать максимальное по включению множество подряд стоящих нулей (0-блок) или единиц (1-блок) в количестве > 1 с учетом циклического сдвига. При работе с динамической системой, ассоциированной с циклом, будем под понятием «блок» подразумевать понятие «циклический блок». Длина блока - число нулей (единиц) в блоке, уменьшенное на 1. Обозначим через р1 суммы длин с учетом циклического сдвига рассматриваемых 0-блоков и 1-блоков соответственно.

Теорема 3.1. Вектор динамической системы (Вп, в), п > 2, тогда и только тогда принадлежит аттрактору, когда у него = 0 или Рс = 0. При этом длины аттракторов равны делителям числа п и если

ад = •

Pe = 0, то аттрактор представляет собой цикл, в котором следующее состояние получается из предыдущего циклическим сдвигом влево на одну компоненту, а при р* = 0 - вправо.

Согласно теореме 3.1 можно провести классификацию аттракторов данной системы в зависимости от состояний, которые их образуют. Так, будем называть аттракторы О-аттракторами, если они образуются состояниями, для которых р° Ф 0 и pl = 0, а 1-аттракторами - если они образуются состояниями, для которых р° = 0 и Рс ^ О-

Теорема 3.2. О- и 1-аттракторы динамической системы (Вп, в), п > 2, находятся во взаимно однозначном соответствии.

Следствие 3.1. Количество аттракторов в динамической системе (Вп, в), п> 2, при нечетном п будет четным, а при четном п -нечетным.

Теорема 3.3. Пусть d - делитель числа п. Количество аттракторов длины d динамической системы (Вп, 6), п> 2, равно

1, если d = 2;

• (Fib(d'~ 1) + Fib(d' + 1)), если d Ф 2, (3-2)

d'\d

где ц(п) - функция Мёбиуса, Fib(ri) обозначает п-й элемент числовой последовательности Фибоначчи.

Теорема 3.4. Количество аттракторов в динамической системе (Вп, в), п > 2, равно

d\n

где k(d) подсчитывается по формуле 3.2.

Теорема 3.5. Общее количество состояний системы (Вп, 6),п> 2, принадлежащих аттракторам, равно

^Г d • k(d),

d\n

где k(d) подсчитывается по формуле 3.2.

В третьем параграфе главы предлагается эффективный алгоритм для подсчёта индексов состояний динамической системы двоичных векторов, ассоциированных с ориентациями циклов, доказывается его корректность (теорема 3.7), а также определяется максимальный из индексов состояний подсистемы заданной размерности.

Будем считать два вектора циклически идентичными, если один будет получаться из другого путем циклического сдвига.

Теорема 3.6 (О равенстве индексов циклически идентичных векторов системы (Вп, в)). Состояния динамической системы (Вп, 9), п > 2, являющиеся циклически идентичными, имеют равные индексы.

Следствие 3.2 (О максимальном индексе состояний в системе (Вп,

в)). Система (Вп, в), п > 2, имеет максимальный индекс, равный п-1 п Л —--1 при нечетном пи- — 1 при четном п.

В четвёртом параграфе главы определяется, какие состояния данной системы являются недостижимыми, подсчитывается их количество в подсистеме заданной размерности.

Из следствия 1.2 можно выразить свойство недостижимости состояний динамической системы (В71, в), п > 2, на языке векторов. Состояние динамической системы (Вп, в), п> 2, недостижимо из других состояний тогда и только тогда, когда в его составе, возможно при циклическом сдвиге, имеется тетраграмма 1100.

Теорема 3.8 (Количество недостижимых состояний в динамической системе (Вп, 9)). Количество недостижимых состояний в динамической системе (Вп, в), ассоциированной с циклом длины п > 2, равно

КНС(п,б) = 3 • 2П-4 + П(0) - 3 • П(4), где П(х) задается формулой 2.2, причём если коэффициенты или степени принимают отрицательные значения, то соответствующие выражения принимают значение 0.

В пятом, заключительном, параграфе приводятся различные статистические данные для динамической системы двоичных векторов, ассоциированных с ориентациями циклов.

Заключение. В заключении подводятся итоги исследований и формулируются основные результаты, полученные в диссертационной работе.

Приложение 1. Здесь приводятся карты динамических систем двоичных векторов, ассоциированных с ориентациями цепей длины О <п <7.

Приложение 2. Здесь приводятся карты динамических систем двоичных векторов, ассоциированных с ориентациями циклов длины 2 < п < 8.

Автор выражает искреннюю благодарность своему научному руководителю, профессору Вячеславу Николаевичу Салию за предложенные задачи, постоянное внимание к работе и большую помощь на протяжении всего времени исследования.

список источников

1. Абросимов М.Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур: Материалы III Всеросс. конф. с межд. участием. - Томск: Изд-во Томского ун-та, 2000. - С. 59-64.

2. Анищенко B.C. Сложные колебания в простых системах: Механизмы возникновения, структура и свойства динамического хаоса в радиофизических системах. - 2-е изд., доп. - М.: Издательская группа URSS, 2009. - 320 с. - ISBN 978-5-397-00722-1.

3. Каравай М.Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // Автоматика и телемеханика. - 1996. - №6. -С. 159-173. - ISSN 0005-2310.

4. Курносова С.Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений: Сб. науч. тр. / Под ред. проф. А.А. Сытника. - Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. - С. 113-125. - ISSN 1815-8692.

5. Салий В.Н. Об одном классе конечных динамических систем // Вестник Томского гос. ун-та. Приложение: Доклады IV Сибирской научной школы-семинара с международным участием «Проблемы компьютерной безопасности и криптография» - SIBECRYPT'05 (Томск, ТГУ, 6-9 сентября 2005 г.). - №14, август 2005. - С. 23-26. - ISSN 15617793.

6. Салий В.Н. Универсальная алгебра и автоматы: учебно-методическое пособие. - Саратов: Изд-во Сарат. ун-та, 1988. - 72 с. -ISBN 5-292-00263-1.

7. Скорняков JI.A. Unars // Coll. Math. Soc. Janos Bolyai. - Vol. 29. -Universal Algebra. Esztergom, 1977. - Amsterdam, 1982. - P. 735-743.

8. Anashin V., Khrennikov A. Applied algebraic dynamics. - Walter De Gruyter. - Vol. 49, 2009. - 533 pp. - ISBN 3-11-020300-6.

9. Barbosa V.C. An atlas of edge-reversal dynamics. - London: Chapman&Hall/ CRC, 2001. - 372 pp. - ISBN 1-58488-209-3.

10. Birkhoff G., Lipson J.D. Universal algebra and automata // Proc. Symp. Pure Math. - Providence, 1974. - V. 25. - P. 41-51.

11. Colon-Reyes O., Laubenbacher R., Pareigis B. Boolean monomial dynamical systems // Ann. Comb. - 2004. - Vol. 8. - P. 425-439.

12. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. - 1976. - Vol.C.-25, №9. - P. 875-884.

13. Jonsson B. Topics in universal algebra. - Berlin, 1972.

14. Kaprekar D.R. An interesting property of the number 6174 // Scripta Math.- 1955.-Vol. 15.-P. 244-245.

15. bagarías J.C. The ultimate challenge: the 3x 4- 1 problem // Providence, R.I.: Amer. Math. Soc. Pubis. - 2011. - 348 pp.

16. Smarandache F. Generalization and alternatives of Kaprekar's routine // Proposed problems of mathematics, Vol. II. - Kishinev: State University of Moldova Press, 1997. - P. 83-84.

Публикации автора по теме диссертации

Al. Власова A.B. Об одной динамической системе / Саратов, гос. унт. - Саратов, 2007. - 17 с. - Библиогр.: 2 назв. - Рус. - Деп. в ВИНИТИ 17.12.07, № 1181-В2007.

А2. Власова A.B. Ветвления в динамической системе п -мерных двоичных векторов / Инновационные технологии XXI века в управлении, информатике и образовании: I Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых: Сборник тезисов. - Нальчик: Издательство М. и В. Котляровых, 2008. - С. 109— 112.

A3. Власова A.B. Ветвления в конечной динамической системе (Вп, в) II Научные исследования студентов Саратовского государственного университета: Материалы итог. студ. науч. конф. - Саратов: Изд-во Сарат. ун-та, 2008. - С. 57-58. - ISBN 978-5-292-03819-1.

A4. Власова A.B. Исследование эволюционных параметров в динамических системах двоичных векторов // Свидетельство о государственной регистрации программы для ЭВМ № 2009614409, выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ 20 августа 2009 г.

А5. Власова A.B. Аттракторы в динамических системах двоичных векторов / Власова A.B.; Саратов, гос. ун-т. - Саратов, 2010. - 19 е.: ил. -Библиогр .: 5 назв. - Рус. - Деп. в ВИНИТИ 23.06.2010, № 392-В2010.

А6. Власова A.B. Аттракторы в динамической системе {В , 5) двоичных векторов // Компьютерные науки и информационные технологии: Материалы науч. конф. - Саратов: Изд-во Сарат. ун-та, 2010. - С. 35-41. - ISBN 978-5-292-03935-8.

А7. Власова A.B. Аттракторы конечных динамических систем, ассоциированных с бесконтурными графами // Ломоносов - 2011: Материалы XVIII Международной научной конференции студентов, аспирантов и молодых ученых: секция «Вычислительная математика и кибернетика»; 11-15 апреля; Москва, МГУ имени М.В. Ломоносова, факультет ВМК: Сборник тезисов. - М.: Издательский отдел факультета ВМК МГУ (лицензия ИД 05899 от 24.09.2001), 2011. - С. 12-14. - ISBN 978-5-89407-450-4.

А8. Власова A.B. Аттракторы конечных динамических систем, ассоциированных с цепями и циклами // Сборник тезисов докладов конференции молодых ученых, Выпуск 1. - СПб: СПбГУ ИТМО, 2011. — С. 70-71.

А9. Власова A.B. Об эволюционных параметрах конечных динамических систем, ассоциированных с графами // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. - С. 98-102. -ISBN 978-5-91326-161-8.

А10. Власова A.B. Аттракторы динамических систем, ассоциированных с циклами // Прикладная дискретная математика. -2011. - № 2 (12). - С. 90-95. - ISSN 2071-0410.

All. Власова A.B. Об аттракторах динамических систем, ассоциированных с циклами // Прикладная дискретная математика. Приложение: Тезисы докладов X Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT' 11 (Томск, ТГУ, 5-10 сентября 2011 г.). -№ 4, сентябрь 2011. - С. 88-89. - ISSN 2071-0410.

А12. Власова A.B. Индексы в динамической системе ( В , Ö ) двоичных векторов // Изв. Сарат. ун-та. Нов. сер. 2011. Т. 11. Сер. Математика. Механика. Информатика, вып. 3, ч. 1. С. 116-122. - ISSN 1814-733Х, ISSN 1816-9791.

А13. Жаркова A.B. Недостижимые состояния в динамических системах, ассоциированных с цепями и циклами // Изв. Сарат. ун-та. Нов. сер. 2011. Т. 11. Сер. Математика. Механика. Информатика, вып. 4. -С. 116-123.-ISSN 1814-733Х, ISSN 1816-9791.

А14. Жаркова A.B. О количестве аттракторов и индексах состояний в динамической системе двоичных векторов, ассоциированных с ориентациями цикла // Ломоносов-2012: Материалы XIX Международной научной конференции студентов, аспирантов и молодых ученых: секция «Вычислительная математика и кибернетика»; 9-13 апреля; Москва, МГУ имени М.В. Ломоносова, факультет ВМК: Сборник тезисов / Сост. Месяц А.И., Шевцова И.Г. - М.: Издательский отдел факультета ВМК МГУ (лицензия ИД 05899 от 24.09.2001), 2012. -С. 95-96. - ISBN 978-5-89407-477-1.

Подписано в печать 13.04.2012. Формат 60x84 1/16. Гарнитура Times. Объем 1,0 печ. л. Тираж 100 экз. Заказ № 101-Т.

Типография СГУ г. Саратов, ул. Б. Казачья, 112А тел.: (8452) 27-33-85

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Жаркова, Анастасия Владимировна, Саратов

61 12-1/914

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО

На правах рукописи

ЖАРКОВА Анастасия Владимировна КОНЕЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ

01.01.09 - дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель кандидат физико-математических наук, профессор В.Н. Салий

Саратов - 2012

ОГЛАВЛЕНИЕ

Введение........................................................................................................................................................................3

Глава I. Задачи и проблемы, общие сведения..............................................................................17

§ 1. Необходимые понятия из теории графов................................................................17

§2. Конечные динамические системы и связанные с ними задачи............20

§3. Некоторые свойства рассматриваемых динамических систем............24

Глава II. Динамическая система, ассоциированная с цепями......................................33

§ 1. Описание динамической системы..................................................................................33

§2. Аттракторы в системе..............................................................................................................36

§3. Индексы состояний...............................................................................................................48

§4. Недостижимые состояния......................................................................................................61

§5. Статистические данные............................................................................................................66

Глава III. Динамическая система, ассоциированная с циклами..................................73

§ 1. Описание динамической системы..................................................................................73

§2. Аттракторы в системе..............................................................................................................76

§3. Индексы состояний......................................................................................................................92

§4. Недостижимые состояния......................................................................................................100

§ 5. Статистические данные............................................................................................................103

Заключение..................................................................................................................................................................113

Список использованных источников..................................................................................................115

Приложение 1. Карты динамических систем, ассоциированных с цепями... 120 Приложение 2. Карты динамических систем, ассоциированных с циклами. 124

ВВЕДЕНИЕ

В современном мире технологии стремительно развиваются с каждым днем. Сейчас трудно представить себе деятельность крупных организаций без наличия различных автоматизированных систем, поэтому отлаженная работа и надежность сетей занимают важное место для успешного развития. Всё это было бы невозможно, не имей эти структуры под собой фундамента из крепкого математического аппарата.

Так, в задачах, связанных с отказоустойчивостью компьютерных сетей, заметное место занимают графовые модели, в которых отказы процессоров интерпретируются как удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг. Здесь можно выделить следующие три основные конструкции, получившие и самостоятельное значение в теории графов: минимальное расширение графа (см. [1], [7], [22]), Т-неприводимое расширение графа [9], бесконтурный связный ориентированный граф с заданной структурой источников и стоков [17]. В модели [17] в качестве механизма восстановления работоспособности сети предлагается так называемая БЕЯ-динамика бесконтурных связных ориентированных графов. Это позволяет использовать при изучении модельных графов идеи и методы теории конечных динамических систем, и в частности динамических систем двоичных векторов (см., например, [11], [20]) - когда имеется естественная двоичная кодировка графов рассматриваемого класса.

Под динамической системой понимается пара (Я, 3), где 5 - непустое множество, элементы которого называются состояниями системы, 5 5 -> 51 -отображение множества состояний в себя, называемое эволюционной функцией. Различные интерпретации этого понятия вместе с возникающими конкретными конструкциями и проблематикой составляют предмет общей теории

динамических систем, с которой связаны многие теоретические и прикладные исследования как в математике, так и в других естественных науках ([2], [16]).

В приложениях, связанных с дискретной математикой, большой интерес представляют динамические системы, состояния которых наделены некоторой индивидуальной структурой, определяющей эволюцию состоянии. Так, натуральные числа являются состояниями широко известной динамической системы «Зх + 1», с которой связаны многочисленные работы в теории чисел, теории динамических систем, эргодической теории, математической логике и теории алгоритмов (см. [26]). Натуральные числа с фиксированным числом цифр образуют систему Капрекара [24], обобщения которой [29] используются в теоретико-числовых исследованиях. В математической генетике находят приложения булевы динамические системы, состояниями которых являются двоичные векторы заданной размерности [20]. В задачах об отказоустойчивости компьютерных сетей применяется упомянутая SER-динамика, действующая на бесконтурных связных ориентированных графах [17]. Подробнее об этих динамических системах говорится в первой главе.

Динамическая система называется конечной, когда множество S состояний системы является конечным. Каждой конечной динамической системе сопоставляется карта, представляющая собой ориентированный граф с множеством вершин S и дугами, проведенными из каждой вершины s Е S в вершину S(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Получается, что каждый бассейн

представляет собой контур с входящими в него деревьями. Контуры в свою очередь называются предельными циклами, или аттракторами.

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

Целью настоящей работы было изучение конечных динамических систем двоичных векторов, ассоциированных с цепями и циклами, исследование вида и основных характеристик таких систем, отыскание различных параметров динамических систем без проведения динамики.

Для достижения поставленных целей решались следующие задачи. Нужно было рассмотреть и изучить динамическую систему двоичных векторов, ассоциированных с цепями [11], ввести по аналогии динамическую систему двоичных векторов, ассоциированных с циклами. Построить карты для этих динамических систем для различных размерностей. Для обеих динамических систем научиться определять ветвление состояний, находить их непосредственных предшественников; охарактеризовать аттракторы, их количество, вид и размерность; научиться считать индексы состояний данных динамических систем, определять максимальный из них; описать недостижимые состояния динамической системы двоичных векторов, ассоциированных с циклами, подсчитать количество недостижимых состояний

в динамических системах двоичных векторов, ассоциированных с цепями и циклами; получить различные статистические данные для этих систем.

При решении данных задач применялись различные методы исследования теории графов ([3], [6], [15]), теории динамических систем ([2], [16], [25]), теории дискретных систем ([3], [4]), комбинаторики [14], теории алгоритмов

([5], [8]).

Приведем краткое содержание работы по главам. В работе рассматриваются динамические системы двоичных векторов, порожденных графами, а именно такими графами, как цепи и циклы. Работа состоит из введения, трёх глав, заключения, списка использованных источников, включающего 43 наименования, и двух приложений. Диссертация изложена на 119 листах.

Глава I. В первом параграфе вводятся основные определения теории графов, используемые в работе. Так, под ориентированным графом (или орграфом) понимается пара £ = (V, а), где V - конечное непустое множество (<вершины орграфа), а а £ V X V - отношение на множестве V.

В третьем параграфе главы описываются рассматриваемые автором конечные динамические системы, решаются некоторые задачи. Так, в работе

изучаются конечные динамические системы, состояниями которых являются двоичные векторы, которые естественным образом можно представить с помощью ориентаций цепей [11] и циклов. Эволюционная функция задаётся некоторым преобразованием над двоичным вектором таким образом, что при представлении данного вектора через орграф при эволюции получается новый орграф путём переориентации всех дуг, входящих в стоки (вершины с нулевыми степенями исхода).

Для динамической системы, состояниями которой являются всевозможные ориентации данного графа, а эволюционная функция представляет собой процесс одновременного превращения всех стоков в источники у данной ориентации графа (для бесконтурных связных ориентированных графов данная динамика введена в [17]), доказывается следующая теорема о ветвлении и следствия из неё, в которых описывается, какие именно непосредственные предшественники существуют у данного состояния, и определяется свойство недостижимости состояния.

Выделим заранее состояния, в которых нет стоков (например, контуры): они образуют аттракторы единичной длины и соответственно имеют по крайней мере одного непосредственного предшественника - самого себя, и, значит, их ветвление > 1.

Теорема 1.1. Ветвление данного состояния б равно количеству допустимых множеств источников в орграфе, представляющем состояние б.

Следствие 1.1. Для неначального состояния б все его непосредственные предшественники определяются всеми различными допустимыми множествами источников в орграфе, представляющем состояние б, следующим образом: все дуги, исходящие из всех источников данного допустимого множества, переориентируются, а все остальные дуги остаются без изменения.

Следствие 1.2. Состояние 5 динамической системы, ассоциированной с графом, недостижимо тогда и только тогда, когда нет ни одного допустимого множества источников в орграфе, представляющем состояние б, или, другими словами, когда существует хотя бы один сток, не соседствующий с источниками.

Глава II. Во второй главе рассматриваются конечные динамические системы двоичных векторов, ассоциированных с цепями. В первом параграфе главы вводится их описание. Пусть

где через Вп, п> 0, обозначим множество всех двоичных векторов размерности п. Пусть состоянием динамической системы в данный момент времени является вектор v ЕВ. Тогда в следующий момент времени она окажется в состоянии ö(v), полученном путем одновременного применения следующих правил:

I) если первой компонентой в v является 0, то первой компонентой в ö(v) будет 1;

II) если в составе v имеются диграммы (две соседние компоненты) вида 10, то в 6(у) каждая из них заменяется на 01;

III) если последней компонентой в v является 1, то последней компонентой в 5(v) будет 0;

IV) других отличий между v и ö(v) нет.

Каждое состояние размерности п при динамике переходит в состояние также размерности п. Таким образом, система (В, S) в зависимости от п разбивается на конечные подсистемы (Вп, 5). Данная динамика для системы (Вп, 3), п > 0, двоичных векторов определена в [11].

Также в [11] вводится динамическая система (Рп, 8), п > 0, состояниями которой являются ориентации цепи длины п, а эволюционная функция преобразует данную ориентацию цепи путём переориентации всех дуг,

ОО

71=1

входящих в стоки. Показывается, что динамические системы (Вп, 8) и (Рп, 8), п > 0, являются изоморфными, в результате чего различные задачи можно рассматривать как на языке двоичных векторов, так и на языке ориентаций цепей. Замечается, что динамическая система (Рп, 8), п > 0, представляет собой частный случай общей конструкции, введенной в [17].

Теорема 2.3. При любом п > 0 система (Вп, 8) имеет единственный бассейн и единственный аттрактор, представляющий собой двухэлементный

П-1 П-1

контур, образуемый состояниями (01) 2 0 и (10)~1 при нечётном п и

п п

состояниями (01)2 и (10)2 при чётном п.

Следствие 2.1 (О глубине бассейна динамической системы, ассоциированной с цепью). При любом п > 0 система (Вп, 8) имеет глубину бассейна, равную п — 1.

В работе [11] показывается, что состояние (вектор) V динамической системы (Вп, 8), п > 0, недостижимо из других состояний тогда и только тогда, когда в составе V имеется хотя бы один из следующих фрагментов:

1) начальная диграмма 00,

2) тетраграмма 1100,

3) финальная диграмма 11.

Очевидно, что эти три условия на языке векторов выражают факт существования стока, требуемого следствием 1.2.

Теорема 2.5 (Количество недостижимых состояний в динамической системе (Вп, Ö)). Количество недостижимых состояний в динамической системе (Вп, 8), ассоциированной с цепью длины п > 0, равно

КНС(П;5) = 2 • 2п~2 - 2п~4 + П(0) - 2 • П(2) + П(4),

где

¿=1

В первом параграфе главы вводится описание системы на языке двоичных векторов и на языке ориентаций циклов. На множестве

оо

в = \Jfín,

п=3

где через Вп, п > 2, обозначается множество всех двоичных векторов размерности п, рассмотрим следующую динамическую систему (В, в). Пусть состоянием динамической системы в данный момент времени является вектор V ЕВ. Тогда в следующий момент времени она окажется в состоянии 0(v), полученном путем одновременного применения следующими правил:

I) если первой компонентой в v является 0 и последней компонентой является 1, то первой компонентой в в (у) будет 1, а последней компонентой -0;

II) если в составе v имеются диграммы вида 10, то в 6(v) каждая из них заменяется на 01;

III) других отличий между V и в (у) нет.