Chapitre 3 Graphes pondérés et probabilistes.pdf


Aperçu du fichier PDF chapitre-3-graphes-ponderes-et-probabilistes.pdf - page 3/12

Page 1 2 3 4 5 6 7 8 9 10 11 12



Aperçu texte


Problème

1.

3 L’allumeur de réverbères

L’objectif de ce problème est d’introduire la notion de graphe
probabiliste et aussi de matrice de transition d’un graphe
probabiliste. En fin de problème, on donne l’intuition de l’existence
possible d’un état stable.
1.
Jour 0
Jour 1
Jour 2
0,25 A
A

0,75
E
0,25

0,75

B

0,75

A
B

E

 0, 484375 0,515625 
5. M5 = 
 0,515625 0, 484375 
 0,5005 0, 4995 
M10 ≈ 
à 10–4 près.
 0, 4995 0,5005 

( 0,3875

0, 6125 )

=

On conjecture une stabilisation de l’état probabiliste autour
de P = ( 0, 8 0,2 ) .

 0,5 0,5 
≈ 
à 10–4 près.
 0,5 0,5 

6. Sur un grand nombre de jours, le réverbère est allumé un
jour sur deux en moyenne.

Problème

P0M2
P0M5

4. Le coefficient à l’intersection de la première ligne et de la
première colonne est la probabilité de passer de l’état A à l’état
A, celui à l’intersection de la première ligne et de la deuxième
colonne est la probabilité de passer de l’état A à l’état E, etc.

M15

Y

( 0, 490625 0,509375 )
P5 =
≈ ( 0, 67 0,33 )
P10 = P0M10 ≈ ( 0,77 0,23 )
7. P1 = P0M = ( 0, 45 0,55 )
P2 = P0M2 = ( 0,5375 0, 4625 )
P5 = P0M5 ≈ ( 0, 69 0,31 )
P10 = P0M10 ≈ ( 0,77 0,23 )
puis : P1 = P0M = ( 0,7 0,3 )
P2 = P0M2 = ( 0,725 0,275 )
P5 = P0M5 ≈ ( 0,768 0,232 )
P10 = P0M10 ≈ ( 0,79 0,21 )
P2 =

0,75

0,20

 0,95 0, 05 
2. M = 
 
 0,2 0, 8 
3. Pn+1 = PnM
4. Pn = P0Mn

6. P1 = P0M =

2. P (A) = 0,25 × 0,75 + 0,75 × 0,25 = 0,375
3.
0,75
0,25
A
0,25

0,95

0,80

5. P0 =  1 3 
 4 4 

E
0,25

0,05

X

4 Transferts de population

L’objectif de ce problème est de réaliser un calcul d’état stable
d’un graphe probabiliste via un système, et également d’utiliser
la calculatrice pour des calculs d’états probabilistes.

8. Soit P = ( a b ) avec a + b = 1.
P = PM équivaut à :

⎧ 0,95a + 0,2b = a
⎨ 0,05a + 0,8b = b ⇔ 0,05a = 0,2b ⇔ a = 4b .

Par substitution, a = 4 et b = 1 .
5
5
Ce sont les valeurs vers lesquelles l’état probabiliste semble
tendre.

E Exercices
POUR DÉMARrER
1   1. Il y a une unique arête d’origine le sommet vert et
d’extrémité le sommet rouge. Cette arête est étiquetée d’un Y.
Y est donc le seul mot reconnu par le graphe.
2. En partant du sommet vert, puis en empruntant deux fois la
boucle étiquetée d’un X et en finissant par l’arête étiquetée Y
arrivant au sommet rouge, on crée une chaîne montrant que
le mot XXY est reconnu.
3. Les mots reconnus par ce graphe sont constituées d’un
nombre quelconque de X (éventuellement nul) suivis d’un Y.

2   1. La chaîne CAT est bien une chaîne du graphe, partant
du sommet vert et aboutissant au sommet rouge : ce mot est
reconnu par le graphe.
2. HAT n’est pas une chaîne orientée du graphe, et ne peut
donc pas être un mot reconnu par ce graphe.
3   Voir livre page 95.
4   Voir livre page 95.
5   1. La chaîne de poids minimal reliant A à E est ABE pour
un poids total de 4.
2. AECDE est la chaîne de poids maximal reliant A à E et ne
comportant que des arêtes distinctes avec un poids de 12.

Chapitre 3 Graphes pondérés et probabilistes – Term ES spécialité

119