Разработка цифровой дискретной аттракторы

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Первичные определения в регистровых наборах

2. Определение дискретного аттрактора, виды аттракторов

3. Формы представления и их взаимосвязи

4. Конкатенация как инструмент конструирования

5. Структура с двумя операторами

6. Определение репеллера, типы репеллеров

7. Взаимосвязи свойств репеллеров и графа структуры с двумя операторами

8. Уникальные свойства дискретных аттракторов

9. Направления применения, модели агрегации и роста

Заключение

Список литературы

Введение

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

Коротко суть работ В.И. Арнольда по геометрии функциональных пространств базируются на представлении конечных математических структур в виде графа. Граф строится как полная совокупность пар (x; F(x)), где каждому элементу образующего структуру множества X ставится в соответствие его образ по функциональному оператору F. В работах В.И. Арнольда этот граф называется монада. Представление и исследование структуры в виде монады позволяет обнаружить целый ряд фундаментальных свойств, ускользающих при представлении структуры средствами символьных записей. В дальнейшем был применён продуктивный метод совместного рассмотрения структуры в виде символьной записи, графика функции и графа монады. В течение ряда лет проводились работы по применению метода для описания и исследования внутренней среды компьютера и построения современных информационных технологий. При этом элементами структуры являлись кодовые состояния машинных регистров, а функциональные операторы строились на базе машинных команд. Это сузило класс изучаемых структур и вместо термина «монада» стали использовать термин «граф кодовых переходов».

Применение операции автосуперпозиции оператора F на структуре приводит к построению динамической конструкции, которая получила название «аттрактор». Динамика поведения рекуррентного генератора полностью определяется структурой графа кодовых переходов и представляет собой реализацию маршрутов на графе. На этой основе можно конструировать эффективные методы реализации массового динамического параллелизма и целый ряд информационных технологий поиска, сборки сложных объектов, управления распределёнными структурами.

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

1. Первичные определения в регистровых наборах

Введём основные понятия.

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

Дискретный функциональный преобразователь F - устройство, преобразующее состояние регистра заданной разрядности на основе функции F(n).

Функция F(n) должна быть целочисленной, областью её определения является отрезок . Функция F(х) всюду определена на своей области значений .

Округление дробного значения осуществляется до меньшего целого числа. Значение функции F(n) и коэффициентов линейной функции пересчитываются для кольца вычетов по модулю числа где - разрядность регистра. Т.е. при заданной разрядности регистра, в случае если значение выходит за пределы диапазона представимости N, происходит возврат в диапазон через операцию взятия остатка по модулю N.

2. Определение дискретного аттрактора, виды аттракторов

Цифровым дискретным аттрактором (далее дискретный аттрактор, аттрактор, ЦДА) назовем физический прибор, состоящий из входного и выходного регистров определённой разрядности и дискретного функционального преобразователя F.

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

Рисунок 1

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

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

Из определения функции F(n) следует, что граф Gr состоит из N вершин, помеченных положительными натуральными числами от 0 до N - 1. Не существует двух различных вершин графа Gr, помеченных одним числом из N. Все точки отрезка N имеют только однократное вхождение в структуру графа.

В силу функциональности отображения , заданного F(n), и определения графа кодовых переходов, все вершины графа Gr имеют одну и только одну исходящую дугу. Входящих дуг в каждой вершине может быть любое число от 0 до N. Перечисленные ограничения приводят к тому, что все возможные структуры графа Gr исчерпываются следующими пятью типами:

самовозвратный полюс - вершина, не имеющая входящих дуг, кроме дуги, исходящей из этой же вершины.

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

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

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

деревья и цепи, сходящиеся к вершинам кольца (розетка) - множество вершин, из которого можно выделить кольцо и не менее одной цепи или дерева.

Других типов структур на графе Gr быть не может.

Перечисленные структуры изображены ниже на рисунке

самовозвратный полюс,

кольцо,

цепь,

дерево,

розетка

Рисунок 2

Кроме того, граф может быть либо связен, либо распадается на ряд подграфов.

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

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

Очевидно, что структура кольцо удовлетворяет всем ограничениям, т. к. для каждой вершины существует только по одной входящей и выходящей дуге. Кольцо можно представить как граф (X, X^F) удовлетворяющий следующему условию: для любого существует такой , , что . Самовозвратный полюс можно считать частным случаем кольца - кольцо из одного элемента, то есть множество Х содержит только один элемент и условием пренебрегаем.

3. Формы представления и их взаимосвязи

