http://hdl.handle.net/2268.2/225 Sat, 17 Oct 2026 18:49:32 GMT 2026-10-17T18:49:32Z http://hdl.handle.net/2268.2/27517 Title: Quelques preuves automatiques en théorie des jeux Abstract: Ce mémoire étudie l’utilisation des automates finis et de la logique du premier ordre pour démontrer automatiquement certaines propriétés de jeux combinatoires. L’approche repose notamment sur le théorème de Büchi, qui établit un lien entre définissabilité logique et reconnaissance par automate, ainsi que sur son implémentation dans le logiciel Walnut. Nous nous intéressons en particulier au jeu de Wythoff et à la caractérisation de ses positions perdantes, appelées P-positions. Le théorème de Fraenkel permet de décrire ces positions à l’aide du système de numération de Fibonacci. Cette caractérisation est ensuite traduite en propriétés reconnaissables par automate et vérifiée automatiquement à l’aide de Walnut. Le mémoire étudie également le jeu R-Wythoff, obtenu en restreignant les coups autorisés du jeu de Wythoff. Nous montrons que cette restriction conserve les mêmes P-positions que le jeu original et qu’elle est maximale au sens où aucun type de coup supplémentaire ne peut être supprimé sans modifier cet ensemble. L’étude est approfondie par l’analyse de la fonction de Grundy. Enfin, nous abordons la variante de Fraenkel et les systèmes de numération d’Ostrowski, en mettant également en évidence les limites computationnelles de l’approche automatique lorsque la complexité des propriétés considérées augmente. Tue, 23 Jun 2026 22:00:00 GMT http://hdl.handle.net/2268.2/27517 2026-06-23T22:00:00Z http://hdl.handle.net/2268.2/27451 Title: Spectre multifractal et transformée de Legendre : le cas des mesures autosimilaires Abstract: La finalité de ce mémoire est d'étudier le formalisme multifractal dans le cadre des mesures autosimilaires. Pour ce faire, nous présentons tout d'abord les systèmes de similitudes ainsi que la notion de schéma de Cantor qui généralise la construction de l'ensemble triadique de Cantor. Nous introduisons ensuite la transformée de Legendre et le spectre multifractal dans le cadre général avant de les appliquer dans le cadre des mesures autosimilaires pour démontrer le formalisme multifractal. Tue, 23 Jun 2026 22:00:00 GMT http://hdl.handle.net/2268.2/27451 2026-06-23T22:00:00Z http://hdl.handle.net/2268.2/26605 Title: Introduction à la théorie spectrale des graphes et Famille infinie de graphes de Ramanujan Abstract: Ce travail se divise en deux parties. Dans un premier temps, nous introduisons la théorie spectrale des graphes, qui consiste en l'étude des valeurs propres de la matrice d'adjacence et laplacienne d'un graphe. Nous développons les résultats classiques ainsi que des exemples illustratifs, puis nous démontrons le théorème d'Alon-Boppana. Dans un second temps, nous nous intéressons aux graphes de Ramanujan et nous démontrons l'existence, pour un naturel k fixé, d'une famille infinie de graphes k-réguliers de Ramanujan dont le nombre de sommets tend vers l'infini. Tue, 23 Jun 2026 22:00:00 GMT http://hdl.handle.net/2268.2/26605 2026-06-23T22:00:00Z http://hdl.handle.net/2268.2/25528 Title: Résultats autour de la conjecture d'Hartmanis et Stearns Abstract: S'il est connu que les rationnels ont une représentation en base b ultimement périodique, et ce pour tout entier b ≥ 2, que peut-on dire sur la représentation en base b des nombres irrationnels, et en particulier des irrationnels algébriques ? La conjecture de Borel prédit notamment que tout irrationnel algébrique est normal dans toute base b ≥ 2. Afin d’étudier cette question, nous adoptons le cadre de la théorie de la complexité introduit par Hartmanis et Stearns en 1965 à l’aide des machines de Turing. Leur approche consiste à mesurer le temps nécessaire à une machine de Turing pour produire les chiffres du développement d’un nombre réel. Ils posent alors la question suivante : existe-t-il des irrationnels algébriques dont le développement en base b peut être généré en temps linéaire ? La conjecture de Hartmanis et Stearns, toujours ouverte aujourd’hui, postule que la réponse est négative. Dans ce mémoire, nous étudions plusieurs restrictions de cette question en considérant des modèles de calcul plus faibles que les machines de Turing, et montrons que ces modèles ne permettent pas de produire le développement en base b d’un irrationnel algébrique. Tue, 23 Jun 2026 22:00:00 GMT http://hdl.handle.net/2268.2/25528 2026-06-23T22:00:00Z