" Soutenance de thèse de Diego MALDONADO. | Université d'Orléans

Université d'Orléans

Soutenance de thèse de Diego MALDONADO.

26/11/2018 - 13:30 - 26/11/2018 - 17:00

URL: http://www.univ-orleans.fr/actus/soutenances

Nom du contact: Etudes Doctorales

Courriel du contact: etudes.doctorales@univ-orleans.fr

Lieu: Amphi Herbrand - UFR Collegium Sciences et Techniques - Bâtiment 3IA - rue Léonard de Vinci - campus UNIVERSITÉ

Titre : Universalité et complexité des automates cellulaires coagulants.

Discipline : Informatique

ECOLE DOCTORALE MIPTIS

Résumé :

Les automates cellulaires forment une famille bien connue de modèles dynamiques discrets, introduits par S. Ulam et J. von Neumann dans les années 40. Ils ont été étudiés avec succès sous différents points de vue : modélisation, dynamique, ou encore complexité algorithmique. Dans ce travail, nous adoptons ce dernier point de vue pour étudier la famille des automates cellulaires coagulants, ceux dont l'état d'une cellule ne peut évoluer qu'en suivant une relation d'ordre prédéfinie sur l'ensemble de ses états. Nous étudions la complexité algorithmique de ces automates cellulaires de deux points de vue : la capacité de certains automates coagulants à simuler tous les autres automates cellulaires coagulants, appelée universalité intrinsèque, et la complexité temporelle de prédiction de l'évolution d'une cellule à partir d'une configuration finie, appelée complexité de prédiction. Nous montrons que malgré les sévères restrictions apportées par l'ordre sur les états, les automates cellulaires coagulants peuvent toujours exhiber des comportements de grande complexité. D'une part, nous démontrons qu'en dimension deux et supérieure il existe un automate cellulaire coagulants intrinsèquement universel pour les automates cellulaires coagulants en codant leurs états par des blocs de cellules ; cet automate cellulaire effectue au plus deux changements d'états par cellule. Ce résultat est minimal en dimension deux et peut être amélioré en passant à au plus un changement en dimensions supérieures. D'autre part, nous étudions la complexité algorithmique du problème de prédiction pour la famille des automates cellulaires totalistiques à deux états et voisinage de von Neumann en dimension deux. Dans cette famille de 32 automates, nous exhibons deux automates de complexité maximale dans le cas d'une mise à jour synchrone des cellules et nous montrons que dans le cas asynchrone cette complexité n'est atteinte qu'à partir de la dimension trois.