Исследуем зависимость графика функции F(n), порождающей рекуррентную кодовую последовательность, и графа кодовых переходов. Во первых, на графике функции F(n) числа отложенные по горизонтальной оси интерпретируются, как номера начала дуг, то есть это номер вершины из которой выходит дуга. В силу определения функции F(n) очевидно, что граф кодовых переходов содержит все N вершин, пронумерованных от 0 до N - 1, и каждая вершина имеет выходящую дугу и при том только одну. На вертикальной оси цифры представляют собой номера концов дуг. Ясно, что количество точек графика функции, лежащих на прямой, проходящей через точку (0, i), i = 0, …, N - 1 и параллельной горизонтальной оси, показывает число входящих дуг в i-ю вершину графа кодовых переходов. Следовательно, любая вершина может иметь от 0 до N, входящих дуг. Можно сделать следующий вывод, абсцисса точки графика функции F(n) - это номер вершины из которой выходит дуга, а ордината - номер вершины в которую входит дуга. Назовем главной диагональю отрезок с началом в точке (0, 0) и концом в точке (N - 1, N - 1).

Начнем с определения по графику самовозвратного полюса. На графе кодовых переходов, изолированный самовозвратный полюс - это вершина переходящая сама в себя, не имеющая вхождений ни из одной другой вершины. То есть (n, F(n)), такое, что n = F(n) и не существует такого x, что n = F(x). Очевидно, что необходимым условием существования изолированного самовозвратного полюса является принадлежность точки графика функции к главной диагонали. А достаточное условие существования заключается в том, что прямая, проходящая через точку графика, принадлежащую главной диагонали, и параллельная горизонтальной оси больше не содержит ни одной точки графика.

Необходимое условие определения наличия в графе кодовых переходов дерева. Для определения по графику функции наличия в графе кодовых переходов дерева необходимо существование:

1) прямой, параллельной горизонтальной оси и проходящей через точку, лежащую на главной диагонали, которая содержит помимо этой точки еще не менее одной точки;

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

Для выявления наличия цепи в графе по виду графика функции необходимо, чтобы существовал такой набор точек , , который удовлетворяет следующим условиям. Во-первых, в этот набор точек должен входить один и только один самовозвратный полюс, то есть точка графика, лежащая на главной диагонали. Во-вторых, прямая, проходящая через точку графика, соответствующую этому самовозвратному полюсу, и параллельная горизонтальной оси, должна содержать еще одну и при том только одну точку графика. В-третьих, для всех n_j принадлежащих набору и отличных от самовозвратного полюса, прямая, проходящая через точку (0, n_j) и параллельная горизонтальной оси, должна содержать не более одной точки графика функции. Но, к сожалению, все эти условия не являются достаточными. Действительно, если взять все точки графика функции, которые удовлетворяют третьему условию, то может получиться, что некоторые из них принадлежат кольцу.

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

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

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

Приведем еще один способ нахождения по графику функции точек, которые соответствуют вершинам колец в графе кодовых переходов. Он заключается в том, что из графика можно исключить те точки, которые точно не являются точками кольца. Очевидно, на первом шаге можно исключить все самовозвратные полюса, вершины, которые в них входят и вершины, не имеющие входных дуг. На графике функции эти вершины соответствуют следующим точкам:

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

с абсциссой n_i, где n_i такое, что прямая, проходящая через точку (0, n_i) и параллельная горизонтальной оси, не содержит ни одной точки графика функции.

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

Рассмотрим еще один метод определения структуры графа кодовых переходов по виду графика функции. Этот метод позволяет разбить множество всех вершин графа, на непересекающиеся подмножества, соответствующие подграфам. И используя связность подграфов, определить структуру каждого из подграфов графа кодовых переходов. Назовем его комплексным методом определения структуры графа кодовых переходов по виду графика функции. Основные преимущества этого метода заключаются в том, что при его использовании можно выявить все подграфы графа кодовых переходов и полностью определить структуру графа кодовых переходов. Но при этом, комплексный метод обладает существенным недостатком. А именно, этот метод требует анализа всех точек графика функции. Фактически, суть комплексного метода заключается в прохождении на графике функции по вершинам графа, согласно направлению дуг. Сначала выбирается вершина с произвольным номером n₁. Точка графика (n₁, n₂), где n₂ = F(n₁) помечается цифрой 1, это обозначение показывает, что вершина с номером n₁ принадлежит первому подграфу. Из определения графа следует, что вершина с номером n₁ переходит в вершину с номером n₂. Так как вершина n₁ принадлежит первому подграфу, то и вершина n₂ также принадлежит этому подграфу, а следовательно, и все вершины входящие в вершину n₂. Поэтому все точки графика, лежащие на прямой, проходящей через точку (n₁, n₂) и параллельной горизонтальной оси, помечаются цифрой 1.

