Конечные динамические системы тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Жаркова, Анастасия Владимировна

• Жаркова, Анастасия Владимировна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Жаркова, Анастасия Владимировна

ОГЛАВЛЕНИЕ

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

Введение диссертации (часть автореферата) на тему «Конечные динамические системы»

ВВЕДЕНИЕ

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

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

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

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

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

В приложениях, связанных с дискретной математикой, большой интерес представляют динамические системы, состояния которых наделены некоторой индивидуальной структурой, определяющей эволюцию состоянии. Так, натуральные числа являются состояниями широко известной динамической системы «Зх + 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.4) и вычисляется глубина бассейна (максимальный из индексов состояний бассейна).

Следствие 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

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

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

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

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

оо

в = \Jfín,

п=3

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

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

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

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

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

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

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

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

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

учетом циклического сдвига рассматриваемых 0-блоков и 1-блоков соответственно.

Теорема 3.1. Вектор динамической системы (Вп, в), п > 2, тогда и

только тогда принадлежит аттрактору, когда у него р® = 0 или р* = 0. При

этом длины аттракторов равны делителям числа п и если р° = 0, то

аттрактор представляет собой цикл, в котором следующее состояние

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

при Рс=0 — вправо.

Согласно теореме 3.1 можно провести классификацию аттракторов

данной системы в зависимости от состояний, которые их образуют. Так, будем

называть аттракторы 0-аттракторами, если они образуются состояниями, для

которых Рс Ф- 0 и Рс = 0, а 1-аттракторами — если они образуются

состояниями, для которых Рс = 0 и pi Ф 0.

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

находятся во взаимно однозначном соответствии.

Следствие 3.1. Количество аттракторов в динамической системе (Вп,

9), п > 2, при нечетном п будет четным, а при четном п - нечетным.

Теорема 3.3. Пусть d - делитель числа п. Количество аттракторов

длины d динамической системы (Вп, в), п> 2, равно

f 1, если d = 2;

I 2 ^ ^

^ = I d X М (d7) ' (Fib(d' ~ V + Fib^d' + если d ф 2' (3'2)

V d'\d

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

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

Y,

d\n

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

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

d - k(d),

d\n

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

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

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

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

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

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

п Л

нечетном пи- — 1 при четном п.

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

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

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

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

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

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

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

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

Приведем перечень новых научных результатов, содержащихся в работе и выносимых на защиту.

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 год).

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Жаркова, Анастасия Владимировна

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

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

ГЛАВА I. ЗАДАЧИ И ПРОБЛЕМЫ, ОБЩИЕ СВЕДЕНИЯ

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

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

Под ориентированным графом (или орграфом) понимается пара Сг = = {V, а), где V - конечное непустое множество (вершины орграфа), а а Е V X XV - отношение на множестве V. Пара (и, V) Е а называется дугой орграфа с началом и и концом V. Отношение а называют отношением смежности. Каждому орграфу можно сопоставить некоторое изображение — диаграмму, на которой вершины орграфа представляются точками, а дуги - непрерывными кривыми, ориентированными стрелкой от начальной вершины к конечной. На рисунке 1.1 изображены различные ориентированные графы.

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

Отношение а ^ V X V называется антирефлексивным, если никакой элемент V е V не находится сам с собой в отношении а. На графе в (а) антирефлексивность отношения а характеризуется отсутствием петель.

Отношение а Я: V XV называется симметричным, если пары (и, р) и (у, и) при и, V 6 V одновременно принадлежат или не принадлежат отношению а. В графовой интерпретации свойство симметричности означает, что всякая дуга имеет встречную дугу между теми же вершинами.

Неориентированным графом (или просто графом) называется пара С = (V, а), где а - симметричное и антирефлексивное отношение на множестве вершин V. Из каждого орграфа С = (V, а) можно получить неориентированный граф С = (V, а и а ), называемый симметризацией орграфа С. Дуги неориентированного графа называют ребрами. На рисунке 1.2 изображены различные неориентированные графы, являющиеся симметризациями соответствующих орграфов, представленных на рисунке 1.1.

Рисунок 1.2. Неориентированные графы.

Пусть G = (V, а) - некоторый орграф, v 6 V - одна из его вершин. Степенью исхода вершины v называется число дуг орграфа G, имеющих своим началом V. Степенью захода вершины v называется число дуг орграфа G, имеющих своим концом V. Орграф называется функциональным, если степень с/ i W исхода каждой его вершины равна 1, то есть если из каждой его вершины выходит точно одна дуга.

