Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Compter avec les relations de récurrence: Fibonacci Séquence et Bit Strings

Dans cours

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 as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours couvre la définition des relations de récurrence et leur application dans les problèmes de comptage, tels que la séquence de Fibonacci et les chaînes de bits sans 0 consécutifs. Il explore également le puzzle de la tour de Hanoi et les défis de compter les arrangements des parenthèses.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Concepts associés (22)

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.

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.

Suite définie par récurrence

En mathématiques, une suite définie par récurrence est une suite définie par son (ou ses) premier(s) terme(s) et par une relation de récurrence, qui définit chaque terme à partir du précédent ou des précédents lorsqu'ils existent. Une relation de récurrence est une équation dans laquelle l'expression de plusieurs termes de la suite apparait, par exemple : ou ou ou si l'on se place dans les suites de mots sur l'alphabet : Si la relation de récurrence a une « bonne » présentation, cela permet de calculer l'expression du terme d'indice le plus élevé en fonction de l'expression des autres.

Linear recurrence with constant coefficients

In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear in the various iterates of a variable—that is, in the values of the elements of a sequence. The polynomial's linearity means that each of its terms has degree 0 or 1.

Codage de Fibonacci

Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont chaque terme est la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs. Le code de Fibonacci produit est un code préfixe et universel. Dans ce code, on utilise la représentation de Zeckendorf, de telle façon que la séquence « 11 », interdite dans le nombre, apparaisse uniquement en fin de codage, et serve ainsi de délimiteur.

Afficher plus

Séances de cours associées (49)

Comptage avancé: Exemples

Couvre les techniques de comptage avancées, y compris les relations de récurrence linéaire et les fonctions génératrices, avec des exemples de la séquence de Fibonacci et des différences entre les dés et les cartes de poker.

Nombres de Fibonacci et rapport d'or

Explore la séquence de Fibonacci, les identités, le rapport d'or et les formules explicites.

Relations de récurrence linéaire

Explore les relations de récurrence linéaires, y compris des exemples comme les nombres de Fibonacci et la preuve de théorèmes liés.

Relation linéaire de récurrence : Techniques de résolution

Explore les relations linéaires homogènes de récurrence, les techniques de résolution, les équations caractéristiques et des exemples comme les nombres de Fibonacci.

Séquences de nombres: Devinez, Fibonacci, Relations de récurrence

Couvre l'identification des séquences de nombres et la résolution des relations de récurrence.

Afficher plus

Concepts associés (22)

Suite de Fibonacci

Mot de Fibonacci

Suite définie par récurrence

Linear recurrence with constant coefficients

Codage de Fibonacci

Afficher plus