Для того, что бы пометить точку графика, соответствующую вершине с номером n₂, сначала перейдем в точку (n₂, n₂), то есть из точки (n₁, n₂) проведем отрезок до главной диагонали. Затем найдем точку графика, лежащую на прямой, проходящей через точку (n₂, n₂) и параллельную вертикальной оси. Это точка с координатами (n₂, n₃), где n₃ = F(n₂). Для найденной точки повторяем все операции. В результате этого находим точку с координатами (n₃, n₄) и так далее. В силу того, что любой граф имеет кольцо, мы на некотором шаге найдем уже помеченную точку. Очевидно, что этой точке соответствует вершина, принадлежащая кольцу. Тогда изменим метку этой точки на 1к. Повторим те же операции поиска следующей точки и исправим метку найденной точки с 1 на 1к. На некотором шаге мы найдем точку с меткой 1к. Это означает, что мы вернулись в ту точку, с которой начали изменение меток, то есть мы пометили все точки метками 1к, которым соответствуют вершины кольца, входящего в первый подграф. На втором этапе сначала так же выбирается любая не помеченная точка и над ней производятся те же действия, что и на первом этапе. Отличие второго этапа от первого заключается в метках, на втором этапе ставится метка 2. Еще одно отличие второго этапа состоит в несостоятельности утверждения о том, что на некотором шаге мы найдем точку с меткой 2. Действительно, пусть граф кодовых переходов имеет структуру цепь. На первом этапе была выбрана вершина, имеющая входную дугу.

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

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

4. Конкатенация как инструмент конструирования

Конкатенация реализуется как совмещение двух аттракторов без установления связей между ними. Результирующий аттрактор состоит из двух изолированных секций, представляющих старшую и младшую группы разрядов. График функции для результирующего аттрактора строится путём совмещения графиков участников конкатенации. Общая сетка строится последовательно. Сначала строится целочисленная решётка старшей группы разрядов, затем в каждую точку этой решётки встраивается решётка младшей группы разрядов. Это означает, что в каждую точку целочисленной тороидальной решётки встраивается ещё одна тороидальная целочисленная решётка. На плоской проекции тороидальных решёток топологические трудности изображения устраняются. Факт топологической специфичности этой картинки важен для учёта граничных условий трансформации графиков.

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

Рассмотрим на примере, как формируется график при конкатенации.

Рассмотрим функцию F1=x, с размерностью 2, ее график представляет собой точки, принадлежащие главной диагонали, и выглядит следующим образом:

Также возьмем функцию F2=2*x, с разрядностью 3, график выглядит таким образом:



Рисунок 3

При конкатенации F1 с F2, результирующий график будет иметь разрядность 5, при этом сначала наносятся точки графика функции F1, каждая из которых представляет собой график функции F2. В результате получается график такого вида:

Рисунок 4

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

При этом если поменять местами компоненты конкатенации, то график результирующий функции изменится, а граф останется прежним, что следует из определения конкатенации и будет доказано ниже. График конкатенации F2 с F1 выглядит так:

Рисунок 5

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

Проведем теоретическое исследование.

Конкатенация дискретных аттракторов может быть интерпретирована как операция над графами кодовых переходов. В практической работе использовался инструментальный программный комплекс FanScan v.0.13.

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

- финальная группа вершин, в которую входят самовозвратные полюса и кольца;

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

Финальная группа в графе имеет следующие характеристики: количество финальных групп, то есть, сколько колец содержит граф и длина каждого кольца, которая характеризуется количеством элементов.

Маршрутная группа характеризуется максимальной длиной ветви в графе и максимальным ветвлением.

Выведем общую формулу конкатенации двух дискретных аттракторов: аттрактора f1(x1), разрядности n, с аттрактором f2(x2), разрядности m.

Из определения конкатенации двух дискретных аттракторов:

Дано:

Первый аттрактор f1(x1) разрядности n

Второй аттрактор f2(x2) разрядности m

В результате конкатенации получаем:

Аттрактор F(x) разрядности n + m (см. рис. 6)



Рисунок 6

С другой стороны, аттрактор F(x) можно представить в виде:

Рисунок 7

Таким образом получаем, что вклад второго аттрактора в аттрактор F(x) - это f2(x2), а первого - 2^m*f1(x1) (2^m т. к. все разряды первого аттрактора f1(x1) при конкатенации увеличиваются на m. Например, первый разряд становится m + 1 и т. д., а значения всех разрядов с номером меньшим или равным m равно нулю. Другими словами (перевод из двоичной системы в десятичную (f1(x1)_i - i-тый разряд числа f1(x1) в двоичном представлении)) f1(x1) = f1(x1)_n-1*2^n-1 + f1(x1)_n-2*2^n-2 +... + f1(x1)₁*2¹ + f1(x1)₀*2⁰, при конкатенации (первое слагаемое суммы 1) = f1(x1)_n-1*2^n-1+m + f1(x1)_n-2*2^n-2+m +... + f1(x1)₁*2^1+m + f1(x1)₀*2^0+m + 0*2^m-1 +... 0*2¹ + 0*2⁰ = 2^m*( f1(x1)_n-1*2^n-1 + f1(x1)_n-2*2^n-2 +... + f1(x1)₁*2¹ + f1(x1)₀*2⁰) = 2^m*f1(x1)).