Два орграфа G1 = (Vlt аг) и G2 = (V2, а2) называются изоморфными, если можно установить взаимно однозначное соответствие q)\V1^>V2, сохраняющее отношение смежности: (и, v) Е аг <=> ((р(и), (p(v)) Е а2 - для любых u,v EV1.

Цепью называется граф G = (V, а), где V = {v±, v2,., vn], а а = = {(vi, V/)||í-y| = 1} (см. первый граф на рисунке 1.2), а циклом - граф G = = (V,a), где V = {vltv2, .,vn}, а а = {(vitVj)\\i-j\ = l} U {(vlf vn), (vn, vt)} (см. второй граф на рисунке 1.2).

Отношение называется универсальным, если оно содержит все возможные пары. Отношение а Я^У XV называется рефлексивным, если каждый элемент

V Е V находится в этом отношении сам с собой. На графе С (а) рефлексивность отношения а выражается наличием петель в каждой вершине. Отношение а V X V называется транзитивным, если для него выполняется условие: (V и,у,\м Е У)((и, у) £ а & (у, и/) е а => (и, и/) е а). Отношение а в множестве

V называется отношением эквивалентности (кратко: эквивалентностью), если оно рефлексивно, симметрично и транзитивно. Все элементы из V, эквивалентные данному элементу V, образуют множество а (у), которое называется классом эквивалентности элемента V.

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

Маршрутом в орграфе называется последовательность дуг ->(кп-1>*'п), в котором (17^,17^6« для всех 1 < I < п.

Вершина 1>0 называется начальной вершиной маршрута, а рп - конечной. Циклический маршрут в орграфе - это маршрут, в котором начальная и конечные вершины совпадают. Маршрут, в котором никакая дуга не встречается более одного раза, называется путем. Путь, каждая вершина которого принадлежит не более чем двум его дугам, по определению, является простым. Простой циклический путь называется контуром. Длиной маршрута называется количество составляющих его дуг. Орграф, не имеющий нетривиальных контуров, называется бесконтурным графом.

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

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

Под конечной динамической системой понимается пара (Б, 8), где 5 -конечное непустое множество, элементы которого называются состояниями системы, 8' 51 5 - отображение множества состояний в себя, называемое эволюционной функцией системы. т ' и ч/

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

К числу основных характеристик состояний динамических систем можно отнести: ветвление - количество непосредственных предшественников данного состояния; индекс - его расстояние до аттрактора того бассейна, которому принадлежит состояние; принадлежность состояния аттрактору.

Основными параметрами для бассейнов являются:

•S их количество, а точнее количество аттракторов;

S вид аттракторов системы;

S наибольший из индексов состояний системы;

S количество начальных состояний системы (недостижимых, то есть с нулевым ветвлением, состояний).

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

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

Так, например, в книге [17] В. Барбоса рассматривает так называемую SER динамическую систему (dynamics of scheduling by edge reversal), где состояниями системы являются бесконтурные связные ориентированные графы, для которых задано количество вершин и дуг, а эволюционная функция представляет собой процесс переориентирования всех дуг данного орграфа, входящих в стоки (вершины с нулевой степенью исхода), в результате чего получается новый бесконтурный орграф, который и является следующим состоянием системы. Если множество состояний представляет собой совокупность всевозможных двоичных векторов заданной длины п: х = = (х1,х2,хп), а эволюционная функция задается системой булевых функций: (/1;/2, -",/п), каждая от п аргументов, то, полагая 5(х) = = (ЛСЮ'/гС— >/п(*))> получим булеву динамическую систему; если все функции являются булевыми одночленами, получается булева мономиальная динамическая система (см., например, [20]). В известной проблеме Зх + 1, или проблеме Коллатца, (см. [26]) динамическая система определяется следующим образом: состояниями системы являются натуральные числа, а эволюционная функция задаётся по правилам: если число х нечетное, то следующее состояние

Зх + 1 х системы равно —-—, а если же х четное, то за ним следует -. В системе

Капрекара [24] и её различных обобщениях [29] состояниями динамической системы являются /с-значные натуральные числа и эволюционная функция определяется так: берутся перестановки цифр данного числа - в порядке убывания и возрастания, находится их абсолютная разность, которая и является следующим состоянием системы.

Важными проблемами теории конечных динамических систем являются задачи отыскания эволюционных параметров без проведения динамики.

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

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

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

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

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

Ещё одна проблема - это определение начальных состояний системы. То есть, не строя карту динамической системы, нужно уметь определять, какие же состояния данной системы являются недостижимыми и сколько таких состояний в системе.

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

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

В работе [11] В.Н. Салий вводит конечную динамическую систему двоичных векторов. Состояниями системы являются двоичные векторы заданной размерности, а эволюционная функция представляет собой некоторые преобразования с отдельными компонентами вектора, в результате чего получается новый вектор, являющийся следующим состоянием системы. В работе показано, какие состояния данной динамической системы будут являться недостижимыми и ставится задача о поиске количества недостижимых состояний. Рассматриваются аттракторы динамической системы, отмечается симметричность самой системы, ставится задача об определении удаленности данного состояния от аттрактора. Рассматриваются также различные интерпретации - в терминах подмножеств фиксированного конечного множества, на языке автономных автоматов без выхода и в качестве ориентированных графов. При последней интерпретации получается, что состояниями системы являются ориентированные п-звенные цепи, и замечается, что данная динамическая система представляет собой частный случай более общей конструкции, рассмотренной в работе [17]. Ставятся также задачи об определении степени захода данного вектора по его структуре, рассматривая систему как функциональный граф, (то есть определение ветвления состояния); будет ли предъявленное состояние циклическим (о принадлежности состояния аттрактору).

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

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

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

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

Пусть дано конкретное достижимое состояние а (С), где С ориентированный граф. Тогда каждый сток в а(£г) имеет по крайней мере одну соседнюю вершину, которая являлась стоком в С, то есть каждый сток в а(С) имеет по крайней мере одну соседнюю вершину, являющуюся источником в

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

Пример 1.1. Допустимые множества источников.

1) Орграф, представленный на рисунке 1.3, имеет единственное допустимое множество источников - {2}, так как в данном орграфе существует два стока (вершины 3 и 4) и в каждый из них входит дуга из вершины 2, которая является единственным источником в данном орграфе. I 1

Рисунок 1.3. Орграф. 3

Рисунок 1.4. Орграф.

2) Ориентированный граф на рисунке 1.4 имеет два источника (вершины 3 и 4) и единственный сток (вершина 1), в который входит также дуга из источника 4, значит, допустимыми множествами источников в этом орграфе будут множества {4} и {3,4}.

Теперь можно сформулировать теорему о количестве непосредственных предшественников состояния полученной динамической системы.

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

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

Пусть дано конкретное неначальное (достижимое) состояние д = а(д').

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

Отсюда получаем, что каждому непосредственному предшественнику достижимого состояния д соответствует некоторое допустимое множество источников в д.

2. Покажем, что каждому допустимому множеству источников состояния д соответствует некоторый непосредственный предшественник состояния д.

Пусть состояние д имеет некоторое множество источников, в котором в каждый сток состояния д имеется дуга.

Если все источники из этого множества обратить в стоки, то получаем некоторое состояние д'. Если в д' все полученные стоки превратить в источники, то получим опять состояние д. Но последнее преобразование как раз и описывается в заданной динамике, то есть д' является предшественником а состояния д\ д' д.

Таким образом, каждому допустимому множеству источников в д соответствует некоторый непосредственный предшественник состояния д.

3. Покажем взаимную однозначность соответствия между непосредственными предшественниками данного состояния и его допустимыми множествами источников. а) Допустим, что у нас имеется два допустимых множества источников неначального состояния д, которые определяют один и тот же предшественник для д. Надо показать, что эти допустимые множества в таком случае совпадают.

Предположим, что они различны. Но если превратить источники этих допустимых множеств в стоки, то получим различные состояния системы в силу пункта 2 в доказательстве. Значит, два различных допустимых множества источников данного состояния не могут определять один и тот же его предшественник. б) Допустим, что у нас имеется два непосредственных предшественника достижимого состояния д, которые определяются одним и тем же допустимым множеством источников в д. Надо показать, что эти предшественники в таком случае совпадают.

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

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

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

Пример 1.2. Поиск ветвления и предшественников данного состояния. Найдём ветвление орграфа, представленного на рисунке 1.5, и всех его непосредственных предшественников в рассматриваемой динамической системе. 1 4

Рисунок 1.5. Орграф.

Источниками представленного орграфа являются вершины 3, 4, 6. Сток в данном орграфе всего один - вершина 1.

Составим все допустимые множества источников в данном орграфе. Так как со стоком соседствует единственный источник (вершина 6), то допустимые множества источников будут содержать в себе различные сочетания вершин, но с обязательным присутствием вершины 6.

Получаем следующую таблицу 1.1, в которой представлены допустимые множества источников и соответствующие им орграфы-предшественники данного состояния в рассматриваемой динамической системе.

ЗАКЛЮЧЕНИЕ

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

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

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

1) Приведены карты систем для различных размерностей.

