You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
Electronic Thesis;
E-Book
Title:
Colonnes dans les automates cellulaires et suites généralisées de Rudin-Shapiro ; Columns in cellular automata and generalized Rudin–Shapiro sequences
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Cette thèse se situe à la frontière entre mathématiques et informatique théorique. Nous nous intéressons dans un premier temps aux automates finis et aux automates cellulaires. Bien qu’ils s’agissent de deux objets mathématiques assez différents, il est possible de les relier par des constructions explicites, en regardant la réalisation des suites automatiques dans les diagrammes espace-temps des automates cellulaires. Dans un second temps, nous étudions les corrélations discrètes de certaines suites automatiques, appelées suites généralisées de Rudin–Shapiro, qui se comportent comme des suites aléatoires pour la corrélation discrète d’ordre 2, bien qu’elles soient déterministes. Après une introduction des objets d’étude, que nous illustrons par plusieurs exemples, nous rappelons le résultat de Rowland et Yassawi, qui ont montré en 2015 qu’il était possible de construire de manière explicite toute suite p-automatique, dans le cas où p est un nombre premier, en colonne d’un automate cellulaire linéaire, à partir d’une configuration initiale finie. En utilisant leur méthode, nous obtenons différentes constructions de suites automatiques de référence, puis nous établissons un moyen explicite de construire toute une famille de suites p-automatiques, appelées suites généralisées de Rudin–Shapiro, que nous étudions dans la deuxième partie de la thèse, dans un cadre plus général. Nous nous intéressons également au cas de certaines suites non-automatiques, telles que l’indicatrice des polynômes et le mot de Fibonacci, que nous réussissons à construire en colonne d’automates cellulaires non-linéaires. Puis nous obtenons des résultats sur des recodages binaires, permettant de réduire le nombre de symboles dans les automates cellulaires. Grâce à un recodage binaire, nous avons également construit explicitement une suite 3-automatique sur un alphabet binaire, en colonne d’un automate cellulaire à 2 états, non-périodique à partir d’un certain rang, ce qui répond à une question posée par Rowland et Yassawi. Dans la deuxième ...