Следовательно, F(x) = 2^m*f1(x1) + f2(x2), где по определению младшие m разрядов в двоичном представлении x это x2, а старшие n разрядов это число x1 (при этом нумерация начинается с 0 до n-1-m, а не с m до n-1):

Рисунок 8

Поэтому для того, что бы получить из числа x число x2, необходимо выделить m младших разрядов числа x. Выделение m младших разрядов аналогично взятию остатка по модулю 2^m. Т. е. x2 = Mod(x, 2^m). Аналогично, для получения числа x1, необходимо выделить n старших разрядов из числа x. Сначала обнулим m младших разрядов числа x, оставив только n старших. Очевидно, что это аналогично следующему: x - x2 = x - Mod(x, 2^m). Осталось только перенумеровать разряды, снизить их номера на m. По аналогии с выше сказанным о вкладе первого аттрактора в аттрактор F(x), очевидно, что снижение номера разряда осуществляется путем деления на 2^m. Окончательно x1 = (x - Mod(x, 2^m))/2^m.

Таким образом, можно записать окончательную формулу для аттрактора F(x), полученного путем конкатенации двух аттракторов f1(x1), f2(x2). Т. е. искомую общую формулу конкатенации двух дискретных аттракторов с известными функциональными преобразователями f1(x1) и f2(x2):

F(x) = 2^m*f1((x - Mod(x, 2^m))/2^m) + f2(Mod(x, 2^m)),

(Где: x - Mod(x, 2^m))/2^m = x1, Mod(x, 2^m) = x2).

Теорема о сохранении структуры графа кодовых переходов при перестановке аттракторов, участвующих в операции конкатенации.

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

Дано:

Два аттрактора f1(x1) разрядности n, f2(x2) разрядности m.

Аттрактор F1(y1) разрядности n + m, полученный при конкатенации f1(x1) и f2(x2). Обозначим операцию конкатенации как K(f1(x1), f2(x2)) = F1(y1).

Аттрактор F2(y2) = K(f2(x2), f1(x1)) разрядности m + n.

Требуется доказать, что структура графов F1 и F2 совпадает.

По определению граф кодовых переходов -- это множество ориентированных дуг, определяемых как пары вершин (y1, F1(y1)). Таким образом, при конкатенации K(f1(x1), f2(x2)) = F1(y1) мы получаем граф с некоторой структурой. Его можно представить просто как набор пар двух вершин соединенных дугой (в соответствии с определением конкатенации см. рис. 9).



Рисунок 9

Здесь верхний индекс обозначает номер элемента.

При этом, очевидно, что f1(x1)ⁱ может быть равен некоторому f1(x1)^j (аналогично с f2(x2)). Так же x1¹ это старшие n разрядов в двоичном представлении числа y1¹ и соответственно x2¹ - это младшие m разрядов.

Очевидно, что если заменить номер некоторой вершины на другой, отличный от находящихся в графе, то структура графа останется прежней. В этом случае поменяется только нумерация. При таком представлении графа изменение нумерации соответствует замене номера вершины во всех парах, где он встречается, на новый номер. Из определения графа следует, что номер вершины присутствует только в одной вершине с исходящей дугой и от 0 до n + m вершин с входящей дугой.

Так же из определения дискретного аттрактора известно, что , где FX это область значений, а X - область определения. Поэтому любой f1(x1)ⁱ равен некоторому x1^j (аналогично для x2).

Таким образом, мы получим некоторый граф G, структурно не отличающийся от исходного графа кодовых переходов дискретного аттрактора, полученного путем конкатенации двух аттракторов: f1(x1) и f2(x2). При этом в результате произведенной перенумерации вершина с номером x1ⁱx2^j получила номер x2^jx1ⁱ. Как было отмечено выше, такая запись соответствует двоичному представлению соответственно чисел y1 и y2.

Рис. 10. Граф G кодовых переходов

Следовательно, видно, что мы получили граф F2(y2), структурно не отличающийся от исходного графа кодовых переходов F1(y1). Поэтому, мы доказали, что структура графов кодовых переходов, полученных конкатенацией K(f1(x1), f2(x2)) = F1(y1) и K(f2(x2), f1(x1)) = F2(y2) совпадают. А сами графы кодовых переходов отличаются только нумерацией вершин.

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