2) Доказано, что система (Вп, 8), п > 0, имеет единственный бассейн, в котором единственный аттрактор образуется двумя состояниями из чередующихся нулей и единиц, тем самым также определив свойство принадлежности состояния аттрактору системы.

3) Предложен и обоснован эффективный алгоритм подсчета индекса состояния системы, а также определена глубина бассейна подсистемы заданной размерности.

4) Подсчитано количество недостижимых состояний в подсистеме заданной размерности.

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

III. Введена динамическая система двоичных векторов, ассоциированных с ориентациями циклов длины п > 2. Для неё получены следующие результаты.

1) Приведены карты систем для различных размерностей.

2) Установлено, сколько бассейнов имеет подсистема заданной размерности, какими аттракторами она характеризуются, а именно их вид, длина и количество, а также определено свойство принадлежности состояния аттрактору системы.

3) Предложен и обоснован эффективный алгоритм подсчета индекса состояния системы, а также определен максимальный индекс в подсистеме заданной размерности.

4) На языке двоичных векторов определены недостижимые состояния системы и подсчитано их количество в подсистеме заданной размерности.

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ источников

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

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

3. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. - М.: Наука. Физматлит, 1997. - 368 с. - ISBN 5-02-0150339.

4. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств / Под. ред. В.Г. Тоценко. - Саратов: Изд-во Сарат. ун-та, 1986. - 238 с.

