Université de Bejaia.

Faculté des Sciences Exactes.

Département Informatique

Cours
Programmation Avancée

Master 1 en Informatique
Options : ASR, IA et GL

Prof. BOUALLOUCHE Louiza

1
 Chap. 6 La programmation
stochastique

6.1 Introduction à la programmation Stochastique

Les algorithmes classiques font objet de processus de calcul
déterministes. Avec les mêmes données, un algorithme exécutera
toujours la même suite d'opérations. Cependant, pour un
algorithme stochastique ou non-déterministe, deux exécutions
différentes pourraient réaliser des choix différents. Une façon de
réaliser ce choix est de les rendre aléatoires. Il y a plusieurs
usages :
2
 Les algorithmes numériques simulent une variable de loi uniforme, afin
d'obtenir une approximation numérique de la solution du problème (qui
pourraient être obtenue par un algorithme déterministe).

• Les algorithmes de Monte Carlo peuvent produire une solution

incorrecte en un temps déterministe, avec une probabilité d'erreur qui
peut être réduite de manière arbitraire en répétant l'algorithme.

 Les algorithmes de Las Vegas ne se terminent pas nécessairement mais

calculent toujours une solution correcte quand ils terminent le temps
d'exécution étant aléatoire.

 Enfin, les algorithmes de randomisation qui garantissent une complexité

moyenne.
 6.2 Générateurs de nombres pseudo-aléatoires
Un GNA est un algorithme implémenté par une fonction qui retourne à chaque
invocation une nouvelle valeur numérique et telle que la suite de valeurs retournées
ait de bonnes propriétés statistiques. Celles-ci permettent de supposer qu'il s'agit
d'une suite de valeurs aléatoires indépendantes de loi uniforme dans un intervalle
spécifié.
Ces nombres sont utilisés dans deux situations :
 Pour évaluer les performances d’un système (Temps de réponse, Débit en sortie,
Taux d’utilisation, …).
 Pour tester un programme quelconque, en lui soumettant comme données des
"jeux de données" générées aléatoirement et en comparant le résultat calculé au
résultat attendu.
 Pour implémenter des algorithmes stochastiques, soit pour des problèmes
numériques (intégration), soit pour améliorer le comportement d'algorithme par
randomisation, soit pour donner un résultat avec un problème d'erreur (test de
primalité) ou pour briser des symétries (élection d’un chef), par obstination.
La conception d'un générateur de nombres pseudo-aléatoires est délicate. En effet, il est souvent difficile
d'échapper à des régularités arithmétiques qui s'opposent à l'uniformité souhaitée.

En pratique, on fait souvent appel à des générateurs fournis dans les

bibliothèques standards.
La fonction de l'API Java [Link]() retourne un n.a U[0, 1[. Les nombres
aléatoires les plus utilisés sont ces derniers.

Pour obtenir un entier dans l'intervalle [a, b[, on pourra définir la fonction :

static int irand(int a, int b) {

return a + (int)([Link]() * (b - a + 1));
}

Il existe plusieurs techniques de génération de n.a (v.a variables aléatoires).

• La technique d'inversion
• La technique de composition
• La technique de rejet
• etc.

En fait, il s’agit d’engendrer une variable aléatoire (v.a.) X suivant une certaine loi à
partir des lois plus simples (loi uniforme) et en se basant sur des techniques connues.
 6.2.1 Technique d’inversion ou Transformation inverse

Cette technique permet de générer des valeurs de X de fonction de répartition

F(x) désirée (continue et strictement croissante).

Il s’agit de générer un nombre aléatoire uniforme U(U € U[0, 1] ) puis de

calculer

En effet, la dernière égalité provient de l’uniformité de U.

 Fonction de génération par la transformation Inverse

