SVM n°19 jui/aoû 1985
SVM n°19 jui/aoû 1985
  • Prix facial : 16 F

  • Parution : n°19 de jui/aoû 1985

  • Périodicité : mensuel

  • Editeur : Excelsior Publications

  • Format : (203 x 280) mm

  • Nombre de pages : 132

  • Taille du fichier PDF : 200 Mo

  • Dans ce numéro : la micro-informatique expliquée par Bill Gates, le pape du logiciel.

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 64 - 65  |  Aller à la page   OK
Pages suivantes >
64 65
nombres aléatoires ? Il y a d'abord des méthodes faisant appel à un système extérieur, comme une horloge. Certains ordinateurs possèdent une horloge intégrée au millième de seconde. Il suffit alors, quand on a besoin d'un nombre au hasard, de prendre le nombre des millièmes de seconde ou celui des secondes. A condition de ne pas y recourir de façon répétée dans le programme, ce système peut être considéré comme vraiment aléatoire. Une façon de faire analogue, employée en particulier par l'Apple II, permet de se passer d'horloge. Lorsque l'ordinateur attend que vous tapiez un caractère au clavier, il profite de ce temps mort pour faire tourner un compteur à toute vitesse (plus de 50 000 cycles par seconde). Lorsque vous appuyez sur la touche, le compte s'interrompt et le nombre obtenu sert de nombre aléatoire. Tout cela marche très bien, mais si vous avez besoin pour un programme d'utiliser beaucoup de nombres aléatoires, aucun des deux procédés précédents ne peut fonctionner, car l'horloge donne alors des valeurs très proches les unes des autres, et si vous avez besoin de 2 000 nombres aléatoires, il est impensable d'arrêter 2 000 fois le programme pour taper 2 000 touches au clavier afin de les fabriquer. En plus de ces méthodes, les ordinateurs utilisent donc des procédés de calcul qui permettent à partir du nombre aléatoire précédent de fabriquer le suivant à l'aide d'une formule adéquate. Cette suite de nombres n'est pas vraiment aléatoire - on dit qu'il s'agit de nombres pseudo-aléatoires - mais pourvu que la formule qui permet de les calculer soit suffisamment bien choisie (voir les exemples en encadré), il est impossible de faire la différence. A quoi servent alors les autres procédés ? Puisque les nombres pseudo-aléatoires sont fabriqués gr-ace à une formule mathématique déterminée, à partir d'un même nombre on obtient toujours la même suite de valeurs. De temps en temps, il est donc bon de sortir de cette série pour briser le caractère reproductible de notre générateur. On utilise alors le procédé de l'horloge ou celui du clavier pour modifier la série. Ce qui revient en quelque sorte à couper un paquet de cartes. Tester son générateur aléatoire Test d'équidistribution : La plupart des interpréteurs Basic fournissent la fonction RND(). X=RND(1) fournit en général un nombre entre 0 et 1. Ce générateur aléatoire est censé être équidistribué sur 0-1, c'est-à-dire que si l'on coupe cet intervalle en tranches égales, on a autant de chances d'obtenir un nombre aléatoire dans une tranche que dans une autre. Cela permet par exemple de simuler un jet de dé en coupant l'intervalle 0-1 en 6 tranches, chacune d'elles correspondant à un résultat sur le dé. Le fait que le générateur soit équidistribué garantit que le dé n'est pas pipé. Le premier de nos tests consiste donc à vérifier la qualité de cette distribution au moyen d'un test statistique classique dit du chi carré Que ce nom compliqué ne vous effraie pas, il s'agit en fait de quelque chose Graphisme obtenu avec le générateur aléatoire (pas si hasardeux que ça) de !'(M PC. d'assez simple comme'vous pouvez en juger d'après la concision du programme Test d'équidistribution Le principe est le suivant : on découpe l'intervalle en un certain nombre 1000 X = RND (1) : RETURN 10 20 25 30 40 50 60 70 72 73 75 76 80 90 100 1000 X = RND (1) : RETURN + TEST D'EQUIDISTRIBUTION + de tranches égales (30 dans notre cas précis), on effectue un grand nombre de tirages aléatoires (300 par exemple) et on compte le nombre de fois où on est tombé dans chaque tranche. Si on a 300 tirages pour 30 tranches, on attend en moyenne 10 tirages par tranche. Plus on s'éloigne de 10, moins la distribution est conforme-à ce que l'on désire. On calcule pour chaque tranche la quantité : (N-10)2/10 où N est le nombre de tirages dans cette tranche. Si l'on additionne cela sur toutes les tranches, on obtient un nombre (le chi carré de la distribution) qui est une mesure de la qualité de cette distribution. Plus le chi carré est petit, meilleure est la distribution. Pour une partition en 30 tranches comme celle employée par notre programme, une valeur du chi carré inférieure à 20 est excellente et une valeur comprise entre 20 et 35 est tout à 10 DIM T(30) 20 INPUT "NOMBRE DE TIRAGES : " ; M 100 GOSUB 1000 110 N = N + 1 120 K = 1 + INT (X * 30):T(K) = T(K) + 1 130 PRINT N : IF N M THEN 100 140 FOR I = 1 TO 30 : Y = Y + (TU) — M/30) * (TU) — M/30) : NEXT 150 Y = Y * 30/M : PRINT "VALEUR DU CHI 2 =":Y 160 END + CALCUL DES PARAMETRES STATISTIQUES + DU GENERATEUR ALEATOIRE INPUT "NOMBRE DE TIRAGES A FAIRE : " ; M N = N + 1 : GOSUB 1000:Y = X : GOSUB 1000 PRINT N SX = SX + X : SY = SY + Y : XY = XY + X t Y : X2= X2 + X # X : Y2 = Y2 + Y *Y IF N M GOTO 20 VX = SQR ((X2 — (SX X SX/N))/(N — 1)) VY = SQR ((Y2 — (SY * SY/N)) (N — 1)) CV = (XY — (SX * SY/N))/(N — 1) PRINT "MOYENNE DES TIRAGES IMPAIRS : " : PRINT SX/N PRINT "MOYENNE DES TIRAGES PAIRS PRINT SV/N PRINT "ECART TYPE DES TIRAGES IMPAIRS PRINT VX PRINT "ECART TYPE DES TIRAGES PAIRS PRINT VY PRINT "COVARIANCE= " ; CV PRINT "COEFFICIENT DE CORRELATION PRINT CV/(VX * VY) END 64 SCIENCE & VIE MICRO N°19 - JUILLET-AOÛT 1985
fait acceptable. Si, en revanche, vous obtenez une valeur supérieure à 50, votre générateur aléatoire est très suspect. Calcul des paramètres statistiques du générateur aléatoire : Lors d'un jeu à deux joueurs, il arrive qu'il soit nécessaire de tirer une valeur au hasard pour chacun des deux, à tour de rôle. Imaginons le cas extrême d'un générateur aléatoire• qui donnerait alternativement une valeur entre 0 et 0,5 et une valeur entre 0,5 et 1. Celui-ci pourrait alors passer notre premier test d'équidistribution sur l'ensemble des tirages, mais le malheureux joueur qui hériterait des tirages impairs n'aurait jamais que des scores entre 0 et 0,5 tandis que son adversaire aurait, lui, des scores entre 0,5 et 1. Ce cas est peu probable, mais un certain biais peut néanmoins se produire et ainsi déséquilibrer le jeu. Pour tester cela, notre second programme, « Calcul des paramètres statistiques examine moyennes et écarts-types pour les tirages pairs et impairs. Pour un nombre de tirages suffisant (au moins 100), les moyennes doivent évoluer autour de 0,5 et les écarts-types autour de 0,288 (1/n2). Ce programme vérifie également si les tirages pairs et impairs sont indépendants en calculant leur coefficient de corrélation. Pour que votre générateur aléatoire soit correct, celui-ci doit être compris entre - 0,05 et + 0,05 (moins de 5% de corrélation). Analyse graphique de la répartition bidimensionnelle : Le test de corrélation que nous venons d'exposer demeure malgré tout assez grossier et peut se révéler insuffisant. En particulier, si vous utilisez le générateur aléatoire pour fabriquer des coordonnéesX, Y au hasard dans le plan, il faut s'assurer que les points que vous obtiendrez seront répartis au hasard. Un méthode simple consiste à tracer des points au hasard sur l'écran en utilisant le générateur aléatoire et à constater de visu qu'ils sont bien répartis au hasard. Notre surprise a été grande lors de la mise au point du nouveau standard de performances SVM - qui incluait un test d'affichage graphique de ce genre - de constater que le générateur aléatoire de l'IBM PC n'est pas si aléatoire qu'il y parait (voir photo page 64) : ces bandes parallèles qui apparaissent ne semblent rien devoir au hasard. Ce genre de comportement s'observe souvent pour des générateurs congruentiels simples comme celui de notre encadré (X=(29xX)-INT(29xX)). Le programme de test que nous vous proposons est écrit pour un Apple II, mais il ne pose guère de difficultés d'adaptation. Test de répartition bidimensionnelle (voir programme page suivante) : Pour mesurer ce biais dans la répartition bidimensionnelle, nous vous proposons un programme basé sur le même principe que le premier qui mesurait l'équidistribution, le test du chi carré. Au lieu de diviser l'intervalle (0,1) en tranches, on découpe le carré (0,1) x [0,1) correspondant à l'écran en petites cases de tailles égales et on compte le nombre de points par cases de la même manière. La différence entre le nombre moyen attendu et le nombre observé permet de calculer le chi carré. Pour un carré 30 x 30, le chi carré doit 1) On divise le carré (0,1) x (0,1) en NxN petits carrés : 1 o TEST DE CORRÉLATION DE DEUX NOMBRES SUCCESSIFS PAR LA MÉTHODE DU X2 (CHI CARRÉ) 2) On détermine les deux coordonnées d'un point au hasard à l'aide du générateur aléatoire x = RND (1) ; y = RND (1) et on trace le point dans le carré. 3) Lorsqu'un grand nombre de points ont été étre inférieur à 1000, pour un carré 60 x 60, il doit être inférieur à 5 000. Plus le nombre de cases augmente, plus la sensibilité est grande, mais plus le temps de calcul et la place mémoire requise sont importants. Ainsi avec le découpage 30 x 30, on trouve un chi carré de 899 pour un générateur correct contre 1 048 pour un générateur• à rayures comme celui de l'IBM PC, soit une différence assez faible. Avec le découpage 60 x 60, le générateur correct donne 4 350 contre 22 841 à celui qui est biaisé, ce qui est très important. Toutefois le nombre de tirages aléatoires nécessaires passe de 9 000 pour 30 x 30 à 36 000 pour 60 x 60. En dehors des jeux, les nombres aléatoires ont de nombreuses applications pour lesquelles leurs propriétés doivent être vérifiées à X ANALYSE GRAPHIQUE DE LA + + REPARTITION BIDIMENSIONNELLE + Passage en mode graphique haute résolution 5 HGR 10 INPUT "NOMBRE DE POINTS : " ; M : HOME 20 GOSUB 1000:Y = X : GOSUB 1000 Transformation en coordonnées écran 280x192 30 XP = 280 t X:YP = 192 X Y : HPLOT XP,YP 50 VTAB 21:N = N + 1 : PRINT N ; "/" ; M : IF N < M THEN 20 60 END Générateur aléatoire 1000 X = RND (1) : RETURN 1 tracés, on compte le nombre de points dans chaque case. On compare ce nombre au nombre moyen attendu. Ainsi, si l'on a fait 10 x 10 =100 cases et que l'on a tracé 1000 points, on attend en moyenne 10 points par case. Si N13 est le nombre de points obtenus dans la casei,j et si Nr., est le nombre moyen de points par case, le X2 (chi carré) se calcule par la formule : X X n n x2, E E (Nu- Nr4)2 i=1 j=1 NM fond. En mathématiques, lorsque le calcul direct est difficile, on a recours à des méthodes d'échantillonnage statistique dites. méthodes de Monte-Carlo », dont nous donnons une illustration très simple avec le calcul de pi grâce à des nombres aléatoires. Un exemple d'application de première importance : la simulation de ce qui se passe au coeur d'un réacteur de centrale nucléaire. Lorsqu'un neutron est émis dans une barre d'uranium, il existe une certaine probabilité pour qu'il rencontre un noyau d'uranium au bout d'une certaine distance. Lorsque cela se produit, il peut soit étre absorbé, soit être dévié, soit encore provoquer l'émission d'un certain nombre de neutrons secondaires. Le processus recommence alors avec ces nouveaux neutrons. Si ces neutrons secondaires sont Ple)Ur ADelt 17-ansoosilicbn SCIENCE & VIE MICRO N°19• JUILLET•AOÛT 1985 65,../



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :


SVM numéro 19 jui/aoû 1985 Page 1SVM numéro 19 jui/aoû 1985 Page 2-3SVM numéro 19 jui/aoû 1985 Page 4-5SVM numéro 19 jui/aoû 1985 Page 6-7SVM numéro 19 jui/aoû 1985 Page 8-9SVM numéro 19 jui/aoû 1985 Page 10-11SVM numéro 19 jui/aoû 1985 Page 12-13SVM numéro 19 jui/aoû 1985 Page 14-15SVM numéro 19 jui/aoû 1985 Page 16-17SVM numéro 19 jui/aoû 1985 Page 18-19SVM numéro 19 jui/aoû 1985 Page 20-21SVM numéro 19 jui/aoû 1985 Page 22-23SVM numéro 19 jui/aoû 1985 Page 24-25SVM numéro 19 jui/aoû 1985 Page 26-27SVM numéro 19 jui/aoû 1985 Page 28-29SVM numéro 19 jui/aoû 1985 Page 30-31SVM numéro 19 jui/aoû 1985 Page 32-33SVM numéro 19 jui/aoû 1985 Page 34-35SVM numéro 19 jui/aoû 1985 Page 36-37SVM numéro 19 jui/aoû 1985 Page 38-39SVM numéro 19 jui/aoû 1985 Page 40-41SVM numéro 19 jui/aoû 1985 Page 42-43SVM numéro 19 jui/aoû 1985 Page 44-45SVM numéro 19 jui/aoû 1985 Page 46-47SVM numéro 19 jui/aoû 1985 Page 48-49SVM numéro 19 jui/aoû 1985 Page 50-51SVM numéro 19 jui/aoû 1985 Page 52-53SVM numéro 19 jui/aoû 1985 Page 54-55SVM numéro 19 jui/aoû 1985 Page 56-57SVM numéro 19 jui/aoû 1985 Page 58-59SVM numéro 19 jui/aoû 1985 Page 60-61SVM numéro 19 jui/aoû 1985 Page 62-63SVM numéro 19 jui/aoû 1985 Page 64-65SVM numéro 19 jui/aoû 1985 Page 66-67SVM numéro 19 jui/aoû 1985 Page 68-69SVM numéro 19 jui/aoû 1985 Page 70-71SVM numéro 19 jui/aoû 1985 Page 72-73SVM numéro 19 jui/aoû 1985 Page 74-75SVM numéro 19 jui/aoû 1985 Page 76-77SVM numéro 19 jui/aoû 1985 Page 78-79SVM numéro 19 jui/aoû 1985 Page 80-81SVM numéro 19 jui/aoû 1985 Page 82-83SVM numéro 19 jui/aoû 1985 Page 84-85SVM numéro 19 jui/aoû 1985 Page 86-87SVM numéro 19 jui/aoû 1985 Page 88-89SVM numéro 19 jui/aoû 1985 Page 90-91SVM numéro 19 jui/aoû 1985 Page 92-93SVM numéro 19 jui/aoû 1985 Page 94-95SVM numéro 19 jui/aoû 1985 Page 96-97SVM numéro 19 jui/aoû 1985 Page 98-99SVM numéro 19 jui/aoû 1985 Page 100-101SVM numéro 19 jui/aoû 1985 Page 102-103SVM numéro 19 jui/aoû 1985 Page 104-105SVM numéro 19 jui/aoû 1985 Page 106-107SVM numéro 19 jui/aoû 1985 Page 108-109SVM numéro 19 jui/aoû 1985 Page 110-111SVM numéro 19 jui/aoû 1985 Page 112-113SVM numéro 19 jui/aoû 1985 Page 114-115SVM numéro 19 jui/aoû 1985 Page 116-117SVM numéro 19 jui/aoû 1985 Page 118-119SVM numéro 19 jui/aoû 1985 Page 120-121SVM numéro 19 jui/aoû 1985 Page 122-123SVM numéro 19 jui/aoû 1985 Page 124-125SVM numéro 19 jui/aoû 1985 Page 126-127SVM numéro 19 jui/aoû 1985 Page 128-129SVM numéro 19 jui/aoû 1985 Page 130-131SVM numéro 19 jui/aoû 1985 Page 132