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

• Автор: Жаркова, Анастасия Владимировна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Саратов
• Количество страниц: 127 с. : ил.

ОГЛАВЛЕНИЕ

Введение
Глава I. Задачи и проблемы, общие сведения
§ 1. Необходимые понятия из теории графов
§2. Конечные динамические системы и связанные с ними задачи
§3. Некоторые свойства рассматриваемых динамических систем
Глава II. Динамическая система, ассоциированная с цепями
§1. Описание динамической системы
§2. Аттракторы в системе
§ 3. Индексы состояний
§4. Недостижимые состояния
§5. Статистические данные
Глава III. Динамическая система, ассоциированная с циклами
§ 1. Описание динамической системы
§2. Аттракторы в системе
§3. Индексы состояний
§4. Недостижимые состояния
§ 5. Статистические данные
Заключение
Список использованных источников
Приложение 1. Карты динамических систем, ассоциированных с цепями... 120 Приложение 2. Карты динамических систем, ассоциированных с циклами
ВВЕДЕНИЕ

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

динамических систем, с которой связаны многие теоретические и прикладные исследования как в математике, так и в других естественных науках ([2], [16]).
Заметим, что приведенному определению динамической системы удовлетворяют также такие известные объекты как моноунарная алгебра (унар) и автономный (то есть с одним входным сигналом) автомат без выхода. Они интенсивно изучались различными авторами соответственно в теории алгебраических систем и в теории автоматов. Отметим, например, работы [12], [13], [18], [23].
В приложениях, связанных с дискретной математикой, большой интерес представляют динамические системы, состояния которых наделены некоторой индивидуальной структурой, определяющей эволюцию состояний. Так, натуральные числа являются состояниями широко известной динамической системы «Зх + 1», с которой связаны многочисленные работы в теории чисел, теории динамических систем, эргодической теории, математической логике и теории алгоритмов (см. [26]). Натуральные числа с фиксированным числом цифр образуют систему Капрекара [24], обобщения которой [29] используются в теоретико-числовых исследованиях. В математической генетике находят приложения булевы динамические системы, состояниями которых являются двоичные векторы заданной размерности [20]. В задачах об отказоустойчивости компьютерных сетей применяется упомянутая БЕК-динамика, действующая на бесконтурных связных ориентированных графах [17]. Подробнее об этих динамических системах говорится в первой главе.
Динамическая система называется конечной, когда множество 5 состояний системы является конечным. Каждой конечной динамической системе сопоставляется карта, представляющая собой ориентированный граф с множеством вершин 5 и дугами, проведенными из каждой вершины 5 € 5 в вершину ($). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Получается, что каждый бассейн

Теперь можно последовательно выписать получившуюся последовательность из нулей и единиц (из ориентации цепи на рисунке 2.4 получаем: 011101).
Таким образом, каждой ориентации цепи сопоставляется п-мерный двоичный вектор. С другой стороны, каждый такой вектор однозначно определяет некоторую ориентацию цепи, так что между множеством Рп всевозможных ориентированных п-звенных цепей указанного вида и множеством Вп устанавливается взаимно однозначное соответствие.
На языке цепей структура динамической системы вводится следующим образом: если дана некоторая цепь р € Рп, то её динамическим образом 5(р) является цепь, получаемая из р одновременным превращением всех стоков в источники. В [11] замечается, что это частный случай динамики бесконтурных связных орграфов, введённой в [17].
Пусть V £ Вп, тогда соответствующее состояние из Рп будем обозначать Ру, и, наоборот, для р £ Рп соответствующее состояние из Вп - через Ур.
На языке кодирующих цепи из Рп двоичных векторов динамика, введенная на языке ориентаций цепи, означает, что
1) если вектор Ур имеет первой компонентой 0, то есть в вершину р0 цепи р входит дуга (и, значит, р0 является стоком), то в векторе у$(Р), первой компонентой будет 1;
2) если в составе вектора ур встречается диграмма 10, то ей соответствует сток в цепи р, а тогда в У$ф) произойдёт замена указанной диграммы на 01;
3) если вектор ур имеет последней компонентой 1, то есть в цепи р вершина рп является стоком, то У§(р) будет оканчиваться нулём.
То есть преобразования ориентаций цепи соответствуют эволюционным преобразованиям соотносимых им двоичных векторов в динамической системе (Вп, 5), п > 0, а именно У$(р) = 8(ур). Таким образом, эти две динамические системы - (Вп, 5) и (Рп, 6), п > 0, изоморфны, поэтому различные задачи