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

Numéros de Fibonacci: Récursion et induction

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 nombres de Fibonacci, le problème de la croissance de la population de lapins, les propriétés des nombres de Fibonacci, et l'utilisation de l'induction pour prouver ces propriétés. Il explore également des fonctions, des ensembles et des structures définis de manière récursive.

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

Proximité ontologique

Logique

Logique classique: Calcul des prédicats

Concepts associés (32)

Raisonnement par récurrence

vignette|Le raisonnement par récurrence est comme une suite de dominos. Si la propriété est vraie au rang n0 (i. e. le premier domino de numéro 0 tombe) et si sa véracité au rang n implique celle au rang n + 1 (i. e. la chute du domino numéro n fait tomber le domino numéro n + 1) alors la propriété est vraie pour tout entier (i. e. tous les dominos tombent). En mathématiques, le raisonnement par récurrence (ou par induction, ou induction complète) est une forme de raisonnement visant à démontrer une propriété portant sur tous les entiers naturels.

Récursivité

La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle.

Algorithme récursif

Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus petites du même problème. L'approche récursive est un des concepts de base en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité. Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même.

Fonction récursive primitive

En théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas de récursion primitive (ou bornée) et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. Elles ont été initialement analysées par la mathématicienne Rózsa Péter. On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des -uplets d'entiers naturels, et à valeurs dans .

Définition par récurrence

vignette|4 étapes de la construction d'un flocon de Koch. Comme beaucoup d'autres fractales, cette courbe est définie par récurrence. En mathématiques, on parle de définition par récurrence pour une suite, c'est-à-dire une fonction définie sur les entiers positifs et à valeurs dans un ensemble donné. Une fonction est définie par récurrence quand, pour définir la valeur de la fonction en un entier donné, on utilise les valeurs de cette même fonction pour des entiers strictement inférieurs.

Afficher plus

Séances de cours associées (47)

Ensembles et opérations: Introduction aux mathématiques

Couvre les bases des ensembles et des opérations en mathématiques, des propriétés des ensembles aux opérations avancées.

Produit cartésien et induction

Présente le produit cartésien et l'induction pour les épreuves utilisant des entiers et des ensembles.

Induction mathématique: bases et applications

Introduit des principes et des applications d'induction mathématique, y compris les inégalités, la divisibilité, les sous-ensembles et l'induction forte.

Fonctions définies récursivement

Introduit des fonctions définies récursivement et démontre comment calculer des valeurs et prouver des propriétés en utilisant l'induction mathématique.

Aperçu du cours: Teaser on Course Contents

Offre un aperçu de la logique propositionnelle et des prédicats, des ensembles, des fonctions, des relations, des algorithmes, des villes suisses, des tables de tri, des infections Covid, des mains de poker et des nombres premiers.

Afficher plus

Concepts associés (32)

Raisonnement par récurrence

Récursivité

Algorithme récursif

Fonction récursive primitive

Définition par récurrence

Afficher plus