Normal view MARC view ISBD view

Complexité structurelle et algorithmique des pavages et des automates cellulaires / par Julien Cervelle ; sous la direction de Bruno Durand

Auteur principal : Cervelle, Julien, 1977-, AuteurAuteur secondaire : Durand, Bruno, Directeur de thèseAuteur secondaire collectivité : Université de Provence, Etablissement de soutenanceType de document : ThèseLangue : français.Pays : France.Éditeur : [S.l.] : [s.n.], 2002Description : 1 vol. (95 p.) : fig. ; 30 cmBibliographie : Bibliogr. p. 91-93. Index.Sujet MSC : 68Q30, Computer science -- Theory of computing, Algorithmic information theory (Kolmogorov complexity, etc.)
68Q80, Computer science -- Theory of computing, Cellular automata
37B15, Dynamical systems and ergodic theory -- Topological dynamics, Cellular automata
97A70, Mathematics education - General, mathematics and education, Theses and postdoctoral theses
Note de thèse: Thèse de doctorat, informatique et mathématiques, 2002, Aix-Marseille 1
Tags from this library: No tags from this library for this title. Log in to add tags.
Current location Call number Status Date due Barcode
CMI
Salle S
Thèses CER (Browse shelf) Available 00869-01

Bibliogr. p. 91-93. Index

Thèse de doctorat informatique et mathématiques 2002 Aix-Marseille 1

Ce travail de thèse étudie la complexité des pavages et des automates cellulaires. L'analyse débute par des considérations structurelles : la quasipériodicité des pavages. A tout ensemble de tuiles qui pave le plan, on associe une fonction de quasipériodicité qui quantifie sa complexité. Tout d'abord, on montre que toute fonction "raisonnable" peut être capturée par un ensemble de tuiles et qu'il existe des pavages dont la fonction de quasipériodicité croît plus rapidement que n'importe quelle fonction récursive. Ensuite, on démontre un théorème de Rice pour les pavages : l'ensemble des ensembles de tuiles qui admettent les mêmes pavages qu'un autre fixé est indécidable et récursivement énumérable. Enfin, on transpose notre résultat dans le contexte des automates cellulaires. La seconde partie de notre travail concerne l'étude des automates cellulaires sous l'angle des systèmes dynamiques, et plus particulièrement des automates chaotiques. Les définitions usuelles classifiant les automates chaotiques ne sont pas satisfaisantes. Pour palier ce problème, on utilise deux nouvelles topologies. La première est dite de Besicovitch, et permet de supprimer la prédominance du motif central lors de l'étude de l'évolution de l'automate. On apporte plusieurs résultats, les premiers indiquant que notre nouvel espace de travail est acceptable à l'étude des automates cellulaires, en tant que systèmes dynamiques ; les seconds montrent que la notion de chaos subsiste, grâce à la définition de sensibilité aux conditions initiales, mais que les classes plus chaotiques sont vides. La seconde topologie employée est définie à l'aide de la complexité algorithmique. Le but de cette approche est d'avoir une distance qui traduit la facilité à calculer un élément à l'aide de l'autre. Nos résultats complètent les précédents. Ils attestent de manière formelle que les automates cellulaires ne peuvent pas modifier continûment l'information contenue dans une configuration, et surtout qu'ils sont incapables d'en créer

There are no comments for this item.

Log in to your account to post a comment.