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 Exercice de TD
- Décision, optimisation, instance Exercice de TD
- MAX2SAT : la valeur d'un tirage Exercice de TD
- Convertir Las Vegas en Monte-Carlo, et retour Exercice de TD
- Une heuristique n'est pas une approximation Exercice de TD
- Une borne trop basse coupe l'optimum, et se tait Exercice de TD
- Problème — Le voyageur de commerce métrique Exercice de TD
- MAX--sat : la garantie en fonction de Application directe du cours
- La clause qui répète une variable Application directe du cours
- Les huit reines par le hasard Application directe du cours
- Quickselect : la constante, et le pire cas Application directe du cours
- Problème — MAX2SAT : du hasard au déterminisme Application directe du cours
- Problème — Fabriquer un nombre premier Application directe du cours
- Problème — Le sac à dos par séparation et évaluation Application directe du cours
- Problème — La coupe maximale : le hasard, puis mieux Application directe du cours