To see the other types of publications on this topic, follow the link: Automates cellulaires.
Dissertations / Theses on the topic 'Automates cellulaires'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Automates cellulaires.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Ollinger, Nicolas. "Automates cellulaires : structures." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2002. http://tel.archives-ouvertes.fr/tel-00007765.
Full textAbstract:
Les automates cellulaires fournissent un cadre agréable et uniforme pour aborder une des problématiques majeures de l'étude des «systèmes complexes» : comprendre comment et pourquoi des systèmes qui possèdent un comportement microscopique -- local -- facile à décrire peuvent avoir un comportement macroscopique -- global -- beaucoup plus compliqué. Depuis leur introduction dans les années 40, de nombreux travaux ont été entrepris afin de comprendre les liens existant entres les propriétés locales et globales des automates cellulaires.<br /><br />Ces vingt dernières années est apparue une nouvelle approche à travers la recherche de classifications pertinentes des automates cellulaires. Ainsi, de nombreuses classifications formelles ont été proposées pour mieux cerner les comportements de type «chaotique», principalement à l'aide d'outils de nature topologique. Cependant, une autre forme d'automates cellulaires complexes -- les automates cellulaires pour lesquels semblent émerger des structures locales, des particules, qui interagissent selon des schémas complexes -- reste peu étudiée. A notre connaissance, seuls les travaux d'I. Rapaport proposent une classification -- le groupage -- de nature algébrique, inspirée par cette forme de complexité. Nos travaux consistent en la généralisation de cette classification, afin d'une part de prendre en compte certaines notions intéressante comme l'universalité intrinsèque et d'autre part de renforcer la structure algébrique qui fait la force de cet outil -- tout en conservant sa nature géométrique.<br /><br />Dans une première partie, la structure interne des automates cellulaires est étudiée et une nouvelle caractérisation des automates cellulaires de dimension donnée est proposée, mettant en avant la notion de sous-automate. Dans une deuxième partie, les transformations «géométriques» des automates cellulaires sont caractérisées et un modèle de groupage abstrait est défini. Fort de ces deux outils et de la notion de sous-automate, une première extension du groupage est définie. La pertinence de cette classification est illustrée par l'étude de familles classiques d'automates cellulaires dans ce cadre. L'absence de structure de treillis en sus de la structure de pré-ordre amène l'introduction d'une nouvelle généralisation qui induit une structure de demi-treillis par l'opération de produit cartésien. Des liens entre les idéaux de cette structure et des problèmes de décision sont mis en avant. L'objet de la troisième partie est la notion d'automate cellulaire intrinsèquement universel, qui joue un rôle privilégié dans le cadre du groupage généralisé. L'indécidabilité de l'appartenance à cette famille d'automates cellulaires est établie et deux exemples de petits automates cellulaires de dimension 1 intrinsèquement universels sont construits, dont un automate cellulaire à 6 états et voisinage de von Neumann, le plus petit connu à ce jour.
2
Ollinger, Nicolas Delorme Marianne Mazoyer Jacques. "Automates cellulaires structures /." (s.l.) : (s.n.), 2002. http://tel.ccsd.cnrs.fr/tel-00007765.
Full text
3
Yunès, Jean-Baptiste. "Automates Cellulaires; Fonctions Booléennes." Habilitation à diriger des recherches, Université Paris-Diderot - Paris VII, 2007. http://tel.archives-ouvertes.fr/tel-00200440.
Full textAbstract:
Sont présentés les différents travaux que j'ai pu effectuer: dans le domaine des automates cellulaires et de leur programmation, puis les travaux portant sur les fonctions Booléennes et leur complexité.
4
DURR, CHRISTOPH. "Automates cellulaires quantiques finis." Paris 11, 1997. http://www.theses.fr/1997PA112096.
Full textAbstract:
Feynman a propose en 1982 de concevoir un ordinateur quantique - eventuellement sous forme d'automate cellulaire - qui serait base sur la mecanique quantique pour permettre de simuler efficacement des systemes physiques quantiques, car pour les ordinateurs (actuels) classiques on ne connait que des simulations a sur-cout exponentiel. Actuellement l'interet principal des ordinateurs quantiques provient du resultat de shor de 1994, qui montre qu'un ordinateur quantique peut factoriser efficacement des nombres, ce qui rend potentiellement vulnerable le systeme de cryptographie rsa. Dans cette these nous generalisons formellement au calcul quantique le modele des automates cellulaires finis (restreints aux configurations a support fini). Nous fournissons un algorithme cubique qui decide si une instance du modele est valide, c'est-a-dire si l'operateur global d'evolution associe a une fonction de transition locale donnee est unitaire. Ce probleme est l'analogue d'un probleme classique tres etudie, mais la solution que nous proposons utilise de nouvelles techniques. Nous comparons egalement notre modele aux automates cellulaires quantiques restreints aux configurations periodiques. Finalement nous presentons un algorithme quantique pour la recherche du minimum dans un tableau.
5
Provillard, Julien. "Automates cellulaires non-uniformes." Nice, 2012. http://www.theses.fr/2012NICE4082.
Full textAbstract:
Les automates cellulaires (CA) sont des systèmes dynamiques discrets très utilisés dans de nombreux domaines scientifiques. Leurs principales caractéristiques sont d’agir de manière locale, synchrone et uniforme sur l’ensemble des cellules d’une grille régulière. Ces systèmes produisent une grande variété de dynamiques et ont été largement étudiés dans la littérature. De nombreuses variantes ont été proposées. Dans ce travail de thèse nous nous intéresserons aux automates cellulaires non-uniformes (nu-CA). Il s’agit, essentiellement, d’automates cellulaires dans lesquels la contrainte d’uniformité a été relâchée. Dans un premier temps, nous considérerons une famille de nu-CA qui permet de représenter des perturbations dans la structure d’un CA. Il s’agit d’étudier l’influence d’une panne ou d’une erreur ponctuelle dans l’implémentation d’un CA et notamment son influence sur la dynamique. Nous verrons que de nombreuses propriétés ne sont pas stables (à l’exception notable de l’équicontinuité) mais que l’on peut alors établir des liens entre un CA et ses modèles de perturbation. Dans une seconde partie, nous cherchons à déterminer les propriétés que peut avoir un nu6CA en fonction des comportements locaux que l’on peut observer. On se donne un ensemble de règles locales qui peuvent intervenir dans un nu-CA et nous nous intéressons à la façon d’agencer ces règles pour produire certaines propriétés dans l’automate induit. Nous associons alors, à chacune de ces propriétés, un langage de distributions que nous caractérisons) à l’aide de la théorie des langages<br>Cellular automata (CA) are discrete dynamical systems widely used in many scientific domains. Their main characteristic is to act locally, synchronously and uniformly on a regular set of elementary components called cells. These systems have a huge variety of dynamical behaviours and have been extensively studied in literature. Several variants have been proposed. In this work we are interested in non-uniform cellular automata (nu-CA). They are, essentially, CA in which the uniformity constraint has been relaxed. In the first part, we study a family of nu6CZA which allows to easily representing perturbations of the structure of a CA. The idea is to study the impact of the dynamics of failure or of an error in the physical implementation of a CA by electronic components. Indeed, we will prove that several dynamical properties are not structurally stable (except for the equicontinuity property). However, we will show how to link properties of a CA and its “perturbed” versions. In the second part, we try to infer the global properties of a nu-CA from the local behaviours we can observe. Given a set of local rules which can appear in a given nu-CA, we study the way of mowing them to obtain given global behaviours. Moreover, we associate global properties with peculiar formal languages and we completely characterize these formal languages. In this way we obtain a natural notion of complexity for properties on nu-CA. A property is a complex as the class of languages from which it is characterizes
6
Nouvel, Bertrand. "ROTATIONS DISCRETES ET AUTOMATES CELLULAIRES." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2006. http://tel.archives-ouvertes.fr/tel-00444088.
Full textAbstract:
Dans un espace discret, comme l'ensemble des points à coordonnées entières, la modélisation de l'isotropie pose des difficultés théoriques notables. À ce jour, aucune théorie géométrique sur $\ZZ^n$ n'est apte à rendre compte de l'isotropie telle qu'elle est décrite par la géométrie euclidienne. Dans l'optique de contribuer à cette problématique, nous nous intéressons à la conception d'algorithmes capables de donner aux rotations discrètes des propriétés proches de celles de la rotation euclidienne. Ces algorithmes doivent de plus fonctionner à base d'arithmétique entière. Après avoir montré la non-existence de rotation discrète transitive sur $\ZZ^n$, nous introduisons un codage de rotations discrètes que nous relions à la fois à la dynamique symbolique et aux automates cellulaires. Il s'agit alors de mener une étude locale des rotations discrètes. Cette étude se situe au carrefour entre géométrie discrète et systèmes dynamiques symboliques. La pertinence des configurations obtenues est justifiée par l'existence de transducteurs planaires capables d'effectuer des rotations à partir des configurations. Ensuite, afin de réinterpréter ces configurations dans le cadre de la théorie des systèmes dynamiques, nous étendons des notions classiques de cette théorie à la dimension 2. Pour la rotation discrétisée, la dynamique symbolique associée est conjuguée avec un jeu de deux translations orthogonales sur un tore bidimensionnel. Après analyse, nous constatons que les configurations obtenues sont des superpositions de configurations de faible complexité. Cela évoque alors les généralisations planaires des mots sturmiens étudiées entre autres par Valérie Berthé et Laurent Vuillon. Des résultats analogues sont aussi obtenus pour les rotations $3$-transvections. L'analyse les rotations discrètes par le biais de systèmes dynamiques a permis de nombreux résultats : mise en évidence de la quasipériodicité des configurations, calcul de la fréquence des symboles, caractérisation des rotations discrétisées bijectives, ce qui est aussi la réciproque du théorème d'Éric Andrès et Marie-Andrée Jacob. Nous avons aussi étudié les discontinuités du processus de rotation. Ces discontinuités ont lieu pour des angles issus d'un sous-ensemble des angles quadratiques (i.e. les angles charnières). En combinant ces remarques, nous aboutissons à deux algorithmes. Le premier algorithme réalise des rotations sans faire aucun calcul à virgule flottante et sans calculer aucun sinus ni aucun cosinus. Il fonctionne de manière incrémentale et en ordre de complexité optimal. Le second algorithme est une implémentation de la rotation $3$-transvections sur automates cellulaires. D'autres pistes pour la conception d'algorithmes sont mentionnées dans la thèse. En outre, nous nous intéressons aussi aux méthodes substitutives qui engendrent les configurations de rotations. Pour les angles quadratiques, nous montrons que les configurations de rotations sont des entrelacements de configurations autosimilaires; et nous présentons le schéma d'une approche basée sur les graphes de Rauzy pour l'inférence de substitutions planaires. En combinant ces deux approches, nous mettons en avant les éléments essentiels de la démonstration de l'autosimilarité de $C_{\pi/4}$. Les applications potentielles de cette thèse concernent à terme l'implémentation d'algorithmes de rotations pour processeurs graphiques. Elle contribue aussi à l'étude des méthodes algorithmiques pour la modélisation physique en milieu discret de phénomènes isotropes.
7
Chemlal, Rezki. "Valeurs propres des automates cellulaires." Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00794398.
Full textAbstract:
On s'intéresse dans ce travail aux automates cellulaires unidimensionnels qui ont été largement étudiés mais où il reste beaucoup à faire. La théorie spectrale des automates cellulaires a notamment été peu abordée à l'exception de quelques résultats indirects. On cherche a mieux comprendre les cadres topologiques et ergodiques en étudiant l'existence de valeurs propres en particulier celles irrationnelles c'est à dire de la forme e^{2Iπα} où α est un irrationnel et I la racine carrée de l'unité. Cette question ne semble pas avoir été abordée jusqu'à présent. Dans le cadre topologique les résultats sur l'équicontinuité de Kůrka et Blanchard et Tisseur permettent de déduire directement que tout automate cellulaire équicontinu possède des valeurs propres topologiques rationnelles. La densité des points périodiques pour le décalage empêche l'existence de valeurs propres topologiques irrationnelles. La densité des points périodiques pour l'automate cellulaire semble être liée à la question des valeurs propres. Dans le cadre topologique, si l'automate cellulaire possède des points d'équicontinuité sans être équicontinu, la densité des points périodiques a comme conséquence le fait que le spectre représente l'ensemble des racines rationnelles de l'unité c'est à dire tous les nombres de la forme e^{2Iπα} avec α∈Q .Dans le cadre mesuré, la question devient plus difficile, on s'intéresse à la dynamique des automates cellulaires surjectifs pour lesquels la mesure uniforme est invariante en vertu du théorème de Hedlund. La plupart des résultats obtenus demeurent valable dans un cadre plus large. Nous commençons par montrer que les automates cellulaires ayant des points d'équicontinuité ne possèdent pas de valeurs propres mesurables irrationnelles. Ce résultat se généralise aux automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman. Nous démontrons finalement que les automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman possèdent des valeurs propres rationnelles
8
Guillon, Pierre. "Automates cellulaires : dynamiques, simulations, traces." Phd thesis, Université Paris-Est, 2008. http://tel.archives-ouvertes.fr/tel-00432058.
Full textAbstract:
Un automate cellulaire est un système dynamique discret qui modélise des objets ayant une évolution parallèle synchrone: l'espace est divisé en cellules ayant chacune un état et qui évoluent toutes selon une même règle locale, qui ne dépend que d'un nombre fini de cellules voisines. Malgré la simplicité de la formalisation de ce système, des comportements très complexes peuvent apparaître, qui en font notamment un modèle de calcul. Cette complexité a été rattachée à diverses théories: topologie, mesure, décidabilité, information...Nous adoptons ici une approche basée sur la dynamique symbolique, c'est à dire l'étude des mots infinis sur un alphabet donné auxquels on applique un décalage, suppression de la première lettre. À chaque automate cellulaire peut en effet être associé son tracé, l'ensemble des mots infinis représentant la séquence des états successifs pris par la cellule centrale de l'espace - ou un groupe de cellules centrales. On a alors une factorisation topologique: la lecture d'une lettre dans un de ces mots correspond exactement à une étape de l'évolution de l'automate. De nombreuses propriétés topologiques sont alors transmises par cette factorisation. Inversement, le fait que les cellules évoluent toutes de la même manière permet de déduire certaines propriétés de l'automate à partir de celles de son tracé. La première partie de la thèse est consacrée à ces nombreux liens. Une deuxième partie présente des conditions suffisantes pour qu'un ensemble de mots infinis soit le tracé d'un automate cellulaire. Enfin, une troisième partie donne un point de vue plus informatique, en récapitulant les principaux résultats d'indécidabilité sur le sujet et en prouvant que toutes les propriétés du tracé qui peuvent se voir infiniment tard sont indécidables
9
Durand, Bruno. "Automates cellulaires : réversibilité et complexité." Lyon 1, 1994. http://www.theses.fr/1994LYO10030.
Full textAbstract:
Nous etudions les automates cellulaires depuis plusieurs points de vue. Nous commencons par les envisager comme des systemes dynamiques et presentons une nouvelle preuve d'un resultat celebre du a richardson: les automates cellulaires sont exactement les fonctions continues qui commutent avec les translations. Cette preuve nous permet d'etudier la minimisation de la representation des automates cellulaires. Ensuite, nous presentons une classification des automates cellulaires en fonction de leur comportement limite, classification que nous prouvons etre partiellement decidable en dimension 1. Nous montrons aussi une extension en termes de probabilites d'un theoreme du a karel culik en 1989. Les methodes utilisees relevent de la topologie et de la combinatoire. La deuxieme partie est plus tournee vers l'algorithmique et la complexite. Nous y presentons deux reductions de problemes de pavages en problemes concernant les automates cellulaires. A l'aide de ces reductions, nous montrons simplement que la surjectivite des automates cellulaires est indecidable en dimension deux (theoreme du a jarkko kari en 1989) ainsi que la co-np-completude et la co-np-completude en moyenne des problemes de decision suivants: - etant donne un automate cellulaire en dimension 2, est-il bijectif quand il est restreint aux configurations finies plus petites que sa taille? - etant donne un automate cellulaire en dimension 2, est-il bijectif quand il est restreint aux configurations periodiques de periode inferieure a sa taille?
10
Tisseur, Pierre. "Aspects ergodiques des automates cellulaires." Aix-Marseille 2, 1999. http://www.theses.fr/1999AIX22006.
Full textAbstract:
Dans cette these nous etudions deux aspects ergodiques de la dynamique des automates cellulaires unidimentionnels et bilateres. Dans la premiere partie nous cherchons a affiner la notion d'exposant de lyapounov pour ces automates. Une premiere proposition de definition de ces exposants a ete realisee par m. Shereshevsky et parut dans j. Nonlinear sci. En 1992. Ces exposants (droits et gauches) sont definis relativement a une mesure ergodique pour l'automate cellulaire. Nous montrons qu'en prenant les memes definitions pour ces exposants mais en posant comme condition que la mesure soit invariante par l'automate et que cette mesure soit ergodique pour le shift il est possible de prouver l'existence de ces exposants et de montrer une inegalite entre d'une part l'entropie metrique de l'automate cellulaire et d'autre part le produit de l'entropie metrique du shift par la somme des exposants de lyapounov droit et gauche. Il est a remarquer que l'on dispose de beaucoup plus d'exemples de couples (automates cellulaires, mesures) pour lesquels la mesure est invariante par l'automate et ergodique pour le shift que de mesure ergodique pour l'automate cellulaire et invariante par le shift. Ensuite tout en conservant les memes conditions sur la mesure, nous introduisons des exposants de lyapounov (droits et gauches) denommes moyens car ils se definissent a partir de moyennes ergodiques et non pas comme des valeurs maximales sur l'orbite du shift des points. On montre que ces nouveaux exposants sont plus petits ou egaux aux premiers exposants que l'on peut qualifier de maximaux et que le produit de la somme de ces deux exposants par l'entropie metrique du shift est encore un majorant de l'entropie metrique de l'automate cellulaire. Une propriete remarquable des exposants moyens est de s'annuler lorsqu'il existe des points d'equicontinuite dans le support de la mesure. Les exposants de lyapounov maximaux ne partagent pas cette propriete comme nous le montrons dans deux exemples. Puis remarquant qu'il est toujours possible de definir les exposants de lyapounov maximaux pour la mesure uniforme nous montrons que le produit de ces exposants par l'entropie du shift est un majorant de l'entropie topologique de l'automate cellulaire. La seconde partie est une etude des liens existant entre la notion d'equicontinuite et l'existence de mesures invariantes par l'automate cellulaire. Le resultat principal est le suivant : si une mesure est ergodique pour le shift et qu'un automate cellulaire possede des points d'equicontinuite dans le support topologique de cette mesure alors la suite des mesures images par l'automate cellulaire de cette mesure est convergente. Nous donnons une expression asymptotique de cette mesure limite. Ensuite nous finissons par une etude du support topologique de la mesure limite.
11
Nouvel, Bertrand. "Rotations discrètes et automates cellulaires." Lyon, École normale supérieure (sciences), 2006. http://www.theses.fr/2006ENSL0370.
Full text
12
Tougne, Laure. "Cercles discrets sur automates cellulaires." Lyon, École normale supérieure (sciences), 1997. http://www.theses.fr/1997ENSL0049.
Full textAbstract:
Dans cette these, nous etudions le probleme suivant: comment engendrer en temps reel des cercles discrets par automates cellulaires ? il existe, dans la litterature, plusieurs definitions de cercles discrets. Leur etude nous permet tout d'abord de mettre en evidence le fait que, dans le premier octant, un cercle discret est compose de segments verticaux dont les extremites appartiennent a des faisceaux de paraboles discretes. Nous observons alors que construire ces faisceaux par automate cellulaire permet d'engendrer simultanement une famille de cercles discrets. Dans un premier temps, nous nous interessons a une nouvelle discretisation tres proche de celle de pitteway, qui consiste a considerer une famille de paraboles discretes obtenue par passage au plancher d'une famille de paraboles reelles. Nous mettons tout d'abord en evidence des automates cellulaires construisant des parties de ce faisceau a partir d'autres parties, dependant elles-memes de la possibilite de construire les premieres. Ensuite, nous montrons la construction d'un automate unique engendrant ce faisceau des paraboles discretes. La justification de ces constructions necessite une recurrence compliquee. Nous decrivons alors l'automate qui construit les cercles plancher. Ensuite, nous generalisons la construction precedente a d'autres familles de cercles discrets. La premiere consideree est celle des cercles plafond. Dans ce cadre, nous montrons comment passer du faisceau de paraboles plancher au faisceau des paraboles plafond. Par ailleurs, grace a une technique purement liee aux automates cellulaires (le groupage de cellules), nous montrons la possibilite de construire par automates cellulaires tous les cercles discrets raisonnables. Nous completons ce resultat en etudiant la reconnaissance de cercles discrets par automates cellulaires
13
Martin, Bruno. "Automates cellulaires, information et chaos." Lyon, Ecole normale supérieure, 2001. http://www.theses.fr/2001ENSL0177.
Full textAbstract:
En nous appuyant sur les classifications des automates cellulaires deja proposees, nous affinons la plus elaboree. Grace a une mesure sur l'ensemble des classifications et a une pseudo-distance invariante par decalage, nous introduisons la notion de -sensibilite aux conditions initiales. Cela permet de montrer que certaines regles sont a la fois chaotiques et non chaotiques selon la configuration de depart. Nous introduisons egalement la notion d'entropie apparente qui exprime pourquoi en observant l'evolution d'un automate cellulaire, on la ressent comme complexe. Enfin, nous poursuivons l'etude des classifications algebriques existantes en mettant en evidence une loi de conservation des particules dans la regle 54 de wolfram.
14
Durand-Lose, Jérôme. "Automates Cellulaires, Automates à Partitions et Tas de Sable." Phd thesis, Université Sciences et Technologies - Bordeaux I, 1996. http://tel.archives-ouvertes.fr/tel-00548830.
Full textAbstract:
Cette thèse s'intéresse dans un premier temps aux automates cellulaires réversibles, et dans un second temps aux tas de sable linéaires. Nous construisons diverses simulations reliant les automates cellulaires aux automates à partitions, en particulier celle des automates cellulaires réversibles par les automates à partitions réversibles, ce qui était une conjecture depuis 1990. Par des constructions successives, nous montrons que le ``Billiard ball model'' de Toffoli et Margolus est capable de simuler tous les automates à partitions réversibles de dimension 2. En rassemblant ces résultats, nous montrons qu'il existe des automates cellulaires réversibles capables de simuler tous les automates cellulaires réversibles de même dimension. Dans un espace linéaire, ``Tas de sable'' et ``Chip firing game'' sont équivalents. Nous portons notre attention sur le cas où les grains tombent un à un. Des motifs délimités par des signaux apparaissent au sein des configurations engendrées. Nous étudions la dynamique du système et démontrons un équivalent asymptotique. Nous étendons nos méthodes et nos résultats à d'autres types de configurations initiales. Dans chaque cas étudié, le temps parallèle est inférieur au temps séquentiel dans un rapport de l'ordre du nombre de piles mises en œuvre.
15
Besson, Tom. "Discrétisation automatique de machines à signaux en automates cellulaires." Thesis, Orléans, 2018. http://www.theses.fr/2018ORLE2009/document.
Full textAbstract:
Dans le contexte du calcul géométrique abstrait, les machines à signaux ont été développées comme le pendant continu des automates cellulaires capturant les notions de particules, de signaux et de collisions. Une question importante est la génération automatique d’un automate cellulaire reproduisant la dynamique d’une machine à signaux donnée. D’une part, il existe des conversions ad hoc. D’autre part, ce n’est pas toujours possible car certaines machines à signaux présentent des comportements « continus ». Par conséquent, la discrétisation automatique de telles structures est souvent complexe et pas toujours possible. Cette thèse propose trois manières différentes de discrétiser automatiquement les machines à signaux en automates cellulaires, avec ou sans approximation possible. La première s’intéresse à une sous-catégorie de machines à signaux, qui présente des propriétés permettant d’assurer une discrétisation automatique exacte pour toute machine de ce type. La deuxième est utilisable sur toutes les machines mais ne peut assurer ni l’exactitude ni la correction du résultat. La troisième s’appuie sur une nouvelle expression de la dynamique d’une machine à signaux pour proposer une discrétisation. Cette expression porte le nom de modularité et est décrite avant d’être utilisée pour discrétiser<br>In the context of abstract geometrical computation, signal machines have been developed as a continuous counter part of cellular automata capturing the notions of particles, signals and collisions. An important issue is the automatic generation of a cellular automaton mimicking the dynamics of a given signal machine. On the one hand, ad hoc conversions exist.On the other hand, it is not always possible since some signal machines exhibit “purely continuous” behaviors. Therefore, automatically discretizing such structures is often complicated and not always possible. This thesis proposes different ways to automatically discretize signal machines into cellular automata, both with and without handling the possiblity of approximation.The first is concerned with a subcategory of signal machines, which has properties ensuring an exact automatic discretization for any machine of this type. The second is usable on all machines but cannot guarantee the exactness and correction of the result. The third is based on a new expression of the dynamics of a signal machine to propose a discretization.This dynamical expression takes the name of modularity and is described before being used to discretize
16
Reimen, Nicolas. "Contribution à l'étude des automates cellulaires." Paris 7, 1993. http://www.theses.fr/1993PA077335.
Full textAbstract:
Un automate cellulaire, dans sa forme la plus generale, est un ensemble infini d'automates finis interconnectes suivant un reseau regulier et evoluant de facon synchrone au cours du temps. Issus des travaux de john von neumann sur l'auto-reproduction (1950), ils ont connu, ces dernieres annees un nombre croissant d'applications en informatique et en physique theorique. Ce travail est subdivise en trois chapitres: une presentation generale couvrant l'essentiel de l'etat actuel de la recherche au sujet des a. C. Dans le domaine de l'informatique theorique, la presentation d'une preuve originale du theoreme d'acceleration lineaire pour les a. C. Unidimensionnels accepteurs de langages et une derniere partie consacree a un modele derive des a. C. : les automates treillis. Cette partie contient, notamment, l'etude, par des moyens algebriques, de la classe particuliere des automates treillis superposables
17
Theyssier, Guillaume. "Automates cellulaires : un modèle de complexités." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2005. http://tel.archives-ouvertes.fr/tel-00166295.
Full textAbstract:
Nous étudions le modèle des automates cellulaires en adoptant successivement deux points de vue --celui des représentations syntaxiques locales puis celui des dynamiques globales-- et en cherchant à établir des liens entre eux par différentes approches ou outils --algébrique, combinatoire, et de la théorie de la calculabilité. Au cours de notre étude de la structure des règles de transition locales, nous introduisons une nouvelle classe d'automates (appelés automates cellulaires captifs) définie par une contrainte locale très simple. Nous établissons une loi 0-1 sur cette classe qui a pour corollaire que presque tous les automates cellulaires captifs sont intrinsèquement universels. En revanche, nous montrons qu'il est indécidable de savoir si un automate cellulaire captif est intrinsèquement universel ou pas. Dans une seconde partie, nous poursuivons l'étude des automates cellulaires en cherchant au contraire à nous affranchir le plus possible de leur représentation syntaxique pour insister sur leurs propriétés dynamiques globales. Notre problématique devient celle de la classification et de l'étude de notions de complexité selon ce point de vue global. L'outil fondamental est celui de simulation. Nous étendons les résultats de N. Ollinger sur les structures de pré-ordre (nouvelles relations de simulations et nouvelles propriétés induisant des structures d'idéal ou de filtre) et étudions également l'effet du produit cartésien sur ces structures. Nous établissons une construction qui peut s'interpréter comme un produit cartésien limite et nous permet d'exhiber des chaînes infinies croissantes de longueur omega+omega dans l'un des pré-ordres étudiés. Enfin, nous nous intéressons aux dynamiques séquentielles et aux automates cellulaires universels pour le calcul Turing. Nous construisons un treillis infini d'automates cellulaires Turing-universels qui sont tous à distance infinie de tout automate cellulaire intrinsèquement universel.
18
Boyer, Laurent. "Comportements typiques dans les automates cellulaires." Phd thesis, Université de Grenoble, 2010. http://tel.archives-ouvertes.fr/tel-00862704.
Full textAbstract:
Nous abordons les automates cellulaires (AC) en cherchant à dégager des informations quantitatives et en particulier à préciser les comportements répandus. Nous étudions en guise de prélude des AC présentant une forte symétrie de la règle locale (AC dits multi-ensemblistes). Les règles locales qui les définissent ont la propriété de pouvoir être utilisées facilement pour différente tailles de voisinage, et nous exhibons des règles, pour chaque dimension, qui sont universelles pour une infinité de tailles. Nous formalisons ensuite la notion de densité d'une propriété parmi l'ensemble des AC. En remarquant que les propriétés répandues sont liées aux propriétés des objets aléatoires au sens de Kolmogorov, et en utilisant divers outils combinatoires nous montrons la négligeabilité (au sens quantitatif) de propriétés non seulement syntaxiques (injectivité, surjectivité, présence d'états persistants ou envahissants), mais aussi dynamiques (nilpotence, certaines contraintes sur l'ensemble limite...). Et nous montrons à l'opposé que l'universalité intrinsèque , propriété qui semble à priori exigeante, est pour de nombreuses sous-familles une propriété très répandue. En ce qui concerne le comportement typique à long terme d'un AC fixé, la mu-nipotence, que nous introduisons à partir de la notion d'ensembles mu-limites, permet de caractériser les AC convergeant presque toujours vers une configuration unique. Nous montrons que celle-ci n'est ni récursivement énumérable ni co-récursivement énumérable. Ceci montre que la difficulté calculatoire de la prédiction du comportement à long terme des AC n'est pas due à des ensembles de configurations négligeables. Nous exhibons aussi des ensembles mu-limites aux langages non récursifs. Enfin nous montrons des résultats d'existence et de non-existence d'AC universels pour la relation de simulation dite surjective parmi certaines sous-familles.
19
Terrier, Véronique. "Reconnaissance de langages par automates cellulaires." Habilitation à diriger des recherches, Université de Caen, 2011. http://tel.archives-ouvertes.fr/tel-01070916.
Full textAbstract:
Les automates cellulaires ont été introduits il y a une soixantaine d'années par von Neumann et Ulam qui cherchaient à définir les caractéristiques d'un système formel apte au calcul universel et à l'auto-reproduction. Leur utilité a été rapidement reconnue dans des domaines variés comme la physique et la biologie, pour modéliser des phénomènes complexes. En informatique, ils offrent un cadre privilégié pour l'étude du parallélisme massif. Leur description est simple et bien formalisée. Ils ont a la même puissance de calcul que les machines de Turing et de plus la richesse algorithmique propre aux machines parallèles tout en restant un modèle physiquement réaliste. Dans le cadre unificateur de la reconnaissance de langages, je m'intéresse aux questions de complexité sur les automates cellulaires, avec une attention particulière aux petites classes de complexité : calcul en temps réel (i.e. temps minimal) et en temps linéaire; en effet, c'est pour ces classes que l'apport du parallélisme est remarquable par rapport au mode séquentiel. Avec pour objectif de préciser les capacités de ce modèle et de mieux comprendre ce qu'est un calcul parallèle, trois tendances majeures se dégagent de mes travaux : l'étude des limites de ce modèle, la comparaison avec d'autres modèles de calcul et la question de l'influence de certains paramètres comme la dimension ou le voisinage sur ses capacités de reconnaissance.
20
Heen, Olivier. "Economie de ressources sur automates cellulaires." Paris 7, 1996. http://www.theses.fr/1996PA077218.
Full textAbstract:
Un automate cellulaire est un assemblage regulier et potentiellement infini d'unites de calcul toutes semblables: les cellules. Il est etonnant de constater la complexite des phenomenes qu'une machine aussi simple permet de modeliser. De fait, les automates cellulaires trouvent des applications variees en informatique, mais aussi en physique, chimie theorique et meme en biologie. Ce travail traite de l'aspect informatique des automates cellulaires unidimensionnels, qui forment un modele interessant du calcul parallele. Nous reformulons des resultats de complexite dans une optique d'economie des ressources. Plus precisement, nous cherchons a caracteriser la taille minimale des cellules pour realiser certaines taches et repondons a quelques questions: dans quelles proportions faut-il accroitre les ressources pour gagner k pas de calcul ? pour calculer k fois plus vite ? quel est le prix a payer pour envoyer de l'information de cellule en cellule ? quels sont les temps de synchronisation autorises ? l'etude systematique de telles questions a conduit a la mise au point d'une nouvelle methode de simulation d'automates cellulaires mettant en valeur le caractere intrinseque de certaines proprietes: les resultats s'obtiennent a l'interieur de la theorie des automates cellulaires en termes de produits relativement simples de machines (produit de regroupement)
21
Roka, Zsuzsanna. "Automates cellulaires sur graphes de Cayley." Lyon 1, 1994. http://www.theses.fr/1994LYO10180.
Full textAbstract:
Deux notions de réseaux d'automates apparaissent souvent dans la littérature. Les automates cellulaires, automates finis placés sur les sommets de z, z#2,, z#n, et qui communiquent suivant les directions principales de l'espace. La seconde notion est celle de graphe d'automates ou, aux sommets d'un graphe quelconque de degré borne, on place des automates finis qui communiquent par les arêtes. La première notion ne fonctionne que sur des graphes très pauvres, la seconde pose le problème suivant : les cellules ne connaissent pas l'allure du graphe autour d'elles. Voila pourquoi nous avons décidé d'étudier les automates cellulaires définis sur des graphes de Cayley qui sont des graphes modulaires régulièrement coloriés par des générateurs d'un groupe de présentation finie. Notre thèse comporte trois parties: dans la première, nous généralisons la notion d'automates cellulaires unidirectionnels sur les graphes de Cayley. Nous donnons des résultats sur la vitesse de simulation d'un automate cellulaire par un automate cellulaire unidirectionnel dans le cas de graphes usuels, en particulier, les graphes hexagonaux et triangulaires. Nous donnons dans le cas général des conditions nécessaires et des conditions suffisantes pour que de telles simulations soient possibles sur des graphes de Cayley quelconques. Dans la seconde partie, nous étudions la notion de simulation d'un réseau d'automates par un autre. Cette notion est relativement difficile à cerner, nous l'étudions pour les automates cellulaires définis sur les graphes de Cayley correspondants aux pavages archimédiens. Cela nous amène à montrer que tous ces graphes sont équivalents à la grille dans le plan. Nous donnons aussi des conditions suffisantes pour l'existence de telles simulations en terme de morphismes à noyau fini et de morphismes presque surjectifs. Nous étudions aussi les cas de structures finies et périodiques comme les tores d'automates généralisés. Dans la dernière partie, nous montrons comment synchroniser des chemins de longueur minimale entre deux points d'un graphe de Cayley. Pour cela, une difficulté algorithmique apparaît, elle est due à l'apparition de culs-de-sac dans le graphe de Cayley, c'est-à-dire de points à distance n de l'origine dont aucun des voisins n'est à distance n + 1
22
Poupet, Victor. "Automates cellulaires : temps réel et voisinages." Lyon, École normale supérieure (sciences), 2006. http://www.theses.fr/2006ENSL0390.
Full textAbstract:
Dans cette thèse nous nous sommes intéressés à l'importance du choix du voisinage sur les capacités algorithmiques des automates cellulaires. Nous avons travaillé en dimension quelconque en nous concentrant sur les classes de complexité correspondant au temps réel (plus petit temps nécessaire pour que l'automate ait lu le mot en entrée) et temps réel plus une constante. En effet il est connu que les voisinages sont équivalents en temps linéaire et il est donc nécessaire de considérer des temps inférieurs. Nous avons obtenu plusieurs résultats d'équivalences de voisinages au sens du temps réel (des classes de voisinages tels que les automates fonctionnant sur ces voisinages reconnaissent les mêmes langages) et des résultats d'accélérations linéaires ou constantes selon les voisinages<br>In this thesis we have worked on the impact of the choice of a neighborhood on the algorithmic abilities of cellular automata. We have specifically studied the lower complexity classes such as the real time (that corresponds to the shortest time necessary for a cellular automaton to read all the letters of the input word) and the real time plus a constant. It is indeed known that neighborhoods are equivalent in linear time and it is therefore necessary to consider shorter times. We have obtained neighborhood equivalence results with respect to the real time (neighborhood classes such that cellular automata working on any of those neighborhoods can recognize the same languages in real time) and linear or constant speed-up theorems for many classes of neighborhoods
23
Bernardi, Vincent. "Lois de conservation sur automates cellulaires." Aix-Marseille 1, 2007. http://www.theses.fr/2007AIX11055.
Full textAbstract:
Dans cette thèse, nous nous intéressons à plusieurs notions d'invariants de l'évolution d'automates cellulaires dans le temps, en partant de la notion classique d'automate cellulaire conservateur. Nous présentons d'abord le modèle classique des automates cellulaires conservateurs, et plusieurs nouveaux résultats afférents. Puis nous introduisons les automates cellulaires décroissants, une extension naturelle des automates conservateurs, et montrons notamment que la décidabilité de cette propriété dépend de la dimension des automates considérés. Nous nous intéressons au rapport entre les automates décroissants et la notion de particule indifférenciée en introduisant les automates à particules. Enfin, nous étudions deux ensembles plus larges d'invariants, la conservation par fenêtre de fonctions de poids et les invariants d'évolution. Nous précisons la structure algébrique du premier modèle, et nous présentons nos premiers résultats concernant le deuxième.
24
Mariot, Luca. "Automates cellulaires, fonctions booléennes et dessins combinatoires." Thesis, Université Côte d'Azur (ComUE), 2018. http://www.theses.fr/2018AZUR4011/document.
Full textAbstract:
Le but de cette thèse est l'étude des Automates Cellulaires (AC) dans la perspective des fonctions booléennes et des dessins combinatoires. Au-delà de son intérêt théorique, cette recherche est motivée par ses applications à la cryptographie, puisque les fonctions booléennes et les dessins combinatoires sont utilisés pour construire des générateurs de nombres pseudo aléatoires (Pseudorandom Number Generators, PRNG) et des schémas de partage de secret (Secret Sharing Schemes, SSS). Les résultats présentés dans la thèse ont été développés sur trois lignes de recherche, organisées comme suit. La première ligne porte sur l'utilisation des algorithmes d'optimisation heuristique pour chercher des fonctions booléennes ayant des bonnes propriétés cryptographiques, à utiliser comme des règles locales dans des PRNG basés sur les AC. La motivation principale est l'amélioration du générateur de Wolfram basé sur la règle 30, qui a été montré être vulnérable vis à vis de deux attaques cryptanalytiques. La deuxième ligne s'occupe des fonctions booléennes vectorielles engendrées par les règles globales des AC. La première contribution considère la période des pré-images des configurations spatialement périodiques dans les AC surjectifs, et l'analyse des propriétés cryptographiques des règles globales des AC. La troisième ligne se concentre sur les dessins combinatoires engendrés par les AC, en considérant les Carrés Latins Orthogonaux (Orthogonal Latin Squares, OLS), qui sont équivalents aux SSS. En particulier, on donne une caractérisation algébrique des OLS engendrés par les AC linéaires, et on utilise des algorithmes heuristiques pour construire des OLS basés sur des AC non linéaires<br>The goal of this thesis is the investigation of Cellular Automata (CA) from the perspective of Boolean functions and combinatorial designs. Beside its theoretical interest, this research finds its motivation in cryptography, since Boolean functions and combinatorial designs are used to construct Pseudorandom Number Generators (PRNG) and Secret Sharing Schemes (SSS). The results presented in the thesis are developed along three research lines, organized as follows. The first line considers the use of heuristic optimization algorithms to search for Boolean functions with good cryptographic properties, to be used as local rules in CA-based PRNG. The main motivation is to improve Wolfram's generator based on rule 30, which has been shown to be vulnerable against two cryptanalytic attacks. The second line deals with vectorial Boolean functions induced by CA global rules. The first contribution considers the period of preimages of spatially periodic configurations in surjective CA, and analyze the cryptographic properties of CA global rules. The third line focuses on the combinatorial designs generated by CA, specifically considering Orthogonal Latin Squares (OLS), which are equivalent to SSS. In particular, an algebraic characterization of OLS generated by linear CA is given, and heuristic algorithms are used to build OLS based on nonlinear CA
25
Maldonado, Diego. "Universalité et complexité des automates cellulaires coagulants." Thesis, Orléans, 2018. http://www.theses.fr/2018ORLE2027/document.
Full textAbstract:
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 nepeut é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. Pour presque tous les autres automates de cette famille, nous montrons que leur complexité de prédiction est plus faible (sous l’hypothèse P 6≠NP)<br>Cellular automata are a well know family of discrete dynamic systems, defined by S. Ulam and J. von Neumannin the 40s. The have been successfully studied from the point of view of modeling, dynamics and computational complexity. In this work, we adopt this last point of view to study the family of freezing cellular automata, those where the state of a cell can only evolve following an order relation on the set of states. We study the complexity of these cellular automata from two points of view, the ability of some freezing cellular automata to simulate every other freezing cellular automata, called intrinsic universality, and the time complexity to predict the evolution of a cell starting from a given finite configuration, called prediction complexity. We show that despite the severe restriction of the ordering of states, freezing cellular automata can still exhibit highly complex behaviors.On the one hand, we show that in two or more dimensions there exists an intrinsically universal freezing cellular automaton, able to simulate any other freezing cellular automaton by encoding its states into blocks of cells, where each cell can change at most twice. This result is minimal in dimension two and can be even simplified to one change per cell in higher dimensions.On the other hand, we extensively study the computational complexity of the prediction problem for totalistic freezing cellular automata with two states and von Neumann neighborhood in dimension two. In this family of 32 cellular automata, we find two automata with the maximum complexity for classical synchronous cellular automata, while in the case of asynchronous evolution, the maximum complexity can only be achived in dimension three. For most of the other automata of this family, we show that they have a lower complexity (assuming P 6≠NP)
26
Delacourt, Martin. "Automates cellulaires : dynamique directionnelle et asymptotique typique." Thesis, Aix-Marseille 1, 2011. http://www.theses.fr/2011AIX10131/document.
Full textAbstract:
Les automates cellulaires sont à la fois un modèle de calcul parallèle, un système complexe et un système dynamique. Ils fonctionnent de manière synchrone et en temps discret, leur particularité est que les fonctions qu'ils définissent sont issues de l'application simultanée, en tout point de l'espace, d'une règle d'évolution locale. L'ensemble limite est un objet classique des systèmes dynamiques, c'est l'ensemble des états que le système peut atteindre arbitrairement tard. Il a été très étudié dans le cadre des automates cellulaires, et les résultats sont nombreux. Parmi ces résultats, un théorème de Rice démontré par Jarkko Kari dit que toute propriété des ensembles limites est indécidable. Dans ce mémoire, on ne s'intéresse plus à l'ensemble limite traditionnel, mais à une variante pour laquelle on utilise une mesure sur l'espace des entrées, sélectionnant ainsi les comportements susceptibles d'apparaître arbitrairement tard et souvent. Ce nouvel ensemble, que l'on nomme ensemble mu-limite, a été introduit en 2000 par Petr Kurka et Alejandro Maass. La plupart des résultats sur les ensembles limites ne se transposent pas naturellement. On étudie la famille des ensembles mu-limites d'automates cellulaires. On montre que sous certaines contraintes sur la dynamique, l'ensemble mu-limite peut être entièrement décrit. On classe ainsi les automates en fonction de ces contraintes. Dans le cas général, on montre l'existence d'automates cellulaires ayant comme ensembles mu-limites un grand nombre d'ensembles complexes. On finit par montrer un théorème de Rice pour les ensembles mu-limites d'automates cellulaires: tout propriété non triviale de ces ensembles est indécidable<br>Cellular automata are simultaneously a model of parallel computation, a complex system and a dynamical system. They are synchronous and time is discrete. The functions defined by their application is the result of the synchronous application of the same local rule everywhere. The limit set is a classical tool of dynamical systems theory, it is the set of states the system can reach arbitrarily late. It has been studied often in the particular case of cellular automata and there are numerous results. Amongst them, a Rice's theorem proved by Jarkko Kari states that any non-trivial property of limit sets of cellular automata is undecidable. In this thesis, we do not consider the classical limit set, as we add a measure on the space of states of the system. Thus, we get a set which contains behaviors that appear arbitrarily far and often. This set is named mu-limit set and was introduced in 2000 by Petr Kurka and Alejandro Maass. Most of the results on limit sets cannot be directly adapted for mu-limit sets. We study the family of all mu-limit sets of cellular automata. We show that under some constraints on the dynamics, the mu-limit set can be entirely described. We then produce a classification of cellular automata according to these constraints. In the general case, we prove the existence of cellular automata whose mu-limit sets are among a large set of complex sets. We finally prove Rice's theorem for mu-limit sets: any non-trivial property is undecidable
27
Lanthier, Paul. "Aspects ergodiques et algébriques des automates cellulaires." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMR034.
Full textAbstract:
La première partie de ce manuscrit entre dans le cadre de la théorie des probabilités, et est consacrée à l’étude de filtrations engendrées par des automates cellulaires. On étudie deux versions d’un automate algébrique agissant sur des configurations dont les états sont à valeurs dans un groupe abélien fini : l’une est déterministe, et consiste à additionner les états de deux cellules consécutives, et la seconde est une perturbation aléatoire de la première. À partir de ces automates, on construit des processus aléatoires markoviens et on étudie les filtrations engendrées par ces processus. On montre en utilisant le critère de I-confort que les deux filtrations sont standards au sens développé par Vershik. Cependant, les automates cellulaires ont comme particularité de commuter avec l’opérateur de décalages des coordonnées, appelé « shift ». Dans cette thèse, on introduit une nouvelle classification des filtrations dite « dynamique » qui tient compte de l’action de cette transformation. Les filtrations sont définies non plus sur des espaces de probabilité mais sur des systèmes dynamiques, ce sont dans ce cas des filtrations « facteurs » : chaque tribu est invariante par la dynamique du système. Le pendant de la standardité du point de vue dynamique est étudié. On crée ainsi un critère nécessaire pour la standardité dynamique appelé « I-confort dynamique ». La question de savoir si le I-confort dynamique est suffisant reste ouverte mais un premier résultat dans cette direction est donné, en montrant qu’une version renforcée du I-confort dynamique entraîne la standardité dynamique. En établissant qu’elle ne satisfait pas le critère de I-confort dynamique, on prouve que la filtration facteur engendrée par l’automate déterministe n’est pas dynamiquement standard, et donc que la classification dynamique des filtrations diffère de la classification développée par Vershik. L’automate probabiliste dépend d’un paramètre d’erreur, et on montre par un argument de percolation que la filtration facteur engendrée par cet automate est dynamiquement standard pour des valeurs assez grandes de ce paramètre. 0n conjecture qu’elle ne sera pas dynamiquement standard pour les valeurs très petites de ce paramètre. La deuxième partie de ce manuscrit, plus algébrique, tire son origine d’une problématique musicale, liée au calcul d’intervalles dans une ligne mélodique périodique. Les travaux présentés ici poursuivent les recherches du compositeur roumain Anatol Vieru et de Moreno Andreatta et Dan Vuza mais d’une manière originale en se plaçant du point des vue des automates cellulaires. On étudie l’action sur des suites périodiques de deux automates cellulaires algébriques, dont l’un est identique à celui de la première partie. Les questions sur la caractérisation des suites réductibles et reproductibles ainsi que les temps associés ont été approfondies et améliorées pour ces deux automates. Le calcul des antécédents et des images via les deux automates a été explicité. La question de l’évolution des périodes a été traitée avec la création d’un outil appelé « caractéristique » qui permet de décrire et de contrôler l’évolution de la période dans les temps négatifs. Des simulations permettent de voir que l’évolution des périodes lorsque l’on tire au hasard des antécédents suit un motif presque régulier, et l’explication de ce phénomène reste une question ouverte. Les résultats mathématiques de cette deuxième partie ont été utilisés dans le module « automaton » d’un logiciel de composition gratuit, nommé « UPISketch. Ce module permet à un compositeur de créer des lignes mélodiques en itérant les images ou en prenant des antécédents successifs d’une ligne mélodique de départ<br>The first part of this manuscript falls within the framework of probability theory, and is devoted to the study of filtrations generated by some cellular automata. We study two versions of an algebraic automaton acting on configurations whose states take values in a finite Abelian group: one is deterministic, and consists in adding the states of two consecutive cells, and the second is a random perturbation of the first one. From these automata, random Markovian processes are constructed and the filtrations generated by these processes are studied. Using the I-cosiness criterion, we show that the two filtrations are standard in the sense developed by Vershik. However, cellular automata have the particularity of commuting with the coordinate shift operator. In this thesis, we introduce a new classification of the filtrations called "dynamic" which takes into account the action of this transformation. Filtrations are no longer defined on probability spaces but on dynamical systems, and are in this case "factor" filtrations: each sigma-algebra is invariant by the dynamics of the system. The counterpart of standardity from the dynamic point of view is studied. This creates a necessary criterion for dynamic standardity called "dynamic I-cosiness". The question of whether the dynamic I-cosiness is sufficient remains open, but a first result in this direction is given, showing that a strengthened version of the dynamic I-cosiness leads to dynamic standardity. By establishing that it does not satisfy the criterion of dynamic I-cosiness, it is proved that the factor filtration generated by the deterministic automaton is not dynamically standard, and therefore that the dynamic classification of the filtrations differs from the classification developed by Vershik. The probabilistic automaton depends on an error parameter, and it is shown by a percolation argument that the factor filtration generated by this automaton is dynamically standard for large enough values of this parameter. It is conjectured that it will not be dynamically standard for very small values of this parameter. The second part of this manuscript, more algebraic, has its origin in a musical problem, linked to the calculation of intervals in a periodic melodic line. The work presented here continues the research of the Romanian composer Anatol Vieru and of Moreno Andreatta and Dan Vuza, but in an original way from the point of view of cellular automata. We study the action on periodic sequences of two algebraic cellular automata, one of which is identical to that of the first part. The questions on the characterization of reducible and reproducible sequences as well as the associated times have been deepened and improved for these two automata. The calculation of preimages and images via the two automata was explained. The question of the evolution of the periods was treated with the creation of a tool called "characteristic" which allows to describe and control the evolution of the period in negative times. Simulations show that the evolution of the periods when the preimages are drawn at random follows an almost regular pattern, and the explanation of this phenomenon remains an open question. The mathematical results of this second part have been used in the "Automaton" module of a free composing software called "UPISketch ». This module allows a composer to create melodic lines by iterating images or taking successive preimages of a starting melodic line
28
Regnault, Damien. "Sur les automates cellulaires probabilistes : comportements asynchrones." Lyon, Ecole normale supérieure, 2008. http://www.theses.fr/2008ENSLA480.
Full text
29
Grandjean, Anaël. "Reconnaissance de langage en temps réel sur automates cellulaires 2D." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT331/document.
Full textAbstract:
Les automates cellulaires sont un modèle de calcul massivement parallèle introduit dans les années 50. De nombreuses variantes peuvent être considérées par exemple en faisant varier la dimension de l’espace de calcul, ou les possibilités de communication entre les différentes cellules. En effet, chaque cellule ne peut communiquer qu’avec un nombre fini d’autres cellules que l’on appelle son voisinage. Mes travaux s’intéressent principalement à l’impact du choix du voisinage sur les capacités algorithmiques de ce modèle. Cet impact étant bien compris en une dimension, mes travaux portent majoritairement sur les automates cellulaires bidimensionnels. J’ai tout d’abord essayé de généraliser des propriétés classiques de certaines classes de complexité au plus de voisinages possibles. On arrive notamment à un théorème d’accélération linéaire valable pour tous les voisinages. J’ai ensuite étudié les différences entre les classes de faibles complexités en fonction du voisinage choisi. Ces travaux ont permis d’exhiber des voisinages définissant des classes incomparables, ainsi que des ensembles de voisinages définissant exactement les mêmes classes de complexité. Enfin, je présente aussi des travaux sur les différences de puissance de calcul entre les automates de dimensions différentes<br>Cellular automata were introduced in the 50s by J. von Neumann and S. Ulamas an efficient way of modeling massively parallel computation. Many variations of the model can be considered such as varying the dimension of the computation space or the communication capabilities of the computing cells. In a cellular automaton each cell can communicate only with a finite number of other cells called its neighbors. My work focuses on the impact of the choice of the neighbors on the algorithmic properties of the model. My first goal was to generalize some classical properties of computation models to the widest possible class of neighborhoods, in particular I prove a linear speedup theorem for any two dimensional neighborhood. I then study the difference between the complexity classes defined by different neighborhoods, show the existence of neighborhoods defining incomparable classes, and some sets of neighborhoods defining identical classes. Finally, I also discuss the impact of the dimension of the automata on their computational power
30
Martin, Bruno. "Construction modulaire d'automates cellulaires." Lyon 1, 1993. http://www.theses.fr/1993LYO10032.
Full textAbstract:
Nous decrivons dans un premier temps un langage algorithmique pour construire de facon modulaire des automates cellulaires complexes. Nous utilisons pour ce faire un langage logique qui modelise quelques operations simples sur les fonctions de transition qui composent l'automate cellulaire voulu. Ensuite, nous utilisons notre langage pour decrire des automates cellulaires capables de generer des formes fractales simples. Nous proposons aussi un algorithme qui permet de simuler efficacement l'evolution d'un tore d'automates sur un anneau d'automates. Enfin, nous avons etudie les automates cellulaires du point de vue de la calculabilite en construisant une enumeration des automates cellulaires, un automate cellulaire capable de calcul universel et un pour la composition. Nous satisfaisons ainsi les proprietes de la definition d'un systeme de programmation acceptable. Nous en deduisons tous les resultats classiques de la theorie des algorithmes et nous en utilisons certains pour etudier le modele des parallel random-access machines du point de vue de la calculabilite
31
Yunès, Jean-Baptiste. "Synchronisation et Automates Cellulaires: La Ligne de Fusiliers." Phd thesis, Université Paris-Diderot - Paris VII, 1993. http://tel.archives-ouvertes.fr/tel-00139049.
Full textAbstract:
Cette thèse s'articule autour du problème de la synchronisation d'une ligne d'automates. Elle propose une solution économe en nombre d'états en utilisant le schéma de Minsky: temps de synchronisation 3n et nombre d'états 7. Elle s'attache aussi à décrire le comportement de certains automates particuliers découverts lors de la quête automatisée de solutions minimales.
32
Maass, Alejandro. "Contributions à l'étude dynamique des automates cellulaires unidimensionnels." Aix-Marseille 2, 1994. http://www.theses.fr/1994AIX22023.
Full textAbstract:
Dans cette these nous nous attachons aux aspects dynamiques et ergodiques des automates cellulaires unidimensionnels. Dans les deux premiers chapitres nous etudions des automates cellulaires surjectifs, en particulier la classe des automates cellulaires qui sont conjugues avec des sous-systemes de type fini. Nous prouvons qu'ils sont topologiquement melangeants, qu'ils ont une entropie topologique qui est le logarithme d'un entier n, et que leur groupe de dimension est celui d'un full shift sur n lettres. Lorsque nous munissons ces automates cellulaires de la mesure produit uniforme, on trouve qu'elle est l'unique mesure d'entropie maximale donc ces systemes dynamiques sont des systemes de bernoulli. Le troisieme chapitre est consacre a l'etude de l'ensemble limite d'un automate cellulaire. Dans la premiere partie nous construisons une famille d'automates cellulaires dont les ensembles limites atteignent des complexites diverses dans la hierarchie de chomsky des langages formels. Apres nous etudions les ensembles limites sofiques des automates cellulaires. Nous prouvons que tout systeme sofique presque de type fini melangeant qui contient un point fixe receptif peut etre obtenu comme l'ensemble limite d'un automate cellulaire stable. Nous prouvons aussi que les systemes sofiques presque markoviens ne peuvent pas etre obtenus comme des ensembles limites d'automates cellulaires instables. Dans le quatrieme chapitre nous considerons un probleme de dynamique topologique plus abstrait. Nous donnons une generalisation de la notion de couple d'entropie topologique pour un flot topologique (x, t) au cas metrique, c'est-a-dire quand on munit le flot d'une mesure invariante
33
Casse, Jérôme. "Automates cellulaires probabilistes et processus itérés ad libitum." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0248/document.
Full textAbstract:
La première partie de cette thèse porte sur les automates cellulaires probabilistes (ACP) sur la ligne et à deux voisins. Pour un ACP donné, nous cherchons l'ensemble de ces lois invariantes. Pour des raisons expliquées en détail dans la thèse, ceci est à l'heure actuelle inenvisageable de toutes les obtenir et nous nous concentrons, dans cette thèse, surles lois invariantes markoviennes. Nous établissons, tout d'abord, un théorème de nature algébrique qui donne des conditions nécessaires et suffisantes pour qu'un ACP admette une ou plusieurs lois invariantes markoviennes dans le cas où l'alphabet E est fini. Par la suite, nous généralisons ce résultat au cas d'un alphabet E polonais après avoir clarifié les difficultés topologiques rencontrées. Enfin, nous calculons la fonction de corrélation du modèleà 8 sommets pour certaines valeurs des paramètres du modèle en utilisant une partie desrésultats précédents<br>The first part of this thesis is about probabilistic cellular automata (PCA) on the line and with two neighbors. For a given PCA, we look for the set of its invariant distributions. Due to reasons explained in detail in this thesis, it is nowadays unthinkable to get all of them and we concentrate our reections on the invariant Markovian distributions. We establish, first, an algebraic theorem that gives a necessary and sufficient condition for a PCA to have one or more invariant Markovian distributions when the alphabet E is finite. Then, we generalize this result to the case of a polish alphabet E once we have clarified the encountered topological difficulties. Finally, we calculate the 8-vertex model's correlation function for some parameters values using previous results.The second part of this thesis is about infinite iterations of stochastic processes. We establish the convergence of the finite dimensional distributions of the α-stable processes iterated n times, when n goes to infinite, according to parameter of stability and to drift r. Then, we describe the limit distributions. In the iterated Brownian motion case, we show that the limit distributions are linked with iterated functions system
34
Sapin, Emmanuel. "Recherche par algorithmes évolutionnaires d'automates cellulaires universels." Dijon, 2003. http://www.theses.fr/2003DIJOS041.
Full text
35
Cisse, Baki. "Automates cellulaires pour la modélisation et le contrôle en épidémiologie." Thesis, Perpignan, 2015. http://www.theses.fr/2015PERP0011.
Full textAbstract:
Ce travail de thèse traite de la modélisation et du contrôle des maladies infectieuses à l’aide des automates cellulaires. Nous nous sommes d’abord focalisés sur l’étude d’un modèle de type SEIR. Nous avons pu monter d’une part qu’un voisinage fixe pouvait entrainer une sous-évaluation de l’incidence et de la prévalence et d’autre part que sa structure a un impact direct sur la structure de la distribution de la maladie. Nous nous sommes intéressés également la propagation des maladies vectorielles à travers un modèle de type SIRS-SI multi-hôtes dans un environnement hétérogène.Les hôtes y étaient caractérisés par leur niveau de compétence et l’environnement par la variation du taux de reproduction et de mortalité. Son application à la maladie de Chagas, nous a permis de montrer que l’hétérogénéité de l’habitat et la diversité des hôtes contribuaient à faire baisser l’infection. Cependant l’un des principaux résultats de notre travail à été la formulation du nombre de reproduction spatiale grâce à deux matrices qui représentent les coefficients d’interactions entre les différentes cellules du réseau<br>This PhD thesis considers the general problem of epidemiological modelling and control using cellular automata approach.We first focused on the study of the SEIR model. On the one hand, we have shown that the traditionnal neighborhood contribute to underestimate the incidence and prevalence of infection disease. On the other hand, it appeared that the spatial distribution of the cells in the lattice have a real impact on the disease spreading. The second study concerns the transmission of the vector-borne disease in heterogeneous landscape with host community. We considered a SIRS-SI with various level of competence at witch the environnment heterogeneity has been characterized by the variation of the birth flow and the death rate. We simulated the Chagas disease spreading and shown that the heterogeneity of habitat and host diversity contribute to decrease the infection. One of the most important results of our work, was the proposition of the spatial reproduction number expression based on two matrices that represent the interaction factors between the cells in the lattice
36
Borello, Alex. "Reconnaissance de langages en temps réel par des automates cellulaires avec contraintes." Thesis, Aix-Marseille 1, 2011. http://www.theses.fr/2011AIX10127.
Full textAbstract:
Dans cette thèse, on s'intéresse aux automates cellulaires en tant que modèle de calcul permettant de reconnaître des langages. Dans un tel domaine, il est toujours difficile d'établir des résultats négatifs, typiquement de prouver qu'un langage donné n'est pas reconnu en une certaine fonction de temps par une certaine classe d'automates. On se focalisera en particulier sur les classes de faible complexité comme le temps réel, au sujet desquelles de nombreuses questions restent ouvertes.Dans une première partie, on propose plusieurs manières d'affaiblir encore les classes de langages étudiées, permettant ainsi d'obtenir des exemples de résultats négatifs. Dans une seconde partie, on montre un théorème d'accélération par automate cellulaire d'un modèle séquentiel, les automates finis oublieux. Ce modèle est une version a priori affaiblie, mais non triviale, des automates finis à plusieurs têtes de lecture<br>This document deals with cellular automata as a model of computation used to recognise languages. In such a domain, it is always difficult to provide negative results, that is, typically, to prove that a given language is not recognised in some function of time by some class of automata. The document focuses in particular on the low-complexity classes such as real time, about which a lot of questions remain open since several decades.In a first part, several techniques to weaken further still these classes of languages are investigated, thereby bringing examples of negative results. A second part is dedicated to the comparison of cellular automata with another model language recognition, namely multi-head finite automata. This leads to speed-up theorem when finite automata are oblivious, which makes them a priori weaker than in the general case but leaves them a nontrivial power
37
Terrier, Véronique. "Décidabilité en arithmétiques faibles : temps réel sur automates cellulaires." Lyon 1, 1991. http://www.theses.fr/1991LYO10031.
Full textAbstract:
Ce travail de these comporte deux themes distincts: les arithmetiques faibles et les automates cellulaires. En ce qui concerne les arithmetiques faibles, nous montrons divers resultats dont la decidabilite de la theorie existentielle sur n structure par l'ordre naturel, la divisibilite, les fonctions puissances et les predicats puissance. Puis, nous etudions la puissance des automates cellulaires lineaires. Nous montrons d'une part que toute fonction de croissance croissante d'un systeme dol peut etre mise en place en temps reel sur un automate. D'autre part, nous etudions quelques signaux caracteristiques constructibles par des automates et montrons qu'il n'y a pas de signaux a vitesse arbitrairement rapide autre que celui de celerite maximale. Puis, nous donnons une solution intrinseque aux automates cellulaires d'un probleme d'o. Ibarra dont une solution etait connue via les machines de turing, mettant ainsi en valeur l'importance de la notion de signal pour les automates cellulaires
38
Maignan, Luidnel. "Points, distances, et automates cellulaires : algorithmique géométrique et spatiale." Paris 11, 2010. http://www.theses.fr/2010PA112325.
Full textAbstract:
Le calcul spatial a pour but de fournir un cadre de travail passant à l'échelle où les calculs sont distribués sur un milieu de calculs uniforme à communications locales. Nous étudions le cas particulier des automates cellulaires, utilisant une grille régulière et une communication synchrone. Nous proposons de développer des primitives permettant de structurer le milieu de calculs autour d'un ensemble de particules. Nous considérons trois problèmes géométriques : déplacer les particules afin d'uniformiser leur densité, construire leur enveloppe convex, et construire un graphe de proximité connexe connectant les plus proches particules entre elles. Ces deux derniers problèmes sont considérés sur grille multidimensionnelle, tandis que l'uniformisation est résolue sur un espace à une dimension. Notre approche est de considérer l'espace métrique correspondant à l'automate cellulaire et de construire des objets mathématiques basés sur cette métrique seule. Les algorithmes obtenues se généralisent ainsi vers des grilles arbitraires. Nous implantons les grilles usuelles : hexagonale et carré avec 4 et 8 voisins. Toutes les solutions sont basées sur la même brique de base : le champ de distances, associant à chaque point de l'espace sa distance à la plus proche particule. Alors que ces valeurs de distances ne sont pas bornées, nous utilisons le fait que la différence entre valeurs voisines l'est afin d'encoder les gradients sur un nombre fini d'états. Nos algorithmes, exprimés en terme de mouvement par rapport à ces gradients et de détection de motifs de gradient, s'encodent donc en automates d'états finis, avec un petit nombre d'états<br>Spatial computing aims at providing a scalable framework where computation is distributed on a uniform computing medium and communication happen locally between nearest neighbors. We study the particular framework of cellular automata, using a regular grid and synchronous update. We propose to develop primitives allowing to structure the medium around a set of particles. We consider three problems of geometrical nature: moving the particles on the grid in order to uniformize the density, constructing their convex hull, constructing a connected proximity graph establishing connection between nearest particles. The last two problems are considered for multidimensional grid while uniformization is solved specifically for the one dimensional grid. The work approach is to consider the metric space underlying the cellular automata topology and construct generic mathematical object based solely on this metric. As a result, the algorithms derived from the properties of those objects, generalize over arbitrary regular grid. We implemented the usual ones, including hexagonal, 4 neighbors, and 8 neighbors square grid. All the solutions are based on the same basic component: the distance field, which associates to each site of the space its distance to the nearest particle. While the distance values are not bounded, it is shown that the difference between the values of neighboring sites is bounded, enabling encoding of the gradient into a finite state field. Our algorithms are expressed in terms of movements according to such gradient, and also detecting patterns in the gradient, and can thus be encoded in finite state of automata, using only a dozen of state
39
Ben-Azza, Hussain. "Automates cellulaires et pavages vus comme des réseaux booléens." Lyon 1, 1995. http://www.theses.fr/1995LYO10235.
Full textAbstract:
L'un des buts de cette these est de comparer certaines mesures de complexite associees aux deux modeles de calcul suivants: les reseaux booleens et les automates cellulaires. Le premier chapitre decrit l'approche adoptee et donne une idee (rapide) de certains travaux. Le deuxieme chapitre introduit les reseaux booleens, les automates cellulaires en relation avec les machines de turing, et quelques faits incontournables comme illustres par les premiers chapitres du monographe de p. Dunne (absorption, effet shannon-lupanov, trous). Le troisieme chapitre etudie les reseaux booleens synchrones comme ayant un interet propre. Le quatrieme chapitre compare les reseaux booleens et les automates cellulaires. Le cinquieme chapitre definit le probleme de pavage plus precisement et prouve les faits decrits a la fin de ce resume. Un reseau booleen se transforme en un reseau booleen synchrone dont la taille est au plus elevee au carre, et de meme profondeur. La version synchrone de l'evaluation d'un reseau booleen sur une entree est complete pour le temps polynomial deterministe. L'effet lupanov-shannon est aussi valable pour les reseaux booleens synchrones. En plus, par un argument statistique, il vient que la largeur d'un reseau booleen ainsi que sa profondeur peuvent influencer sa taille. Un langage reconnu en temps cellulaire t est reconnu par une famille de reseaux booleensu#e-uniforme synchrone de taille o(t#2), de profondeur o(t). Une famille de reseaux booleens u#c-uniforme synchrone de taille z, de profondeur d et de largeur l, est simulee en temps et largeur cellulaire, o(dz#2logz), o(log d + log l) respectivement. Savoir si une grille est pavable par des paves de taille k = 2 est dans nc#2. Un jeu, par les k-paves (k > 2), est montre complet pour l'espace deterministe polynomial
40
YASMINEH, SALIM. "Abondance des ondes et proprietes chaotiques des automates cellulaires." Paris 6, 1998. http://www.theses.fr/1998PA066368.
Full textAbstract:
L'objet de cette these est d'essayer de comprendre la complexite spatio-temporelle des automates cellulaires. Ces modeles sont de plus en plus utilises pour decrire des dynamiques dans plusieurs domaines des sciences naturelles et humaines, allant de la biologie a l'hydrodynamique, la physique, la chimie, l'informatique etc la these regroupe a la fois des travaux numeriques et analytiques. Dans la premiere partie, nous etudions numeriquement la propagation des ondes progressives dans les automates cellulaires a une dimension. Ceci nous a permis d'observer une grande richesse de vitesses de propagation et de longueurs d'onde. Nous comparons ces resultats avec la classification de wolfram. La seconde partie fait suite a une etude commencee par m. Courbage sur la distribution des longueurs d'ondes pour une classe d'automates cellulaires. Nous montrons que cette distribution est entierement expliquee par les racines dans un corps fini d'une famille de polynomes associees a l'automate et nous expliquons l'allure de l'accroissement exponentiel des ondes avec la vitesse de propagation dans certains cas. La troisieme partie est consacree aux automates cellulaires ayant la propriete du chaos spatial, autrement dit ayant une abondance de structures stationnaire periodiques et aperiodiques mesuree par la positivite de l'entropie topologique de ces structures.
41
St-Amand, André. "Approche des modèles de croissance par les automates cellulaires." Thèse, Université du Québec à Trois-Rivières, 1997. http://depot-e.uqtr.ca/4946/1/000634774.pdf.
Full text
42
Pérez, Brokate Cristian Felipe. "Etude de la compétition entre corrosion uniforme et localisée par automates cellulaires." Thesis, Paris 6, 2016. http://www.theses.fr/2016PA066650/document.
Full textAbstract:
Les modèles numériques sont un outil complémentaire pour la prédiction de la corrosion. L'objectif de cette thèse est de développer un modèle de corrosion reposant sur la méthode des automates cellulaires pour l'étude de l'évolution morphologique des surfaces, ainsi que de la cinétique de corrosion. Le modèle développé couple les demi-réactions électrochimiques d'oxydation et de réduction. Au niveau cinétique, la simulation par automates cellulaires peut alors reproduire les courbes intensité-potentiel d'une réaction redox sur électrode inerte. L'échelle spatio-temporelle choisie décrit des phénomènes de corrosion à l'échelle mésoscopique, niveau intermédiaire par rapport aux approches habituelles. Dans notre modèle, les probabilités rendent compte de la nature stochastique des réactions anodiques et cathodiques. Cette étude nous a permis de décrire l'évolution de la morphologie de la corrosion dans différents contextes: corrosion généralisée, corrosion par piqûre et corrosion en milieu confiné. Deux régimes de corrosion ont été observés: un régime de corrosion uniforme dans lequel les demi-réactions sont distribuées de manière homogène suivi par un régime de corrosion localisée, caractérisé par une séparation spatiale des zones cathodiques et anodiques<br>Numerical modelling is complementary tool for corrosion prediction. The objective of this work is to develop a corrosion model by means of a probabilistic cellular automata approach at a mesoscopic scale. In this work, we study the morphological evolution and kinetics of corrosion. This model couples electrochemical oxydation and reduction reactions. Regarding kinetics, cellular automata models are able to describe current as a function of the applied potential for a redox reaction on an inert electrode. The inclusion of probabilities allows the description of the stochastic nature of anodic and cathodic reactions. Corrosion morphology has been studied in different context: generalised corrosion, pitting corrosion and corrosion in an occluded environment. A general tendency of two regimes is found. A first regime of uniform corrosion where the anodic and cathodic reactions occur homogeneously over the surface. A second regime of localized corrosion when there is a spatial separation of anodic and cathodic zones, with an increase of anodic reaction rate
43
Martin, Jean-Yves. "Synthèse d'images à l'aide d'automates cellulaires : le projet Autoformes." Rennes 1, 1990. http://www.theses.fr/1990REN10134.
Full textAbstract:
Les automates cellulaires permettent de construire, de façon relativement simple, une multitude d'images. La création de ces images passe par la définition d'un certain nombre de paramètres : nombre d'états, voisinage, fonction de transition. Lorsque nous donnons des valeurs au hasard à ces paramètres, il est difficile de prévoir ce qui sera affiché. Nous avons abordé les automates cellulaires sous une nouvelle optique: la modélisation déclarative. Grâce à cette méthodologie, le concepteur n'a plus qu'à décrire l'image qu'il veut. Les paramètres à déterminer sont pris en compte par l'ordinateur qui engendre alors une ou des image(s) respectant la description fournie. Pour mettre en place cette méthodologie, nous avons défini des outils de description (permettant au concepteur de déterminer ce qu'il veut), des techniques d'exploration de l'univers des automates cellulaires (qui permettent de sélectionner les fonctions de transition intéressantes), et un ensemble de théorèmes (permettant de faire des déductions sur d'autres fonctions de transition). Ces éléments nous permettent ainsi de créer des images sans avoir à nous préoccuper des paramètres à fournir
44
Richard, Gaétan. "Systèmes de particules et collisions discrètes dans les automates cellulaires." Phd thesis, Université de Provence - Aix-Marseille I, 2008. http://tel.archives-ouvertes.fr/tel-00347778.
Full textAbstract:
Cette thèse a pour objet l'étude des systèmes de particules et collisions dans les automates cellulaires. En se basant sur des observations expérimentales, nous proposons des définitions formelles de ces objets et montrons qu'ils peuvent être mis en relation avec des coloriages réguliers du plan. À l'aide d'une représentation sous forme syntaxique de ces objets, nous introduisons une opération syntaxique d'assemblage: les schémas de ligature. Cette opération peut être interprétée en termes de coloriage et correspond à une opération intuitive utilisée dans l'étude algorithmique des automates cellulaires. Nous prouvons que, dans le cas d'assemblages finis, le lien entre l'opération syntaxique et l'interprétation peut être complètement caractérisé de façon algorithmique. Nous explorons ensuite des pistes d'extension de ces systèmes facilitant l'encodage et permettant de dépasser le cas fini. Enfin, nous étudions les applications de tels systèmes en lien avec l'universalité dans les automates cellulaires. En particulier, nous donnons une nouvelle preuve de l'universalité de l'automate cellulaire 110 et présentons la construction d'un automate cellulaire intrinsèquement universel de rayon 1 et à 4 états.
45
Marcovici, Irène. "Automates cellulaires probabilistes et mesures spécifiques sur des espaces symboliques." Phd thesis, Université Paris-Diderot - Paris VII, 2013. http://tel.archives-ouvertes.fr/tel-00933977.
Full textAbstract:
Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage. Les ACP sont utilisés en informatique comme modèle de calcul, ainsi qu'en biologie et en physique. Ils interviennent aussi dans différents contextes en probabilités et en combinatoire. Un ACP est ergodique s'il a une unique mesure invariante qui est attractive. Nous prouvons que pour les AC déterministes, l'ergodicité est équivalente à la nilpotence, ce qui fournit une nouvelle preuve de l'indécidabilité de l'ergodicité pour les ACP. Alors que la mesure invariante d'un AC ergodique est triviale, la mesure invariante d'un ACP ergodique peut être très complexe. Nous proposons un algorithme pour échantillonner parfaitement cette mesure. Nous nous intéressons à des familles spécifiques d'ACP, ayant des mesures de Bernoulli ou des mesures markoviennes invariantes, et étudions les propriétés de leurs diagrammes espace-temps. Nous résolvons le problème de classification de la densité sur les grilles de dimension supérieure ou égale à 2 et sur les arbres. Enfin, nous nous intéressons à d'autres types de problèmes. Nous donnons une caractérisation combinatoire des mesures limites pour des marches aléatoires sur des produits libres de groupes. Nous étudions les mesures d'entropie maximale de sous-décalages de type fini sur les réseaux et sur les arbres. Les ACP interviennent à nouveau dans ce dernier travail.
46
Meunier, Pierre-etienne. "Les automates cellulaires en tant que modèle de complexités parallèles." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00770175.
Full textAbstract:
The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation.
47
Bacquey, Nicolas. "Automates Cellulaires : aspects algorithmiqued des configurations périodiques en toute dimension." Caen, 2015. http://www.theses.fr/2015CAEN2060.
Full textAbstract:
Cette thèse analyse les capacités de calcul des automates cellulaires travaillant sur les configurations périodiques de dimension quelconque. D'une part, nous étudions les objets maximaux identifiables par ces automates cellulaires; nous appelons ces objets les racines primitives des configurations périodiques de dimension quelconque. Nous en présentons une caractérisation et mettons en évidence certaines de leurspropriétés. D'autre part, nous présentons un ensemble d'algorithmes, chacun adapté à une ou plusieurs dimensions particulières, permettant aux automates cellulaires d'extraire les racines primitives des configurations périodiques sur lesquelles ils sont appliqués. Ceux-ci utilisent des outils algorithmiques originaux étendant la notion de signal sur les automates cellulaires en dimension quelconque. Au-delà des aspects techniques et algorithmiques, cette thèse pose les bases du calcul périodique uniforme, c'est-à-dire du calcul effectué sur un modèle dans lequel le programme et l'entrée sont isotropes. Nous y abordons notamment les problématiques de l'arrêt d'un tel calcul, de lecture de son résultat et de sa complexité en temps et en espace<br>This thesis analyses the computational capabilities of cellular automata working on periodical configurations of any dimension. We first study the maximal objects these cellular automata can identify; we call those objects primitive roots of periodical configurations of any dimension. We characterize them and show some of their properties. Secondly, we present a set of algorithms on cellular automata, each one adapted to one or more dimensions, that extract primitive roots from the periodical configurations on which they are applied. Those algorithms use original tools that extend the notion of signals on cellular automata. Beyond its technical and algorithmical aspects, this thesis lays the foundations of uniform periodical computation, i. E. Computation performed on a model whose program and entry data are isotropic. In particular, we address the issues of halting such computation, reading its result and defining its temporal or spatial complexity
48
Cervelle, Julien. "Complexité structurelle et algorithmique des pavages et des automates cellulaires." Aix-Marseille 1, 2002. https://hal.archives-ouvertes.fr/tel-01208375.
Full textAbstract:
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
49
RAPAPORT, IVAN. "Ordre induit sur les automates cellulaires par l'operation de regroupement." Lyon, École normale supérieure (sciences), 1998. http://www.theses.fr/1998ENSL0091.
Full textAbstract:
En regroupant un segment de plusieurs cellules en une unique nouvelle cellule, nous introduisons la notion d'automate groupe. Un tel nouvel automate cellulaire peut se definir algebriquement et peut etre vu comme une puissance du premier. Nous introduisons une relation de pre-ordre sur les automates cellulaires en disant que x est plus petit que y si une puissance de x est un sous-automate d'une puissance y. On transforme la structure de pre-ordre dans un ordre en considerant les classes d'equivalence. On montre d'abord que cet ordre admet un minimum global et que des classes d'equivalences tres naturelles apparaissent comme petites pour cet ordre. Parmis ces classes, citons non seulement l'extension des deux premieres classes de wolfram (automates nilpotents et automates periodiques), mais encore des classes d'automates cellulaires algebriquement simples (addition sur les entiers modulo p avec p premier). Nous montrons egalement qu'on peut trouver dans l'ordre deux chaines infinies admettant un maximum. Par contre, l'ordre n'admet pas de maximum global. Ce dernier resultat montre qu'il n'existe pas d'automate universel vis a vis de cette notion de regroupement. Il implique aussi qu'il n'existe pas un automate cellulaire intrinsequement universel en temps reel. L'etude de cet ordre conduit a des resultats d'indecidabilite. Tout d'abord, savoir si deux automates sont equivalents est indecidable (consequence d'un theoreme non trivial de culik et kari). Meme si on ajoute des conditions restrictives, on est conduit a des resultats d'indecidabilite mettant en jeu des techniques complexes : pavages nord-ouest deterministes.
50
Louvet, Benjamin. "Automates cellulaires pour la modélisation multi-échelle des systèmes biologiques." Thesis, Clermont-Ferrand 2, 2014. http://www.theses.fr/2014CLF22479/document.
Full textAbstract:
Ce projet de thèse, dans le cadre d’une collaboration entre le LIMOS et le LPC, s’inscrit dans une démarche de recherche permettant la mise en synergie des domaines de la biologie, de la physique et de l’informatique par la proposition d’une démarche de simulation permettant la réalisation d’expériences in silico. Pour cela, nous nous proposons de développer une plateforme logicielle dédiée à la modélisation multiéchelle des systèmes biologiques qui pourra par la suite être interfacée avec les outils de simulation de physique des particules. Nous proposons également un modèle individu-centré de cellule biologique paramétrable à l’aide de données obtenues d’expériences in vitro. Nous présentons l’élaboration de cette plateforme et une démarche de validation de ses fonctionnalités à travers l’implémentation de modèles d’automates cellulaires de la littérature. Nous présentons ensuite la construction du modèle de cellule biologique en prenant le temps d’expliquer comment est pris en compte le système biologique, comment nous le modélisons puis comment nous paramétrons le modèle. Nous modélisons les processus internes de la cellule, dont les caractéristiques sont liées à l’information génétique qu’elle porte. Ce modèle de cellule permet de reproduire le comportement d’une cellule isolée, et à partir de là, d’un ensemble de cellules via l'automate. Le modèle est ensuite utilisé pour retrouver les courbes de croissance d'une population de bactéries Escherichia coli. Des valeurs de données de fluxomique ont été exploitées et ont permis la reproduction in silico des expériences in vitro dont elles étaient issues<br>This PhD thesis project is part of a research program in the fields of biology, physics and computer science aiming to propose a simulation approach for performing experiments in silico. For this, we propose to develop a software platform dedicated to multi-scale modeling of biological systems that can be combined with particle physics simulation tools. We also propose a general individual-based model of biological cell in which data obtained from in vitro experiments can be used. We present the development of this platform and the validation process of its functionalities through the implementation of cellular automata from the literature. We then present the design of the biological cell model by giving the hypothesis we made, how we model and how we parameterize the model. Starting from a simple biological system, bacteria, observed in liquid culture, our model uses a multi-scale middle-out approach. We focus on the cell and we model internal processes, assuming that all their properties come from genetic information carried out by the cell’s genome. This model allows to consider the cell behavior, and then to obtain the behavior of a cell population. Data from fluxomic experiments have been used in this model to parameterize the biochemical processes. The results we obtain allow us to consider the model as validated as simulation results match the experimental data