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

Comptage avancé: Exemples

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 les techniques de comptage avancées, telles que la résolution des relations de récurrence linéaire et l'utilisation de fonctions génératrices. L'instructeur explique comment trouver des racines et des solutions pour différentes équations caractéristiques, avec des exemples comprenant la séquence de Fibonacci. De plus, la séance de cours explore les différences entre les dés et les cartes de poker en termes de combinaisons et de réalisations.

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 (32)

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.

Série génératrice

En mathématiques, et notamment en analyse et en combinatoire, une série génératrice (appelée autrefois fonction génératrice, terminologie encore utilisée en particulier dans le contexte de la théorie des probabilités) est une série formelle dont les coefficients codent une suite de nombres (ou plus généralement de polynômes) ; on dit que la série est associée à la suite. Ces séries furent introduites par Abraham de Moivre en 1730, pour obtenir des formules explicites pour des suites définies par récurrence linéaire.

Généralisations de la suite de Fibonacci

En mathématiques, la suite de Fibonacci est définie par récurrence par : pour tout entier . Autrement dit, les deux valeurs de départ 0 et 1 étant données, chaque nombre est la somme des deux précédents. La suite de Fibonacci peut être généralisée de nombreuses façons ; par exemple, en partant d'autres nombres que 0 et 1, en ajoutant plus de deux termes pour générer le suivant, ou en ajoutant des objets autres que des nombres. À l'aide de la relation , on peut étendre la suite de Fibonacci à des indices entiers négatifs.

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 (48)

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.

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

Couvre la définition des relations de récurrence et leur application dans les problèmes de comptage.

Compter avec les relations de récurrence: Résumé

Explore le comptage avec les relations de récurrence, les relations de récurrence linéaires, la génération de fonctions et les principes de comptage.

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.

Générer des fonctions: Comptage avancé

Couvre la définition des fonctions génératrices et leur application dans la résolution des relations de récurrence.

Afficher plus

Concepts associés (32)

Suite de Fibonacci

Mot de Fibonacci

Série génératrice

Généralisations de la suite de Fibonacci

Codage de Fibonacci

Afficher plus