Algorithmes probabilistes et d'approximation

Résumé en cinq points

Algorithmes déterministes et probabilistes

Algorithme déterministe

Un algorithme est déterministe si, pour une entrée donnée, la suite des instructions exécutées est entièrement fixée : même résultat et même temps à chaque exécution.

Algorithme probabiliste

Un algorithme probabiliste peut en plus effectuer des tirages aléatoires, par exemple un entier uniforme entre 0 et n − 1 (Random.int n en OCaml). On les suppose indépendants et uniformes, ce qui idéalise les générateurs pseudo-aléatoires.

Pour une entrée fixée, résultat et temps deviennent des variables aléatoires. Point essentiel : les probabilités portent sur les tirages de l'algorithme, l'entrée étant fixée et quelconque. Rien n'est supposé sur la loi des entrées, contrairement à la complexité en moyenne d'un algorithme déterministe.

Algorithme de type Las Vegas

Un algorithme Las Vegas rend toujours un résultat correct. Seul son temps d'exécution est aléatoire. On l'analyse par l'espérance de ce temps, dans le pire cas sur les entrées. Exemple : le tri rapide à pivot uniforme trie toujours, en temps espéré O(n log n).

Variante fréquente : une tentative en temps borné réussit avec probabilité p > 0 ou signale un échec, sans jamais rendre de résultat faux. La relancer jusqu'au succès donne un Las Vegas. Le nombre de tentatives suit une loi géométrique de paramètre p, d'espérance 1/p.

Algorithme de type Monte Carlo

Un algorithme Monte Carlo a un temps d'exécution borné quels que soient les tirages, mais son résultat peut être faux, avec une probabilité d'erreur bornée pour toute entrée.

Pour un problème de décision (réponse oui ou non), on distingue :

• erreur unilatérale : une des deux réponses est toujours sûre. Si c'est « non », l'erreur consiste à répondre « oui » quand la bonne réponse est « non », avec une probabilité au plus q < 1.
• erreur bilatérale : les deux réponses peuvent être fausses, chacune avec une probabilité au plus q < 1/2.

Amplification unilatérale : on répète k fois, tirages indépendants, et on répond « non » dès qu'une exécution le fait. L'erreur exige que les k exécutions se trompent, d'où une probabilité au plus q^k. Dans le cas bilatéral, on garde la réponse majoritaire. L'analyse de ce vote est hors programme.

Passer d'un type à l'autre

• De Las Vegas à Monte Carlo : si le temps espéré est au plus T, on coupe l'exécution après 2T étapes. Par l'inégalité de Markov, l'échec a une probabilité au plus 1/2.
• De Monte Carlo à Las Vegas : quand on sait vérifier efficacement une réponse, on relance jusqu'à obtenir une réponse vérifiée.

Exemples d'algorithmes probabilistes

k-ième minimum d'un tableau non trié (Las Vegas)

Entrée : n éléments comparables et un entier k avec 1 ≤ k ≤ n. Sortie : l'élément de rang k dans l'ordre croissant. On tire un pivot uniformément, on répartit les éléments en plus petits, égaux et plus grands que le pivot, puis on poursuit dans la seule partie qui contient le rang k.

(* hypothèse : 1 <= k <= List.length l *)
let rec kieme k l =
  let p = List.nth l (Random.int (List.length l)) in
  let petits = List.filter (fun x -> x < p) l in
  let egaux = List.filter (fun x -> x = p) l in
  let grands = List.filter (fun x -> x > p) l in
  let a = List.length petits and b = List.length egaux in
  if k <= a then kieme k petits
  else if k <= a + b then p
  else kieme (k - a - b) grands

Correction : le rang cherché est conservé (on retranche a + b en passant aux grands) et la liste raccourcit strictement, puisque le pivot en sort. Le résultat est toujours juste : Las Vegas.

Complexité : au pire Θ(n²), si le pivot tombe sans cesse sur un extrême. En espérance, O(n). Idée : avec une probabilité d'environ 1/2, le pivot a un rang entre n/4 et 3n/4 et la partie conservée a au plus 3n/4 éléments. Il faut en moyenne environ deux tirages, de coût O(n) chacun, pour un tel bon pivot. Les tailles décroissent géométriquement et n(1 + 3/4 + (3/4)² + …) = 4n. On bat ainsi le tri préalable en O(n log n).

