Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Фазовое пространство последовательной динамической системы

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

Определение [ править ]

SDS состоит из следующих компонентов:

  • Конечный граф Y с множеством вершин v [ Y ] = {1,2, ..., n}. В зависимости от контекста граф может быть направленным или неориентированным.
  • Состояние х v для каждой вершины I из Y , взятой из конечного множества K . Состояние системы - это n -набор x = ( x 1 , x 2 , ..., x n ), а x [ i ] - набор, состоящий из состояний, связанных с вершинами в 1-окрестности i в Y (в фиксированном порядке).
  • Вершинная функция F I для каждой вершины I . Вершинная функция отображает состояние вершин я в момент времени т в состояние вершины в момент времени т  + 1 на основе состояний , связанных с 1-окрестности I в Y .
  • Слово w = ( w 1 , w 2 , ..., w m ) над v [ Y ].

Удобно ввести Y -локальные отображения F i, построенные из вершинных функций формулой

Слово w определяет последовательность, в которой составлены Y -локальные карты, чтобы получить последовательное отображение динамической системы F : K n → K n как

Если последовательность обновления представляет собой перестановку, часто говорят о SDS перестановки, чтобы подчеркнуть этот момент. Фазовое пространство , связанное с последовательной динамической системой с картой F : К п → К п есть конечный ориентированный граф с множеством вершин К п и направленные ребра ( х , Р ( х )). Структура фазового пространства определяется свойствами графа Y , вершинными функциями ( f i ) i и последовательностью обновления w. Большая часть исследований SDS стремится вывести свойства фазового пространства на основе структуры компонентов системы.

Пример [ править ]

Рассмотрим случай, когда Y - граф с множеством вершин {1,2,3} и неориентированными ребрами {1,2}, {1,3} и {2,3} (треугольник или 3-окружность) с состояниями вершин из К = {0,1}. Для вершинных функций используйте симметричную логическую функцию nor: K 3 → K, определенную как nor ( x , y , z ) = (1+ x ) (1+ y ) (1+ z ) с логической арифметикой. Таким образом, единственный случай, когда функция не возвращает значение 1, - это когда все аргументы равны 0. Выберите w = (1,2,3) в качестве последовательности обновления. Начиная с начального состояния системы (0,0,0) в момент времени t= 0 вычисляется состояние вершины 1 в момент времени t = 1 как nor (0,0,0) = 1. Состояние вершины 2 в момент времени t = 1 равно nor (1,0,0) = 0. Обратите внимание, что состояние вершины 1 в момент времени t = 1 используется немедленно. Затем получают состояние вершины 3 в момент времени t = 1 как nor (1,0,0) = 0. На этом последовательность обновления завершается, и делается вывод, что карта Nor-SDS отправляет состояние системы (0,0,0 ) в (1,0,0). Состояние системы (1,0,0) в свою очередь отображается в (0,1,0) приложением карты SDS.

См. Также [ править ]

Ссылки [ править ]