Modélisation des réseaux :TP1 Génération des nombres aléatoires Socle Commun M1/S1
  Faculté des Sciences
Département d’Informatique
Masters : Socle Commun
Module : Modélisation des Processus Stochastqies
TP 1 Génération de Nombres Pseudo-Aléatoires Entrée d’un modèle de simulation :
Pour modéliser un système, on doit lui présenter ses paramètres d’entrées. Pour cela, plusieurs méthodes existent : les entrées par traces de mesure ou d’exécution, les entrées par modèles statistiques et la génération des nombres pseudo aléatoires.
On utilise la méthode de « génération des nombres pseudo aléatoires » qui est primordiale pour les différentes applications, qui sont :
Répartition des fichiers.
Fraction de fichiers répliqués.
Arrivée d’un message ou d’un client
Etc ….
Génération des nombres pseudo aléatoires :
La génération des nombres aléatoires a connu plusieurs étapes :
Génération suivant un processus physique : la séquence est non reproductible donc impossible à tester.
Etablissement de tables de nombres aléatoire : ces tables sont difficiles à manipuler.
Mise au point de méthodes algorithmique : facile à programmer. Ici, on aura la même séquence de nombres à chaque relance du générateur seulement si ce dernier est appelé avec les mêmes paramètres d’entrées. Cette méthode peut être appelée « générateur de nombres pseudo aléatoires ».
Un générateur est considéré bon s’il est :
-Simple est rapide : ces caractéristiques peuvent être vérifiées si l’algorithme génère le nombre aléatoire Xi uniquement à partir de Xi-1.
-D’une périodicité aussi longue que possible.
Il existe plusieurs méthodes algorithmiques, on cite en particulier :
Méthodes congruentielles pour la génération de nombres aléatoires :
Elles reposent sur une simple formule de récurrence :
Pour démarrer ce générateur, il faut fixer son état initial qui est d’après cette formule :
-  la graine ou la racine du générateur ; qui doit être inferieure à m et de préférence un nombre premier et petit. En général, la graine est un nombre premier, mais les contraintes exactes à son sujet dépendent de l'algorithme. Certaines graines peuvent conduire à des séquences dégénérées.
- m : le terme de la congruence, qui est le plus souvent une puissance de 2 ou 10
La période de ce générateur est au maximum de m-1, c’est-à-dire qu’elle est relativement courte puisque m est souvent choisi de manière à être de l’ordre de la longueur des mots sur l’ordinateur (par exemple : 232 sur une machine 32 bits). Mais cette méthode présente un avantage : on connaît les critères sur les nombres a, c et m qui vont permettre d’obtenir une période maximale (égale à m).
Critères de choix :
Les critères souvent pris en considération sont :
1) c et m doivent être premiers entre eux
2) a ≡ 1 [p] pour chaque facteur premier de m
3) a ≡ 1 [4] si m est multiple de 4
Exemple :
On prend comme argument initial m = 8, a = 5 (puisque m est multiple de 4) et c = 1 (car c doit être premier avec m) :
n
|
xn
|
xn+1
|
0
|
2
|
3
|
1
|
3
|
0
|
2
|
0
|
1
|
3
|
1
|
6
|
4
|
6
|
7
|
5
|
7
|
4
|
6
|
4
|
5
|
7
|
5
|
2 (arrêt)
|
Tableau 5 – D.H.Lehmer
Inconvénient :
Cette méthode exige une contrainte qui n’est pas des moindres :
m doit être une puissance de 2 ou de 10, ce qui pose un sérieux problème puisque nous aurons besoins de générer une suite de nombres pseudo aléatoire pour n’importe quel nombre.
Puisque la méthode marche pour les puissances de 2 et qu’on veut utiliser pour n’importe quel nombre, on a pensé à chercher d’abord la première puissance de 2(qu’on appellera m’) qui est supérieur à l’argument m, à chaque fois qu’on génère un nombre qui est compris entre 0 et m’, on vérifie d’abord si ce nombre est strictement inférieur à m, car ne l’oublions pas, notre suite de nombres pseudo aléatoires doit être comprise entre 0 et l’argument m.
Conditions initiales : a = 5, c = 1,  =2.
Ces choix sont faits pour les raisons suivantes :
Le a = 5 est un simple choix qu’on a pris et en plus on est sûr qu’il marche pour les nombres qui sont puissance de 2.
Le c = 1 car il doit être premier avec tous les m et le chiffre 1 est premier avec tous les autres nombres.
Enfin,= 2 est un simple choix et on a voulu que notre séquence de nombres pseudo aléatoire commence toujours par le chiffre 2.
Exemple :
En prenant comme argument m = 11 et avec les conditions initiales précédemment mentionnées ;
n
|
xn
|
xn+1
|
0
|
2
|
8
|
1
|
8
|
9
|
2
|
9
|
7
|
3
|
7
|
4
|
4
|
4
|
5
|
5
|
5
|
10
|
6
|
10
|
3
|
7
|
3
|
0
|
8
|
0
|
1
|
9
|
1
|
6
|
10
|
6
|
9(arrêt)
|
Tableau 6 – Une autre proposition Méthode
Dans cette exemple, m’=16 car c’est le premier nombre supérieur à m = 11 qui est une puissance de 2. Au commencement n = 0, ici x = 2, si on multiplie x par a = 5 et on ajoute par la suite c = 1, on obtient le chiffre 11 qui est certes strictement inférieur à m’ mais ne l’est pas avec m = 11 donc on l’inclura pas dans la séquence, néanmoins, on l’utilise pour la suite de l’opération car en le multipliant par a et en lui ajoutant c on obtient 56 et avec 56 mod 16 on obtiendra le chiffre 8 qui est strictement inferieur à m.
L’algorithme suivant montre comment fonctionne la méthode proposée:
i++ ; m’= ;
Ftq
x =( 5 * val + 1 ) mod m’ ;
si ( x alors
envoyer x ;
sinon
envoyer Pseudoaléatoire( x, m) ;
Fsi
Fin.
Algorithme de génération de nombres pseudo-aléatoires
Travail à réaliser :
1- Réaliser un générateur de nombres pseudo aléatoires
2- Tester les différents cas pour les choix des paramètres. |
