Abstract FR:

Dans cette these, nous presentons quelques contributions a l'algorithmique sur des graphes d'automates, notamment pour le probleme dit d'election d'un chef, ainsi que pour l'etude de simulations d'un graphe par un autre, afin d'aider a eclaircir des questions de complexite. Un graphe d'automates est un graphe (regulier, infini) dont les sommets sont munis d'une copie d'un meme automate fini fixe. Les automates finis sont synchrones, leur alphabet d'entree est l'ensemble de d-uplets des etats des voisins, avec d le degre du graphe, et une configuration est la fonction donnant l'etat courant pour chaque sommet. L'election du chef consiste a trouver un ensemble d'etats et une fonction de transition de l'automate fini afin qu'a partir d'une configuration ou tous les sommets sont dans le meme etat, on aboutisse par iterations a une configuration ou un seul sommet est dans un etat special nomme chef, et les autres, dans des etats speciaux nommes soldats. Nous presentons des algorithmes pour quelques classes de graphes euclidiens et hyperboliques, en temps lineaire et en temps quadratique. Une simulation d'un graphe d'automates par un autre represente le fait de mimer son comportement, c'est-a-dire le fait de pouvoir envoyer le graphe d'evolution d'un des graphes sur celui de l'autre, bijectivement. Le graphe d'evolution est un graphe dont les sommets sont les configurations du graphe d'automates et les arcs donnent les iterations d'une configuration a une autre. Nous prouvons des liens d'equivalence entre l'existence des simulations de types particuliers et des proprietes d'isomorphisme de graphes, et donnons des simulations effectives pour une classe de graphes reguliers hyperboliques, en vue de l'etude d'une hierarchie de complexite.