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


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

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




Aperçu texte


chapitre

3

Graphes pondérés
et probabilistes

A Le programme
L’enseignement de spécialité prend appui sur la résolution de problèmes. (…)
Les graphes probabilistes permettent d’étudier des phénomènes d’évolution simples et de faire un lien avec les suites. (…)
Exemples de problèmes

Contenus

Codage par un graphe étiqueté, applications à l’accès à un réseau
informatique, reconnaissance de codes.
Minimisation d’une grandeur (coût, longueur,
durée, etc.).
Phénomènes évolutifs (variation d’une population, propagation
d’une rumeur ou d’un virus, etc.).

Recherche du plus court chemin sur un graphe pondéré
connexe.

Graphe probabiliste à deux ou trois sommets : matrice de
transition, état stable d’un graphe probabiliste.

B Notre point de vue
Ce chapitre est également axé sur la résolution de problèmes. Il s’articule en deux séquences.
La première partie, consacrée aux graphes pondérés est composée de deux problèmes permettant d’introduire les
graphes étiquetés, puis les graphes pondérés :
Avec un ordinateur traite tout ce qui est autour de la reconnaissance de codes, avec un approfondissement sur les
automates ;
Itinéraire routier a pour objectifs principaux la découverte des graphes pondérés, la notion de plus courte chaîne et
la mise en œuvre de l’algorithme de Dijkstra.
La seconde partie est dédiée aux graphes probabilistes : L’allumeur de réverbères est un problème dont l’objectif est
l’introduction d’un graphe probabiliste et de sa matrice de transition, mais aussi l’utilisation de la calculatrice pour
conjecturer l’existence d’un état stable. Transferts de population est un problème classique de graphe probabiliste à
deux états, où on calcule un état stable en résolvant l’équation P = PM.
Ce chapitre fait la part belle à l’algorithmique avec l’algorithme de Dijkstra (souvent présenté sous forme de tableau).
La calculatrice y est également indispensable afin de calculer rapidement des états probabilistes à un rang donné.
Les travaux pratiques sont quant à eux consacrés à l’algorithme PageRank et à l’utilisation du tableur pour réaliser des
simulations de marches sur un graphe probabiliste à deux états et, plus précisément, pour évaluer des temps d’attente
de retour à un état donné.

  Les notions abordées dans le chapitre 3  
1. Graphes étiquetés et pondérés
2. Graphes probabilistes

C Avant de commencer
Voir livre page 95 et le site www.bordas-indice.fr pour les corrigés détaillés.
Chapitre 3 Graphes pondérés et probabilistes – Term ES spécialité

117