Réseaux d’automates, fonctions locales et configurations

Télécharger le fichier pdf d’un mémoire de fin d’études

Influence du mode de mise à jour

La façon dont les automates sont mis à jour au cours du temps a souvent un rôle cri-tique dans la dynamique d’un réseau. Nous pouvons le mettre en évidence avec l’exemple minimaliste suivant (que nous reprendrons à plusieurs reprises dans ce manuscrit). Ima-ginons un réseau simplement constitué de deux automates a et b, chacun avec une fonc-tion locale qui recopie l’état de l’autre automate. Si les deux automates commençaient dans deux états différents et étaient mis à jour simultanément de manière régulière (ce que l’on appelle un mode de mise à jour parallèle), alors la dynamique du système de-viendrait périodique. En effet, après la première série de mises à jour de a et b, les deux automates s’échangeraient leurs valeurs. Après la deuxième série de mises à jour, chacun reprendrait son état original avant de se l’échanger de nouveau à la troisième série de mises à jour, etc. Maintenant, imaginons que, sans changer la fréquence d’actualisation, la mise à jour de l’automate a soit légèrement en avance sur celle de b (ce que l’on ap-pelle un mode de mise à jour séquentiel). Alors l’automate a se mettrait dans l’état de b, effaçant à tous jamais l’information de son état de départ et le système entrerait dans une configuration stable (que l’on appelle point fixe) dont il ne pourrait pas sortir (quelle que soit la mise à jour).
En biologie, le mode de mise à jour est souvent perçu comme une incertitude de plus sur la dynamique du système. De nombreux travaux ont étudié l’influence du mode de mise à jour sur la dynamique d’un système [74, 112, 113] et les systèmes « robustes », dont la dynamique n’est pas ou peu affectée par le mode de mise à jour [11]. Une question, que l’on pourrait se poser dans ce contexte est la suivante. Est-ce que l’on peut déduire le mode de mise à jour d’un système à partir de sa dynamique ? Dans d’autres do-maines de l’informatique, la question de savoir s’il existe des calculs fondamentalement parallèles est une question ouverte (voir par exemple le problème ouvert « P=NC ? »). Ici, on peut se poser la question suivante. Est-ce qu’il existe des dynamiques intrinsèque-ment parallèles ? Autrement dit, est-ce qu’il est possible d’observer la dynamique d’un système et de se dire « Ceci n’est pas un système mis à jour de manière séquentielle. » ?
À l’inverse, quand on considère le réseau d’automates comme un objet que l’on peut concevoir et configurer comme on le souhaite pour obtenir une dynamique voulue, le mode de mise à jour peut se transformer en un outil intéressant. En effet, imaginons que l’on dispose d’un circuit imprimé dont chaque composant est un automate que l’on peut mettre à jour à volonté (avec un bouton poussoir par exemple). Alors, on pourrait « pro-grammer » notre circuit imprimé avec cette série de mises à jour, ce qui permettrait au circuit imprimé de pouvoir calculer plusieurs fonctions différentes. D’ici, on peut se poser plusieurs questions. Quel type de fonctions sont calculables par un tel circuit imprimé ? Que peut-on calculer de cette manière, et avec quelle efficacité ?
On peut analyser cette dernière problématique du point de vue de la simulation intrin-sèque, c’est-à-dire la simulation d’un réseau d’automates par un autre réseau d’automates. On peut voir une analogie entre la simulation intrinsèque d’un réseau d’automates et la réduction dans le domaine de la complexité algorithmique. En effet, pour convaincre quelqu’un qu’un problème de décision est difficile, on peut prouver que le résoudre per-met de résoudre un autre problème lui-même connu pour être difficile. De la même façon, pour prouver qu’un système est « complexe », on peut montrer qu’il en simule un autre qui lui-même est connu pour être complexe. Par exemple, il est bien connu que la famille des réseaux monotones booléens est universelle. En effet, pour chaque réseau booléen mis à jour en parallèle, on peut trouver un réseau booléen monotone qui le simule pas à pas.

Importance de l’alphabet

