Les nombres aléatoires
- Il est souvent utile d'avoir une fonction qui produit des nombres apparemment
aléatoires
- fonction rand() prédéfini ou écrit ``à
la main''
- chaque fois appelée, elle donne un nombre différent
(normalement en [0..1))
- Pas vraiment aléatoire mais statistiquement
Génération
de nombres
- entiers pseudo-aléatoires x1,...,xi,...
- calcul simple comme xi+1 = xi*m (mod
N) pour m bien choisi et N une puissance de 2
- diviser par N pour le réel aléatoire
- ensuite mutiplier par R pour un réel en [0..R)
- et arrondir pour un entier en 0..R-1
Génération
de structures
- Soit générer un entier dans la bonne intervalle et décoder
- Soit générer la structure itérativement avec
un entier généré chaque fois que l'algorithme doit prendre
une décision
- deuxième méthode plus facile à programmer
- et évite problèmes d'entiers trop grands
Utilisation 0: interface
avec l'extérieur
- programme de jeu: ne pas toujours jouer pareil
- joli écran
- réseau: attendre temps aléatoire avant de réessayer
après collision
Utilisation 1: tester un
algorithme
- Générer un jeu de tests sur les cas aléatoires
- Ne remplace pas les tests systématique qui utilisent chaque
branche du programme
- ``Tester ne prouve jamais qu'un programme est sans fautes''
- Sauf pour ceux avec un nombre fini (et petit) de données possibles
Utilisation 2: calcul numérique
de statistiques
- Par exemple: hauteur moyenne d'un arbre construit par AVL sur n sommets
- Générer, disons 1000, cas aléatoires et calculer
la hauteur de chacun
- dangéreux: avec très faible probabilité peut
être loin du vrai moyen.
- dangéreux: si la distribution est très bizarre (écart
type très grand), presque certain d'être loin du vrai moyen.
Utilisation 3: tester une
théorie
Utilisation 4: algorithmes
probabilistes
- algorithmes pour un calcul exact qui utilisent des choix aléatoires
- probabilité d'échec mais, souvent, ils reconnaissent
qu'un échec est arrivé
- répéter plusieurs fois (avec choix différents)
réduit exponentiellement la probabilité d'échec
Exemple: un algorithme
de factorisation
Donné un grand entier n chercher un facteur p
dans le cas où n est trop grand pour essayer tous les facteurs possibles
jusqu'á racine de n
- un groupe défini selon deux paramètres et où
les calculs utilisent l'arithmétique (mod p)
- on calcule une grande puissance d'un élément aléatoire;
il y a une bonne probabilité que le résultat soit l'identité
- si on fait l'arithmétique (mod n), le fait d'avoir trouvé
l''identité se manifeste par un calcul impossible de x-1 où x a un facteur commun avec n
- donc on a trouvé un facteur!
- répéter plusieurs fois avec les paramètres du
groupe choisis aléatoirement!
Le choix de probabilité
d'échec
- un algorithme classique avec un choix déterministe des aléas
marcherait dans presque tous les cas
- mais peut-être nous ne savons pas comment programmer ce bon
choix
- l'algorithme probabiliste a la même probabilité d'échec
à chaque essai que la déterministe
- mais maintenant c'est une très petite probabilité pour
chaque n
File translated from TEX by
TTH,
version 3.05.
On 8 Mar 2004, 15:25.