Problème des huit reines (Las Vegas)

Il faut placer huit reines sur un échiquier 8 × 8 sans que deux soient sur une même ligne, colonne ou diagonale. Méthode aléatoire : ligne après ligne, on place la reine sur une colonne tirée uniformément parmi les cases non menacées. Si aucune case n'est libre, on recommence tout depuis la première ligne.

Quand l'algorithme s'arrête, la configuration est valide : il est Las Vegas. Il existe des solutions (92 au total) et chacune peut être tirée avec une probabilité strictement positive, donc une tentative réussit avec une probabilité p > 0. Le nombre de tentatives suit une loi géométrique, de moyenne 1/p.

Construire un nombre premier de taille cryptographique

La cryptographie demande des nombres premiers d'environ 1 024 bits, qu'aucune formule déterministe efficace connue ne produit. Méthode : tirer un entier impair de 1 024 bits au hasard, tester s'il est premier, recommencer sinon.

Le théorème des nombres premiers (admis) dit que la proportion de nombres premiers au voisinage de N est d'environ 1/ln N. Pour N ≈ 2¹⁰²⁴, ln N ≈ 710. Parmi les impairs, la proportion double, soit environ 1/355. Le nombre de tirages suit une loi géométrique, de moyenne de l'ordre de 355. Avec un test de primalité exact, la méthode est Las Vegas : le nombre rendu est toujours premier, seul le nombre d'essais est aléatoire.

Hors programme, pour la culture : en pratique, on teste avec Miller-Rabin, Monte Carlo à erreur unilatérale, et l'ensemble devient un Monte Carlo à erreur infime.

Un exemple de Monte Carlo : vérifier un produit de matrices

Entrée : trois matrices carrées A, B, C de taille n. Question : AB = C ? Méthode de Freivalds : tirer r dans {0, 1}ⁿ uniformément et comparer A(Br) avec Cr, en O(n²) au lieu du O(n³) d'un produit naïf. S'ils diffèrent, on répond « non », et c'est sûr. Sinon on répond « oui ».

Si AB ≠ C, D = AB − C a un coefficient d_ij non nul. La coordonnée i de Dr vaut d_ij r_j plus un terme indépendant de r_j. Les autres coordonnées fixées, au plus une valeur de r_j l'annule. Donc l'erreur a une probabilité au plus 1/2 : Monte Carlo à erreur unilatérale, ramenée à 2^−k par k répétitions.

Problèmes de décision et d'optimisation

Problème, instance, problème de décision

Un problème est décrit par ses entrées possibles, les instances, et la sortie attendue pour chacune. Un problème de décision attend une réponse oui ou non. Exemple : étant donnés un graphe G et un entier k, G admet-il une couverture de sommets d'au plus k sommets ?

Problème d'optimisation, fonction de coût

Un problème d'optimisation associe à chaque instance un ensemble de solutions admissibles et une fonction de coût (ou de valeur) sur ces solutions. On cherche une solution admissible de coût minimal (ou de valeur maximale), de valeur notée OPT. Exemple : trouver une couverture de sommets de taille minimale.

À tout problème d'optimisation correspond un problème de décision : existe-t-il une solution de coût au plus k (ou de valeur au moins k) ? Pour beaucoup de problèmes naturels, couverture de sommets, sac à dos, MAX2SAT, on ne connaît aucun algorithme exact en temps polynomial en la taille de l'entrée. Pour le sac à dos, la programmation dynamique en O(nW) n'est que pseudo-polynomiale, car W s'écrit sur environ log W bits.

Algorithme d'approximation

Un algorithme d'approximation de facteur ρ est un algorithme en temps polynomial qui, sur toute instance, renvoie une solution admissible s avec :

• pour une minimisation : coût(s) ≤ ρ × OPT, avec ρ ≥ 1.
• pour une maximisation : valeur(s) ≥ OPT / ρ, avec ρ ≥ 1. On écrit aussi valeur(s) ≥ ρ' × OPT avec ρ' ≤ 1, par exemple ρ' = 1/2 ou 3/4. Il faut préciser la convention.

