mardi 22 octobre 2024

par Nathalie BUTEL

Aymeric Picard Marchetto soutiendra sa thèse de doctorat le mardi 22 octobre à 14h00, salle 007 du bâtiment des Algorithmes.

 

La thèse intitulée « Isomorphisme de réseaux d'automates et son influence sur le graphe d'interaction » a été réalisée dans le pôle MDSC sous la direction de Adrien Richard.

 

Résumé :

Un réseau d'automates à n composantes sur un alphabet fini Q est un système dynamique discret décrit par l'itération successive d'une fonction f : Q^n -> Q^n. Dans la plupart des utilisations de ces réseaux, un paramètre important est le graphe d'interaction : un graphe sur les sommets de 1 à n ayant un arc de i vers j si fj(x) dépend de xi. Ce graphe d'interaction est en général plus facile à déterminer que la dynamique du réseau en elle-même, d'où découle une question importante : qu'est-ce que le graphe d'interaction nous apprend sur la dynamique du réseau ? Pour tenter de trouver des limites à cette question, on se pose ici la question inverse : que nous dit la dynamique sur le graphe d'interaction ? 
Pour cela, on étudie les réseaux à isomorphisme près. L'isomorphisme préserve la plupart des propriétés étudiées, mais ne préserve pas le graphe d'interaction. On va donc étudier G(f), l'ensemble des graphes d'interaction des réseaux isomorphes à f. 
On prouve notamment que Kn, le graphe d'interaction ayant tous les arcs, se trouve toujours dans G(f), qu'il est le seul à avoir cette propriété. Cela signifie que si Kn est le graphe d'interaction de f, il ne donne aucune information sur f à isomorphisme près. Réciproquement, on montre qu'il existe des réseaux f qui ne donnent aucune information sur leur graphe d'interaction : G(f) contient tous les graphes, sauf le graphe vide.