Système dynamique séquentiel

Un système dynamique séquentiel (SDS) repose sur un graphe fini ${\displaystyle G}$, c'est-à-dire un ensemble de sommets pouvant être connectés deux à deux par des arêtes[A 1]. Chacun des sommets de ce graphe a un état, dans l'ensemble fini ${\displaystyle K}$. De plus, il existe pour chaque sommet ${\displaystyle v\in V(G)}$ une fonction ${\displaystyle F_{v}}$ qui met à jour l'état de ${\displaystyle v}$ selon l'état de sommets déterminés de ${\displaystyle V(G)}$. L'ensemble des mises à jour des états est ordonné par un mot ${\displaystyle w=(w_{1},...,w_{k}),w_{i}\in V(G)}$. Ainsi, un SDS est défini par le triplet ${\displaystyle (G,(F_{v})_{v},w)}$. Une fois l'ensemble des mises à jour effectué dans l'ordre donné par ${\displaystyle w}$, l'état du graphe a changé, ce qui se décrit formellement par ${\displaystyle [F_{G},w]:K^{n}\rightarrow K^{n}}$.

État du système étape par étape

État initial ${\displaystyle x}$ selon chacun des ${\displaystyle x_{i}}$, montrant l'ordre et les fonctions.

Application de ${\displaystyle F_{0}}$. L'état ${\displaystyle x_{0}}$ devient ${\displaystyle 1\cdot 1=1}$.

Application de ${\displaystyle F_{1}}$. L'état ${\displaystyle x_{1}}$ devient ${\displaystyle 1+1=1}$.

Application de ${\displaystyle F_{2}}$. L'état ${\displaystyle x_{2}}$ devient ${\displaystyle 1\oplus 1=0}$.

Application de ${\displaystyle F_{0}}$. L'état ${\displaystyle x_{0}}$ devient ${\displaystyle 1\cdot 0=0}$.

Application de ${\displaystyle F_{1}}$. L'état ${\displaystyle x_{1}}$ devient ${\displaystyle 0+0=0}$. Les états ne changent plus.

     

 

La définition d'un système dynamique séquentiel peut se faire en définissant successivement les éléments suivants : le graphe ${\displaystyle G}$ (quels sont les sommets et les arêtes), les états possibles ${\displaystyle K}$ des sommets, les fonctions mettant à jour les états, et l'ordre de mise à jour. Dans cet exemple, le graphe est formé de 3 sommets numérotés ${\displaystyle 0}$, ${\displaystyle 1}$ et ${\displaystyle 2}$, liés en un cycle. L'état ${\displaystyle x_{v}}$ de chacun des sommets ${\displaystyle v}$ est 0 ou 1, c'est-à-dire que ${\displaystyle K=\{0,1\}}$. Un graphe où chaque sommet peut prendre deux états est appelé réseau booléen. L'état de l'ensemble du système dynamique est donné par l'état de chacun des trois sommets, soit ${\displaystyle x=(x_{0},x_{1},x_{2})}$.

Pour mettre à jour les états des sommets, il existe trois fonctions ${\displaystyle F_{i}:K^{4}\rightarrow K^{4}}$. Concrètement, la fonction ${\displaystyle F_{i}}$ ne change que l'état du sommet ${\displaystyle i}$. Pour changer l'état, elle se fonde sur le voisinage du sommet. Par exemple, l'état peut être changé en appliquant une fonction logique sur les états des deux sommets voisins :

Un ordre possible de mise à jour consiste à exécuter tout d'abord ${\displaystyle F_{0}}$, puis ${\displaystyle F_{1}}$ et enfin ${\displaystyle F_{2}}$. Cet ordre est dénoté ${\displaystyle w=(0,1,2)}$, et est illustré ci-contre, partant de l'état ${\displaystyle x=(0,1,1)}$. La notation ${\displaystyle [F_{G},(0,1,1)]}$ consiste à appliquer les fonctions dans l'ordre donné par ${\displaystyle w}$ et à renvoyer le résultat une fois toutes les fonctions appliquées[Note 1]. Ainsi qu'illustré étape par étape, le résultat est ${\displaystyle [F_{G},(0,1,1)]=(1,1,0)}$. Formellement, appliquer la troisième fonction sur le résultat de la seconde, elle-même venant du résultat de la première, s'écrit ${\displaystyle [F_{G},(w_{0},w_{1},w_{2})]=F_{w_{2},G}\circ F_{w_{1},G}\circ F_{w_{0},G}}$. Appliquer une fonction ${\displaystyle F_{v}}$ est appelé mise à jour de l'état ${\displaystyle x_{v}}$, tandis qu'appliquer toutes les fonctions par ${\displaystyle [F_{G},w]}$ à partir d'un état ${\displaystyle x}$ est appelé mise à jour du système.

Espace des phases pour l'exemple du réseau booléen. Ainsi qu'illustré pas à pas, il y a une transition de 011 à 110.

Espace des phases en utilisant comme fonctions ${\displaystyle F_{0}(x_{0},x_{1},x_{2})=(x_{1}+x_{2},x_{1},x_{2})}$, ${\displaystyle F_{1}(x_{0},x_{1},x_{2})=(x_{0},x_{0}\cdot x_{2},x_{2})}$ et ${\displaystyle F_{2}(x_{0},x_{1},x_{2})=(x_{0},x_{1},x_{0}+x_{1})}$.

L'espace des phases décrit les transitions entre les différents états possibles du système. Il s'agit donc d'un graphe, où un sommet correspond à un état possible, et un arc va d'un sommet à un autre s'il existe une transition entre les deux états. Formellement, l'espace des phases est le graphe dirigé ${\displaystyle \Gamma }$. Chaque sommet ayant un état parmi ${\displaystyle K}$ possibles, l'ensemble des états correspond à toutes les combinaisons possibles d'états initiaux des ${\displaystyle n}$ sommets. Ainsi, ${\displaystyle V(\Gamma )=\{x\in K^{n}\}}$. L'ensemble des arêtes est donné en prenant comme source chacun des sommets (i.e., état possible) et comme destination son résultat par la mise à jour du système : ${\displaystyle E(\Gamma )=\{(x,[F_{G},w](x))|x\in V(\Gamma )\}}$. Le principal but des SDS est de « déduire autant d'informations que possible sur la structure de l'espace des phases ${\displaystyle \Gamma }$, selon les propriétés du graphe ${\displaystyle G}$, les fonctions ${\displaystyle (F_{v})_{v}}$, et l'ordre de mise à jour ${\displaystyle w}$ »[A 2].

(en) Henning S. Mortveit et Christian M. Reidys - An introduction to sequential dynamical systems, Springer, 2008, (ISBN 9780387498799).

• Portail de la physique
• Portail des mathématiques