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


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

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




Aperçu texte


D Problèmes
L’objectif de ce problème est de découvrir et d’utiliser les graphes
étiquetés, spécialement dans le but de reconnaître des codes. Ce
problème se divise en deux parties, la première étant proposée
pour acquérir les compétences du programme, la seconde
constituant un élargissement de ce domaine.
Partie A. Reconnaissance de codes
sur un écran informatique
1. Oui.
2. Il y en a 6 : DACF, DECF, DCIF, DBIF, DEBF et DABF.

3. M = 


0
0
0
0

1
2
0
0

0
2
1
0

2 Itinéraire routier

Les objectifs de ce problème sont de découvrir les graphes
pondérés, la notion de plus courte chaîne et aussi l’algorithme de
Dijkstra. La fin du problème constitue une première application
de cet algorithme.
Lettre autre que M

M

Mâcon

Roanne

125

73

86

Lyon

Clermont-Ferrand

63

147

Saint-Étienne

Moulins

107
94

79
Clermont-Ferrand
88

Mâcon

Roanne

52

86

Lyon
48

Saint-Étienne
2. En observant le second graphe, Camille va choisir Lyon –
Mâcon – Moulins.
3. En observant le premier graphe, Camille va choisir Moulins –
Roanne – Lyon.
4. Sylvain fera un kilomètre de moins en passant par SaintEtienne, et mettra surtout 29 minutes de moins en choisissant
cet itinéraire !
Il choisira donc Clermont-Ferrand – Saint-Étienne – Lyon.
5. On a la liste suivante : Clermont-Ferrand (210), Mâcon (73)
et Roanne (86).
Depuis Mâcon, Moulins seule est accessible. On obtient  :
Clermont-Ferrand (210), Moulins (214) et Roanne (86).
Reprenons le raisonnement depuis Roanne. Clermont-Ferrand
est une ville adjacente, mais avec 125 kilomètres, ce qui fait un
total de 211, ce qui est moins intéressant que précédemment.
Moulins est accessible avec 98 km, donc un total de 184 km.
On obtient donc : Moulins (184), Clermont-Ferrand (210).
Enfin, depuis Clermont-Ferrand, Moulins est accessible mais
avec bien trop de kilomètres.
On trouve ainsi le chemin le plus court reliant Lyon à Mâcon.

M

M

A

M

MA

Lettre autre que M ou A
Lettre autre que M
Lettre autre que A ou M
Lettre autre que M ou N

118

98

103

83

 0 1 0 0
 0 34 21 8 
5 = 8.
M =  0 2 1 0  ; M5 =  0 89 55 21  donc M1,4
0 1 1 1
0 55 34 13




0 0 0 0
0 0 0 0
Il y a donc 8 chemins de longueur 5 reliant le premier au dernier
sommet.
Partie B. Recherche d’un mot dans un texte
Voir schéma en bas de page. Cet automate reconnaît le mot
« MAMAN » dans un texte quelconque composé de caractères
parmi les lettres de l’alphabet.

Départ

141

0
0
1

0

 0 16 30 14 
5 = 14.
4. M5 =  0 32 62 30  donc M1,4
0 0 1 1


0 0 0 0
Il y a donc 14 chemins de longueur 5 reliant le premier au
dernier sommet.
5. DECIF est reconnu mais pas DAAEEBIIF.
Il y a trois mots de longueur 4 : DACF, DECF et DCIF.

Problème

Moulins

1.

1 Avec un ordinateur

Problème

M

A
MAM

MAMA
M

N

MAMAN