Pourquoi les algorithmes probabilistes ou comment l’aléatoire apporte un « plus » ?
L’aléatoire est une ressource algorithmique des plus intéressantes d’un point de vue opérationnel. Il est donc naturel d’explorer certaines techniques développées par l’algorithmique avancée. L’analyse de complexité (au sens mesure de performances) peut cependant être plus délicate. On examinera certaines techniques d’analyse (e.g. définir la bonne variable aléatoire en est l’exemple le plus concret).
Les algorithmes probabilistes sont souvent plus simples que les algorithmes déterministes analogues qui traitent le même problème. C’est donc l’opportunité de discuter d’algorithmes astucieux. Le plan du chapitre sera de suivre ces remarques. On s’attachera à illustrer les techniques les plus importantes en étudiant des algorithmes-exemples et on passera en revue différents domaines ou champs d’applications où les algorithmes probabilistes se montrent les plus efficaces.
Les algorithmes probabilistes ont pour caractéristique de mettre le hasard à profit en faisant des choix aléatoires. Il convient toutefois de préciser que la définition d’algorithme nécessite d’être revue. En effet, une conséquence de l’utilisation du hasard est que deux exécutions d’un algorithme probabiliste avec les mêmes données d’entrée peut prendre un temps d’exécution différent et éventuellement donner des résultats différents.
On autorisera donc qu’un algorithme puisse, avec une faible probabilité, renvoyer une mauvaise réponse ou ne jamais terminer…