Laurent s'occupe de distribuer le courrier dans les bureaux d'une grande entreprise.
Le graphe ci-dessous représente les différents parcours qu'il peut faire pour distribuer le courrier dans les bureaux A, B, C, D, E, F et G. Le poids de chaque arête indique le nombre d'obstacles (portes, escaliers, machines à café…) qui nuisent à la distribution du courrier.
Laurent se voit confier par le bureau A un colis à livrer au bureau G. Indiquer un parcours qui permette à Laurent de partir du bureau A pour arriver au bureau G en rencontrant le minimum d'obstacles.
Pour déterminer le parours comportant un minimum d'obstacles, pour aller de A à G, on utilise l'algorithme de Dijkstra.
A | B | C | D | E | F | G | Sommet sélectionné |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
5 (A) | ∞ | 10 (A) | 6(A) | ∞ | ∞ | B (5) | |
10 (B) | 10 (A) | 6 (A) | ∞ | ∞ | E (6) | ||
10 (B) | 9 (E) | 11(E) | ∞ | D (9) | |||
10 (B) | 10(D) | 13(D) | C (10) | ||||
10(D) | 13(D) | E (10) | |||||
12 (F) | G (12) |
Le sommet G étant marqué, pour lire la chaîne de poids minimal, on part de G et on "remonte" la chaîne en suivant les prédécesseurs. .
Le parcours qui permette à Laurent de partir du bureau A pour arriver au bureau G en rencontrant le minimum d'obstacles est A-E-D-F-G. (Laurent rencontre 12 obstacles).
Pris par le temps, il n'est pas rare de voir Laurent oublier de livrer le courrier du matin !
On considère que :
Le lundi matin 1er octobre, Laurent a bien distribué le courrier. On note la probabilité que Laurent distribue le courrier le n-ième jour de travail (on considère donc que le lundi 1er octobre est le premier jour et que ).
Traduire les données de cet exercice à l'aide d'un graphe probabiliste. Préciser la matrice de transition associée à ce graphe.
Notons A l'état : « Laurent a distribué le courrier » et B l'état : « Laurent a oublié de distribuer le courrier ».
Le graphe probabiliste qui représente la situation est : | |
La matrice de transition associée est |
Démontrer que, pour tout , on a : .
Soit (avec ) la matrice ligne décrivant l'état probabiliste le n-ième jour. Alors,
D'où avec . Soit
Ainsi, pour tout , on a .
On considère la suite définie, pour tout , par .
Démontrer que la suite est une suite géométrique de raison 0,5. Calculer son premier terme.
Pour tout ,
Ainsi, pour tout entier naturel , . Donc la suite est une suite géométrique de raison 0,5.
Le terme initial de la suite est :
La suite est une suite géométrique de raison 0,5 et de premier terme 0,6.
En déduire, pour tout , la valeur de en fonction de n.
est une suite géométrique de raison 0,5 et de premier terme 0,6, alors pour tout entier naturel ,
Soit pour tout entier naturel ,
Ainsi, pour tout entier naturel , .
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.