Études de la complexité algorithmique des réseaux d'automates

Contenu

Titre

Études de la complexité algorithmique des réseaux d'automates

Date

25 janvier 2022

Créateur

Kévin Perrot

Est référencé par

AJ936LCE

Résumé

Les réseaux d’automates modélisent toute dynamique discrète finie. Chaque automate possède un état, qui évolue en étapes de temps discrètes, selon l’état des autres
automates. La structure des interactions est décrite par un graphe et des fonctions
locales de transition. Une dynamique globale est obtenue avec un mode de mises à
jour, décrivant quels automates appliquent leur fonction locale pour changer d’état,
de façon déterministe ou non déterministe. Cette grande expressivité permet la modélisation de phénomènes observés dans la nature, où le paradigme du passage des
règles locales au comportement global capture l’essence des systèmes « complexes ».
Un réseau d’automates est encodé par les circuits (booléens) de ses fonctions locales. Puisque l’espace est fini, toute la dynamique peut être calculée. Nous proposons
une compréhension des variantes du modèle, à travers la caractérisation des complexités algorithmiques de problèmes : liés au calcul du graphe des interactions, liés
à la dynamique asymptotique d’un réseau d’automates donné, liés à la dynamique
asymptotique de tous les réseaux possibles sur une structure d’interactions donnée,
et liés à plusieurs modes de mises à jour. Il s’agira indirectement d’appréhender la
capacité à implémenter du calcul dans les différentes facettes du modèle.
Nous dégagerons des éléments clés sur la structure des interactions, le principe de
localité, l’importance des alphabets d’états, et les encodages. Ce travail aboutira à des
perspectives sur le long terme, guidées par l’extension d’informations partielles sur un
réseau, et l’énoncé de théorèmes « à la Rice » formulés grâce à la théorie des modèles.

Type

HDR

Editeur

Aix-Marseille Université

Langue

fr

uri

https://theses.hal.science/tel-03611794/document

Source

Zotero

Date de soumission

2 septembre 2023 à 04:18:56 +00:00

is compiled by

Lucky Semiosis

Complexité

233

Date de modification

19 avril 2024 à 08:41:19 +00:00

Détails de la complexité

dimension,niv (sujet),niv objet,sujet,objet,prédicat,nb,c

Physique,1,,,,,13,13

Physique,2,,,,,25,50

Actant,1,,,,,1,1

Actant,2,,,,,2,4

Concept,1,,,,,12,12

Concept,2,,,,,20,40

Rapport,1,1,Actant,Concept,properties,12,12

Rapport,1,1,Actant,Physique,values,12,12

Rapport,1,1,Actant,Physique,owner,1,1

Rapport,2,1,Actant,Physique,dcterms:isPartOf,2,4

Rapport,2,2,Actant,Concept,properties,20,40

Rapport,2,2,Actant,Physique,values,20,40

Rapport,1,1,Actant,Actant,dcterms:creator,1,1

Rapport,1,1,Actant,Actant,cito:isCompiledBy,1,1

Rapport,1,1,Actant,Physique,media,1,1

Rapport,1,1,Actant,Physique,uri,1,1

Totaux de la complexité

Physique,2,1,2,38,63

Actant,2,1,2,3,5

Concept,2,1,2,32,52

Rapport,10,1,2,71,113

Existence,16,1,2,144,233,

Collections

Zotero