La garantie vaut pour toutes les instances. Comme OPT est inconnu, la preuve le compare à une borne calculable, inférieure pour une minimisation, supérieure pour une maximisation.

L'étude de techniques générales d'approximation est hors programme.

MAX2SAT : la méthode probabiliste donne une approximation

Instance : n variables booléennes et m clauses, chacune formée de deux littéraux portant sur deux variables distinctes, comme x₁ ∨ ¬x₃. Problème : trouver une affectation qui satisfait le plus grand nombre de clauses. Décider si toutes les clauses sont satisfiables à la fois (2SAT) est polynomial, mais on ne connaît pas d'algorithme polynomial pour maximiser.

Algorithme : donner à chaque variable la valeur vrai ou faux avec probabilité 1/2, indépendamment. Coût O(n + m).

Calcul : une clause ℓ₁ ∨ ℓ₂ est fausse si et seulement si ses deux littéraux sont faux. Les variables étant distinctes, ces deux événements sont indépendants, chacun de probabilité 1/2. La clause est donc fausse avec probabilité 1/4, vraie avec probabilité 3/4. Le nombre X de clauses satisfaites est une somme d'indicatrices. Par linéarité de l'espérance, qui ne demande aucune indépendance entre clauses, E(X) = 3m/4. Comme OPT ≤ m, on obtient E(X) ≥ (3/4) OPT.

Hypothèse indispensable : sinon, x ∨ ¬x est toujours vraie et x ∨ x ne l'est qu'avec probabilité 1/2.

Conséquences :

• Existence : une variable aléatoire prend au moins une fois une valeur supérieure ou égale à son espérance. Il existe donc une affectation satisfaisant au moins 3m/4 clauses.
• Garantie certaine : soit p la probabilité que X ≥ 3m/4. Si X < 3m/4, alors 4X ≤ 3m − 1 puisque 4X et 3m sont entiers. En majorant X par m dans l'autre cas, 3m/4 = E(X) ≤ (1 − p)(3m − 1)/4 + p m, d'où 1 − p ≤ p m, soit p ≥ 1/(m + 1). En retirant une affectation jusqu'à en trouver une qui satisfait au moins 3m/4 clauses, ce qui se vérifie en O(m), on obtient un Las Vegas qui fait en moyenne au plus m + 1 tirages, donc en temps polynomial en moyenne, et garantit le facteur 3/4.

Approximation par la méthode gloutonne

Un algorithme glouton enchaîne des choix locaux définitifs. Exact pour certains problèmes (première année), il fournit ici seulement une solution garantie.

Couverture de sommets

Une couverture de sommets d'un graphe non orienté G = (S, A) est un ensemble C de sommets tel que toute arête a au moins une extrémité dans C. On cherche C de taille minimale.

Algorithme par couplage maximal : C est vide au départ. Tant qu'il reste une arête {u, v} dont aucune extrémité n'est dans C, on ajoute u et v à C. Un parcours des arêtes suffit, en O(|S| + |A|).

Correction : à la fin, aucune arête n'a ses deux extrémités hors de C, donc C est une couverture.

Facteur 2 : soit M l'ensemble des arêtes choisies. Deux arêtes de M n'ont aucune extrémité commune, puisqu'on ne choisit que des arêtes aux deux extrémités libres. M est donc un couplage (maximal) et |C| = 2|M|. Toute couverture optimale contient au moins une extrémité de chaque arête de M, extrémités toutes différentes. Donc OPT ≥ |M|, puis |C| = 2|M| ≤ 2 OPT.

Le facteur 2 est atteint : sur un graphe réduit à une arête, l'algorithme prend deux sommets alors qu'un seul suffit.

Piège classique : le glouton « prendre un sommet de degré maximal, le retirer avec ses arêtes, recommencer » n'a aucun facteur d'approximation constant : sur certaines familles de graphes, son rapport à l'optimum croît comme le logarithme du nombre de sommets.

Problème du sac à dos

Instance : une capacité W et n objets, l'objet i de poids w_i > 0 et de valeur v_i > 0. On cherche un sous-ensemble de poids total au plus W et de valeur maximale. On suppose w_i ≤ W pour tout i, quitte à éliminer les objets trop lourds.

