A La Des Decouverte de l'Aleatoire Et Des Probabilites

7/25/2019 A La Des Decouverte de l'Aleatoire Et Des Probabilites

1/46

A la dcouverte de

l'alatoire et desprobabilits

Par sebsheep

www.openclassrooms.com

Licence Creative Commons 2 2.0Dernire mise jour le 15/09/2011
http://www.openclassrooms.com/http://www.openclassrooms.com/


2/46

Sommaire

2Sommaire ...........................................................................................................................................1Lire aussi ............................................................................................................................................3A la dcouverte de l'alatoire et des probabilits ...............................................................................

4Partie 1 : Simuler l'alatoire ................................................................................................................ 4Fabriquez votre propre fonction "rand" .............................................................................................................................4L'alatoire... vraiment alatoire ? ................................................................................................................................................................................4Que de la poudre aux yeux ! .......................................................................................................................................................................................4Des moyens purement alatoires ...............................................................................................................................................................................5Un avant got historique : la mthode des carrs mdians ........................................................................................................................................5Une mthode... puissante ! .........................................................................................................................................................................................5 la dcouverte de la mthode ...................................................................................................................................................................................6Un premier code ..........................................................................................................................................................................................................7Maximisons la priode ! ...............................................................................................................................................................................................8Minimisons la corrlation ! ...........................................................................................................................................................................................9Quelques bons gnrateurs ........................................................................................................................................................................................9Une classe Aleatoire ...................................................................................................................................................................................................

11L'alatoire en C et C++ : se servir de rand ......................................................................................................................12Le cur de l'alatoire en C : rand .............................................................................................................................................................................12Des nombres pas si alatoires que a ! ....................................................................................................................................................................

12Votre premire exprience avec l'alatoire ...............................................................................................................................................................13Restez entre les bornes ............................................................................................................................................................................................13Avec des entiers ........................................................................................................................................................................................................14Et les flottants ? .........................................................................................................................................................................................................15La gnration sans doublons ....................................................................................................................................................................................15Une premire ide .....................................................................................................................................................................................................16Une approche plus efficace ! .....................................................................................................................................................................................

19Simuler une distribution de cartes gomtrique ..............................................................................................................19Un brave jeu de 32 cartes .........................................................................................................................................................................................19Une machine "quilibre" ..........................................................................................................................................................................................21Une machine dsquilibre .......................................................................................................................................................................................23Un jeu infini ! ..............................................................................................................................................................................................................23Un problme pineux ................................................................................................................................................................................................24Un jeu de pile ou face ...............................................................................................................................................................................................29Des variantes ............................................................................................................................................................................................................

30Partie 2 : La mthode de Monte Carlo ..............................................................................................31Calculons pi ! ...................................................................................................................................................................31Titi la rescousse .....................................................................................................................................................................................................31Un jeu de flchettes ..................................................................................................................................................................................................32Reflchissons un peu ................................................................................................................................................................................................32Un pitre tireur : votre ordinateur ..............................................................................................................................................................................33Lancer une flchette ..................................................................................................................................................................................................33Sommes-nous dans le disque ? ................................................................................................................................................................................33 vous de jouer ! .......................................................................................................................................................................................................

36Savez-vous intgrer ? .....................................................................................................................................................36Dfinissons les choses ..............................................................................................................................................................................................37Une mthode de calcul classique .............................................................................................................................................................................37 la main ...................................................................................................................................................................................................................38Grce notre ordinateur ...........................................................................................................................................................................................39Le calcul par Monte Carlo .........................................................................................................................................................................................39L'ide de l'algorithme .................................................................................................................................................................................................39Le calcul concret .......................................................................................................................................................................................................

40Passez dans les dimensions suprieures .......................................................................................................................41Les fonctions deux variables, ou comment avoir de jolies courbes en 3D .............................................................................................................42Doublez les intgrales ...............................................................................................................................................................................................42Une histoire de volume .............................................................................................................................................................................................43Le retour des rectangles ............................................................................................................................................................................................44Commentaires sur la mthode ..................................................................................................................................................................................44Et avec Monte Carlo, c'est mieux ? ...........................................................................................................................................................................45Comment a marche ? ..............................................................................................................................................................................................45 vous de jouer ! .......................................................................................................................................................................................................46Les patatodes arrivent ! ............................................................................................................................................................................................

2/47

http://fr.openclassrooms.com/http://-/?-


3/46

Logos raliss parLaolis

A la dcouverte de l'alatoire et des probabilits

Par sebsheep

Mise jour : 15/09/2011Difficult : Facile

Chers zros, bonjour et bienvenue sur ce tutoriel !

L'alatoireintervient dans de nombreux phnomnes, du s imple lancer de d aux mouvements de particules subatomiques, enpassant par le cours d'actions en bourse et j'en pass e. Il est donc intressant de l'tudier, et en particulier de le simulerafin deprvoir l'volution de certains paramtres . Cette tude relve du domaine des probabilits .

Vous dcouvrirez ici de nombreuses facettes de l'alatoire et de ses applications parfois surprenantes. Vous apprendrez bien sr vous servir de la fameuse fonction rand, et bien plus encore : vous comprendrez entre autres le fonctionnement internedecette fonct ion ! Vous serez alors capables de crer votre propre fonctionrand, et mme de simuler un d pip, ou d'autres

phnomnes alatoires complexes. On s 'intress era galement au calcul des intgrales (des "surfaces" si vous prfrez), calculsutiles dans de nombreuses branches des s ciences et de l'ingnierie.

A qui est destin ce cours ?

La philosophie de ce cours es t d'expliquerau plus grand nombre tous les concepts et rsultatsprsents. Les pr-requismathmatiques sont donc relativement faibles : fin du collge du s ystme franais. Ce tutoriel pourra donc intresser les curieuxqui aiment comprendre le fond des choses ou des tudiants souhaitant avoir une vue d'ensemble avant d'aborder un cours de

probabilits .

Le but de ce tutoriel est d'expliquer les concepts, pas de donner la mthode la plus efficace poss ible pour tous les

algorithmes prsents. Il peut cons tituer une excellente "mise en bouche" mais n'a absolument pas la prtention de s esubstituer un vritable cours de mathmatiques , ni d'tre une rfrence technique ce su jet.

Une dernire note avant de commencer : les diffrentes parties ont t crites des moments et dans des esprits d iffrents .Concrtement, les chapitres de la premire partie sont des articles indpendants : il possible de les lire dans n'importe quel ordre.La deuxime partie vous prsente une application originale de l'alatoire et cons titue un seul bloc, il est par cons quent cons eillde la lire dans l'ordre.

Sommaire 3/47

http://fr.openclassrooms.com/http://www.siteduzero.com/membres-294-179242.htmlhttp://www.v3.siteduzero.com/tutoriel-21-133680-a-la-decouverte-de-l-aleatoire-et-des-probabilites.htmlhttp://www.v3.siteduzero.com/membres-294-18643.html


4/46

Partie 1 : Simuler l'alatoire

Dans cette partie, nous allons voir des techniques permettant de "simuler" l'alatoire. En particulier, vous dcouvrirez commentfonctionne la fonction "rand" , qui permet dans la plupart des langages de crer un entier alatoire. Cela permet par exemple desimuler simplement un lanc de d "normal".

Dans le 3me article, vous allez aussi apprendre s imuler un d "pip" de faon efficace, et vous dcouvrirez galement unemthode permettant de s imuler des lois de probabilit un peu p lus complexes.

A venir prochainement : la simulation de variables alatoires continues.

Fabriquez votre propre fonction "rand"Comment faire pour avoir des nombres alatoires ?

Facile ! Suffit de faire rand() et puis voil ! Et puis avant faut initialiser avec srand sinon c'est toujours pareil.

Oui mais imaginons que nous n'avons pas accs rand, comment faire (imaginons que nous devions recoder toutes lesbibliothques C suite un crash massif de machines) ? Et puis pourquoi faut-il initialiser avec un t ime() si c'est alatoire ?

Heu ... tu me poses une colle l !

Dans ce tuto, vous allez dcouvrir tout ce qui se cache derrire rand.Vous n'avez besoin d'aucune connaissance particulire pour lire ce tuto (pas mme avoir dj utilis rand). Les exemples seronten C++, mais sont videmment transposables tous les langages. Vous aurez un petit cadeau la fin du tutoriel : une classeAleatoire qui produit des nombres alatoires comme une grande !

Note : ne vous attendez pas crire plein de code super compliqu dans ce tuto ; l'ensemble du code final ne dpas sera pas les

40 lignes . Le but ici est de bien comprendre ce qu'on fait et pourquoi on le fait.L'alatoire... vraiment alatoire ?Que de la poudre aux yeux !

Eh oui, je vais commencer fort en vous assnant d'entre cette vrit troublante : aucun algorithme de calcul ne peut produiredes nombres de faon alato ire. En effet, par dfinition, l'alatoire ne peut pas tre calcul par un quelconque algorithme. Vousallez me dire qu'aprs tout, a semble logique, mais il fallait le dmontrer : mons ieur Per Martin-Lf l'a fait en 1966.

Quoi ? Mais tu nous a rouls alors ! Le tuto est dj fini ?

Non, ne vous inquitez pas , c'est loin d'tre fini ! On ne peut effectivement pas gnrer un nombre parfaitement alatoire, mais onpeut quand mme s'en approcher. On appelle alors les nombres crs des nombres pseudo-alatoires. On a l'impression que lesnombres gnrs s ont alatoires, mais si on fait une tude approfondie, on peut se rendre compte qu'ils suivent un certainmcanisme. C'est ce que l'on va voir dans ce tuto.

