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.
- Bien fondé, ou pas Exercice de TD
- Pourquoi « le plus petit » est indispensable Exercice de TD
- Induction structurelle sur les listes Exercice de TD
- Une identité sur les formules Exercice de TD
- Ackermann : ce qui décroît quand rien ne décroît Exercice de TD
- Problème — Le sac de billes Exercice de TD
- Problème — Les mots bien parenthésés, ou deux définitions pour une famille Exercice de TD
- Ordre, ou pas ? Application directe du cours
- Minimal n'est pas minimum, et l'on peut les compter Application directe du cours
- Produit ou lexicographique : compter les comparables Application directe du cours
- McCarthy 91 : le variant n'est pas un argument Application directe du cours
- Quand on ne sait pas construire l'ordre Application directe du cours
- Problème — La récurrence forte est une induction bien fondée Application directe du cours
- Problème — Une récursion qui n'est pas structurelle Application directe du cours
- Problème — Le tri par insertion, prouvé entièrement par induction structurelle Application directe du cours