Exercices corrigés — Algorithmes probabilistes, approximation, séparation et évaluation (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Ranger six algorithmes
- MAX2SAT : la valeur d'un tirage
- Décision, optimisation, instance
- MAX--\textsc{sat} : la garantie en fonction de
- La clause qui répète une variable
- Les huit reines par le hasard
- Une heuristique n'est pas une approximation
- Convertir Las Vegas en Monte-Carlo, et retour
- Une borne trop basse coupe l'optimum, et se tait
- Quickselect : la constante, et le pire cas
- Probleme – MAX2SAT : du hasard au déterminisme
- Probleme – Fabriquer un nombre premier
- Probleme – Le sac à dos par séparation et évaluation
- Probleme – Le voyageur de commerce métrique
- Probleme – La coupe maximale : le hasard, puis mieux