Informatique et aléatoire

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: VPE

Voila,je ne sais pas si je suis sur le forum le plus adéquat pour ce genre de questions mais je me suis toujours demandé :
Comment un ordinateur peut-il donc "choisir" un nombre aléatoirement.
Tout les languages de programmations possédent une instruction "Random "(rnd) permettant de stocker une valeur aléatoire dans une fourchette donnée,a l'interieur d'une variable choisie.
D'autemps plus qu'aprés de nombreux testes je me suis apercu que certaines valeurs revenaient beaucoups plus que d'autres.


Posted by: cesar

tu peux fabriquer toi meme une table de nombres "au hasard".

comment fabriquer des nombres reellement au hasard : simplement, vous faites un calcul iteratif sur une fonction chaotique et vous mettez en plus dans ce programme un fonction de detection des touches du clavier. Lorsque l'iteration est en cours, vous appuyez sur une touche et le nombre de l'iteration au moment où vous appuyez sur la touche est mis dans le fichier. C'est rustique et pas pratique, mais c'est indiscutablement du hasard.


Posted by: Flodelarab

Citation:
Posté par VPE
Voila,je ne sais pas si je suis sur le forum le plus adéquat pour ce genre de questions mais je me suis toujours demandé :
Comment un ordinateur peut-il donc "choisir" un nombre aléatoirement.
Tout les languages de programmations possédent une instruction "Random "(rnd) permettant de stocker une valeur aléatoire dans une fourchette donnée,a l'interieur d'une variable choisie.
D'autemps plus qu'aprés de nombreux testes je me suis apercu que certaines valeurs revenaient beaucoups plus que d'autres.

La première chose a dire est OUI. Tu as raison!
Faire générer quelque chose d'aléatoire par une machine dont on a tout fait pour maitriser le résultat est une entreprise difficile.
La plupart du temps, on utilise un outil qui donne de nombreuses valeurs insignifiantes. Comme le nombre de millisecondes.

Tu noteras (notamment en pascal) que l'utilisation du générateur aléatoire nécessite une initialisation .... sinon, il choisira "aléatoirement" TOUJOURS la même sequence de chiffres. Cete initialisation a pour but de décoller le générateur aléatoire de tout processus prévisible ou reproductible.


Posted by: Dominique Lefebvre

c'est en effet très difficile de faire générer une suite de nombres aléatoires par un ordinateur!

Il y a quelques annèes, sur un projet pour lequel j'avais besoin d'une vraie suite de nombres aléatoires, j'ai résolu le pb en utilsant un mécanisme externe qui fonctionnait par comptage de désintégrations atomiques. Au moins, je suis certain qu'une désintégration est un phénomène aléatoire...


Posted by: GzD

Flodelarab>
Citation:
La plupart du temps, on utilise un outil qui donne de nombreuses valeurs insignifiantes. Comme le nombre de millisecondes.
où as-tu vu ça ?

Citation:
Tu noteras (notamment en pascal) que l'utilisation du générateur aléatoire nécessite une initialisation .... sinon, il choisira "aléatoirement" TOUJOURS la même sequence de chiffres. Cete initialisation a pour but de décoller le générateur aléatoire de tout processus prévisible ou reproductible.
Non mister, mais alors NON ! Je vais commencer par le commencement.
Effectivement un ordinateur est incapable de générer des séquences aléatoires de nombres : on parlera donc de générateurs pseudo-aléatoires. Mais comment marchent ces bidules ?
C'est là que ce que tu écris est complètement faux. Il s'agit de suite => leur évolution est purement déterministe ! L'initialisation sert à fixer la valeur d'une variable appelée le "germe" (le u0 de la suite si vous préférez) : si tu ne la change pas, en effet elle reste fixée à la valeur par défaut et tu obtient toujours la même séquence. De la même manière si tu l'initialise à une valeur x en début d'exécution, 10 exécutions successives te donneront toujours les même résultats. Après si on est malin on peut initialisé le germe à partir de l'horloge (ce n'est pas ce que tu as écris) et tu peux donc l'initialiser "aléatoirement" (à utiliser en connaissance de cause, car ce n'est pas aléatoire).

Flo tu confonds, malheureusement pour toi, les verbes "connaître" et "savoir" (ni voit pas d'attaque gratuite : on ne progresse qu'en se trompant).

Dominique>ton exemple de générateur aléatoire est très bon ! Il existe d'autres générateurs aléatoire du même genre utilisant des phénomènes physique tels que les propagations accoustiques ou les émission d'électrons par des semi-conducteurs.

