Système dynamique séquentiel

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
ArticlesToBeReadFirst v2.svg  Cette page se comprend mieux après la lecture de Théorie des graphes.

Un système dynamique séquentiel (SDS, « sequential dynamical system » en anglais) est un formalisme décrivant la façon dont l'état des sommets d'un graphe change en fonction de leurs voisins, dans un ordre donné. Par exemple, un ensemble de personnes peut être représenté par un graphe, où chaque personne est un sommet et deux personnes sont connectées lorsqu'elles sont en contact. Dans un problème d'épidémie, l’état de ces personnes peut correspondre à leur état de santé : sains ou infectieux. Leur état de santé dépend de leurs voisins : un individu est infecté si un de ses voisins est infecté. Si l'état de santé est mis à jour dans un ordre, alors la propagation de cette épidémie se modélise par un système dynamique séquentiel. La notion d'ordre, ou de séquence, est une différence essentielle par rapport à des formalismes tels que les automates cellulaires, où l'application de fonctions selon les voisins se fait en parallèle (i.e., tous les états sont mis à jour en même temps). Le but de ce formalisme est d'étudier les transitions entre les différents états possibles du système, c'est-à-dire l'espace des phases, selon le graphe, les fonctions, et l'ordre.

Définition[modifier | modifier le code]

Un système dynamique séquentiel (SDS) repose sur un graphe fini 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 K. De plus, il existe pour chaque sommet v \in V(G) un ensemble de fonctions (F_v)_v qui mettent à jour l'état de v selon l'état de sommets déterminés de V(G). L'ensemble des mises à jour des états est ordonné par un mot w = (w_1,...,w_k), w_i \in V(G). Ainsi, un SDS est défini par le triplet (G,(F_v)_v,w). Une fois l'ensemble des mises à jour effectué dans l'ordre donné par w, l'état du graphe a changé, ce qui se décrit formellement par [F_G,w] : K^n \rightarrow K^n.

Exemple : réseau booléen[modifier | modifier le code]

Articles connexes : Fonction logique et Réseau booléen.
État du système étape par étape
État initial x selon chacun des x_i, montrant l'ordre et les fonctions.
Application de F_0. L'état x_0 devient 1 \cdot 1 = 1.
Application de F_1. L'état x_1 devient 1 + 1 = 1.
Application de F_2. L'état x_2 devient 1 \oplus 1 = 0.
Application de F_0. L'état x_0 devient 1 \cdot 0 = 0.
Application de F_1. L'état x_1 devient 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 G (quels sont les sommets et les arêtes), les états possibles 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 0, 1 et 2, liés en un cycle. L'état x_v de chacun des sommets v est 0 ou 1, c'est-à-dire que 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 x = (x_0, x_1, x_2).

Pour mettre à jour les états des sommets, il existe trois fonctions F_i : K^4 \rightarrow K^4. Concrètement, la fonction F_i ne change que l'état du sommet 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 :

F_0(x_0,x_1,x_2) = (x_1 \cdot x_2, x_1, x_2), où \cdot représente la fonction ET
F_1(x_0,x_1,x_2) = (x_0, x_0 + x_2, x_2), où + représente la fonction OU
F_2(x_0,x_1,x_2) = (x_0, x_1, x_0 \oplus x_1), où \oplus représente la fonction OU exclusif

Un ordre possible de mise à jour consiste à exécuter tout d'abord F_0, puis F_1 et enfin F_2. Cet ordre est dénoté w = (0, 1, 2), et est illustré ci-contre, partant de l'état x = (0,1,1). La notation [F_G,(0,1,1)] consiste à appliquer les fonctions dans l'ordre donné par 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 [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 [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 F_v est appelé mise à jour de l'état x_v, tandis qu'appliquer toutes les fonctions par [F_G,w] à partir d'un état x est appelé mise à jour du système.

Espace des phases[modifier | modifier le code]

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
F_0(x_0,x_1,x_2) = (x_1 + x_2, x_1, x_2), F_1(x_0,x_1,x_2) = (x_0, x_0 \cdot x_2, x_2) et 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é \Gamma. Chaque sommet ayant un état parmi K possibles, l'ensemble des états correspond à toutes les combinaisons possibles d'états initiaux des n sommets. Ainsi, 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 : 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 \Gamma, selon les propriétés du graphe G, les fonctions (F_v)_v, et l'ordre de mise à jour w »[A 2].

Références[modifier | modifier le code]

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

  1. Préface.
  2. Chapitre 1 : What is a Sequential Dynamical System? p. 3-4

Notes[modifier | modifier le code]

  1. Par définition, appliquer les fonctions en suivant un ordre revient à définir un système séquentiel. Cependant, certaines fonctions peuvent être appliquées en parallèle : par exemple, deux fonctions se suivant dans l'ordre et n'utilisant pas les mêmes sommets peuvent être appliquées en même temps.