Algorithmes probabilistes, approximation, séparation et évaluation
Cours · informatique (MP2I/MPI), chapitre 25 · MP2I et MPI · le début du chapitre, la suite sur Adloun
25.1 Trois façons de renoncer
Le chapitre chap:exploration s'achevait sur un constat : le retour sur trace reste exponentiel, et sur certains problèmes personne ne connaît mieux. Le chapitre chap:decidabilite dira pourquoi. Entre les deux, celui-ci répond à la question pratique : que fait-on quand l'exact est hors de portée ?
Trois renoncements, et chacun garde quelque chose :
| On renonce à… | On garde… | Nom |
|---|---|---|
| la certitude du résultat | un temps borné | Monte-Carlo |
| un temps borné | la certitude du résultat | Las Vegas |
| l'optimalité | une garantie sur l'écart | approximation |
| rien (on reste exact) | un élagage plus fort | séparation et évaluation |
25.2 Algorithmes probabilistes
Un algorithme déterministe produit toujours le même résultat en le même temps sur la même entrée. Un algorithme probabiliste consulte une source d'aléa. On en distingue deux familles, et le programme les nomme toutes deux :
- Las Vegas : le résultat est toujours correct, le temps d'exécution est aléatoire ;
- Monte-Carlo : le temps est borné, le résultat peut être faux avec une probabilité contrôlée.
Le programme borne l'exigence : « on s'en tient aux définitions et à des exemples choisis par le professeur ».
Le programme cite ce problème ici, après l'avoir cité au chapitre chap:exploration pour le retour sur trace. La version Las Vegas est brutale :
(* Renvoie un placement valide de n reines. Précondition : n >= 4.
TOUJOURS correct ; temps aléatoire. *)
let rec reines_las_vegas n =
let pos = Array.init n (fun i -> i) in
melanger pos; (* une permutation au hasard *)
if valide pos then pos else reines_las_vegas nUne permutation garantit déjà qu'aucune reine ne partage sa ligne ni sa colonne : il ne reste à vérifier que les diagonales. Le résultat rendu est toujours valide ; c'est le nombre d'essais qui est aléatoire.
Le programme donne la vraie motivation : « on mentionne l'intérêt d'une méthode Las Vegas pour construire un objet difficile à produire par une méthode déterministe (par exemple, construction d'un nombre premier de taille cryptographique) ».
Pour engendrer un nombre premier de bits, personne ne sait en construire un directement. On procède donc ainsi : tirer un entier impair au hasard, tester sa primalité, recommencer s'il est composé. Le théorème des nombres premiers assure qu'environ un entier sur est premier ; en ne tirant que des impairs, il en faut environ . C'est immédiat, et aucune méthode déterministe n'approche cette efficacité.
Le hasard n'est pas ici un pis-aller : c'est le seul procédé connu.
Le quickselect choisit un pivot au hasard et ne récurse que d'un côté :
(* k-ième plus petit élément de t (k à partir de 0).
Précondition : 0 <= k < longueur. Espérance : Theta(n) ; pire cas : Theta(n²). *)
let rec selection t k =
let pivot = t.(hasard (Array.length t)) in
let inf = filtre (fun x -> x < pivot) t
and egal = filtre (fun x -> x = pivot) t
and sup = filtre (fun x -> x > pivot) t in
if k < Array.length inf then selection inf k
else if k < Array.length inf + Array.length egal then pivot
else selection sup (k - Array.length inf - Array.length egal)C'est encore un Las Vegas, et non un Monte-Carlo : le résultat est toujours le bon élément, seul le temps est aléatoire. Le programme cite ce problème sans le classer ; la définition donnée plus haut tranche.
Trier coûterait ; ici l'espérance est , car le pivot aléatoire élimine en moyenne la moitié du tableau. Le pire cas reste — mais il exige une suite de pivots systématiquement extrêmes, dont la probabilité décroît exponentiellement. Aucun adversaire ne peut la provoquer, puisqu'il ne connaît pas les tirages.