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

Induction structurelle

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 introduit le concept d'induction structurelle, une méthode pour prouver les propriétés des éléments dans des ensembles définis récursivement, étroitement liés à l'induction mathématique. À travers des exemples avec des chaînes et des formules bien formées, l'instructeur illustre comment appliquer l'induction structurelle pour prouver des propriétés sur des structures définies récursivement.

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

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.

Induction structurelle

En mathématiques et davantage en informatique, la définition récursive ou induction structurelle est un procédé de définition conjointe d'un type (classe ou ensemble) et d'objets (éléments) qui le compose au moyen de règles de construction (constructeurs) qui agencent ou structurent ces objets. L'on peut ainsi définir des nombres, des listes, des arbres, des relations, et plus généralement, toute structure mathématique (langage, système, ...). En permettant par le même principe de définir un prédicat total i.

Formule logique

En logique on dit d’une suite finie de lettres qu’elle est une formule, ou parfois formule bien formée, d'un langage logique donné lorsqu’elle peut être construite en appliquant une combinaison des règles de la grammaire formelle associée, on parle de la syntaxe du langage. Informellement les formules sont les assemblages de lettres auxquels il est possible de donner une signification en termes de valeur de vérité (Vrai, ou Faux). Les formules logiques sont l'équivalent des phrases du langage naturel.

Formule atomique

En logique mathématique, une formule atomique ou atome est une formule qui ne contient pas de sous-formules propres. La structure d'une formule atomique dépend de la logique considérée, p. ex. en logique des propositions, les formules atomiques sont les variables propositionnelles. Les atomes sont les formules les plus simples dans un système logique et servent à construire les formules les plus générales.

Démonstration (logique et mathématiques)

vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.

Afficher plus

Séances de cours associées (28)

Induction structurelle

Introduit l'induction structurelle, une méthode pour prouver les propriétés des éléments dans des ensembles définis récursivement.

Numéros de Fibonacci: Récursion et induction

Explore les nombres de Fibonacci, la croissance de la population de lapins et les fonctions définies récursivement.

Induction et récurrence : résumé

Couvre l'induction mathématique, les fonctions définies récursivement et les algorithmes itératifs pour la résolution de problèmes.

Induction et Récursivité : Quiz

Couvre des sujets liés à l'induction et à la récursion, y compris les épreuves d'induction mathématiques et les définitions récursives.

Formules logiques et types: comprendre l'isomorphisme de Kerry Howard

Explore l'isomorphisme de Kerry Howard, traduisant des propositions logiques en types et en termes, en mettant l'accent sur la preuve par induction et la préparation à l'examen.

Afficher plus

Concepts associés (13)

Raisonnement par récurrence

Induction structurelle

Formule logique

Formule atomique

Démonstration (logique et mathématiques)

Afficher plus