Glouton par rapport : trier les objets par rapport v_i / w_i décroissant, en O(n log n), puis les parcourir dans cet ordre en prenant chacun s'il rentre encore.

Ce glouton seul peut être arbitrairement mauvais. Exemple : W grand, objet 1 de poids 1 et valeur 2 (rapport 2), objet 2 de poids W et valeur W (rapport 1). Le glouton prend l'objet 1, l'objet 2 ne rentre plus : valeur 2 contre OPT = W.

Correction classique : renvoyer la meilleure solution entre le glouton et l'objet de plus grande valeur pris seul (admissible car w_i ≤ W). C'est une approximation de facteur 2 : valeur renvoyée ≥ OPT / 2.

Preuve. Numérotons les objets dans l'ordre du tri. Si tous rentrent ensemble, le glouton les prend tous et il est optimal. Sinon, soit k le plus petit indice tel que w₁ + … + w_k > W, et P = {1, …, k}. Le glouton prend au moins les objets 1 à k − 1, donc sa valeur G vérifie G ≥ v₁ + … + v_k−1. Montrons que OPT ≤ v₁ + … + v_k. Soit S une solution optimale et r = v_k / w_k. Les objets hors de P ont un rapport au plus r, ceux de P un rapport au moins r. Donc valeur(S hors P) ≤ r × poids(S hors P) et valeur(P hors S) ≥ r × poids(P hors S). Or poids(S hors P) ≤ W − poids(S ∩ P) < poids(P) − poids(S ∩ P) = poids(P hors S). Ainsi valeur(S hors P) ≤ valeur(P hors S), et OPT = valeur(S ∩ P) + valeur(S hors P) ≤ valeur(P). Enfin, si V est la plus grande valeur d'un objet, V ≥ v_k. D'où OPT ≤ G + V ≤ 2 max(G, V).

Ce facteur 2 est optimal pour cet algorithme. Avec W = 2, un objet de poids ε et de valeur 2ε, puis deux objets de poids 1 et valeur 1 : le glouton obtient 1 + 2ε, le meilleur objet seul vaut 1, alors que OPT = 2.

Méthodes

• Classer un algorithme probabiliste : temps seul aléatoire, Las Vegas. Justesse aléatoire et temps borné, Monte Carlo.
• Las Vegas par tentatives : succès de probabilité p > 0, loi géométrique d'espérance 1/p.
• Espérance : somme d'indicatrices et linéarité, sans indépendance.
• Monte Carlo unilatéral : identifier la réponse sûre, borner l'erreur q, amplifier en q^k.
• Facteur d'approximation : borner OPT par une quantité calculable (taille d'un couplage, valeur d'un préfixe trié), puis comparer.
• Facteur atteint ou glouton mauvais : exhiber une petite instance explicite.

Ce qu'il faut savoir refaire en khôlle

1. Définir Las Vegas, Monte Carlo (erreur unilatérale, bilatérale) et algorithme d'approximation de facteur ρ, avec des exemples.
2. Écrire le k-ième minimum par pivot aléatoire, justifier sa correction et expliquer pourquoi son temps espéré est linéaire.
3. Calculer le nombre moyen de tirages pour obtenir un nombre premier de taille donnée, et dire pourquoi la méthode est Las Vegas.
4. Montrer qu'une affectation aléatoire satisfait en moyenne 3m/4 clauses de MAX2SAT, en précisant l'hypothèse sur les clauses.
5. Prouver le facteur 2 de la couverture de sommets par couplage maximal, et donner un cas où il est atteint.
6. Donner une instance où le glouton seul du sac à dos est arbitrairement mauvais, puis prouver le facteur 2 de la version corrigée.

Les résultats à connaître

Le programme s'en tient aux définitions et à des exemples. Les « résultats » sont donc les outils de calcul et les garanties des exemples classiques.