Enfin, une autre problématique intéressante, mais peu souvent abordée est celle du nombre d’états d’un réseau d’automates. Plus tôt, on a dit que l’on pouvait schématique-ment considérer qu’un gène pouvait avoir deux états : inhibé ou exprimé. Pourtant, des expériences montrent fréquemment des gènes pouvant se trouver dans des états intermé-diaires (voir par exemple la figure 3 de l’article de [104]). On pourrait répondre à cette objection que les réseaux booléens sont déjà suffisant à une simulation près. En effet, un automate non booléen peut toujours être représenté par plusieurs automates booléens. Cela dit, on peut se poser la question de la pertinence de cette simplification du point de vue des deux autres problématiques abordées. D’abord, cette représentation n’a pas forcément les mêmes propriétés de résilience aux variations du mode de mise à jour. En effet, un automate est un objet discret qui ne peut pas être mis à jour « à moitié » alors que sa représentation en deux automates si. Dans le cas extrême, si un réseau d’automate est composé d’un seul automate alors sa dynamique est parfaitement parallèle.
En outre, quand on regarde des propriétés fines (comme la proportion des bassins d’attractions par exemple), un réseau d’automates booléen ne permet pas de simuler par projection n’importe quel réseau d’automates de la même façon qu’on ne peut pas simuler le comportement d’un dé à trois faces en lançant une pièce un nombre fini de fois.
Enfin, quand le graphe d’interaction du réseau est fixé comme dans l’exemple du net-work coding, la taille de l’alphabet peut avoir une importance, et savoir pour quelle taille d’alphabet on peut obtenir une certaine propriété peut être une question pertinente.

Organisation du manuscrit

Après un chapitre 2 consacré à fixer des notations et à définir formellement les réseaux d’automates et les outils associés, le manuscrit est partagé en deux parties.
La partie I est consacrée tout entière à l’étude des problématiques liées aux graphes d’interaction des réseaux d’automates.
Dans le chapitre 3, on s’intéressera aux problèmes de déduire le nombre de points fixes d’un réseau admis par un certain graphe d’interaction. C’est un problème très classique mais on l’aborde d’un point de vue original : on veut déterminer la complexité algorith-mique de ce problème. On s’attachera à plusieurs variations de ce problème, par exemple en bornant le degré des graphes considérés où en faisant varier le nombre de points fixes recherchés. Selon la version considérée, on verra que le problème peut appartenir à plu-sieurs classes de complexité (certaines plutôt exotiques) allant de P à NEXPTIME.
Dans le chapitre 4, on s’intéressera à une propriété différente du nombre de points fixes d’un réseau : l’expansivité. Un réseau est expansif si, en partant d’une configuration initiale quelconque, on peut deviner cette configuration initiale simplement en observant l’évolution de n’importe quel automate du réseau pendant suffisamment longtemps. Il y a différentes manières d’interpréter cette propriété. L’une d’entre elle est de se dire que l’on a affaire à un système très chaotique, où la moindre différence locale entre deux configurations va avoir des répercussions globales sur la dynamique du système. Dans ce contexte, on caractérisera les graphes d’interaction qui admettent un réseau expansif sur un certain alphabet. On montrera qu’en plus du graphe d’interaction, une donnée très importante du problème est la taille de l’alphabet du réseau. On s’intéressera à des propriétés liées à l’expansivité comme le temps d’expansivité, la fréquence d’expansivité, etc.
La partie II est quant-à-elle consacrée au calcul séquentiel et à la simulation intrin-sèque. On va dire dans cette partie qu’un réseau d’automates en simule un autre s’il existe un mode de mise à jour séquentiel du premier réseau (l’état suivant est obtenu par la mise à jour séquentielle des automates selon un ordre prédéterminé) qui produit la même dynamique que le second réseau lorsqu’il est mis à jour en parallèle.
Dans le chapitre 5, on étudiera le problème de la simulation de réseaux mis à jour parallèlement par des réseaux mis à jour en séquentiel. On verra que les réseaux mis à jour séquentiellement ont un « désavantage » pour calculer certaines fonctions : ils doivent être plus grands. On va appeler ce nombre le coût de séquentialisation et on va essayer de borner ce coût le plus précisément possible. On mettra particulièrement en valeur le lien entre la taille de l’alphabet et ce coût.
Enfin, le chapitre 6 sera consacré a un cas un peu plus général où on s’autorise à mettre à jour autant de fois que désiré le même automate entre deux étapes de temps. On in-troduira dans un premier temps les réseaux d’automates complets. Ce sont des réseaux d’automates qui peuvent simuler tous les réseaux d’une certaine taille sur un certain al-phabet. On construira des réseaux complets de taille minimum ou minimisant le temps de simulation. Enfin, on s’intéressera à la simulation sans mémoire : on considère un réseau mis à jour en parallèle et on veut trouver un réseau qui le simule en étant exacte-ment de la même taille et en travaillant sur le même alphabet. On montrera que même en s’aidant de la répétition, il existe une infinité de réseaux impossibles à simuler dans ces conditions.
Pour clore ce document, on mettra en perspective les résultats obtenus dans le contexte des problématiques évoquées ici.