Далее выведем формулу для пересчета номеров вершин.

Вывод формулы пересчета номеров вершин при перестановке аттрактров, участвующих в конкатенации.

Дано:

Два аттрактора f1(x1) разрядности n, f2(x2) разрядности m.

Аттрактор F1(y1) = K(f1(x1), f2(x2)) разрядности n + m

Аттрактор F2(y2) = K(f2(x2), f1(x1)) разрядности m + n.

Требуется вывести формулу пересчета номеров вершин при переходе от графа аттрактора F1(y1) к F2(y2).

При перестановке аттракторов старшие n разрядов числа y1 становятся младшими, а младшие m разрядов (число x2) - старшими. Следовательно, необходимо сдвинуть старшие n разрядов на m разрядов вправо, а младшие m разрядов на n - влево. По аналогии с выводом формулы для конкатенации, очевидно, что сдвиг вправо на m разрядов эквивалентен делению на 2^m, а влево на n разрядов соответственно умножению на 2ⁿ. Из того же вывода видно, что для выделения из числа y1 младших m разрядов необходимо взять остаток по модулю m. Старшие n разрядов соответственно выделяются путем вычитания из числа y1 младших m разрядов, т. е. y1 - Mod(y1, 2^m). Следовательно, при пересчете номеров вершин, необходимо воспользоваться следующей формулой:

y2 = (y1 - Mod(y1, 2^m))/2^m + 2ⁿ*Mod(y1, 2^m) = x1 + 2ⁿ*x2

Теорема о кольцах, содержащих две вершины.

Пусть первый граф f1(x1) имеет n колец, где nЄ{0,1,2,…,N, где N - натуральное число}, каждое из которых содержит по две вершины.

Пусть второй граф f2(x2) имеет m колец, где mЄ{0,1,2,…M, где M - натуральное число }, каждое из которых содержит по две вершины.

В результате конкатенации получится граф F(x), который обязательно будет содержать 2*n*m колец, каждое из которых содержит по две вершины.

Доказательство.

Докажем тот факт, что при данных условиях, в результате конкатенации получится 2*n*m колец.

Мы знаем, что если график функции содержит две точки, симметричные относительно главной диагонали, то граф кодовых переходов содержит кольцо из двух вершин (и если граф содержит кольцо из двух вершин, то на графике они симметричны относительно главной диагонали). Следовательно, известно, что в первом графе у нас n колец, то есть 2*n вершин. Значит, в результате конкатенации получится по n старших разрядов по обе стороны от главной диагонали, причем они симметричны друг другу. Обозначим все точки графика f1(x1), лежащие над главной диагональю как , а лежащие ниже главной диагонали соответственно через , где i изменяется от 0 до n. Т. к. эти вершины попарно симметричны относительно главной диагонали, тогда справедлива следующая система равенств: (Система 1).

Далее в каждую секцию графика мы вписываем график второй функции, который содержит 2*m точек графика. В результирующем графике мы имеем 2*m*n вершин, лежащих по одну сторону от главной диагонали (так как в n секций мы вписали по 2*m вершин). Эти 2*m*n точек симметричны таким же 2*m*n точкам, лежащим по другую сторону от главной диагонали графика. Для доказательства этого факта, необходимо показать, что для любого x2, существует некоторый x2', такой, что (Система 2). Другими словами, что для любой пары симметричных и , найдется такая пара x2 и x2', что при конкатенации соответствующие вершины и образуют кольцо. Т. к. эти вершины образуют кольцо, тогда соответствующие точки на графике будут симметричны относительно главной диагонали и следовательно выполняется Система 2. Заметим, что граф f2(x2) состоит из m колец по две вершины, следовательно, для любого x2 существует x2', такой, что f2(x2') = x2 и f2(x2) = x2'. Воспользовавшись общей формулой конкатенации, распишем , где - двоичное представление некоторого числа x. Получим: . Из Системы 1 и замечания про граф f2(x2), следует, . Приведя полученный результат к двоичному виду, получаем: . Аналогичными действиями получаем следующее равенство: . Таким образом, мы показали, что Система 2 выполняется для любого x2, что и требовалось доказать.

Следствие.

Пусть в конкатенации участвуют графы произвольного вида. И пусть среди них содержатся графы, в финальной группе которых по два элемента в каждом. В результате конкатенации получится граф, который обязательно будет содержать как минимум 2*m*n колец, по две вершины в каждом. Естественно при условии, что в финальной группе первого графа содержится m колец указанного вида, а в финальной группе второго - n колец.

Теорема о наибольшем числе входящих дуг в маршрутной группе.