• Définitions de déterministe, Las Vegas, Monte Carlo (erreur unilatérale ou bilatérale), problème de décision, d'optimisation, instance, fonction de coût, algorithme d'approximation de facteur ρ : exigibles.
• Loi géométrique : si chaque tentative indépendante réussit avec probabilité p > 0, le nombre T de tentatives vérifie E(T) = 1/p et P(T > t) = (1 − p)^t : outil des mathématiques, à savoir utiliser.
• Amplification unilatérale : k répétitions indépendantes d'un test d'erreur au plus q donnent une erreur au plus q^k : à savoir justifier.
• Inégalité de Markov : pour X ≥ 0 et a > 0, P(X ≥ a) ≤ E(X)/a : outil des mathématiques, à savoir utiliser pour couper un Las Vegas.
• Linéarité de l'espérance, sans hypothèse d'indépendance, et existence d'une issue où X ≥ E(X) : outils des mathématiques, à savoir utiliser.
• k-ième minimum par pivot aléatoire : toujours correct, temps espéré O(n), pire cas Θ(n²) : exemple du cours, idée de l'analyse à savoir expliquer.
• Test de Freivalds : erreur au plus 1/2, seulement quand AB ≠ C, en O(n²) : exemple à savoir refaire.
• MAX2SAT, deux variables distinctes par clause : une affectation uniforme satisfait en moyenne 3m/4 clauses : exemple cité par le programme, preuve à savoir refaire.
• Couverture de sommets par couplage maximal : facteur 2, atteint : exemple cité par le programme, preuve à savoir refaire.
• Sac à dos, glouton par rapport valeur sur poids corrigé par le meilleur objet seul : facteur 2 : exemple du programme, preuve à savoir refaire.
• Densité des nombres premiers voisine de 1/ln N : admise.
• Hors programme signalé : analyse du vote majoritaire, test de Miller-Rabin, techniques générales d'approximation.

Clés de démonstration

Espérance d'une loi géométrique. On écrit E(T) = Σ_{t ≥ 0} P(T > t), puis P(T > t) = (1 − p)^t car les t premières tentatives échouent indépendamment. La somme géométrique vaut 1/p. L'astuce est cette formule de la queue, plus rapide que Σ t p (1 − p)^{t − 1}.

Amplification. L'erreur ne se produit que si les k exécutions se trompent toutes. Les tirages étant indépendants, la probabilité est le produit, au plus q^k. L'astuce est d'identifier d'abord la réponse sûre : on ne répète utilement que l'autre.

Couper un Las Vegas. Soit X le temps, d'espérance au plus T. On a a × 1_{X ≥ a} ≤ X, puis on prend l'espérance : P(X ≥ a) ≤ T/a. Avec a = 2T, l'échec a une probabilité au plus 1/2. L'astuce est de relancer plusieurs coupures courtes plutôt qu'une longue (exercice 3).

Méthode probabiliste. On écrit X comme une somme d'indicatrices, on calcule chaque probabilité, et la linéarité donne E(X). Comme X ne peut pas être partout strictement sous sa moyenne, une issue vérifie X ≥ E(X). L'astuce est de ne jamais chercher l'indépendance entre les termes.

Facteur d'approximation. OPT est inconnu, donc on le borne par une quantité que l'algorithme voit : un couplage pour une couverture, le nombre m de clauses pour MAX2SAT, une somme de durées pour un ordonnancement. L'astuce est de choisir la borne avant d'analyser l'algorithme.

Freivalds. On fixe toutes les coordonnées de r sauf r_j, où d_ij ≠ 0. La coordonnée i de D r est alors affine en r_j, de pente non nulle, et s'annule pour au plus une des deux valeurs. L'astuce est ce conditionnement : on raisonne sur une seule coordonnée tirée en dernier.

Exemples et contre-exemples à connaître