VPE>Ton problème réside dans le fait que les suites dont je t'ai parlé plus haut ont des périodes au bout desquelles elles bouclent sur elles-mêmes : c'est un des principaux critères de qualité pour un générateur. Si tu veux évaluer celui que tu utilises tu peux te servir de la méthode DieHard (http://www.stat.fsu.edu/pub/diehard/)
. Un autre critère de qualité de ton générateur et l'uniformité de la distribution des valeurs qu'il renvoie (problème de valeurs qui resortent plus souvent que d'autres): la même batterie de test devrait te permettre de répondre à ces questions aussi.
Voila, j'espère t'avoir un peu éclairé : si ce n'est pas le cas n'hésite pas à me poser des questions plus précises


Posted by: Patastronch

aléatoire c'est pas simplement des nombres imprévisible. Il faut que laproba qu'un nombre a de sortir soit la meme que pour les autres.

C'est d'ailleur un des gros problemes de laplupart des randoms en informatique , leur génération aléatoire n'est pas équiprobable (pour vulgariser de maniere tres grossiere c'est a cause du modulo qui va s'effectuer pour recadrer dans le bon intervalle) et ils sont obligé de "tricher" pour corriger cette non equiprobabilité (lorsqu'ils tentent de le faire), ce qui fausse totalement le phénomène aléatoire.

Le temps en microseconde est pas mal mais si un algo qui n'a aucune fuite de mémoire effectue N fois le meme nombres d'opération en mettant exactement le meme temps pour chaque boucle (ce qui est le cas lorsqu'on test de gros algos sur des machines dépourvu de systeme d'exploitation pour la précision des tests), il va tomber sur une suite répétitive des nombres générés aléatoirement.

En bref, générer une suite de nombres qui simule le hasard est une chose tres complexe et loin d'etre résolu.


Posted by: Dominique Lefebvre

Citation:
Posté par GzD
Dominique>ton exemple de générateur aléatoire est très bon ! Il existe d'autres générateurs aléatoire du même genre utilisant des phénomènes physique tels que les propagations accoustiques ou les émission d'électrons par des semi-conducteurs.

Si ça t'intéresse, j'ai aussi fais l'expérience avec un générateur de bruit blanc basé sur une diode schottky. Avec autant de succès! Je pense que n'importe quel mécanisme quantique qui produit un signal mésoscopique ou macroscopique aléatoire peut convenir.


Posted by: Dominique Lefebvre

Il faut aussi tenir compte de l'usage que l'on fait d'un générateur de nombre aléatoire! Si c'est pour faire une intégration avec MC, les générateurs logiciels standards, à condition de bien les utiliser, sont suffisants! Il existe d'ailleurs des algo de contrôle de distribution aléatoire des suites issues du générateur. Pour ma part, je les passe toujours avant de me servir d'un générateur que je ne connais pas (souvent un langage...). D'ailleurs, en passant, celui de Java Sun est mauvais...

Mais pour les manip où j'ai vraiment besoin d'aléatoire (par exemple les simus de systèmes chaotiques quantiques), j'utilise toujour un générateur externe physique.


Posted by: VPE

Citation:
Posté par Patastronch
Le temps en microseconde est pas mal mais si un algo qui n'a aucune fuite de mémoire effectue N fois le meme nombres d'opération en mettant exactement le meme temps pour chaque boucle (ce qui est le cas lorsqu'on test de gros algos sur des machines dépourvu de systeme d'exploitation pour la précision des tests), il va tomber sur une suite répétitive des nombres générés aléatoirement.

C'est exactement ce que je disait,la je suis sur un projet en vb et je pense que l'algorithme utilisé par vb est basé sur le temps de réponse en ms d'aprés ce que j'ai pu lire.
Seulement,étant donnée que je tire un trés grand nombre de nombres aléatoires,j'utilise la boucle suivante :

i = 0
Tant que i <> 100 000 alors :
incrémentation de i
initialisation de j'ai pas trop compris quoi
N = nombre aléatoire entre 1 et 100
Retour tant que

Seulement certains nombres ne sortent qu'une dizaine de fois lorsque d'autre plus de 4000...
En particulié les nombres proches de 60 ont un haut "taux d'occurence".
Existerai t- il des bibliothéques ou une API de windows qui comporte cette fonction et a laquel l'on pourrai faire appel pour obtenir de meilleurs résultats ?
Ou peut- étre existe il un autre alogorithme plus efficace auquel je peut soumettre ce fameux temps de réponse aprés l'avoir récupéré ?


Posted by: anima

Je vais casser le suspens: l'ancien systeme de hasard sur les ordis dépendait de la fréquence du processeur. Cependant, désormais, un américain (si ma mémoire ne me fait pas défaut) a trouver un moyen de faire abstraction de cette contrainte gènante (truquer le hasard...)


Posted by: Dominique Lefebvre

Citation:
Posté par VPE

En particulié les nombres proches de 60 ont un haut "taux d'occurence".
Existerai t- il des bibliothéques ou une API de windows qui comporte cette fonction et a laquel l'on pourrai faire appel pour obtenir de meilleurs résultats ?
Ou peut- étre existe il un autre alogorithme plus efficace auquel je peut soumettre ce fameux temps de réponse aprés l'avoir récupéré ?


Je te recommande la lecture des Numerical Recipes in C (ou Fortran ou C++), ouvrage que tout numéricien a dans sa bibliothèque. Au chapitre "Random Numbers", tu trouveras une étude intéressante du générateur de nombres aléatoires du C (resp. Fortran ou C++, mais c'est le même!). Mais plus encore, ils donnent un algo simple pour tester le générateur et un générateur de bit presque parfaitement aléatoire. Bref, une référence dans le domaine.

NB: tu peux trouver cet ouvrage sur le net...










-