Пусть в конкатенации участвуют два графа.

В первом графе наибольшее число ветвей, входящих в вершину равно n.

Во втором графе наибольшее число ветвей, входящих в вершину равно m.

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

(Здесь мы рассматриваем все возможные ветви, входящие в вершину, включая ветви, принадлежащие кольцу.)

Доказательство.

Количество точек графика функции, лежащих на прямой, проходящей через точку (0, i), i = 0, …, N - 1 и параллельной горизонтальной оси, показывает число входящих дуг в i-ю вершину графа кодовых переходов. У нас в первом графе таких входящих дуг n. В результате конкатенации мы получаем n старших разрядов, лежащих на одной прямой, параллельной оси абсцисс. В каждую секцию мы вписываем график второй функции, содержащий m точек, лежащих на прямой, параллельной оси абсцисс. В результате мы получаем, что наибольшее количество ветвей получается на прямой, которая содержит m вершин второго графа, причем количество таких секций равно n. Следовательно, наибольшее ветвление равно n*m. Что и требовалось доказать.

Теорема о кольцах.

1) Пусть первый граф содержит в своей финальной группе самовозвратный полюс.

Пусть второй граф содержит в своей финальной группе кольцо, содержащее n элементов.

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

2) Пусть первый граф в финальной группе содержит кольцо, состоящее из m вершин.

Пусть второй граф в финальной группе содержит кольцо, состоящее из m вершин.

(То есть два графа содержат в финальной группе одинаковое количество элементов.)

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

3) Пусть первый граф содержит в финальной группе кольцо, состоящее из 2*n элементов.

Пусть второй граф содержит в финальной группе кольцо, состоящее из 2*m элементов.

Возможны два случая:

3.1 И пусть m=n.

Тогда, в этом случае, в результате конкатенации получится 2*m колец по 2*m вершин в каждом

3.2 Пусть m?n, для определенности будем считать m<n.

Тогда, в результате конкатенации получится k колец, в каждом из которых будет по (2*m)*(2*n)/k вершин.

Где k=НОД{2*m,2*n}.

4) Пусть первый граф содержит в финальной группе одно кольцо, состоящее из 2*m+1 элементов.

Пусть второй граф содержит в финальной группе одно кольцо, состоящее из 2*n+1 элементов.

Возможны два случая:

4.1 И пусть m=n.

Тогда, в этом случае, в результате конкатенации получится 2*m+1 колец по 2*m+1 вершин в каждом

4.2 Пусть m?n, для определенности будем считать m<n.

Тогда, в результате конкатенации получится k колец, в каждом из которых будет по (2*m+1)*(2*n+1)/k вершин.

Где k=НОД{2*m+1,2*n+1}.

5) Пусть первый граф содержит в финальной группе одно кольцо, состоящее из 2*m элементов.

Пусть второй граф содержит в финальной группе одно кольцо, состоящее из 2*n+1 элементов.

Тогда, в результате конкатенации получится k колец, в каждом из которых будет по (2*m)*(2*n+1)/k вершин. Где k=НОД{2*m,2*n+1}.

Как искать НОД? Идея метода проста. Из набора выбираются любые два ненулевых числа, и большее из них (или любое, если числа равны) заменяется разностью этих чисел. Этот процесс повторяется до тех пор, пока не останется одно ненулевое число. Это число и будет наибольшим общим делителем исходного набора, состоящего из натуральных чисел.

В общем виде теорема формулируется так:

Если первый граф содержит одно кольцо, содержащее n вершин, второй граф содержит одно кольцо, содержащее m вершин. То в результате конкатенации получится k колец, содержащих m*n/k вершин в каждом. Где k=НОД{m,n}.

5. Теорема о максимальной длине ветви.

При конкатенации максимальная длина ветви сохраняется.

Для доказательства последних двух теорем введем понятие уровня.

Введем определение уровней графа кодовых переходов. Нулевым уровнем графа назовем множество вершин, которые не имеют ни одной входящей вершины. Пусть (X, X^F) это граф кодовых переходов, порожденный функцией F(x). Тогда нулевым уровнем этого графа является множество X⁰ = {x⁰}, состоящее из таких элементов, что для любого из этих x⁰ не существует (т. е. нет ни одной вершины из всего графа X) такого, что F(x) = x⁰. Исходя из всех возможных структур графа кодовых переходов, можно утверждать, что . Строгого вложения нет, т. к. в любом графе есть хотя бы один самовозвратный полюс или кольцо. Следовательно, как минимум одна вершина имеет входящую дугу (в случае самовозвратного полюса) или больше (в случае кольца). Первым уровнем назовем множество вершин, не имеющим входящих дуг, за исключением тех, которые начинаются с нулевого уровня. Т. е. множество X¹ = {x¹} такое, что для любого элемента не существует такого, что F(x) = x¹. Аналогично, можно утверждать, что .