1. Un tri rapide qui prend toujours le premier élément comme pivot est déterministe. Il est rapide en moyenne sur des entrées aléatoires mais quadratique sur un tableau déjà trié. Avec un pivot uniforme, aucune entrée n'est mauvaise en espérance.
2. Un algorithme qui répond toujours « oui » n'est pas Monte Carlo : sur une instance « non », il se trompe avec probabilité 1. La borne d'erreur doit valoir pour toute entrée.
3. Las Vegas ne veut pas dire temps borné : les huit reines par relances n'ont aucune borne déterministe. Le temps est fini avec probabilité 1 et d'espérance finie.
4. Pour D = AB − C égale à la matrice 2 × 2 de lignes (0, 1) et (0, 0), D r = (r₂, 0). Le test de Freivalds détecte l'erreur avec probabilité exactement 1/2 : la borne est atteinte.
5. Les quatre clauses x₁ ∨ x₂, x₁ ∨ ¬x₂, ¬x₁ ∨ x₂, ¬x₁ ∨ ¬x₂ : toute affectation en satisfait exactement 3. Ici OPT = 3 = 3m/4 < m. La garantie d'existence d'une affectation satisfaisant au moins 3m/4 clauses ne peut donc pas être améliorée en général, et la borne OPT ≤ m utilisée dans la preuve n'est pas toujours atteinte.
6. Étoile à k branches : la couverture par couplage prend 2 sommets, l'optimum en prend 1. Facteur 2 atteint pour tout k ≥ 1.
7. Graphe complet à n sommets, n pair : le couplage maximal prend les n sommets, l'optimum en prend n − 1. Le rapport tend vers 1 : le facteur 2 est un pire cas, pas la règle.
8. Sac à dos glouton par valeur seule, n ≥ 3 : W = n, un objet de poids n et de valeur 2, n objets de poids 1 et de valeur 1. Le glouton obtient 2, l'optimum n.
9. Sac à dos glouton par poids croissant : W = 2, un objet de poids 1 et de valeur 1, un objet de poids 2 et de valeur 100. Le glouton obtient 1, l'optimum 100.
10. Un algorithme d'approximation de facteur 1 est un algorithme exact en temps polynomial.

Techniques du chapitre

Technique 1, classer un algorithme. Mini-exercice : un tableau de booléens contient soit aucun true, soit au moins la moitié de true. On tire 10 cases, uniformément et indépendamment, et on répond « oui, il y a un true » dès qu'on en voit un, « non » sinon. Le temps est borné par 10 lectures. C'est un Monte Carlo à erreur unilatérale : « oui » est toujours sûr, et un « non » à tort a une probabilité au plus (1/2)¹⁰ = 1/1 024. Sans la promesse sur l'entrée, l'erreur n'est bornée par aucun q < 1.

Technique 2, exploiter la loi géométrique. Mini-exercice : une tentative réussit avec probabilité 1/4. Le nombre moyen de tentatives vaut 4. La probabilité qu'il en faille plus de 10 vaut (3/4)¹⁰ ≈ 0,056.

Technique 3, dimensionner une amplification. Mini-exercice : erreur unilatérale q = 1/3, cible 10⁻⁶. Il faut 3^k ≥ 10⁶. Comme 3¹² = 531 441 et 3¹³ = 1 594 323, on prend k = 13.

Technique 4, découper en indicatrices. Mini-exercice : nombre moyen de points fixes d'une permutation uniforme de n éléments. X = Σ 1_{σ(i) = i} et P(σ(i) = i) = 1/n, donc E(X) = n × 1/n = 1. Les indicatrices ne sont pas indépendantes, et cela n'importe pas.

Technique 5, borner OPT par un couplage. Mini-exercice : dans un cycle à 5 sommets, les arêtes {1, 2} et {3, 4} sont disjointes, donc toute couverture a au moins 2 sommets. En fait OPT = 3, car 2 sommets couvrent au plus 4 arêtes sur 5.

Technique 6, jouer une solution contre son complément. Mini-exercice : pour des clauses non vides de taille quelconque, une affectation a ou son complément satisfait au moins m/2 clauses. Une clause fausse sous a a tous ses littéraux faux, donc tous vrais sous le complément. Chaque clause est satisfaite par l'une des deux, et la meilleure en satisfait au moins m/2.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

(* indice_vrai : bool array -> int
   Précondition : au moins la moitié des cases valent true. *)
let rec indice_vrai t =
  let i = Random.int (Array.length t) in
  if t.(i) then i else indice_vrai t

(* couverture : int -> (int * int) list -> bool array
   Sommets 0 à n - 1. Renvoie dans, avec dans.(s) vrai si s est dans C. *)
let couverture n aretes =
  let dans = Array.make n false in
  List.iter
    (fun (u, v) ->
      if not dans.(u) && not dans.(v) then begin
        dans.(u) <- true;
        dans.(v) <- true
      end)
    aretes;
  dans

Erreurs fréquentes