Topic outline

  • General

  • Pour bien commencer

    Les définitions inductives et les définitions par récurrence consistent à construire des objets finis à partir d'autres selon certaines règles. Les définitions inductives permettent également d'appréhender les objets infinis définis par des définitions récursives. Comme l'informatique manipule précisément des objets de ce type, que les définitions récursives interviennent dans les structures de données de même que dans la conception de programmes récursifs, ce corpus est essentiel. Les preuves de tels programmes se font alors par récurrence.

    Ce corpus commence par les deux principes de récurrence (faible et forte) sur les entiers. Le troisième module introduit la notion de définitions récursives et induction structurelle et montre comment prouver des propriétés d'ensembles données par des définitions inductives. Quant au quatrième module — Pour aller plus loin —, il revient sur le processus de définition constructive issue de la définition inductive d'un ensemble, opérations de construction appelées règles d'inférence.

    Vous y trouverez des activités :

    Apprendre comprenant un module de [Cours] lequel comprend :

    • Une partie [Notions de base].
    • Éventuellement une partie [Pour aller plus loin] qui concerne principalement ceux qui veulent approfondir les notions.

    S'exercer comprenant :

    • Éventuellement le module [Comprendre le cours avec solutions] permettant d'appliquer les notions de [Cours] avec des exercices auto-évaluées et des exercices détaillés.
    • Les modules [Exercices] et [Exercices avec solutions]. Le lecteur ne doit pas hésiter à consacrer du temps à un travail personnel de recherche en s'appuyant sur le cours et les aides successives proposées dans les exercices. Il doit ensuite rédiger avec soin ses travaux et les comparer avec les solutions proposées.

    S'évaluer comprenant des exercices d'auto-évaluation permettant de vous évaluer et de vous positionner dans votre apprentissage : [N12] concernant la partie [Notions de base] avec des exercices taggés de niveau 1 et 2 ainsi qu'éventuellement [N34] concernant la partie [Pour aller plus loin] et/ou des exercices de niveau 3 et 4 de la partie [Notions de base].
    • Le système tire au hasard un certain nombre de questions.
    • La note minimale de validation (sur 10) est indiquée pour chaque test.

    Évaluation finale termine le module. Attention! vous n'avez droit qu'à une seule tentative.

    URL: 1

  • S1 - Récurrence mathématique (8h - 10h)

    Objectifs : Savoir effectuer un raisonnement par récurrence, Distinguer vérité et hérédité, Savoir écrire une somme ou un produit symbolique
    Pour aller plus loin : Appliquer un raisonnement par récurrence sur des exemples moins standard (combats de tartes, pavages)
    Text and media areas: 3 URLs: 4

  • S2 - Récurrence forte (4h - 6h)

    Objectifs : Savoir effectuer un raisonnement par récurrence forte, Distinguer une récurrence forte d'une récurrence faible
    Text and media areas: 3 URLs: 3

  • S3 - Définitions récursives et induction structurelle (4h - 6h)

    Objectifs : Appliquer une définition récursive, Donner une définition récursive d'une fonction, Donner une définition inductive d'un ensemble, Effectuer une preuve par induction structurelle
    Text and media areas: 3 URLs: 3

  • S4 : Pour aller plus loin : Système d'inférence (4h - 6h)

    Objectifs : Comprendre une définition d'un ensemble décrit par des règles d'inférence, Utiliser des règles d'inférence pour construire un arbre de dérivation ou une preuve directe d'appartenance à un ensemble, Comprendre un argument de preuve par induction sur une définition par règle d'inférence
    Text and media areas: 2 URLs: 3

  • Évaluation finale "Récurrence et Induction" et crédits

    URL: 1 Text and media area: 1