Таким образом, определение i-го уровня будет следующим - это множество вершин Xⁱ = {xⁱ} таких, что для любого xⁱ из Xⁱ не существует , который удовлетворяет следующему равенству: F(x) = xⁱ. Очевидно, что . Этот процесс закончится на некотором шаге. Т. е. когда не останется таких вершин, которые не имели бы входящих дуг за исключением с предыдущих уровней. Очевидно, что при этом останется еще одни уровень, назовем его финальным, или кольцевым. Он состоит из кольцевых вершин (или из самовозвратного полюса). Другими словами, он состоит из вершин, которые помимо входящих дуг с предыдущих уровней, имеют входящие дуги с этого же уровня. Множество финальных вершин X^Ф = {x^Ф} таких, что для любого элемента существует такой, что . При этом, если существует I уровней, то . Таким образом каждой вершине графа соответствует некоторый уровень. Поэтому .

Договоримся, что при конкатенации нумерацию уровней двух графов будем производить по графу с большим количеством уровней. Пусть у одного графа FI(x) I уровней, а у второго FJ(x) - J уровней, при этом I > J. Тогда последний кольцевой уровень графа FJ(x) будет иметь номер I. Начиная с уровня J до I - 1 граф FJ(x) не содержит вершин. Пример показан на рисунке

Рисунок 11

Рассмотрим, что происходит при конкатенации двух графов. Пусть даны два графа F1(x1) и F2(x2). Не теряя общности, можно считать, что количество уровней в графе F1(x1) не меньше чем в F2(x2) (исходя из теоремы о перестановки графов при конкатенации). Исходя из определения конкатенации, для получения результирующего графа кодовых переходов, необходимо произвести конкатенацию каждой вершины первого графа со всеми вершинами второго графа.

Конкатенацию начнем с первого элемента нулевого уровня графа F1(x1). Т. к. это элемент нулевого уровня, тогда из определения уровня следует, что не существует такого x1^и, что F1(x1^и) = x1. Следовательно, не существует и такого x1^иx2^л, что F(x1^иx2^л) = x1x2. Здесь F(x1x2) = K(F1(x1), F2(x2)), x2^л - любой элемент графа F2 и F2(x2^л) = x2. Таким образом, элемент с любого уровня графа F2 при конкатенации с элементом нулевого уровня графа F1 в результирующем графе окажется на нулевом уровне. Аналогичная операция производится со всеми другими элементами нулевого уровня графа F1.

Далее берем элемент первого уровня графа F1. Здесь может возникнуть два варианта. Первый вариант, когда конкатенация производится с элементом более низкого уровня. Второй вариант, когда конкатенация производится с элементом этого же или более высокого уровня. При первом варианте x1 соединяется с некоторым x2 нулевого уровня. Таким образом, не существует такого x2^и, что F2(x2^и) = x2. Следовательно, не существует и такого x1¹x2^и, что F(x1¹x2^и) = x1x2, где F1(x1¹) = x1. Таким образом, элемент, составленный из элемента первого уровня графа F1 и нулевого уровня графа F2, в результирующем графе окажется на нулевом уровне. При втором варианте x1 соединяется с некоторым где X2 - множество вершин графа F2, X2⁰ - множество вершин нулевого уровня графа F2. Из определения первого уровня следует, что не существует такого , что F1(x1^и) = x1 (здесь X1 - множество вершин графа F1, X1⁰ - множество вершин нулевого уровня этого же графа). Следовательно, не найдется и такого x1^иx2^л, что F(x1^иx2^л) = x1x2. При этом, согласно рассмотрению конкатенации с вершинами нулевого уровня, любой x1^иx2^л принадлежит множеству вершин нулевого уровня в результирующем графе. Поэтому по определению уровней, получаем, что вершина x1x2 принадлежит первому уровню в результирующем графе.

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

Из приведенного выше, можно сделать следующий вывод. При конкатенации двух вершин с некоторых уровней I и J, в результирующем графе образуется вершина, на уровне минимальном из двух исходных (Min(I, J)). Назовем это эффектом поглощения.

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

Докажем тот факт, что эффект поглощения распространяется и на исходящие дуги. Пусть известно, что некоторая вершина в первом графе находится на уровне i1 и имеет исходящую дугу на уровень i2. Так же известно, что во втором графе есть вершина на уровне j1 и имеет исходящую дугу на уровень j2. Т. к. структура результирующего графа при перестановки участников конкатенации местами не изменяется, то можно считать, что i2 > j2.

Рисунок 12