J'entends dj quelques esprits retors me demander si on ne peut quand mme pas produire des nombres de faon purementalatoire ; en fait vous connaiss ez dj la rponse : c'est oui. Lancez un d : vous venez de raliser une exprience purementalatoire ; mais pour l'utiliser en informatique, ce n'est gure commode, vous en conviendrez (bien que certains l'aient fait). C'est

pourquoi nous allons effectuer un bref survol de ces mthodes purement alatoires.

Des moyens purement alatoires

L'accumulation d'entropie

Ne vous enfuyez pas en courant ! Le nom est un peu pdant, mais l'ide es t fort simple. L'entropie, on peut traduire ce mot

A la dcouverte de l'alatoire et des probabilits 4/47

http://fr.openclassrooms.com/http://www.blogeee.net/2009/05/27/un-jeteur-de-des-analogique-au-secours-dun-editeur-web


5/46

simplement par "dsordre". Donc cette mthode cons iste attendre qu'un nombre d'vnements alatoires (le mouvement de lasouris, les temps d 'accs mmoire, les connexions reues sur un port rseau...) suffisamment lev se produise pour pouvoirdonner un nombre. Cette mthode n'est priori pas de trs bonne qualit, pour deux raisons :

les vnements considrs ne s ont que moyennement alatoires (en effet, on clique toujours sur les mmes boutons) ;cette mthode es t relativement lente ! Si on attend un mouvement de s ouris et que l'utilisateur ne se sert que du clavier,on peut attendre longtemps avant d'avoir un nombre quelconque !

C'est pourquoi on ne l'utilise pas "brut de dcoffrage", mais enveloppe dans des algorithmes tels que Yarrowou Fortuna(entreautres) en cryptologie ; il est en effet trs dur pour un pirate de prvoir les nombres gnrs . Comme l'indiquent les articles misen lien, son implmentation dans une optique de cryptologie est ass ez complexe !

Les mthodes physiques

On peut auss i utiliser des mthodes phys iques pour produire des nombres alatoires. Effectivement, il existe des phnomnesqui sont parfaitement alatoires : les variations d'une rsistance lectrique, la prsence d'un photon un endroit donn... Toute ladifficult de ces mthodes est de ne pas trop perturber le systme pour qu 'il conserve son caractre alatoire sans tre biais(dform) lors de la mesure de la valeur. Par exemple, si pour mesurer une variation de rsistance (qui sera videmment minime),on utilise un voltmtre qui introduit une faible rsistance dans le circuit, la mesure s era fausse !

Pour avoir un exemple concret, Toshiba a dvoil en fvrier 2008 la sortie d'un circuit gnrateur de nombres alatoires trscompact (1200 micromtres) produisant 2Mbits alatoires par s econde. Pour vous faire une ide, cela correspond environ62500 entiers sur la plupart des machines ; autant dire que c'est ridiculement faible par rapport un appel la fonction rand quien gnre beaucoup plus , en beaucoup moins de temps ! Ceci dit, les nombres trouvs avec rand ne sont que ps eudo-alatoires,donc de moins bonne qualit.

Un avant got historique : la mthode des carrs mdians

Von Neuman, l'un des pres de l'informatique moderne, introduisit cet algorithme en 1946. On considre que c'est la premiremthode algorithmique des tine gnrer automatiquement des nombres alatoires. Vous allez voir, son fonctionnement n'es t

pas trs compliqu, mais nous allons dj voir apparatre des choses intress antes.

Le principe est le suivant : on prend un nombre, par exemple 35, que l'on met au carr. Dans notre cas nous avons 35x35=1225. Ensuite, on prend les chiffres du milieu, ici 22. Puis on recommence ; on met 22 au carr : 22x22 = 484, que l'on peut crire 0484. Nousobtenons un nouveau nombre : 48 ... La suite des nombres gnres sera donc : 35, 22 et 48.

videmment, en pratique, on ne se contente pas de prendre des nombres 2 chiffres, mais le principe est le mme.L'implmentation de cette mthode n'est pas trs complique ... condition de rflchir en base 2 et de se servir des oprateurs

bits bits. Ceci tant compltement en dehors de ce que je veux vous expliquer, je vous renvoie au tuto de 1337833Ksur le sujet.

Nous allons cependant continuer la main les calculs :Code : Console

35 22 48 30 90 10 ...

Et l on s'arrte ! Eh oui, vu qu'on connat nos tables de multiplications : 10x10=0100 ; on prend les chiffres du milieu, on retombesur 10 et on n'en bougera plus . Pas trs alatoire comme mthode ! C'est encore pire si l'on part de 84 :

Code : Console

84 05 02 00 00 00 00 00

Von Neumann tait bien videment conscient de ces problmes (parce qu'il y en a en fait plus ieurs) mais craignait d'en introduired'autres en modifiant l'algorithme. Vous l'aurez compris, cette mthode est limite et as sez dlicate utiliser ; c'est pourquoi peude temps aprs, Lehmer introduisit une nouvelle mthode ...

Une mthode... puissante ! la dcouverte de la mthode

Partie 1 : Simuler l'alatoire 5/47

http://fr.openclassrooms.com/http://www.siteduzero.com/tutoriel-3-32150-les-operateurs-bits-a-bits-employes-sur-des-nombres-entiers.htmlhttp://fr.wikipedia.org/wiki/John_von_Neumannhttp://fr.wikipedia.org/wiki/Fortuna_%28cryptologie%29http://fr.wikipedia.org/wiki/Yarrow


6/46

L'une des mthodes les plus utilises actuellement es t la mthode des congruences linaires.

L encore, des grands mots pour quelque chose de pas si compliqu que a ! Dcortiquons ensemble cette express ion barbare.Congruence: dans notre cas , cela se rfre ce qui a rapport avec le reste de la division entire (vous savez, le signe '%' qui nesert rien ?).

Linaire: en simplifiant, cela revient dire que l'on ne fait que des oprations de type addition et multiplication. Le typed'opration "mise au carr" et " logarithme" n'existe pas (ce n'est pas trs grave s i vous ne comprenez pas cette phrase, c'est justepour la culture).

De faon plus concrte, voici une formule permettant de calculer une suite de nombres alatoires :

Code : Autre

nouveau_nombre= (a*ancien_nombre + b) % m

Petit rappel important pour la suite, "a%n" signifie le restede la division de apar n. Par exemple 11%3=2 : 11 divis par

3 gal 3, il reste 2 ; et 12%3=0 : 12 divis par 3 gal 4, il reste 0.

Pour traduire cela avec des mots , a donne : pour trouver le nouveau nombre alatoire, il faut :1. Prendre celui que l'on vient de calculer, le multiplier par a puis ajouter b ;2. Si le nombre obtenu est plus grand que m, lui enlever m jusqu' ce qu'il soit plus petit.

Rien ne vous choque ? Pas un petit problme de variable non dfinie ? Ah si quand mme ! La formule dit qu'il faut prendre lenombre que l'on vient de calculer, mais s i on n'a encore rien calcul, on prend quoi ? C'est l un s ujet pineux dont on pourraitdbattre longtemps, mais nous n'allons pas nous tendre s ur ce s ujet. En gnral, comme premire valeur, on prend le timestamp;cette premire valeur s'appelle la graine(seeden anglais).

Cela vous explique pourquoi, en C, vous devez initialiser rand par s rand (qui doit vouloir dire seedrand), en passant en argumentle timestamp actuel ! Si vous ne le faites pas , la suite de nombres gnre es t toujours la mme... c'est fcheux pour un jeu dehasard...

Dans des langages plus volus, comme Java ou Python, on n 'a pas faire cette initialisation, le langage s'en chargelui-mme !

Un premier code

Maintenant que vous avez la thorie, je vous propose de coder votre propre gnrateur alatoire. L'exercice cons iste crire unprogramme (tout dans le main, on s'embtera plus tard avec des jolies s tructures) qui affiche 15 nombres alatoires.Vous devez rflchir comment coder la formule que j'ai donne au-des sus (pour les valeurs de a, b et m, mettez un peu au hasard

pour l'ins tant, en bidouillant pour que a marche mieux si besoin, mais gardez-les relativement petits).

Attention, prts ? C'est parti !

Secret (cliquez pour afficher)

Code : C++

#include #include usingnamespacestd;

main(){unsignedinta=3,b=3,m=5; // Dfinition des valeursunsignedintnombre =time(NULL); // Dfinition de la graine


http://fr.openclassrooms.com/http://www.v3.siteduzero.com/tutoriel-3-133680-a-la-decouverte-de-l-aleatoire-et-des-probabilites.html?pdf=1&all=1#http://fr.wikipedia.org/wiki/Timestamp_%28informatique%29


7/46

for(inti=0;i


8/46

si m est un multiple de 4, alors a%4 = 1;pour tous les nombres premierspdiviseurs de m, on a a%p =1 .

Rappel :

Nombres premiers : tous les nombres entiers qui ne peuvent pas se dcompos er en facteurs autres que lenombre lui-mme ou 1. Par exemple, on peut dcomposer 15 (= 3*5), donc il n'est pas premier. Par contre 13 est

premier, on ne peut pas trouver 2 entiers a et b (autres que 1 et 13) tels que a*b=13.Nombres premiers entre eux : soient deux nombres entiers x et y. On peut dcomposer ces nombres en facteurs :x=1*d*e*f*... et y=1*n*o*p*... On dit que x et y sont premiers entre eux s'ils n'ont aucun facteur en communautre que 1. Par exemple 24 = 1*3*2*2*2 est premier avec 35 = 1*5*7, ils n'ont que 1 en commun. En revanche,35 = 1*5*7 n'est pas premier avec 15 = 1*5*3 : ils ont 5 comme facteur commun.

Mais la 2econdition, elle ne sert rien ! Ce n'est qu'un cas particulier de la 3e!

Erreur ! La troisime nous parle des diviseurs premiers de m. La deuxime est effective si 4 est un diviseur de m. Mais 4 n'est pas

premier (eh oui 4=2*2).

Si vous n 'avez absolument jamais entendu parler de nombres premiers, ne vous attardez pas dess us, retenez juste qu'il suffit devrifier certaines conditions sur a, b et m pour avoir une priode maximale.Pour les autres qui en savent un peu plus, essayez vraiment de voir quoi ces conditions correspondent, et tentez de montrerque les valeurs que l'on a prises au-dess us ne donnent pas une priode maximale.Pour les trs forts en arithmtique, vous pouvez essayer de dmontrer ce rsultat (sans aller voir la dmo sur Wikipdia ouquivalent, cela va sans dire...).

Si vous voulez voir comment vrifier effectivement ce critre, jetez un coup d'oeil au QCM, la correction est assez complte.

Maintenant, nous pouvons former un gnrateur priode maximale. Par exemple les valeurs : a=5, b=3, m=8 vrifient les 3conditions ci-dess us et produisent la sortie suivante (c'est exactement le mme programme, il suffit de changer les valeurs dans

la premire ligne du main) :

Code : Console

0 3 2 5 4 7 6 1 0 3 2 5 4 7 6 1

Tous les chiffres sont bien parcourus, la priode est maximale, YOUHOU !!! Nous avons notre premier gnrateur alatoireefficace !!!

Mais attendez, ce n'est pas fini ! Les nombres que nous utilisons l sont trs petits. Quand on veut utiliser des nombres plus

grands, d'autres problmes apparaissent.

Minimisons la corrlation !

Encore un mot compliqu, mais comme d'hab, une signification pas bien sorcire : la corrlation entre deux nombres alatoirespeut tre vue comme la capacit, connaissant un nombre, de dterminer le second.

Un exemple pour comprendre : on prend a=230+1, b=3 et m=231. La sortie donne un truc du genre :

Code : Console

1073741832 1073741835 14 17 1073741844 1073741847 26 29 1073741856 1073741859 38 41


http://fr.openclassrooms.com/


9/46

Si on fait attention, on remarque qu'on passe d 'une valeur l'autre en ajoutant 3 (crivez la main ce que a donne, vous verrez).Les nombres sont donc fortement corrls.

Il va donc falloir encore une fois trouver des critres qui nous permettent d'avoir une faible corrlation. Et encore une fois, on ditmerci aux matheux :

mdoit tre le plus grand poss ible (en gnral, on veut profiter de tous les entiers disponibles, donc on prend 232-1 ou

231

). C'est un truc qui nous arrange bien car cela permet d'avoir une priode trs longue ;bdoit tre "petit" par rapport aet m;adoit tre proche de la racine carre de m.

Dans l'exemple que j'ai pris juste au-dess us (a=230+1, b=3 et m=231), aest trs loign de la racine de m; grce ce critre,nous aurions pu voir immdiatement que ce gnrateur tait pourri !

Si on prend m=232-1, il n'est pas ncessaire d'effectuer le modulo explicitement car ce nombre correspond au plus

grand entier non sign en C (sur une machine 32 bits). Le modulo se fera donc de lui-mme ! Cependant, 232-1n'est pas

forcment trs pratique utiliser, et on prfre des fois prendre 231qui n'a qu'un seul diviseur (2) ce qui simplifie l'tudedu gnrateur. Nous garderons donc le %m; de plus la dfinition des entiers varie d'une plate-forme l'autre, on ne peut

pas supposer froidement que les entiers sont cods sur 32 bits !

Quelques bons gnrateurs

Voil, maintenant, vous savez pratiquement tout s ur les gnrateurs congruentiels linaires.Donc pour rsumer, pour avoir un bon gnrateur, il faut avoir une priode maximale etil faut que les coefficients respectentquelques rgles. Si vous oubliez une des conditions, le gnrateur sera mdiocre.

Je vais terminer cette partie en vous invitant aller voir quelques "bons" gnrateurs u tiliss par certaines librairies (j'ai choisil'article anglais car l'article franais est beaucoup moins bien fait) : article anglais s ur les gnrateurs congruentiels linaires surWikipdia(le coefficient que j'ai appel 'b' est appel 'c' dans cet article).

Une classe AleatoireDans cette partie, nous allons mettre en pratique ce que nous avons appris. Comme je l'annonce depuis le dbut, nous allonstous ensemble construire cette class e Aleatoire.

Je vais tre assez spcial vu que je vais vous demander de faire un gnrateur "paramtrable". Je veux que n 'importe qui puissedfinir un gnrateur congruentiel linaire en tes tant diffrentes valeurs. Je veux en plus que cette classe s oit indpendante,dans la mesure o elle devra elle-mme initialiser la graine.

Ess ayez de la faire par vous-mmes, il n'y a aucun "pige" particulier. Il s'agit juste de mettre dans une classe le code que l'on atap dans le main un peu plus haut.

Voici une correction possible.

Le fichier Aleatoire.h :

Code : C++

#ifndef _ALEATOIRE_H#define _ALEATOIRE_H#include classAleatoire{ private: unsignedintm_a,m_b,m_m; // Les coefficients du gnrateur unsignedintm_nombre; // le nombre actuel gnr

public:

Aleatoire(unsignedinta=16807, unsignedintb=0, unsignedintm=0x7FFFFFFF); // par dfaut, le gnrateur prendra les valeurs du

// compilateur Apple CarbonLib intgenerer();};


http://fr.openclassrooms.com/http://en.wikipedia.org/wiki/Linear_congruential_generator


10/46

#endif

Et le fichier Aleatoire.cpp :

Code : C++

#include "aleatoire.h"

Aleatoire::Aleatoire(unsignedinta,unsignedintb,unsignedintm) :m_a(a),m_b(b),m_m(m){

m_nombre =time(NULL);}

intAleatoire::generer(){ m_nombre =(m_a*m_nombre +m_b) %m_m; returnm_nombre;

}

Et voil ! Une classe toute s imple, prte l'emploi !

Un petit main pour l'utiliser :

Code : C++

#include #include

#include "aleatoire.h"usingnamespacestd;

intmain(intargc, char*argv[]){ Aleatoire a(3,3,5); for(inti=0;i


11/46

Si vous voulez aller vraiment plus loin (en dess ous de bac +1 en maths, s 'abstenir), vous pouvez essayer de comprendre lamthode de Mersen Twister qui permet d'avoir une gnration encore meilleure.

Si vous voulez des applications de ce que l'on a fait, vous pouvez aller voir mon tuto sur la mthode de Monte Carloqui est trsutilise en phys ique nuclaire.


http://fr.openclassrooms.com/http://www.siteduzero.com/tutoriel-3-133680-toute-la-puissance-de-monte-carlo.html


12/46

L'alatoire en C et C++ : se servir de randEnvie de coder un Yams ? Besoin de simuler un phnomne phys ique ? Enfin bref, vous voulez utiliser des nombres alatoiresdans votre programme en C ?

Ce tutoriel est l pour vous !

Aprs avoir dcrypt la fonction rand, nous verrons comment gnrer simplement des nombres alatoires, entiers ou en virguleflottante. Je vous montrerai ensuite une technique pour gnrer une suite d'entiers sans doublons, utile pour simuler des cartestires dans un paquet par exemple.

Ce tutoriel a t crit pour le langage C, mais si vous utilisez le langage C++, ce tutoriel est encore valable. Il suffit justede modifier les "include" : vous devez retirer le ".h" la fin du nom de la bibliothque et insrer un "c" au dbut. Parexemple #include deviendra #include ; et #include deviendra#include .

Le cur de l'alatoire en C : randDes nombres pas si alatoires que a !

Avant de commencer, il faut que vous ayez en tte que l'on ne peut pas avoir de nombres parfaitement alatoires avec la mthodeutilise ici. Vous aurez l'impressionqu'ils le sont, mais en ralit, il ne s'agit que de nombres "pseudo-alatoires" . Si vous voulezen savoir plus, je vous renvoie l'article traitant de ce sujet. Cela n'est en gnral pas trs gnant, sauf si vous faites de lacryptographie ou d'autres applications o la scurit est primordiale, car on pourra "deviner" les nombres qui vont sortir. Dans lasuite, j'emploierai "alatoire" la place de "pseudo-alatoire" par abus de langage.

Votre premire exprience avec l'alatoire

Vous l'attendez tous, alors voici la fonction qui permet de gnrer des nombres alatoires :Code : C - La fonction rand

intrand(void)

Elle fait partie de la bibliothque stdlib , vous devrez donc l'inclure ("stdlib.h"si vous tes en C, "cstdlib"enC++).

"rand" est la troncature du mot " random" qui en anglais veut tout s implement dire "alatoire".

Dans la foule, un exemple pour s 'en servir ; le code suivant affiche cinq nombres alatoires :

Code : C - Gnration de 5 nombres alatoires

#include #include #include //Ne pas oublier d'inclure le fichier time.h

intmain(void){inti =0;intnombre_aleatoire =0;for(i=0; i


13/46

Mais elle es t nulle ta fonction ! J'ai relanc le programme et j'ai eu exactement les mmes nombres !

Oui, cela illustre bien ce que je vous disais au dbut : rand va en ralit toujours renvoyer la mme squence de nombres. Enl'occurrence pour le programme ci-dessus, on aura :

Code : Console

41 18467 6334 26500 19169

Donc priori, pas du tout alatoire ! En pratique, cette squence es t trs (trs) longue, c'est ce qui va nous permettre de "fairecroire" que les nombres sont tirs au hasard. Mais si on part toujours du mme point, ce n'est pas intressant. On va donc "dire" rand de se placer ds le dpart une autre position dans la squence. Mais l, on se mort un peu la queue : il faut choisir"alatoirement" la position initiale.

Le plus courant est d'utiliser la fonction inttime(int*) qui est dfinie dans time.h ; cette fonct ion donne le nombrede secondes coules depuis le premier janvier 1970 (il est trs rare qu'on lance le programme deux fois dans la mme seconde

). On ne se s ervira pas du paramtre que l'on mettra donc NULL, je vous renvoie la doc officiellesi a vous intresse. Onl'appellera donc comme ceci :time(NULL); .

Il me reste vous dvoiler comment "dire rand de se mettre telle position" : on le fait grce la fonction voidsrand(intstart) , o startindiquera o se placer dans la squence.

Le code ci-dessus devient alors :Code : C - Gnration de 5 nombres alatoires

#include #include #include //Ne pas oublier d'inclure le fichier time.h

intmain(void){inti =0;intnombre_aleatoire =0;srand(time(NULL)); // initialisation de randfor(i=0; i


14/46

Code : Autre

rand()%c

Maintenant, mettons que vous vouliez tirer un entier dans l'intervalle [a,b[ (c'est d ire a inclus et b exclu), il vous suffit de tirerun nombre entre 0 et la longueur de cet intervalle (qui est gale b-a), puis d'ajouter a. Le nombre sera bien dans [a,b[. Au final,la fonction ressemblera :

Code : Autre

// On suppose a


15/46

faire, il suffit d'ajouter (double)devant la variable que l'on veut convertir.

En ralit, vous ne gnrerez pas toutes les valeurs entre a et b ; la plus pet ite distance entre deux nombres tirs sera de(b-a)/RAND_MAX. Si (b-a) est petit devant RAND_MAX, pas trop de problmes. Sinon, il faudra trouver d'autresmthodes.

Voil donc la fonction qui gnre des nombres flottants entre 2 bornes :Code : Autre

double frand_a_b(double a, double b){ return ( rand()/(double)RAND_MAX ) * (b-a) + a;}

La gnration sans doublonsOn est parfois amen devoir gnrer une s uite de nombres sans doublons ; c'est dire que s i un certain nombre a dj t tir,il n'est pas possible de le tirer nouveau. Les exemples sont multiples : tirer des cartes dans un tas , tablir un ordre de pas sagealatoire un examen pour une liste d 'tudiants, faire un d iaporama alatoire, ... bref les applications ne manquent pas .

Pour expliquer l'algo, je gnrerai une liste sans doublons d 'entiers de 0 MAX; la modification apporter pour avoir unegnration entre MINet MAXtant minime, elle sera apporte tout la fin.

Une premire ide

La premire ide, nave, qu'on pourrait avoir serait de tirer un nombre au hasard, regarder si ce nombre a dj t tir, et en retirerun autre tant que ce nombre n'a pas t tir.

Mais comment peut-on s avoir si un nombre a dj t tir ?

On peut procder ainsi : les nombres t irs s ont s tocks dans un tableau de taille MAX, dans leur ordre d'apparition. La premirecase contiendra le premier nombre tir, la deuxime case le deuxime, et ains i de suite.

Lorsqu 'on tire un nouveau nombre, on parcourt le tableau pour voir s'il y est dj prsent ; s i c'est le cas, on ne touche pas autableau et on recommence en tirant un nouveau nombre ; sinon, on ajoute ce nombre la dernire case libre du tableau. Pourconnatre l'indice de cette case, on peut utiliser une variable "compteur" qu'on initialisera 0 au dbut, puis qu 'on augmentera de1 chaque fois qu'on ajoute un nombre.

On a donc potentiellement un algo qui fonctionne. Maintenant, s i vous avez du temps perdre, vous pouvez l'implmenter ettester diffrentes valeurs de MAX: 200, 2 000, 20 000, 200 000 ... Personnellement, ma bcane traite le cas 20 000 en une dizaine desecondes et ne s'arrte pas en temps raisonnable (infrieur la minute) pour 200 000. C'est dommage, j'ai 200 000 candidats quivont pass er le Bac ( sable ) et je dois leur donner un ordre de pass age alatoire...

Ce qui est trs long dans cette faon de faire, c'est qu'on parcourt toute la partie du tableau dj remplie pour savoir si un nombrea t tir. Si on pouvait connatre instantanment cette information, on gagnerait beaucoup en efficacit. L'ide es t donc de lastocker dans un deuxime tableau test: si le nombre ia dj t tir, alors test[i]est 1, sinon il est 0.

L'intuition nous pous se penser que cet algo peut ne jamais s 'arrter. C'est faux ! Prenons par exemple le cas o il nereste plus qu'un nombre tirer : la probabilit de NE PAS tirer ce nombre au premier coup es t extrmement leve, maistout de mme strictement infrieure 1. Notons la p. Pour que ce nombre ne s oit pas apparu au deuxime coup, il nedoit pas tre sorti au premier coup, ET ne doit pas tre sorti au deuxime.

Si vous avez dj manipul un peu de probas , vous devez savoir que la probabilit de l'vnement "A ET B" es t gale la probabilit de l'vnement "A" multiplie par celle de l'vnement "B" (si les vnements sont indpendants, ce quiest le cas). Donc ici la probabilit de "le nombre n'est pas apparu au deuxime coup" es t de : p*p=p.

Et ainsi de suite, vous comprenez sans peine que la probabilit de "le nombre n'est pas apparu au n-ime coup" est de

pn. Mais pest strictement infrieur 1. Donc lorsque n devient trs grand, pndevient aussi proche de 0 que l'on veut.Donc l'vnement "le nombre n'apparat jamais" a une probabilit de 0, tout pile.

En conclusion, le nombre de coups ncess aires pour avoir le dernier nombre est bien fini ; il peut en revanche tre trs




16/46

grand.

Une approche plus efficace !

L'ide

La dernire version tourne assez rapidement (MAX=200 000 est trait chez moi en un clin d'?il), mais il subsiste deux points noirs:

comme indiqu dans l'encadr juste au-dess us, mme s i le nombre de tirages est fini, il peut tre trs grand, ce qui prendrabeaucoup de temps ;on a bes oin d'un tableau annexe (test), ce qui prend de la place.

Pour comprendre le nouvel algo, je vais faire l'analogie avec un jeu de cartes ; remarquez que distribuer toutes les cartes auxjoueurs revient gnrer sans doublons toutes les cartes et les donner aux joueurs au fur et mesure. Pour faire cela, est-ce quevous utilisez l'algo que j'ai dcrit au dess us lorsque vous jouez aux cartes en famille ? Je ne pense pas (ou alors allez vite

consulter un mdecin, c'est grave ); non, vous mlangezvos cartes !

C'est exactement la mme ide ici. Nous allons encore avoir besoin d'un tableau (mais d'un seul cette fois). Pour l'initialiser, nousle remplissons "dans l'ordre" : la case n 0, on y met 0, la n1, on y met 1 et ainsi de suite jusqu' MAX. Ensuite il suffit de lemlanger.

Alors un paquet de cartes , je vois comment le mlanger, mais un tableau s tock dans la RAM, j'ai plus de mal ...

Pas de panique ! L'ide es t toute s imple : vous tirez un nombre alatoire aentre 0 et MAX; puis vous changez le contenu de lacase n0avec la case na. Et vous faites a pour toutes les cases . Cet algo corrige bien les deux cueils que j'avais relevs

propos du premier et gnre bien une s uite sans doublons .

Il reste une petite broutille : pour l'instant, l'algorithme gnre des entiers entre 0 et un nombre. Pour gnrer une suite valeursdans [a,b[, il n'y a qu'une modification faire, lors de la gnration du tableau : la case n0, on met a, la case n1, on meta+1et ainsi de suite. C'est tout ! Le reste du code se contentera de mlanger les cases, sans s e proccuper de leurs valeurs (ilfaut tout de mme bien penser tirer les valeurs dans l'intervalle [0,b-a[pour que les nombres tirs soient bien des indices dutableau).

L'implmentation

On pourrait crire une fonction qui prend en argument aet b, les bornes de l'intervalle dans lequel on veut gnrer notre suite, etqui alloue un tableau, lui applique l'algo dcrit au-dess us et le renvoie.

Problme : si on veut gnrer plusieurs s uites alatoires du mme intervalle, on devra allouer et initialiser un nouveau tableau chaque fois. Ce qui prend du temps. Et vous l'aurez remarqu, je n'aime pas en perdre !

On va donc crire deux fonctions : une qui alloue et initialise le tableau et une qui se contente de mlanger un tableau pass enparamtre. Si on veut une nouvelle suite, il nous s uffira de re-mlanger le tableau, sans avoir le rallouer.

La premire ne devrait pas vous poser de problmes ; elle prend deux arguments entiers aet bqui sont les bornes de l'intervalleet renvoie un pointeur sur un tableau de taille (b-a)contenant {a, a+1, a+2, ..., b-1}. La voici :

Code : C

int*init_sans_doublons(inta, intb){inttaille =b-a;

int*resultat=malloc((taille)*sizeof(int));inti=0;// On remplit le tableau de manire ce qu'il soit trifor(i =0; i


17/46

}

Pour la deuxime, la seule difficult se s itue peut-tre dans l'change des valeurs de deux cases ; pour ce faire, on est obligd'utiliser une variable temp. Cette fonction prend deux arguments : un pointeur vers un tableau et la taille de celui-ci.

Code : C

voidmelanger(int*tableau, inttaille){inti=0;intnombre_tire=0;inttemp=0;for(i =0; i


18/46

Ici, j'ai choisi de pas ser la taille du tableau en s econd argument de la fonction melanger. C'est as sez dsagrable : onest oblig de la calculer (alors que initle fait dj) puis de se souvenir de cette taille pour appeler cette fonction. Lasolution habituelle est de crer un structqui contient deux champs : le tableau et la taille de celui-ci.init_sans_doublonsrenverrait alors un pointeur vers une structure de ce type, calculant la taille une fois pourtoute. Et melangerprendrait alors un seul argument : (un pointeur vers) la structure cons idre.

Pour des raisons de s implicit, je n'ai pas opt pour cette s olution pour le tuto ; dans la vraie vie, si vous devez vousservir de nombreuses reprises de ces fonctions, je ne peux que vous conseiller de l'implmenter.

Voici un premier aperu de l'utilisation des nombres alatoires en C. Si vous voulez vous entrainer un peu, vous pouvez vousamuser coder des jeux comme un yams ou un Mas ter Mind, une animation en SDL qui simule une chute de neige ou encore

plein d'autres applications auxquelles je ne pense pas .

Vous pouvez aussi vous amuser vrifier "numriquement" ceci : si on a une file de personnes places alatoirement contenantPierre et Paul, le nombre de personnes le plus probableentre les deux comparses est de 0 (autrement dit, Pierre et Paul sont cte cte). Cela vous fera utiliser la gnration sans doublon . Cela parat surprenant, mais c'est pourtant vrai, un simple calcul de

dnombrement permet d'arriver au rsultat.

Pour une utilisation un peu plus surprenante de l'alatoire, vous pouvez allez voir le tuto s ur la mthode Monte Carlo.

Bonne continuation et bientt pour un autre tuto !


http://fr.openclassrooms.com/http://www.siteduzero.com/tutoriel-3-133680-toute-la-puissance-de-monte-carlo.html


19/46

Simuler une distribution de cartes gomtriqueDis, pourquoi y'a que 32 cartes dans ton jeu ?

Voici la question que m'a pos Titi, alors que nous terminions une partie endiable de "bataille".

Je lui ai alors rpondu que j'avais s ous la main un jeu de 54 cartes, mais a ne lui suffisait pas : "Pourquoi QUE54 cartes ?" ;commenant m'impatienter, j'esprais lui clouer le bec avec les 78 cartes du jeu de tarot, mais c'tait peine perdu : "PourquoiQUE78 cartes ? Pourquoi est-ce qu'on ne peut pas avoir autant de cartes diffrentes que l'on veut, a serait plus marrant non

?".

Au dbut, en tant que grande personne, j'tais s ceptique, mais Titi a t trs indulgent avec moi ; il m'a donn et redonn s esexplications... Je vous transcris ici ce que j'en ai compris.

Son ide tait d'inventer une variante au jeu de la bataille : au lieu de tirer les cartes dans le tas devant s oi, on prend les cartesdlivres par une machine, avec une infinit de cartes diffrentes. Et ensuite de programmer une telle machine.

Pour comprendre tout cela, il m'a d'abord expliqu comment simuler un simple jeu de cartes , puis comment simuler un d pip. Il

en a profit pour m'expliquer ce qu'taient un espace de probabilit et une loi de probabilit, et comment simuler ces lois.

Il m'a ensuite emmen dans le monde de l'infini, j'ai alors compris que raliser cette machine n'tait pas une sincure !

Un brave jeu de 32 cartesUne machine "quilibre"

D'entre de jeu, Titi m'a dstabilis en changeant le nom des cartes. Il m'a dit que cela n'avait pas d'importance ; au lieu d'avoir"As de cur", "Roi de pique" ... Nous aurons simplement des entiers : 1, 2, 3, et ce jusqu' 32. Il suffira d'avoir une liste dans uncoin o l'on a not que 1 correspond "As de cur", 2 "As de carreau", etc.

Du coup, j'ai propos moi-mme une mthode pour simuler cette machine : tirer un nombre alatoirement entre 1 et 32 et crire le

nombre obtenu sur un carton ! J'ai test a dans mon langage favori... et a marche !

videment, Titi n'a pas pu s'empcher de faire son intress ant :

Euh oui, a marche, mais quel est ton espace de probabilit ? Quelle est ta loi de probabilit ?

Devant mes yeux grands comme des soucoupes , il se sent it oblig de m'expliquer. Au dbut, je ne voyais pas l'intrt de s ecompliquer la vie avec de nouveaux noms, mais trs v ite, je me suis rendu compte ces notions nous facilitaient grandement latche ; soyez donc patients et attentifs, je vous promets que le rsultat sera convaincant !

Espace de probabilitC'est tout simplement l'ensemble de tous les vnements possibles. C'est pourquoi on l'appelle aus si "univers des possibles".Dans notre cas c'est trs simple, il s'agit de {1, 2, 3, ..., 30, 31, 32}.

Probabilit

La probabilit d'un vnement, c'est un nombrequi caractrise la frquence d'un vnement. Si ce nombre est trs proche de 0,l'vnement aura trs peu de chances de se produire ; s'il est trs proche de 1, l'vnement aura au contraire beaucoup de chancede se produire.

Par exemple, quand on tire pile ou face, la probabilit de tomber sur face est de 0,5 (=1/2) : on a 1 chance sur 2 que cela arrive.Quand on lance un d, la probabilit de tomber sur le 3 est de 0,166... (=1/6) : on a 1 chance sur 6 que cela arrive. La probabilit de

tirer la dame de pique (ou toute autre carte) dans notre jeu de 32 cartes est de 1/32.

Retenez bien : s i la probabilit d'un vnement est 0 (tout pile), l'vnement ne s e produirajamais; s i c'est 1,l'vnement se produira toujours . Une probabilit est toujours comprise entre 0 et 1.




20/46

Loi de probabilit

Une loi de probabilit, c'est ce qui dtermine la probabilit de chaque vnement.

C'est quoi la diffrence avec une probabilit ?

C'est compltement diffrent. Aprs de longues rflexions, j'ai compris qu'en fait, connatre une loi de probabilit, a revient connatre un tableau qui indique quelle probabilit apparat chaque lment. Par exemple, pour notre jeu, la loi est donne par :

Loi de probabilit d'une machine "quilibre"

Carte n 1 2 3 ... 30 31 32

Probabilit ...

Comme vous pouvez le voir sur le tableau, la loi de probabilit pour notre jeu de carte est assez simple : chaque lment a lamme probabilit d'apparition, savoir 1/32.

Pour faire un peu plus srieux, je me suis permis d'introduire une notation pour cette loi de probabilit : dans notre cas parexemple, je noterai la probabilit que le "3" apparaiss e avec : P({3}). Ici, on a donc P({3})= 1/32. De mme, pour n'importe quelentier n entre 1 et 32, on a P({n})=1/32. J'appellerai {3} un "vnement lmentaire", et P({3}) une "probabi lit lmentaire".

Vous avez donc une deuxime manire de connatre une loi, c'est de connatre chaque probabilit lmentaire ; autrement dit,pour tous les vnements lmentaires ede l'univers des possibles, vous connaissez P(e).

Vous avez donc deux manires de reprsenter une loi : soit grce un tableau, soit grce P. Vous devez vous assurerque vous avez bien compris que ces deux notations servent la mme chose. Dans la suite, on utilisera soit l'un s oitl'autre su ivant ce qui est le plus adapt : il faut pouvoir jongler entre les deux sans problmes !

Au pass age, vous aurez remarqu que je dis maintenant s implement " loi" au lieu de "loi de probabilit" car je su is un grosfainant, et que tout le monde sait bien de quoi on parle. Si un plouc pens e que je parle de la "loi franaise", je lui cons eilled'arrter la fac de droit>

Ne voulant pas en rester l, j'ai eu envie de connatre la probabilit que le 3 ou le 7 apparaisse. En gardant la mme notation, cetteprobabilit sera reprsente par P({3,7}) qui est clairement gale P({3}) + P({7}) = 2/32 (ou 1/16 pour les puristes).

Les plus malins d'entre vous tenteront de calculer P({3,3}). On peut le faire bien sr, mais cela ne vaut pas P({3}) +P({3}) ; {3, 3} reprsente l'vnement : "le 3 sort" OU "le 3 sort"... Vous admettrez qu'il s'agit tout s implement del'vnement "le 3 sort" et donc que sa probabilit est gale P({3}).

Parti sur ma lance, j'ai cherch la probabilit que 5 cartes donnes apparaissent, puis 10, et puis tant qu' faire 32 (c'est dire, latotalit du jeu). Cette probabilit est de : P({1, 2, ..., 31, 32}) = P({1}) + P({2}) + ... + P({31}) + P({32}) = 32/32 = 1. Vous allez medire que j'aurais pu m'en douter : l'vnement que je considre se produit tout le temps (lorsqu 'on tire une carte, on tire soit le 1,soit le 2, ...., soit le 32). Or un vnement qui se produit tout le temps a une probabilit de 1 !

Titi m'a alors fait remarquer la chose suivante : la somme de toutes les probabilits lmentaires est gale 1 !

a ne marche que pour notre jeu de cartes a non ?

Eh bien non, c'est en fait trs gnral. Si vous reprenez le paragraphe au-dess us, vous vous rendez compte que vous pouvez lemodifier pour l'adapter n'importe quel univers des possibles. On peut donc caractriser une loi de probabilit : il suffit quelorsqu'on additionne toutes les probabilits lmentaires, on obtienne 1.

Aprs m'avoir expliqu tout a, Titi n'tait pas encore trs satisfait : "Ta machine elle marche, mais elle est pas drle ; et puis lescartes, j'en ai ma claque, j'ai envie de jouer aux ds maintenant ! Je veux une machine qui simule un d pip : plein de 4 et pas




21/46

beaucoup d'autres chiffres !"

Une machine dsquilibre

Faites votre loi !

Pour faire cela, Titi m'a dit qu'il suffisait de dfinir une nouvelle loi de probabilit.

Ce que veut Titi, c'est avoir beaucoup de "4". Pour cela, je mets donc une grosse probabilit sur "4", disons 0,6. Une fois que j'aifix cette probabilit, je ne peux pas prendre ce que je veux pour les autres probabilits lmentaires. Souvenez vous, il faut quela somme de toutes les probabilits lmentaires soit gale 1. Il me reste alors 0,4 (= 1 - 0,6) rpartir entre les valeurs restantes.

Par exemple, je peux avoir la loi suivante :Loi de probabilit d'une machine "dsquilibre"

Face n 1 2 3 4 5 6

Probabilit 0.08 0.08 0.08 0.6 0.08 0.08

videmment, je ne suis pas oblig de mettre la mme probabilit pour "1", "2", "3" ,"5" et "6". Je peux aussi prendre :Loi de probabilit d'une machine"dsquilibre"

Face n 1 2 3 4 5 6

Probabilit 0.05 0.05 0.1 0.6 0 0.2

Vous remarquez ici que la probabilit de tirer un 5 est de 0 ; cela veut dire que le 5 ne sortira jamais !

Je vous laiss e le soin de vrifier que la somme des probabilits fait bien 1. Et coup de chance, cette loi plat beaucoup Titi !

Construire la machine

Mais cette loi est un peu plus dure simuler que la premire : chaque lment a une probabilit diffrente de sortir. Tirer "auhasard" ne rendra pas compte de cette loi.

L'approche ici est totalement diffrente. Elle part du cons tat suivant: si on tire un nombre au hasard dans l'intervalle [0;1], ce nombreaura par exemple beaucoup plus de chances de se trouver dans lesous-intervalle [0;0,8] que dans [0,8;1]. De faon gnrale, plus lesous-intervalle sera grand, plus la probabilit de tirer un nombre l'intrieur sera grande.

On peut mme tre plus prcis : la probabilit de tirer un nombre dans le sous-intervalle [a,b] est gale la longueur de ce

dernier, c'est dire (b-a). Et c'est l que va se situer toute l'astuce de la technique : un vnement lmentaire de probabilit p,on as socie un s ous-intervalle de [0,1] de longueur p.

En se dbrouillant pour que les sous-intervalles ne s e chevauchent pas , on aura donc compltement recouvert notre segment[0,1] ! Pour m'assurer que j'avais bien compris, Titi m'a demand de lui faire un dessin ; il fut relativement du de mes talentsartistiques :

Comme vous pouvez le constater, j'ai construit mes sous-intervalles pour coller avec la loi ci-dessus. La partie verte est as socie l'vnement "le 1 sort", la partie violette l'vnement "le 4 sort" , et ainsi de suite. On constate aussi que chaque sous -intervalle a bien la bonne longueur : la partie verte mesure 0.05, la violette 0.6 (=0.8 - 0.2), etc.




22/46

Maintenant, pour s imuler notre machine, il suffira de tirer un nombre au hasard entre 0 et 1. Sa pos ition dans le schma ci-dessusdterminera quelle carte doit sortir : si le nombre est dans la partie bleue, on sortira le 3, s'il est dans la partie rouge, on sortira le6. De cette manire, le 1 et le 2 sortiront avec une probabilit de 0.05 (les longueurs des parties verte et orange), le 3 avec une

probabilit de 0.1, etc. Donc la machine suivra bien la loi que Titi avait choisie !

Certains se demandent peut-tre s'il faut prendre des sous-intervalles ferms ou ouverts (c'est dire, en incluant ou pasles bornes de l'intervalle) ; en thorie, cela n'a en fait aucune importance. Effectivement, la probabilit de tomber dans

un intervalle est gale sa longueur. Ici, la "longueur" d 'un intervalle constitu d'un seul nombre est de 0, et donc laprobabilit de tomber dess us tout pile est galement 0 ! Donc, mme si en pratique le gnrateur alatoire n'est pasparfait, il s'agit d'un vnement qui se produit extrmement peu souvent. En rsum, faites comme vous voulez !

Pour l'implmenter, pas d'astuces : on tire un nombre alatoire xentre 0 et 1. On regarde si xest infrieur la premire valeurdans le tableau ; dans ce cas , on renvoie 1 ; s inon, on regarde s 'il est infrieur la somme des deux premires valeurs du tableauauquel cas on renvoie 2, et ainsi de su ite ...

Hein ? Pourquoi la sommedes deux premires valeurs ? Pourquoi pas la deuxime valeur directement ?

Revenez au petit schma ci-dessus : on veut d'abord s avoir si xest dans la zone verte, donc on le compare 0,05. Aprs, on veutsavoir s'il est dans la zone bleue, autrement d it, s'il est

suprieur 0,05 : de ce ct l, pas de problme, si on arrive cet endroit du code, c'est que xn'est pas infrieur 0,05;

ETinfrieur 0,1 : autrement dit s 'il est infrieur 0,05 + 0,05, ce qui correspond aux 2 premires valeurs du tableau. Sic'est le cas, on renvoie 2.

Et on continue ainsi jusqu' ce que xsoit infrieur la somme de tous les lments parcourus.

Pour faire plaisir Titi, j'ai implment cet algo en C, il fut cette fois trs content du rsultat (pour une fois !) :

Secret (cliquez pour afficher)Code : C

#include #include #include

/* Renvoie un nombre alatoire entre 0 et 1 */doublerand_0_1(){ returnrand()/(double)RAND_MAX; }

/*Gnre un entier entre 1 et taille suivant la loi modlise parle tableau

pass en paramtre */

intalea_perso(doubleloi[], inttaille){inti=0;doublex=rand_0_1();doublesomme=0;/* Dans le premier passage dans la boucle, on testerasi x est infrieur somme, c'est dire loi[0]. Si ce n'est pasle cason relance la boucle : somme vaudra alors loi[0] + loi[1]... et ainsi de suite.*/do{ somme +=loi[i]; i++;}while( somme


23/46

intnb_tirages=0;inti=0;intcarte=0;srand(time(NULL));do{

printf("Combien de tirages voulez-vous effectuer ? "); scanf("%d",&nb_tirages);

}while(nb_tirages 0) return0.05; else return0; /* La numrotation des cartes commence 1, doncla probabilit de tirer un nombre infrieurou gal 0 est nulle ! */}

C'est un peu mieux ... Mais cette fonction ne reprsente absolument pas une loi de probabilit : en additionnant les 20 premiresprobabilits lmentaires, on obtient 1, et si on continue, on dpasse le allgrement ; c'est mme pire que a, vu qu'il y en a unnombre infini, la somme de toutes les probabilits sera ... infinie !

Et prendre une probabilit plus petite ne changera rien, on mettra juste "plus de temps atteindre l'infini".




24/46

Gare celui qui me propose d 'alterner des nombres pos itifs et ngatifs pour faire en sorte que certains termes enannulent d'autres : une probabilit ngative n'a aucun sens !

J'ai alors pens ne mettre une probabilit que sur un nombre fini de cartes, le reste des cartes ayant une probabilit nulle. Ce quicorrespondrait :

Code : C

doubleloi(intn){ if(n>0&&n


25/46

Et donc P({2}) = 1/2 = 1/4. De la mme manire, vous pouvez trouver que P({3}) = 1/2 * 1/2 * 1/2 = 1/23=1/8, P({4})=1/24, ... On

peut alors gnraliser : P({n}) = 1/2n. Nous connaiss ons donc bien notre loi vu que pour chaque vnement lmentaire, on aune probabilit.

Mais avons nous bien une loi ? Autrement dit, la somme de toutes les probabilits lmentaires fait-elle bien 1 ?

La loi du gteau idal

Dj, quel est l'univers des possibles ? Le score du jeu peut tre 1, 2, 3, 42,512, ... en fait, n'importe quel entier positif non nul.Donc on a bien un univers infini.

Et on veut vrifier que la somme des probabilits lmentaires soit gale 1. Autrement dit que :

Vous remarquerez que j'ai utilis cette fois " ..." sans rien mettre derrire ; cela signifie qu'on continue la somme "l'infini". Si j'avais mis "0.1+ 0.2 +0.3 +... + 0.9" cela signifierait que j'ai une somme finie.

Pour m'expliquer ce problme, Titi m'a racont ce qu'il a fait son dernier anniversaire. Comme tous les anniversaires, il y avaitun beau gros gteau, comme on les aime de par chez nous , un gteau " idal" : on peut en couper des parts aus si fines qu'onveut, sans en perdre une miette.

Et Titi a beaucoup de chance, il a beaucoup d'amis. Quand je dis beaucoup, ce n'est pas 10, 100 ou 100 000. Non, beaucoup. Uneinfinit !

Et comme Titi est moiti gnreux, chaque nouvel arrivant, il offrait la moiti restante du gteau. Donc pour le premier invit,le gteau tait entier, il a donn la moiti du gteau ; donc 1/2. Il restait alors la moiti du gteau ; le deuxime invit a donc reula moiti de la moiti, autrement dit un quart (1/4). Et ains i de suite, le troisime a reu 1/8, le quatrime 1/16 ...La ques tion est : quand il aura servi tous ses amis, restera-t-il du gteau pour Titi ?

Pour dj faire le lien avec notre problme, on peut remarquer que la quantit de gteau donne par Titi correspond la sommequi nous intresse.

On remarque immdiatement que cette somme ne dpassera jamais 1 : Titi ne peut pas donner plus de gteau que le gteau luimme ! Et en regardant les images ci-dess us, on voit bien qu' la fin, Titi aura distribu tout le gteau et qu'il n'en aura pas ; pasde chance, il fallait s e servir avant ! Tout a pour dire que la somme qui nous intresse fait bien 1.

Pourquoi n'a-t'il pas la moiti de la dernire part ?

Il y a une infinit d'ami... Du coup, pas de dernire part !

Nous sommes maintenant sr d'avoir affaire une loi de probabilit, on peut maintenant essayer de la simuler !

Une machine rapide !

Maintenant qu'on a une loi, on peut radapter le programme qu'on avait fait pour s imuler ce jeu dans la premire partie. Je vousrappelle la mthode : on tire un nombre x compris entre 0 et 1, puis on regarde dans quelle "zone" il se situe. Ici le dcoupage deszones se fait ainsi :




26/46

Pour "regarder dans quelle zone x se s itue", je vous rappelle (n'hsitez pas relire la premire partie) qu'en gros , on teste s i x estdans la zone "1", puis s'il est dans la zone "2", et ainsi de suite.

Pour appliquer le mme algo, il faut alors dfinir une fonction qui reprsentera notre loi :Code : C

#include doubleloi(intn){ if(n


27/46

,}printf("\n");return0;}

Mais en fait, ce n'es t pas beaucoup mieux que la premire version. Je vous rappelle que dans la premire version, on tirait unnombre 0 ou 1 tant que ce nombre n'tait pas 1 ; donc s i le score valait 5, on avait donc 5 "tours de boucles". Ici, si on regarde dela mme faon le "nombre de tours", on s e rend compte trs vite qu'il est auss i gal au score ; donc niveau efficacit, c'est laloose .

On va donc essayer d'tre plus efficace : on va rflchir pour trouver directement dans quelle zone se situe x sans faire aucuneboucle. Autrement dit, on va chercher une formule mathmatique qui nous donnera la zone directement partir de x.

Pour certaines valeurs , c'est trs facile de d ire " l'il nu" dans quelle rgion est x. Par exemple, si x=0.2, il est clairement dans largion "1" ; si x=0.6, il est dans la rgion "2". Mais si x=0.9876, vous serez bien en peine de me dire - sans calculs ! - dans quellergion es t x ! C'est cette " recherche de zone" que l'on va automatiser dans ce qui suit.

La partie qui su it, mme si explique en dtail, est relativement technique ; savoir ce qu'est une inquation es t fortementrecommand. Si vous voyez que vous ne comprenez rien mon charabia, sautez la formule finale sans tats d'mes.

Pour bien comprendre, mettons que x est dans la zone "3". Regardez le schma au-dessus, cela veut dire que xes t compris entreP({1})+P({2}) et P({1})+P({2})+P({3}). Autrement dit :

On connat trs bien P({1}),P({2}) et P({3}), on peut donc crire :

Mais la zone dans laquelle est x, c'est pas ce qu'on cherche trouver ? On se mord la queue l, non ?

Oui, c'tait un exemple pour bien comprendre la formule que je vais vous balancer. Maintenant, mettons que x est dans la zone"n" (que nous ne connaissons pas); on peut donc crire :

.

Nous avons donc une s uperbe inquation, et le but du jeu, c'est de trouver n(nous connaiss ons dj la valeur de x) !

Dans un premier temps, nous allons trouver une forme plus s ympathique aux gross es s ommes de part et d'autre des ingalits.Vous remarquerez que :

...




28/46

Donc notre gros se ingalit se re-crit : . Ce qui me fait dj beaucoup moins peur. En

enlevant 1 chaque bout, puis en multipliant par (-1) on a (multiplier par un nombre ngatif change le sens d'une ingalit) :

Gloups ... et comment je fais "sauter" la puissance ?

Alors pour faire a, rappelez vous de la faon dont vous faites "s auter" un carr : vous prenez la racine carr !

Mais qu'est-ce que la racine carr ? Vous connaiss ez surement trs bien la fonction "carr" f(x)=x qui a pour effet de multiplier unnombre par lui mme. Eh bien la racine carr est la fonction qui fait le boulot inverse de la fonction carr.

Dans notre cas, nous avons la fonction "puissance de 1/2" ; eh bien il existe une fonction qui fait le boulot

inverse la fonction "puissance de 1/2". Cette fonction s'appelle le logarithme de base 1/2 (videment, s i on considre la fonction

"puissance de a", on aura affaire au " logarithme de base a"). Je le noterai log1/2. Ainsi, on aura :

Vous pouvez remarquer que log1/2est dcroissante, donc quand je l'applique, les ingalits "changent de sens".

Revenons notre calcul, j'applique le log1/2 :

Donc il n'y a plus qu'une seule poss ibilit pour n : c'est l'entier qui est jus te au-dessus (fonction ceilen C) de log1/2(1-x).

Une dernire petite optimisation (c'est vraiment du bout de chandelles ...) : x est un nombre alatoire compris entre 0 et 1 ... c'estauss i le cas de 1-x, donc dans l'argument du log1/2, on peut s e contenter de prendre x au lieu de 1-x.

Dernire note technique : pour calculer log1/2(x) concrtement en C, vous devrez faire le calcul suivant : log(x)/log(0.5)

(en ayant inclus math.hvidemment).

Pfiou, j'ai enfin fini ! Bah ... pourquoi tout le monde est parti ?

La formule finale

Tout ceci nous mne ce superbe rsultat ; pour s avoir dans quelle zone s e situe x, il suffit de faire le calcul :

ceil( log(x) / log(0.5) );

Cela correspond au score que j'ai obtenu au jeu de pile ou face. Il ne me reste p lus qu' l'crire sur une carte !

Tout ce patacaisse pour une pauvre petite malheureuse formule ? Mais qu'est-ce qu'on a gagn ?

Vous avez gagn sur plusieurs points :

efficacit du code : le calcul du log es t trs rapide, optimis par des grosses brutes des mathmatiques, beaucoup plusefficace que notre boucle !simplicit du code : nous n'avons plus besoin de dfinir une fonction "loi" auxiliaire, la s imulation du score s e fait en 1




29/46

ligne (voir code plus loin).vous avez appris quelques techniques mathmatiques qui vous ress erviront peut-tre .

Pour simuler le score ce jeu, il suffit de faire une fonction ressemblant (je vous laisse faire le main qui va autour) :Code : C

intscore_pile_face(){ doublex=rand_0_1(); intscore=ceil(log(x)/log(0.5)); returnscore;}

Que l'on peut condenser en un ligne returnceil(log(rand_0_1())/log(0.5)) . Le simple appel cette fonctionrenverra le score qu'on obtient en jouant ce jeu ; l'entier qu'elle renverra pour donc ne pas tre toujours le mme !

Des variantes

Titi est content, il a sa machine qui lui permet de simuler un jeu infini de cartes ; mais nous pouvons encore trouver d'autres lois.Par exemple, nous pouvons prendre une pice "dsquilibre" qui tombe sur face avec une probabilit de 0,7. Vous pouvez tenterde refaire les calculs ci-dess us pour obtenir une formule pour cette nouvelle machine.

Nous pouvons aus si modifier un peu le jeu : on tire 100 fois pile ou face, et notre score est le nombre de "piles" que nousavons obtenus.

On pourrait faire le mme genre d'tude que juste au-dessus, mais malheureusement, nous ne pourrons pas nous servir dulogarithme, ni d'aucune fonction "simple" pour inverser l'expression que nous allons trouver (Titi a tent de m'expliquer le calcul,

je n'y ai rien compris ...). Le plus efficace es t alors d'appliquer un algo "naf" :Code : Autre

compteur=0faire 100 fois nombre = tirer 0 ou 1 au hasard si nombre = 0 compteur ++afficher compteur

Je l'ai rpt assez de fois, pour avoir une loi, il suffit que la somme des probabilits lmentaires soit gale 1 ; mais, vu qu'il y aune infinit de termes, cela force chacun de ces termes devenir de plus en plus petit.

Pour construire une loi, vous pouvez donc ess ayer de trouver une suite (infinie) de nombres qui tend vers 0 et faire en sorte queleur somme vaille 1 ; le problme n'est pas vident car s i les nombres ne tendent pas "assez vite" vers 0, la somme explose et tendvers l'infini ! Mais comme je suis gentil, je ferai un petit article ce sujet dans pas longtemps...

Nous avons donc rempli not re objectif initial : construire une machine dlivrant une infinit de cartes.

En ralit, pour employer le vocabulaire mathmatique, Titi vous a initi la simulation de "variables alatoires" (que j'avaisappeles "machines" dans le tuto pour ne pas vous surcharger en vocabulaire), et vous a fait dcouvrir une loi bien connue des

probabilistes : la loi gomtrique.

Parfois on parle de "distribution" gomtrique la place de " loi" gomtrique. Ce n'est pas exactement la mme chosemais revient au mme. Vous pouvez donc maintenant comprendre le double sens du titre de ce tuto !

Nous avons aussi effleur le problme de la loi binomiale : il s'agit du jeu o l'on lance 100 fois une pice et o l'on compte lenombre de "faces". Je vous ai dit qu'il n'y avait pas de mthodes "malines" pour s imuler cette loi ; mais lorsque le nombre detirages est grand, on peut approcher la loi binomiale par une autre - la loi de Poisson - qui elle est facile simuler.

Il y a un point que nous n'avons abs olument pas abord dans ce tuto : les lois continues . Effectivement, nous n'avons parl quede lois discrtes (c'est le mot mathmatique pour dsigner ce qui n'est pas continu), or il en existe d'autres ! Prenez par exemple le




30/46

retard de votre bus sur son horaire : l'univers des possibles est [0,+infini[, ce qui est un ensemble infini, mais "beaucoup plusgrand" (et donc compliqu apprhender) que ce que nous avons vu (c'est dire l'ensemble des entiers : {0,1,2,3,...}).

Voici donc ce que vous avez creuser s i le sujet vous intresse... Mais comme vous avez pu le sentir, avant de pouvoir vraimentfaire des probabilits intressantes, il faut d'abord avoir un bagage mathmatique convenable pour pouvoir se dptrerd'ingalits tordues et de sommes gigantes ques !




31/46

Partie 2 : La mthode de Monte Carlo

Avez-vous entendu parler du "Projet Manhattan" ? Non ? Bon, le bombardement de Nagasaki et Hiroshima, peut-tre ? Ah dja vous parle !

Mais quel peut bien tre le rapport entre 2 villes japonaises, un quartier New-yorkais et un quartier de Monaco ?

Hiroshima et Nagasaki ont t bombardes avec des bombes atomiques (a, vous tes senss savoir !) ; bombes atomiques quiont t dveloppes par les amricains la fin de la Seconde Guerre mondiale, dans le cadre du "Projet Manhattan". Projet qui,

pour la premire fois de l'histoire, a utilis mass ivement ces fameuses mthodes dites de Monte Carlo pour effectuer des calculs.

Mais pourquoi Monte Carlo me direz vous ? Eh bien tout simplement car ces mthodes s ont bases s ur la simulation de nombresalatoires ; qui dit "nombre alatoire" dit "hasard", et qui dit "hasard" fait fortement penser aux casinos ... D'o le nom !

Dans cette partie, vous allez donc comprendre comment fonctionnent ces mthodes et quels sont leurs avantages par rapportaux mthodes plus "classiques" ( propos desquelles nous serons obligs de dire quelques mots).

La partie se dcoupe en 3 :

Un premier exemple introductif accessible tout le monde o l'on dcouvre une mthode originale pour calculer pi ;des explications un peu plus thoriques sur la mthode, son utilisation et ses avantages avec des mthodes plus"classiques". Cette section, dcompose en deux chapitres, est un peu plus corse mathmatiquement ; j'ess aierai de larendre accessible tout le monde mais un niveau de seconde (systme franais) me semble un minimum ;un exemple d'application finale utilisant la mthode dcrite prcdemment : le calcul de la valeur du champ lectriqueautour d'une plaque charge ( venir).

Calculons pi !Bon, je t'arrte tout de suite, pi je connais depuis que j'ai 10 ans, a vaut 3.14159... !

Je suis d'accord avec vous ... Mais comment connaissez-vous cette valeur ? Grce la matress e qui vous a demandd'apprendre par cur ce nombre ? Mais cette matresse, comment elle l'a su ? Grce sa propre matresse ?

On voit bien que s i l'on continue le raisonnement, il faut b ien que quelqu'un, un jour, ait trouv cette valeur. Ce calcul a toujourst un grand problme des mathmatiques et plusieurs mthodes ont t imagines ; on peut notamment citer celle d'Archimdedans la Grce antique. Aujourd'hui encore, certains fous furieux tentent de dcouvrir des mthodes encore plus efficaces afin deconnatre encore plus de dcimales.

Ici, nous n'allons rien faire de compliqu, la mthode sera trs simple comprendre (satisfait ou rembours !).

Titi la rescousseUn jeu de flchettes

Je vais vous montrer ici une technique trs simple, tellement simple que c'est Titi, votre petit frre de 3 ans et demi, qui va nousservir de "calculateur". On va demander Titi de jouer un jeu, lui aussi trs s imple, consistant envoyer des flchettes sur lacible reprsente ci-dessous :

Partie 2 : La mthode de Monte Carlo 31/47



32/46

On ne va pas lui demander de viser, il en est incapable ; la flchette doit juste arriver dans le carr. On donne Titi 100 flchetteset on le laisse jouer une heure ou deux. A la fin, la cible ressemblera :

Reflchissons un peu

Voil, le plus gros du travail est fait (pas trs fatigant, et en plus , on a occup Titi tout l'aprs-midi) ! Bon, laissons Titi tranquillepour le moment et commenons rflchir... Lorsque Titi lanait ses flchettes, le jet tait compltement alatoire, donc la

probabilit qu 'elles at terrissent s ur la partie rouge est proportionnelle la surface de cette partie rouge. Cela se comprendintuitivement : plus une partie est grande, plus on a de chance de "tomber" dedans. Plus prcisment, on a :

On cherche connaitrep(vous comprendrez pourquoi dans un instant). Pour cela, rpondons quelques quest ions : commentest constitue la cible ? Rpons e : un quart de disque rouge dans un carr noir. Maintenant, un peu plus dur : Quelle est l'aire dela partie rouge (on cons idre que le carr est de ct 1) ? Vous schez ? Alors prenons calmement : un disque de rayon R a une

surface de . Ici nous avons un quart de disque, donc sa surface est ; etR=1, donc, la surface est de .

La surface totale de la cible est de 1x1=1(c'est un carr de ct 1).

Donc nous avons : .

Mais nous avons un autre moyen d'estimerp. Cette es timation est toute simple, elle consiste cons idrer quepest peu prs

gale au rapport . videmment, plus le nombre de points est important, meilleure sera

cette es timation. En m'amusant compter combien de points sont dans la partie rouge, je trouve : 82. En remplaant dans les

formules trouves plus tt, on a donc : . Une petite manipulation trs simple donne : .

Mais ton rsultat est faux ! Elle n'est pas juste ta mthode !

Je dirais plutt que mon rsultat comporte une erreur ; souvenez vous, on a estimla valeur p comme tant le rapport "nombrede points dans le rouge" /"nombre de points total". Il est donc normal que l'on ait qu'une estimationde pi. Pour rduire l'erreur, ilsuffit d'augmenter le nombre de tirages ; mais malheureusement, Titi est fatigu et ne peut p lus rien faire... Nous allons doncdemander nos ordinateurs de lancer des flchettes notre place.

Un pitre tireur : votre ordinateurNous allons donc implmenter ici un algorithme permettant de reproduire l'exprience que l'on vient de faire avec Titi ;grossirement, il ressemblera ceci :

Code : Autre

initialiser un compteur c 0lancer N flchettes dans un carr de ct 1 : si la flchette est dans le quart de cercle, on augmente le compteur de 1 sinon, on ne fait rien




33/46

on retourne c*4/N

Les s euls points un peu compliqus sont les lignes 2 et 3.

Lancer une flchette

Pour "lancer une flchette dans un carr de ct 1", il suffit de tirer au hasard deux nombres compris entre 0 et 1. Pour a, il fautimplmenter cette fonction partir de rand (rfrez-vous au tutoriel de natimsur le sujet pour tout comprendre) :

Code : C

doublerand_0_1(void){ returnrand()/(double)RAND_MAX;}

Maintenant, pour tirer effectivement notre flchette, c'est tout simple :Code : C

doublex =rand_0_1();doubley =rand_0_1();

Les variablesxetycontiennent alors respectivement l'abciss e et l'ordonne de la flchette.

Sommes-nous dans le disque ?

Pour rpondre cette ques tion, il suffit de dfinirprcisment ce qu'est un d isque de rayon 1et de centreO. On peut prendre la dfinition suivante :

Un disque de rayon 1 et de centre O est l'ensemble des

points M tels que la distance OM soit infrieure ou

gale 1.

Pour mieux comprendre cette dfinition un peu abstraite,

un petit exemple : prenons le pointM(0.5,0.2) ;Mes t-ildans le cercle ?

Pour rpondre, utilisons la dfinition : il faut que. Pour s implifier les calculs, prenons le carr

de cette ingalit : .

Or d'aprs notre cher Pythagore :MO = (0.5-0)+(0.2-0) = 0.5 + 0.2 = 0.25 + 0.04 = 0.29 .

0.29est bien infrieur 1doncMest dans le disque.

Donc dans notre problme, la condition "le point (x,y) est dans le disque"s 'exprimera :Code : C

( x*x +y*y )


34/46

Vous avez maintenant tous les ingrdients pour implmenter l'algorithme. Je vous propose donc de faire un programme quidemande l'utilisateur combien de lancers il veut faire, puis qui affiche une valeur approche de pi.

Voici un programme possible :Secret (cliquez pour afficher)

Code : C

#include #include #include

doublerand_0_1(void){returnrand()/(double) RAND_MAX;}

intmain(intargc, char*argv[]){

unsignedintn=0; // le nombre de jetsunsignedintcompteur=0; // le compteur de flechettes dans lacibleunsignedinti=0; // le compteur de boucledoublex,y;doublepi;printf("Combien de jets voulez vous effectuer ? ");scanf("%d",&n);printf("Simulation en cours, cela peut prendre quelques minutes

... \n");

for(i=0; i


35/46

Grce cette formule, en s'arrtant n = 100, on a 3.1302 comme valeur de pi, puis avec n = 3000, on obtient 3.14127, et les tempsde calcul restent imperceptibles s ur un ordinateur actuel. Monte Carlo es t donc largement dpass, d'autant qu'il existe d'autresformules donnant pi encore plus rapidement. Ceci tant, personne n'aurait le courage (moi y compris) de justifier et d'expliquerces mthodes sur le SdZ. Justifier Monte Carlo est relativement simple (du moins dans l'ide), et c'est cette simplicit qui va treun des atouts de cette mthode.

Cette simplicit de l'algorithme a son importance, car mme si les mthodes classiques sont plus performantes, il vaut mieuxpasser 4 heures de moins coder plut t que gagner 3 minutes l'excution. Ce qui compte c'est la rapidit (temps de codagecompris) avec laquelle on obtient le rsultat (videment cette remarque n'a aucun sens dans un contexte "temps rel").

Mais une mthode n'est en gnral pas choisie uniquement pour sa simplicit, mais aussi pour son efficacit. Ici, le problmetait en ralit trop simple pour qu'il soit intressant d 'y appliquer cette mthode. Pour faire une analogie avec le bricolage : pourvisser des grosses vis, vous prenez un gros tournevis ; si vous prenez le mme tournevis pour des toutes petites vis, vous allezavoir beaucoup de mal et ne serez pas trs efficace. C'est exactement le mme problme ici : Monte Carlo est un trs grostournevis, et pi, une toute petit vis !

Nous allons donc voir dans quels cas les mthodes "class iques" (des PMT : Petits et Moyens Tournevis) ne peuvent pasrsoudre efficacement un problme et donc dans quels cas nous devrons utiliser Monte Carlo. Mais pour cela, il faut comprendrecomment fonctionnent ces mthodes "classiques" !




36/46

Savez-vous intgrer ?Nous l'avons vu dans le chapitre prcdent, les mthodes de Monte Carlo peuvent s ervir calculer des surfaces (il existed'autres mthodes dites de "Monte Carlo" dont je ne parlerai pas ici). En ralit, nous avons calcul ce qu'on appelle uneintgrale... Non, ne partez pas ! Bon tant pis, je continue tout seul. Mais qu'est-ce qu'une intgrale ?

Nous allons voir donc dans cette partie ce qu'est une intgrale, une mthode "classique" de calcul d'une intgrale, puis un calcul

par Monte Carlo. Cela nous permettra de comparer les deux mthodes.

Pour aborder ce tutoriel tranquillement, vous devez parfaitement maitriser les notions de fonction et de reprsentation d'unefonction.

Ce chapitre renvoie d 'autres articles du Web (notamment un tu toriel du SdZ) ou techniques mathmatiques .Cependant, le tutoriel a t pens pour se suffire lui-mme. Admettez donc les choses en premire lecture pour ne pasvous embrouiller ; mais plus tard, n'hsitez pas suivre les liens ou faire des recherches sur les sujets vous intressant.

Dfinissons les choses

De faon simple, l'intgrale d'une fonction positivefentre deux points aet bpeut-tre vue comme la surface sous la courbe reprsentantfentrex=aet

x=b. On note cette surface : (lire : "l'intgrale defentre aet

b" ; on dira auss i que l'on "intgrefsur l'intervalle [a,b]"). Sur l'image dedroite, la partie rose s aumon correspond l'intgrale de 1 4 de la fonction

f(x) = x3-5x2+20 reprsente en bleu. Dans ce cas, on note alors :

.

En Terminale, on utilise plus la notation : . Cela revient

exactement au mme, mais lorsque nous verrons les intgrales doubles un peu plus loin, cette notation ne sera pas trscommode utiliser.

Mais si la fonction es t ngative, ce n'est pas dfini ?

Si, mais cela ne nous sera pas utile pour ce tu toriel. Si vous voulez en s avoir plus, so it vous attendez patiemment la Terminale,soit vous vous renseignez sur Wikiversit. Sachez tout de mme que tout ce je vais dire par la suite est vrai quel que soit le signedef.

Revenons maintenant la notation . Elle va nous aider mieux cerner le problme. Le dxreprsente une variation

infinitsimale (=infiniment petite) de x. L'ide est de considrer que s ur un intervalle [x,x+dx]la fonction est cons tante (vu quec'est un intervalle infiniment petit, a se comprend). Dans c

Documents

A La Des Decouverte de l'Aleatoire Et Des Probabilites