Algorithmes stochastiques

 

La définition classique des algorithmes en fait des processus de calcul déterministes : avec les mêmes données, un algorithme exécutera toujours la même suite d'opérations. Cependant, l'hypothèse de déterminisme est restrictive, voire contraignante. Un algorithme non-déterministe admettrait des instructions du genre << faire ceci ou faire cela>>, << choisir un élément dans un ensemble >>, etc ; deux exécutions différentes d'un tel algorithme pourraient réaliser des choix différents. Une façon de réaliser ces choix est de les rendre aléatoires : on obtient ainsi les algorithmes stochastiques, ou probabilistes. Il y a plusieurs usages de l'aléatoire :

• les algorithmes numériques simulent une variable de loi uniforme, afin d'obtenir une approximation numérique de la solution du problème (qui pourrait être obtenue par un algorithme déterministe) ;
• les algorithmes de Monte-Carlo peuvent calculer une solution incorrecte en un temps déterministe avec une probabilité d'erreur qui peut être rendue arbitrairement petite en répétant l'algorithme ;
• les algorithmes de Las Vegas ne terminent pas nécessairement, mais calculent toujours une solution correcte quand ils terminent, le temps d'exécution étant aléatoire ;
• enfin, les algorithmes de randomisation garantissent une complexité moyenne.

Un générateur de nombres pseudo-aléatoires est un algorithme implémenté par une fonction, qui retourne à chaque invocation une nouvelle valeur numérique^2.3, et telle que la suite des valeurs retournées ait de bonnes propriétés statistiques : ces propriétés permettent de supposer qu'il s'agit d'une suite de variables aléatoires indépendantes de loi uniforme dans un intervalle spécifié. Ces nombres sont utilisés dans deux situations :

•   pour tester un programme quelconque, en lui soumettant comme données des << jeux de test >> générés aléatoirement, et en comparant le résultat calculé au résultat attendu ;
•   pour implémenter des algorithmes stochastiques, soit pour des problèmes numériques (intégration de Monte-Carlo), soit pour améliorer le comportement d'algorithmes par randomisation, soit pour donner un résultat avec une probabilité d'erreur (test de primalité), ou pour briser des symétries (élection d'un chef), par obstination.

La conception d'un générateur de nombres pseudo-aléatoires est délicate (ce n'est pas que ces algorithmes soient difficiles à écrire, c'est qu'il est difficile d'échapper à des régularités arithmétiques qui s'opposent à l'uniformité souhaitée). Dans la pratique, il est préférable d'utiliser un générateur fourni dans la bibliothèque standard : la fonction Math.random() de l'API Java retourne un double dans l'intervalle [0,1[.

Pour obtenir un entier dans l'intervalle [a,b], on pourra définir la fonction :

  static int irand(int a, int b) {
    return a + (int)(Math.random() * (b-a+1));
  }

On obtiendra un tirage à pile ou face en invoquant irand(0,1).

Comme la fonction Math.random() n'a en soi rien d'aléatoire, chaque exécution du programme verra la même suite générée. Si l'on doit faire des traitements statistiques portant sur les résultats de plusieurs exécutions, il est alors nécessaire d'obtenir une suite différente à chaque exécution, pour assurer l'indépendance des résultats. Il faut alors initialiser la graine (anglais seed) du générateur.

L'API Java offre la classe Random dans le paquet java.util qui permet cette initialisation à la création de l'instance. Sans argument, le constructeur utilise le temps courant pour l'initialiser. Une instance de cette classe est un générateur de nombres pseudo-aléatoires dont les valeurs successives sont obtenues par l'une des méthodes nextBoolean(), nextInt(), nextLong(), nextFloat() et nextDouble() qui simulent des loi uniformes sur l'ensemble des valeurs de type, respectivement, boolean, int, long, float et double ; la méthode nextInt(int n), avec un argument entier positif n simule une loi uniforme sur l'intervalle [0, n[ ; enfin, la méthode nextGaussian() simule une gaussienne de moyenne 0 et de variance 1.

On obtiendra par exemple une suite de doubles pseudo-aléatoires de la façon suivante :

  public static void main(String[] argv) {

    Random g = new Random();
    while (true)
      System.out.println(g.nextDouble());
  }