Exercices corrigés — Exploration exhaustive et retour sur trace (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Ordonner avant de parcourir : deux nombres de somme donnée Exercice de TD
- Ce que chaque test d'élagage rapporte Exercice de TD
- Énumérer les permutations d'un mot à lettres répétées Exercice de TD
- L'ordre des choix change tout Exercice de TD
- Le même sous-problème, vingt-deux millions de fois Exercice de TD
- Problème — Colorier un graphe, et casser les symétries Exercice de TD
- Problème — Le voyageur de commerce : quatre niveaux d'élagage Exercice de TD
- Trois seuils, et ce qu'une machine mille fois plus rapide y change Application directe du cours
- Le masque qui déborde Application directe du cours
- La ligne qu'on oublie : combien de solutions produit-elle ? Application directe du cours
- Compter les chemins hamiltoniens, avec la grille complète Application directe du cours
- Le même élagage, dix fois plus vite Application directe du cours
- Problème — Le sudoku : la même exploration, deux ordres de choix Application directe du cours
- Problème — La droite de balayage Application directe du cours
- Problème — Les mots bien parenthésés, et pourquoi ils sont si peu nombreux Application directe du cours