Exercices corrigés — Diviser pour régner (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Pourquoi le milieu ne s'écrit pas
- Le nombre exact de comparaisons
- Le comptage des inversions du cours donne 1 sur une liste triée
- Une ligne qui coûte un ordre de grandeur
- Dichotomiser sur la réponse : la racine carrée entière
- Dichotomiser sur les valeurs candidates, et non sur les réels
- Ce que la rencontre au milieu énumère vraiment
- Trois récurrences, trois régimes
- Karatsuba : trois produits au lieu de quatre
- La dichotomie entière qui ne se termine pas
- Probleme – Le tri par partition-fusion sur tableaux : coût exact et stabilité
- Probleme – Élever à une puissance, et Fibonacci en
- Probleme – La paire de points la plus proche, du croquis au programme
- Probleme – Un même problème, trois méthodes, trois compromis
- Probleme – Le tri rapide : pourquoi il gagne en moyenne et perd au pire