Mode de mise à jour, digraphe de transition et dynamique

Pour étudier la dynamique d’un réseau d’automates, on doit d’abord définir un mode de mise à jour qu’on peut représenter de la manière suivante. Entre deux étapes de temps discrètes t et t+1 que l’on peut observer, il va y avoir un certain nombre d’étapes intermé-diaires pendant lesquelles les coordonnées peuvent éventuellement être mises à jour. Un mode de mise à jour indique la liste des sous-étapes auxquelles chaque coordonnée est mise à jour. Plus précisément, dans cette thèse, on va se concentrer sur les modes de mise à jour déterministes périodiques. Un mode de mise à jour déterministe périodique pour un réseau de taille n peut toujours être représenté comme un vecteur W = (W1, . . . , Wt) avec W1, . . . , Wt ⊆ [n] (même si, dans certains cas ce n’est pas forcément une manière très succincte de les décrire). La dynamique d’un réseau avec le mode de mise à jour W peut alors être décrite par la fonction fW = fWt ◦ fWt−1 ◦ · · · ◦ fW1 .
Une sous-famille des modes de mise à jour déterministes périodiques W est la famille des modes de mise à jour bloc-séquentiels qui respectent les deux conditions suivantes. D’abord, les ensembles W1, . . . , Wt sont non nuls et disjoints et ensuite W1 ∪· · ·∪Wt = [n]. Une autre manière de formuler ceci est de dire que chaque coordonnée est mise à jour une et une seule fois entre deux étapes de temps.
Parmi les modes blocs-séquentiels, le mode de mise à jour le plus classique est proba-blement le mode de mise à jour parallèle (parfois appelé mode de mise à jour synchrone) où t = 1. En d’autre termes, on a W = [n] et la dynamique du réseau avec ce mode peut simplement être décrite par la fonction f.
Une autre sous-famille classique de modes de mise à jour blocs-séquentiels est la fa-mille des modes de mise à jour séquentiels où chaque ensemble Wi est de taille 1. Autre-ment dit, les coordonnées sont mises à jour une à la fois. On représentera chaque mode de mise à jour séquentiel par un mot w ∈ S[n] tel que W1 = {w1 }, . . . , Wn = {wn }. La fonction qui décrit la dynamique de f avec le mode de mise à jour séquentiel w est alors f w.
Enfin, dans le chapitre 6, on considèrera une généralisation des modes de mise à jour séquentiels qu’on appellera modes de mise à jour séquentiels avec répétition. Dans ce cas-là, entre deux étapes de temps, les coordonnées sont mises à jour une à la fois (|Wi| = 1 pour tout i), mais on s’autorise à mettre à jour autant de fois que voulu une même coordonnée. On pourra alors décrire ces modes de mise à jour par des mots w ∈ [n]∗.
Une manière classique de représenter la dynamique d’un réseau f ∈ F(n, q) avec un mode de mise à jour W est via son digraphe de transition f,W . Le digraphe de transition est un digraphe f,W = (An, A) où il y a un arc de x ∈ An vers y ∈ An si et seulement si fW (x) = y. Notons que chaque configuration a un seul arc sortant. Si W est le mode de mise à jour parallèle, on écrit simplement f
Enfin, un autre outil souvent utilisé pour étudier la dynamique d’un réseau f est son ˜ ˜ n digraphe de transition asynchrone f . Il s’agit d’un graphe f = (A , A) tel qu’il existe un arc de x ∈ An vers y ∈ An si et seulement s’il existe i ∈ [n] tel que fi(x) = y. Notons que chaque configuration a au plus n arcs sortants et que tous ses voisins sont à distance de Hamming au plus 1.
En guise d’exemple, considérons le réseau f ∈ F(2) défini par f : x 7→(x2, ¬x1). Sont représentés ci-dessous, dans l’ordre de gauche à droite, son digraphe d’interaction signé, et les graphes de transitions f , f,w avec w = (1, 2) et enfin le digraphe de transition asynchrone ˜f .

Notations relatives aux graphes d’interaction signés

