Exercices corrigés — Ordres bien fondés et induction structurelle (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Ordre, ou pas ?
- Minimal n'est pas minimum, et l'on peut les compter
- Produit ou lexicographique : compter les comparables
- Bien fondé, ou pas
- Ackermann : ce qui décroît quand rien ne décroît
- Pourquoi « le plus petit » est indispensable
- Induction structurelle sur les listes
- Une identité sur les formules
- McCarthy 91 : le variant n'est pas un argument
- Quand on ne sait pas construire l'ordre
- Probleme – Les mots bien parenthésés, ou deux définitions pour une famille
- Probleme – Le sac de billes
- Probleme – La récurrence forte est une induction bien fondée
- Probleme – Une récursion qui n'est pas structurelle
- Probleme – Le tri par insertion, prouvé entièrement par induction structurelle