(Все возможные варианты взаиморасположения вершин двух исходных графов, при условии, что i2 > j2)

Рисунок 13

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

Пусть известно, что в некоторую вершину x1 графа F1 входит I дуг, а в вершину x2 графа F2 - J дуг. Требуется доказать, что при конкатенации вершина x1x2 будет иметь I*J число входящих дуг. То что вершина x1 имеет I входящих дуг означает, что есть набор x1ⁱ i = 1... I таких, что F1(x1ⁱ) = x1. Аналогично для графа F2 задан набор x2^j j = 1... J таких, что F2(x2^j) = x2. Следовательно, в вершину x1x2 могут перейти все возможные комбинации x1ⁱx2^j из известных наборов (i = 1... I, j = 1... J). Т. е. F(x1ⁱx2^j) = x1x2 для любых x1ⁱ и x2^j заданных выше. Поэтому число входящих дуг в вершину x1x2 графа F = K(F1, F2) будет равно I*J.

Выведем формулы для нахождения количества вершин на заданном уровне в рузультирующем графе. Пусть известно количество вершин на каждом уровне в обоих исходных графах F1 разрядности n и F2 разрядности m. Обозначим их через i - количество вершин в графе F1, j - количество вершин в графе F2. Индексом обозначим на каком уровне берутся вершины. Например, i4 - количество вершин на четвертом уровне в графе F1, а j3 - количество вершин на уровне 3 в графе F2.

Для начала рассмотрим нулевой уровень. Согласно эффекту поглощения вершины нулевого уровня в результирующем графе кодовых переходов могут образоваться только в результате конкатенации любой вершины с вершиной нулевого уровня начальных графов. Поэтому при конкатенации вершины с нулевого уровня первого графа со всеми вершинами второго графа образуются вершины нулевого уровня в графе F = K(F1, F2). Т. к. размерность второго графа равна m, то он содержит 2^m вершин. Т. к. первый граф на нулевом уровне содержит i0 вершин, то в графе F он породит 2^m*i0 вершин. К этим вершинам необходимо добавить вершины, полученные в результате конкатенации элементов первого графа уровня с номером больше нуля и вершин нулевого уровня графа F2. Очевидно, что количество таких вершин будет следующим: (2ⁿ - i0)*j0. Поэтому, полное число вершин на нулевом уровне в результирующем графе будет 2^m*i0 + (2ⁿ - i0)*j0.

Рассмотрим первый уровень. Аналогично, согласно эффекту поглощения, вершины первого уровня могут получится: а) в случае конкатенации вершин первого уровня графа F1 со всеми вершинами, за исключением вершин предыдущих уровней, графа F2, б) в случае конкатенации вершин первого уровня графа F2 с вершинами высших уровней графа F1. Поэтому можно записать следующую формулу: (2^m - j0)*i1 + (2ⁿ - (i0 + i1))*j1.

Следуя этим же рассуждениям легко вывести формулу для произвольного уровня p. Число вершин уровня p будет содержать вершины полученные из: а) вершин графа F1 уровня p и вершин графа F2 уровня больше или равного p, б) вершин графа F2 уровня p и вершин графа F1 с уровней, строго больших p. Таким образом получаем общую формулу для определения числа вершин на уровне p результирующего графа F (обозначим его через kp): , здесь n - разрядность дискретного аттрактора F1, m - разрядность аттрактора F2, is - число вершин на уровне s в графе кодовых переходов F1, js - число вершин на уровне s в графе кодовых переходов F2.

Из этой формулы можно получить упрощенную формулу для финального уровня. Пусть iф - число вершин на финальном уровне в графе F1, jф - число вершин на финальном уровне в графе F2. Т. к. рассматривается финальный уровень, то очевидно, что равна количеству всех вершин в графе F1 (т. е. 2ⁿ). Таким образом второе слагаемое в общей формуле равно нулю. Очевидно, что в данном случае ip = iф, т. е. количество вершни в финальном уровне графа F1. Легко заметить, что в случае, когда p - финальный уровень, равна количеству всех вершин в графе F2 за исключением финального уровня. Следовательно, - число вершин в финальном уровне графа F2 (т. к. 2^m - общее число вершин графа F2). Таким образом .

Поэтому число вершин в финальном уровне графа F находится путем перемножения числа вершин в финальных уровнях исходных графов F1 и F2. Формула для нахождения числа вершин финального уровня графа F имеет следующий вид: kp = iф*jф, где iф - число кольцевых вершин графа F1, jф - число кольцевых вершин графа F2.

6. Структура с двумя операторами

Рассмотрим структуру с несколькими функциональными операторами.

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

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

Рисунок 14

Рисунок 15

7. Определение репеллера, типы репеллеров

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

...