On a déjà défini les graphes d’interaction signés ( GIS) dans la section 2.4 mais on va poser ici quelques notations supplémentaires. On rappelle qu’un GIS D = (V, A, σ) est un digraphe (V, A) associé à une fonction σ : A → {−1, 0, 1} qui donne un signe (négatif, positif ou nul) à chaque arc de D. Ce signe représente l’influence qu’a la valeur xi sur le résultat de fj(x). On écrit σij ou σa le signe de l’arc a = (i, j) ∈ A. Pour tout s ∈ {−1, 0, 1} et tout j ∈ V , on définit NDs(j) comme l’ensemble {i ∈ ND(j) | σij = s}. En outre, pour tout S ⊆ {−1, 0, 1}, NDS(j) = S NDs(j). Les notations précédentes sont illustrées dans la s∈S figure 3.1. Un graphe d’interaction simplement signé ( GISS) est un GIS qui ne contient aucun arc nul (i.e. ND0(j) = ∅ pour tout j ∈ V ). Pour i ∈ ND{−1,1}(j), on note σ˜ij = 0 si σij = −1 . 1 si σij = +1.

Problèmes de décision et classe de complexité

Une 3FNC ψ est une formule logique représentée à l’aide de n variables λ = {λ1, . . . , λn} et de m clauses µ = {µ1, . . . , µm}. Chaque clause µj est composée de 3 littéraux µj,1, µj,2, µj,3. Un littéral µj,γ est lui-même composé d’une variable λi ∈ λ et d’une polarité ρ ∈ {⊥, >}. Si ρ = > on dit que λi apparait positivement dans la clause µj et si ρ = ⊥ on dit qu’il apparait négativement. Une valuation de λ est une fonction v : λ → {⊥, >}.
On dit que v satisfait la clause µj s’il existe un littéral µj,γ = (λi, ρ) tel que v(λi) = ρ. On dit que v satisfait (ou est une solution de) la 3FNC ψ s’il satisfait toutes les clauses µj ∈ µ. Par abus de langage et pour simplifier la notation, on écrira souvent v(µj) = > (resp. v(ψ) = >) pour dire que v satisfait µj (resp. ψ). Sinon, on écrira v(µj) = ⊥ (resp. v(ψ) = ⊥). Pour tout b ∈ {0, 1}n, on notera vb : λ → {⊥, >} la valuation telle que vb(λi) = ⊥ si bi = 0 pour tout i ∈ [n].

Définitions et résultats préliminaires

Nous rappelons dans les sous-sections 4.2.1 et 4.2.1 quelques résultats classiques d’al-gèbre [99] et présentons les notations que nous allons utiliser par la suite. Nous présen-tons des résultats moins classiques dans la sous-section 4.3, et des résultats préliminaires dans les sous-sections 4.2.3 et 4.2.4.

Groupes et corps finis

