|
|
PRATIQUE ALGO/METHODES |
|
|
|
Expliquez-moi
Comment simuler informatiquement le hasard ? |
|
Nombre aléatoire ou pseudo-aléatoire ? En pratique, les ordinateurs ne nous laissent pas beaucoup de choix. Voici pourquoi.
(24/03/2006) |
|
|
Forum |
|
Réagissez
dans les forums
de JDN Développeurs
|
Choisir un nombre au hasard peut sembler une évidence, mais dans la réalité les machines y arrivent beaucoup moins bien qu'un être humain. Les générateurs de nombre aléatoires ne sont la plupart du temps que pseudo-aléatoires. La principale raison en est que ces générateurs partent d'une graine de calcul, là où le hasard réel n'a aucune origine apparente.
|
Holy Rollers, par Bradley Wilson
|
Un nombre aléatoire est ainsi construit à partir d'une graine (seed), sorte de point de départ pour la découverte du chiffre attendu. Cette graine est elle-même un nombre.
Idéalement, il faudrait pour s'assurer d'un nombre final réellement aléatoire, partir d'une graine elle-même aléatoire. Ce n'est logiquement pas réalisable, car même en faisant se suivre plusieurs générateurs à la suite, chacun produisant une graine pour le suivant, on trouvera à terme des motifs dans la suite de nombres aléatoires proposés. Ces motifs montrent qu'il est possible de déterminer les chiffres proposés - l'aléatoire n'est alors plus.
Une
vraie séquence de nombres aléatoires ne contient aucun motif.
L'objectif consiste donc à tirer sa graine d'évènements imprévisibles
ou de sources chaotiques. Des chercheurs ont ainsi basé
leur générateur
de graine sur le
hash cryptographique de la photographie numérique
de six lampes à lave ! Selon eux, ce système est suffisamment
chaotique pour s'assurer des graines totalement imprévisibles.
En l'état, cependant, on ne peut décrire le nombre obtenu que
comme pseudo-aléatoire.
C'est ainsi : malgré tout les efforts mis dans l'algorithme
de création de graines elles-mêmes aléatoires, la séquence de
chiffres résultants aura toujours une chance, certes infime,
de présenter des motifs. Même si ces motifs n'apparaissent que
sur le très long terme, un nombre généré par un algorithme
ne pourra jamais être autre chose que pseudo-aléatoire.
La méthode la plus propice repose sur les phénomènes physiques : le chaos qui régit certaines mécaniques, comme la radioactivité, les bruits thermiques ou électromagnétiques, ou la mécanique quantique - cette dernière étant ce qui se fait de mieux en matière de hasard.
Il faut donc en informatique se contenter du pseudo-aléatoire - ce qui, à vrai dire, peut faciliter les choses. Plutôt que de chercher à obtenir la graine la mieux apte à la création d'un nombre aléatoire, les développeurs peuvent se contenter de solutions plus simples.
Ainsi, on adaptera sa quête de l'aléatoire en fonction des besoins du projet. Si le but est de créer un jeu de lancer de dés, on se suffira d'une graine statique, rapidement mise en place. En revanche, s'il s'agit de générer une clef cryptographique forte, ou de calculer les probabilités d'explosion d'une navette spatiale au décollage, il faudra une graine beaucoup plus forte, et les ressources nécessaires devront suivre.
Le développeur lambda se contentera donc de générateurs pseudo-aléatoires. Les recherches en la matière sont continues depuis plusieurs décennies, à commencer par la méthode du carré médian de Von Neumann en 1946, et de nouvelles solutions fleurissent chaque année. Pour les accompagner, des méthodes d'analyse statistiques ont été mises au point, la plus connue étant celle de Monte Carlo. |
|
|