Algorithmes probabilistes et problèmes courants

Algorithmes déterministes et probabilistes

Un algorithme déterministe est un algorithme qui, pour une entrée donnée, exécutera une suite d'instructions fixe : il fournit donc toujours le même résultat pour cette entrée, en un temps prédictible.

Un algorithme probabiliste utilise des choix aléatoires dans son processus, ce qui peut aboutir à des résultats différents et/ou à des durées d'exécution variables, pour une même entrée. On distingue deux grandes catégories d'algorithmes probabilistes : les algorithmes de Monte Carlo et les algorithmes de Las Vegas.

Algorithmes de Monte Carlo

Les algorithmes de Monte Carlo fournissent une solution rapidement, mais sans garantie de précision. Leur probabilité de trouver une solution est élevée.

Par exemple, on peut utiliser un algorithme de Monte Carlo pour calculer une approximation du nombre pi. Pour cela, on doit :

• simuler des points aléatoires dans un carré de côté 2 centré à l'origine ;
• compter combien tombent à l'intérieur d'un quart de cercle de rayon 1 inscrit dans ce carré.

La probabilité qu'un point aléatoire se trouve à l'intérieur du quart de cercle est proportionnelle à la surface du quart de cercle par rapport au carré, et correspond à $\pi / 4$.

Avec cet algorithme, la durée d'exécution sera connue à l'avance, car elle dépend du nombre de points aléatoires générés. La précision sera plus ou moins bonne, et sera aussi liée au nombre de points placés.

Algorithmes de Las Vegas

Les algorithmes de Las Vegas garantissent un résultat correct, mais leur durée d'exécution est variable. Ces algorithmes arrêtent leurs calculs lorsqu'une solution est trouvée.

Par exemple, pour construire un nombre premier de grande taille (utile en cryptographie), on peut générer un nombre aléatoire et tester sa primalité jusqu'à en trouver un qui soit premier. Cette méthode, bien qu'aléatoire, finit toujours par donner un résultat exact : un nombre premier. Sa durée d'exécution n'est par contre par connu à l'avance.

k-ième minimum

La recherche du k-ième minimum dans un tableau non trié est un problème classique illustrant les différences entre algorithmes déterministes et probabilistes.

Approche déterministe : on trie le tableau en $O(n\log n)$, puis on sélectionne le k-ième élément. Cette méthode est simple mais coûteuse en temps.

Approche probabiliste (Las Vegas) avec l'algorithme Randomized Quickselect : on utilise un pivot choisi aléatoirement pour partitionner le tableau. La recherche continue ensuite dans la sous-partie pertinente jusqu'à trouver le k-ième élément. Ce procédé garantit un résultat exact, avec une complexité moyenne de $O(n)$.

Problème des 8 reines

Le problème des 8 reines consiste à placer huit reines sur un échiquier sans qu'aucune ne puisse en attaquer une autre.

Approche déterministe : on utilise une méthode de backtracking (retour sur trace) qui explore systématiquement toutes les configurations possibles pour garantir une solution, mais cela peut être très coûteux en temps, avec une complexité exponentielle.

Approche probabiliste (Las Vegas) : on place les reines aléatoirement, puis on ajuste leurs positions pour éliminer les conflits. Si une solution n'est pas trouvée rapidement, on recommence depuis le début. Cette méthode est souvent plus rapide en pratique.

Algorithmes d'approximation et MAX2SAT

Les algorithmes probabilistes sont également efficaces pour les problèmes d'approximation, où trouver une solution exacte est trop coûteux.

Un exemple notable est le problème MAX2SAT, qui consiste à maximiser le nombre de clauses satisfaites dans une formule booléenne où chaque clause contient au plus deux littéraux.

Une méthode probabiliste (Monte Carlo) consisterait à assigner aléatoirement des valeurs vraies ou fausses aux variables. Cette méthode garantit qu'au moins 50 % des clauses sont satisfaites en moyenne, car chaque clause a une probabilité de 50 % d'être vraie si les assignations sont indépendantes.