Un groupe G est composé d’un ensemble E et d’une loi de composition ◦. La loi de composition ◦ est une application de E2 dans E. L’image de (a, b) ∈ E2 par ◦ se note a ◦b. De plus, la loi ◦ respecte trois propriétés :
• elle est associative : pour tout a, b, c ∈ E, (a ◦b) ◦c = a ◦(b ◦c) .
• elle possède un élément neutre : il existe un élément e ∈ E tel que, pour tout a ∈ E, a ◦e = e ◦a = a.
• elle est symétrique : pour tout a ∈ E, il existe b ∈ E tel que a ◦b = b ◦a = e.
Dans ce chapitre, on ne va travailler qu’avec des groupes finis. Plus précisément, l’en-semble E de définition de nos groupes sera souvent alphabet A = [0, q[.
Un morphisme entre un groupe G = (E, ◦) et un autre groupe G0 = (E0, ) est une application m : E → E0 qui respecte m(a ◦ b) = m(a) m(b). Un endomorphisme e du groupe G = (E, ◦) est un morphisme de G dans lui-même. Les endomorphismes de groupes ont certaines propriétés faciles à démontrer.
Proposition 2. Soit e un endomorphisme d’un groupe G = (E, ◦) d’élément neutre 0. Pour tout a ∈ E, on note le symétrique de a par a¯. L’endomorphisme e a les propriétés suivantes :
1. e(0) = 0 .
2. pour tout a ∈ E, e(¯a) = e(a).

Définitions et résultats préliminaires

Un groupe abélien A = (E, ⊕) (aussi appelé groupe commutatif ) est un groupe dont la loi de composition ⊕ est commutative sur E. En d’autres termes, pour tout a, b ∈ E, a ⊕ b = b ⊕ a. Dans la suite du chapitre, on notera 0 l’élément neutre d’un groupe abélien et −a le symétrique de a ∈ E. De plus, on notera simplement la loi de composition d’un groupe abélien + (et on utilisera P comme pour l’addition normale).
Un anneau (ring en anglais) R est composé d’un ensemble E, d’une loi d’addition ⊕ telle que le groupe (E, ⊕) est abélien et une loi de multiplication ⊗ qui respectent les propriétés suivantes :
• elle est associative .
• elle est distributive par rapport à la loi d’addition : pour tout a, b, c ∈ E, a ⊗(b ⊕c) = (a ⊗ b) ⊕ (a ⊗ c) ..
• elle possède un élément neutre (que l’on notera 1 dans la suite).
Similairement à l’addition, on simplifiera la notation a ⊗ b en ab.
Un corps fini (finite field en anglais) est un anneau (A, +, ∗) tel que le groupe (A\{0}, ∗) (avec 0 l’élément neutre de l’addition) est un groupe abélien. La taille q de l’alphabet d’un corps fini est toujours une puissance d’un nombre premier et un corps fini est toujours commutatif. On note souvent GF(q) un corps fini de cardinalité q. Quand q est premier, le corps fini GF(q) = (A, +, ∗) se comporte exactement comme Z/qZ. En d’autres termes, à un renommage des lettres près, les lois d’addition et de multiplication sont des simples additions et multiplications modulo q.
Considérons un groupe G = (A, +) et un anneau R = (A, +, ∗). Pour tout n ∈ N, on définit le groupe Gn = (An, ⊕) et l’anneau R n = (A,⊕, ⊗) comme suit. La loi d’addition ⊕ (resp. de multiplication ⊗) correspond à la loi + (resp. ∗) appliquée composante par composante. Par exemple, pour tout x, y ∈ An, x ⊕ y = (x1 + y1, . . . , xn + yn).
Dans la suite, plutôt que de dire que l’on considère un groupe, un anneau, etc. portant sur l’ensemble A, on dira souvent que A est doté des lois qui correspondent à la structure correspondante.

Table des matières

Introduction 
1.1 Présentation générale des réseaux d’automates
1.1.1 Modélisation de phénomènes naturels
1.1.2 Modèle de calcul
1.2 Problématiques
1.3 Organisation du manuscrit
2 Notations et définitions générales 
2.1 Intervalles, mots et permutations
2.2 Réseaux d’automates, fonctions locales et configurations
2.3 Graphes et digraphes
2.4 Digraphe d’interaction
2.5 Mode de mise à jour, digraphe de transition et dynamique
I Graphe d’interaction 
3 Complexité et points fixes 
3.1 Introduction
3.2 Définitions et notations
3.2.1 Notations relatives aux graphes d’interaction signés
3.2.2 Problèmes de décision et classe de complexité
3.3 k-Maximum Fixed Point Problem avec k = 1
3.4 k-Maximum Fixed Point Problem pour k 2
3.5 Maximum Fixed Point Problem
3.5.1 Avec (D) borné
3.5.2 Sans restriction sur (D)
3.6 Minimum Fixed Point Problem
3.7 Conclusion et perspectives
4 Expansivité 
4.1 Introduction
4.2 Définitions et résultats préliminaires
4.2.1 Groupes et corps finis
4.2.2 Matrice
4.2.3 Matrice d’adjacences et familles de réseaux d’automates
4.2.4 Trace et réseaux d’automates expansifs
4.3 Graphes d’interaction et expansivité
4.4 Graphes admettant un réseau expansif pour tout alphabet
4.5 Inexistence de réseaux expansifs
4.6 Temps d’expansion
4.7 La super-expansivité
4.8 Fréquence d’expansivité
4.9 Liens avec l’expansivité dans les réseaux d’automates cellulaires
4.10 Conclusion et perspectives
II Calcul séquentiel 
5 Coût de séquentialisation 
5.1 Introduction
5.2 Définitions et notations
5.3 Graphe de confusion
5.4 Coût de séquentialisation dans un certain ordre
5.5 Borne inférieure sur le coût de séquentialisation
5.6 Complexité procédurale
5.7 Graphe d’interaction
5.8 Conclusion et perspectives
6 Calcul séquentiel avec répétition 
6.1 Introduction
6.2 Définitions et notations
6.3 Réseau n-complet de temps minimum
6.4 Réseau n-complet de taille minimum
6.5 Réseau n, q-complet
6.6 Simuler un réseau sans mémoire
6.7 Conclusions et perspectives
7 Conclusion et perspective 

Télécharger le rapport complet