5. Грин Д., Кнут Д. Математические методы анализа алгоритмов. - М.: Мир, 1987. - 120 е., ил.

6. Зыков A.A. Основы теории графов. - М.: Наука, 1987. - 380 с.

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

8. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ / Перевод с англ. - 2-е изд. - М.: Издательский дом «Вильяме», 2005. - 1296 с. - ISBN 5-8459-0857-4, 0-07-013151-1.

9. Курносова С.Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений: Сб.

науч. тр. / Под ред. проф. A.A. Сытника. - Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. - С. 113-125. - ISSN 1815-8692.

10. Онл айн-энциклопедия целочисленных последовательностей [Электронный ресурс]. - URL: http://oeis.org/71anguage-russian (дата обращения: 17.02.2012).

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

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

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

14. Стенли P. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. - М.: Мир, 2005. - 768 с. -ISBN 5-03-003476-5.

15. Харари Ф. Теория графов / Перевод с англ. В.П. Козырева, под ред. Г.П. Гаврилова. - М.: Мир, 1987. - 300 с.

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

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

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

19. Coin tossing [Электронный ресурс] // Wolfram Math World: the web's most extensive mathematical resource. - URL: http://mathworld.wolfram.com/CoinTossing. html (дата обращения: 17.02.2012).

20. Colon-Reyes О., Laubenbacher R., Pareigis B. Boolean monomial dynamical systems // Ann. Comb. - 2004. - Vol. 8. - P. 425^39.

21. Du B.-S. A simple method which generates infinitely many congruence identities // Fibonacci Quarterly. - 1989. - № 27. - P. 116-124.

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

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

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

25. Khrennikov A., Nilsson M. On the number of cycles of p-adic dynamical systems // Journal of number theory. - 2001. - Vol. 90, Issue 2. - P. 255-264.

26. Lagarias J.C. The ultimate challenge: the Зх + 1 problem // Providence, R.I.: Amer. Math. Soc. Pubis. - 2011. - 348 pp.

27. Sequence A006206 [Электронный ресурс] // Онлайн-энциклопедия целочисленных последовательностей. - URL: http://oeis.org/A006206 (дата обращения 17.02.2012).

28. Sequence А135491 [Электронный ресурс] // Онлайн-энциклопедия целочисленных последовательностей. - URL: http://oeis.org/A135491 (дата обращения: 17.02.2012).

29. 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.

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

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

А2. Власова А.В. Ветвления в динамической системе п-мерных двоичных векторов / Инновационные технологии XXI века в управлении,

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

A3. Власова A.B. Ветвления в конечной динамической системе (Вп, 0) // Научные исследования студентов Саратовского государственного университета: Материалы итог. студ. науч. конф. - Саратов: Изд-во Сарат. унта, 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. Аттракторы в динамической системе (В, S) двоичных векторов // Компьютерные науки и информационные технологии: Материалы науч. конф. - Саратов: Изд-во Сарат. ун-та, 2010. - С. 35-41. - ISBN 978-5-29203935-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. - С. 7071.

А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 Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография» -SIBECRYPT11 (Томск, ТГУ, 5-10 сентября 2011 г.). - № 4, сентябрь 2011. -С. 88-89. - ISSN 2071-0410.

А12. Власова A.B. Индексы в динамической системе (В, S) двоичных векторов // Изв. Сарат. ун-та. Нов. сер. 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.