Mot de Fibonacci

En mathématiques et plus précisément en combinatoire des mots, un mot de Fibonacci est une suite particulière de symboles pris dans un alphabet quelconque de deux lettres. Les mots de Fibonacci sont à l'opération de concaténation ce que les nombres de Fibonacci sont à l'addition. Le mot de Fibonacci infini est l'exemple paradigmatique de mot sturmien. Le nom « mot de Fibonacci » réfère aussi parfois aux éléments d'un langage formel composé des mots sur un alphabet de deux lettres et et ne contenant pas deux consécutifs. Le nombre de mots de longueur n dans ce langage est le n-ième nombre de Fibonacci. Fixons l'alphabet à . La suite des mots de Fibonacci est définie par et , et pour , par : (le produit est la concaténation des deux précédents termes). Le mot infini de Fibonacci, noté , est la limite de cette suite, c'est-à-dire l'unique mot infini dont tous les mots sont des préfixes. Les mots de Fibonacci sont appelés ainsi par analogie avec les nombres de Fibonacci, puisque le procédé de construction est analogue, en remplaçant l'addition par la concaténation. Les premiers mots de Fibonacci sont : Le mot infini de Fibonacci commence donc par : 0100101001001010010100100101001001... Ce mot infini est la . On trouve dans la littérature également le terme Rabbit sequence (c'est-à-dire « suite de lapins », en référence au problème de la croissance du nombre de lapins, de génération en génération). La n-ième lettre du mot de Fibonacci est où φ est le nombre d'or et est la fonction partie entière. Le mot infini de Fibonacci est donc le mot sturmien de pente 2 – φ = 1/φ, tandis que la suite du Lapin est de pente φ – 1 (voir figure plus haut). Les mots de Fibonacci peuvent être définis via un morphisme (ou substitution). Partant d'un mot de Fibonacci , on obtient le mot en : remplaçant la lettre "1" par "0" remplaçant la lettre "0" par "01" Que l'on peut aussi écrire : avec le morphisme défini par : et et, pour le mot infini de Fibonacci, . On dit aussi que le mot infini de Fibonacci est le point fixe du morphisme car .

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (2)

Cours associés (2)

Séances de cours associées (48)

Tight bounds on the AUH codes

Ali Kakhbod

In this paper we consider the class of anti-uniform Huffman codes and derive tight lower and upper hounds on the average length, entropy, and redundancy of such codes in terms of the alphabet size of the source. Also an upper bound on the entropy of AUH codes is also presented in terms of the average cost of the code. The Fibonacci distributions are introduced which play a fundamental role in AUH codes. It is shown that such distributions maximize the average length and the entropy of the code for a given alphabet size. Another previously known bound on the entropy for given average length follows immediately from our results.

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2008

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

MATH-111(e): Linear Algebra

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications.

Mot de Fibonacci

Suite de Fibonacci

vignette|Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13 et 21. En mathématiques, la suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Notée , elle est définie par , et pour . Les termes de cette suite sont appelés nombres de Fibonacci et forment la : vignette|Représentation géométrique de la fraction continue de φ faisant apparaître les nombres de la suite de Fibonacci.

Logique et algorithmes CS-101: Advanced information, computation, communication I

Couvre la logique, le raisonnement mathématique, les structures de base et les algorithmes, explorant les preuves, les ensembles, les fonctions et la récursion.

Relations, séquences, sommation CS-101: Advanced information, computation, communication I

Couvre les progressions arithmétiques, les treillis, la vérification formelle, les chaînes, les formules explicites, les relations de récurrence, les formules fermées et l'argument Diagonal de Cantor.

Calcul des séquences de Fibonacci CS-119(h): Information, Computation, Communication

Couvre le calcul de la séquence Fibonacci à l'aide de Python, démontrant l'implémentation étape par étape.