Supposons que l’on dispose d’une fonction Uniforme() ([Link]() en Java) qui
génère des nombres U[0, 1[ (telle que [Link]() de l’API java).

Et soit

Algorithme qui génère une de X de fonction de répartition F(x).

type function generer () ;

{
U=uniforme() ;
X=Finv(U) ;
return X;
}
Exemple

Soit X une v.a suivant une loi exponentielle :

La fonction de répartition de X

real function generer-Exp();

{
X= - ln (Uniforme ( ) ) / lambda; / *U et 1-U même fonction-répartition
Return X
}

Si X = durée de traitement d’une tâche,

h[i] : l’instant de fin de traitement de la tâche i.
On pourrait connaître la séquence des instants de fin de traitement des tâches

h[i]= h[i -1] + generer-Exp()

6.2.2 Méthode de Convolution

Cette méthode s’applique lorsque la v.a. X est la somme de plusieurs variables

données.

Exemple.
Soit
Où
Schématiquement, X est représentée par k serveurs fictifs en série

Loi Erlang-k
6.2.3 Génération de v.a discrètes

Soit X une v.a. discrète prenant l’ensemble fini de valeurs x1, x2, ...,xk.

Aiguillage probabiliste à k sorties

6.2.4 Méthode de génération d’une sortie dans l’aiguillage
probabiliste

On cumule les probabilités , et on obtient

Int function aiguillage () ;

{ j=1; U= Uniforme();
While U > Pc [ j ]
j++;
return j; /* X = x [ j ]
}
Exemple P
X=1

Soit X une v.a suivant une loi Bernoulli(p) définie par 1-P
P1=Pr(X=1)=p et P2=Pr(X=0)=1-p. X=0

On réalise un aiguillage à 2 sorties.

Int function Bernoulli () ;

{ if Uniforme() ≤ p then return 1 else return 0;

}

Application
Soit X une v.a suivant une loi de Poisson définie par

NB.
Il est important de calculer les Pk et de limiter l’ensemble des valeurs de X d’une
manière efficace
6.2.4 Méthode de composition

Générer X selon F1(x) ( f1(x))

P1

P2 Générer X selon F2(x) ( f2(x))

P3

Générer X selon Fi(x) ( fi(x))

Pn

Générer X selon Fn(x) ( fn(x))

6.2.5 Génération par des méthodes mixtes

≡ Combinaison des méthodes simples (connues) et de l’aiguillage

probabiliste Lois Sophistiquées.

Exemples très simples (vus en cours) :

1° loi Erlangk (voir méthode de convolution), où on a k serveurs fictifs en série,
2° loi hyper-exponentiellek (voir méthode de composition).

Exemple de loi plus sophistiquée : loi Coxk, dont chaque serveur est
exponentiel et schématisée comme suit :
 real function coxk () ;

{ j=1; X=-ln(Uniforme()) / lambda[1];

while ( Uniforme() ≤ P[ j ] )
{ X = X - ln(Uniforme()) / lambda[j] ;
j++;
}

Return X ;
}

NB. On met Pk = −1 et on éviterait ainsi le test sur le nombre d’´etapes.

 6.2.6 Méthode de rejet (ou d’acceptation)

Soit à générer une v.a. X de densité f(x) bornée (f(x) ≤ B pour

tout X)

Si f(x) ≠ 0, a < x ≤ b, on peut faire ce changement de variable

Générer (x, f(x) ) revient à générer (y, f*(y) )

La méthode est :

• générer U1, U2 € U[0,1]

• si U2 ≤ f*(U1) on accepte le couple et donc y = U1 ou x=a+U1*(b-a)
 Fonction de génération par rejet

real function rejet () ;

{ Do
U1 = Uniforme() ; U1= (Uniforme();

While ( U2 > f*(U1) )

X = a + U1*(b-a) ;

Return X ;

}
6.3 Méthode de Monté Carlo
6.3.1 Introduction et Définition
La méthode de Monte Carlo est une approche numérique qui
repose sur l’utilisation de variables aléatoires pour
approximer des solutions à des problèmes complexes. Elle est
particulièrement utile dans des situations où une solution
exacte est difficile à obtenir, comme dans le calcul d'intégrales
de haute dimension, la simulation de systèmes physiques, ou
l'optimisation stochastique. Développée initialement dans le
cadre de la recherche nucléaire pendant la Seconde Guerre
mondiale, elle a rapidement démontré son potentiel dans
divers domaines scientifiques et technologiques.
• Les principes fondamentaux sont les suivants
• Génération aléatoire : La méthode repose sur la
génération d'échantillons aléatoires provenant d'une
distribution donnée.
• Estimation par moyennes : Les résultats sont obtenus
en utilisant des statistiques d’échantillons pour estimer
la quantité recherchée.
• Convergence statistique : Grâce à la loi des grands
nombres, les résultats obtenus deviennent plus précis à
mesure que le nombre d’échantillons augmente.
6.3.2 Contribution des avancées technologiques et domaines
d’application
L’émergence de puissants ordinateurs a considérablement renforcé l’efficacité et
l’applicabilité de la méthode de Monte Carlo. La disponibilité d'une grande puissance
de calcul permet aujourd'hui de traiter des simulations massives en un temps
raisonnable, rendant ces méthodes opérationnelles dans des domaines où les calculs
étaient auparavant inaccessibles. La méthode de Monte Carlo s’impose aujourd’hui
comme une approche incontournable dans de nombreux secteurs scientifiques et
technologiques :
• Finance : Évaluation des options et gestion des risques.
• Mathématiques : Approximation d’intégrales complexes ou résolution de
problèmes d’analyse.
• Physique : Simulation des systèmes de particules ou des phénomènes
thermodynamiques.
• Biologie moléculaire et génétique : Étude des interactions moléculaires et
simulations génétiques.
• Télécommunications et réseaux : Optimisation des flux et des ressources.
• Recherche opérationnelle : Résolution de problèmes d’optimisation stochastique.
• Industrie 4.0 : Planification et contrôle des systèmes intelligents.
Les progrès dans les architectures matérielles, comme le calcul
parallèle et l’utilisation des GPU, ont permis d’accélérer
considérablement les simulations Monte Carlo. De plus,
l’intégration avec l’intelligence artificielle et le machine learning
ouvre de nouvelles perspectives, en permettant d’explorer des
espaces de solutions plus vastes de manière efficace.
 6.3.3 Méthode d’application

Une des approches pour calculer une certaine quantité à l'aide de la

méthode de Monte Carlo consiste à exprimer cette quantité sous la forme
d'une espérance mathématique. Une fois cette reformulation effectuée, il
s'agit de calculer l'espérance E(X) d'une variable aléatoire X. Pour cela, il
est essentiel de savoir simuler X suivant sa loi de probabilité. On génère
alors une suite (Xi)1≤ i ≤ N de N réalisations de la variable aléatoire X, puis
on approxime alors E(X) par :

1
E(X) ≈ (𝑋1 + ⋯ + 𝑋𝑁 )
𝑁
 6.3.4 Application au calcul d’intégrales
Le calcul d’une intégrale définie sur un domaine complexe est l’un des exemples
classiques de la méthode de Monte Carlo. Supposons qu’on veuille calculer :
𝑏
I = ‫𝑥𝑑 𝑥 𝑓 𝑎׬‬

Faisons un changement de variables

𝑥−𝑎 1 1
= 𝑡 ⋴ [0. 1] I = ‫׬‬0 𝑓 𝑎 + 𝑏 − 𝑎 𝑡 𝑏 − 𝑎 𝑑𝑡 = ‫׬‬0 𝑔 𝑡 𝑑𝑡
𝑏−𝑎

Soit M = max | 𝑔 𝑡 | et U = max (1, M) et ℎ 𝑡 = 𝑔 𝑡 /𝑈

1
𝑆
= න ℎ 𝑡 𝑑𝑡 → ℎ 𝑡 <
𝑈 0

La méthode de Monte Carlo consiste à

 Générer N points ξ 𝑖 𝑢𝑛𝑖𝑓𝑜𝑟𝑚é𝑚𝑒𝑛𝑡 𝑒𝑛𝑡𝑟𝑒 0 𝑒𝑡 1 (i = 1. 2. …, N)
1
 Approcher l’intégrale ‫׬‬0 ℎ 𝑡 𝑑𝑡 par
1 σℎ ξ𝑖
‫׬‬0 ℎ 𝑡 𝑑𝑡 = 𝑁
les ξ 𝑖 𝑠𝑜𝑛𝑡 𝑔é𝑛é𝑟é𝑠 𝑢𝑛𝑖𝑓𝑜𝑟𝑚é𝑚𝑒𝑛𝑡 𝑒𝑛𝑡𝑟𝑒 0 𝑒𝑡 1
Erreur et convergence :
o L'erreur associée à cette méthode décroît selon un ordre de grandeur
O(1/ 𝑁), et ce, quel que soit le nombre de dimensions considérées.
o Cela rend Monte Carlo compétitif pour les intégrales de haute
dimension où les méthodes classiques, comme les quadratures,
deviennent inefficaces.
Exemple simple : Calcul de π
1 1 1
π = 4 ‫׬‬0 𝑑𝑥 ℎ 𝑡 =
1+𝑥 2 1+𝑡 2

Fonction Pi() : réel

Début
S←0;
Pour I allant de 1 à 800 Faire
U ← Random(); //* Générer un nombre aléatoire entre 0 et 1
S ← S + 1 / (1 + U*U); //* Ajouter h(U) à la somme
Fin Pour
S ← S /800; // Moyenne des valeurs
Return 4*S; // Approximation de π
Fin