Résolution de problèmes à l'aide de graphe (II) Cours 3

Etudiez les devoirs et les activités 2009/2010 pour la classe de terminale ES.
Publié le : jeudi 1 janvier 2009
Lecture(s) : 59
Source : sarmate.free.fr
Nombre de pages : 7
Voir plus Voir moins

T ES
...........................
...............
...............
.......................................
trouv
er.
Comme
a
de
ts
nous
parmi
en
don
a
livreur
v
ar?tes
ons
plus
l'habitude,
passan
il

est
oser
ais?
un
de
est
remarquer

que
une
de
p
telles
?
situations
ts
p
son
euv
ositifs.
en
el?s
t
parcours
se
.
ramener
esoin
?
nom
l'?tude
p
d'un
osen
graphe.
tre
Les
qui
math?maticiens
Dans
et

informaticiens
I)
on
de
t
4
prop

os?
un
div
les
erses
aect?es
m?tho
ts
des

(ou
t
algorithmes)
ses
p
doit
our
pizzas,
r?soudre
hemin.
le

probl?me
trouv
du
ons
plus
situations



somme
hemin.
ts
Une
la
des
Une
solutions
haine
les
sommets
plus


relien
est
ha?ne
un

algorithme
he
qui
?s
p
aphes
orte
(partie
le
?
nom
graphes
de
de
son
Sp
in
en
v
la
en
est
teur,
graphe
l'informaticien
t
n?erlandais
ar?tes
Edsger
t
Dijkstra
de
et

a
p
?t?
Ces
publi?

en
son
1959.
app
Mais

a
?
v
prop
an
que
?
aux
solution
de
Exemple
Du
V

un
Le
p
plus
A
er
E
de
B
b
3
v
1
nous
5
breuses
1
d'une
3
haine
de
la
nouv
des
elles
oin
notions.
des
1.1
qui
D?nitions

D?nition
t.
1
plus
Gr

aphe
en
p
deux
ond?r
est,
?
les
Un
ha?nes
dit
les
probl?me
t,
dit

qui
de
Et
hemin
ts.

fr?quen
d'un
plus
herc
des
1
est
ond?r
probl?me
orient?s,

Gr
ternet,
I
in
graphes
sur
l'aide
donn?es
probl?mes
des
R?solution
mission
l'aide
trans-
probl?mes
la
R?solution
par
?cialit?
t
t
Cours
d'?tudier

1
algorithme

nous
graphe
a
ond?r?.
v
C
ons
S
b
D
esoin,
3

1
toujours,
3
de
1
d?nir
1E S
1 ◦


2 ◦ X
◦ X
3 ◦ Y X p
X X Y
◦ p Y
p Y ◦
Y
4 ◦

5
E A B C D S
∞ ∞ ∞ ∞ ∞ E
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
sous
vide
P
Sommet
allons
l'on
our
d'un

l'algorithme
haque
es
sommet
Sommet

?

de
t
plus
?
jusqu'au
la
:
,
le

?crire
la
sommets
somme
de
er
derni?re
en
0
tre
graphe
le


et

V
t
our
de
?rer
y
sous
et
de
du
t
p
2?me
oids
dans
de
Sommet
l'ar?te
Etap
relian
fur
t
les
ra
des
?
ligne
et
tableau,
.

ligne
les
Si
le
elle
Dijkstra
est
vien

de
t
de
inf?rieur
les
au
es

le

la
t
sommets.
de
0
nouv

dans
et
la
le
ligne
0
pr?c?den

te,
du
inscrire
Sur
une
1?re
dans
graphe
la
tous

0


o
de
dan
?
te
hoisir
de
que
la
form?e

et
Commenecr
l'ensem
.

minimal.
Sommet
Sinon,
t
inscrire
utiliserons
le
utilisation

t.

et
t
en
de
hemin
t
trouv
de
allons
la
Algorithme
ligne
pro
pr?c?den
t,
te,
ainsi

suite

sommet
.
d?part.
ligne

par
?tap
des


p

remplir
ts
tableau
de
1.
la
dans
ligne
Rep
pr?c?den
autres
te.

de
les
sommet
t
S'il

reste
2.
des
d?part
sommets
sommet
non
sous


retourner
0
?

l'?tap
le
e
tableau,
2.
ligne
le
la
Sinon,
tableau.
passer
ligne
?
la
l'?tap
3.
e
du
5.
les
ligne
Placer
La

longueur
eectuer
minimale
he
est
e
le
l'algorithme.
nom
l'?x?cution
bre
mesure
lu
et
sur
au
la

derni?re
nous
ligne
sommets
du
par
tableau.

La
la

sommets
haine
ble
de
4.
longueur
os?e
minimale
est
se
premi?re
trouv

e
la
en
don
lisan
une
t
nous
le
de
tableau
haque
en
A
repartan
pr?c?den
t
du
du
sommets
dernier
tre
de

sommet
le
et

en
er
regardan
t
t

de
Nous
quel
de
sommet
et
1.2

la
2E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
5(C) 7(C) D
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
5(C) 7(C) C
6(D) S
E−B−C−D−S
S
D D
C
v2
v v1 4
v3
..................
la
mani?re
suiv
orien
ar?tes
que
an
Sommet
te
que
:
an
dans
est
la
graphe

t?es,
gauc
eut
de
sens.
3
,
on

rep
l'origine
?re
plus
le
Sommet
p
t
oin
t
t
?
inscrit
ne
le
les
plus
un
en
2
bas,
en

:
?
Une
.
une
Puis
don
dans
l'extr?mit?
la


0
droite
0
on
un
note
don
le
les
sommet
son
inscrit
orien
le

plus
dire
en
l'on
bas,
p
de
parcourir

ar?tes
Le
dans
p
seul
oids
Exemple
de
t

l'?criv

3
he,
ha?ne
est
D?nition
6.
Boucle
2
b
Graphes
est
orien
ar?te
t?s
t?e
D?nition
t
2
et
Gr
donc
aphe
haine
orient?

Un
Une
graphe

orien
6.
t?

est
.
5.
On
l'obtien
Exemple
t
3A
B C
n
n n×n i
j i j 0
 
1 0 1A
 A= 0 1 1
0 0 0
C
B
t
n
um?rot?s
une
Un
L
1
?tiquet?
?
p
?

est
?tiquet?s
une
les
matrice
bres


de
v
dimension
ts

tation
asso
aphe
matrice
orien
,
aect?es
o?
son
le
5
terme
:
guran
A
t
pas
en
des
ligne
mais
La
reli?s
et
t

3
orient?
5
est
Un
?gale
un
?
don
1
son
s'il
Remarque
existe
les
une
des
ar?te
ositifs.
d'orgine
graphes
aphe
t
et
ALEZY,
d'extr?mit?b
gr
E
,
non
et
a
un
ec
sinon.
sommets
Exemple
ts,
4

?
et
son
par
p
ar?te
sommets
oss?dan
les
l'orien
t

e
Graphes

D?nition
asso
Gr
e
?tiquet?
Matric
graphe
don
est
un
graphe
d'ordre
t?
t?
t
orien
ar?tes
p
t
est
d'?tiquettes.
graphe
2
dans
graphe
graphe
ond?r?
4
un
D?nition
?tiquet?
g?n?rer
lequel
de
?tiquettes
des
t
des.
nom
graphe
p
an
Exemple
p
Les
par
?tiquet?s
de
ermetten
les
de
Remarque
ou
1

P

our
Le
appliquer
suiv
l'algorithme
t
de
ermet,
Dijkstra
exemple
a
g?n?rer
un
mots
graphe
ALLEZ,
orien
ALEZZYLE
t?,b
onb
remplit
Z
le
Y
tableau
4.........
(600 000 40
000)
n
n n×n
i j i j 0
le
futur.
Exemple
de
ansition
un
6
?
Deux
le
villes
0,2
v
une
oisines
une
X
n
et
haque
Y
A
totalisen
Un
t
ossibles
?
deux
elles
de
deux
deux
une
d'ordre
p
la
opulation
graphe
d'un
eut
million
sa
d'habitan
0,1
ts.
Etat
La
syst?me
ville
ble
X
est
est
3
plus
probabiliste
agr?able,
on
mais
situations
la
million
ville
Matric
Y
transition
ore
les
de
?
meilleurs
dimension
salaires.
?
20%
de
des
v
habitan
stable
ts
oir
de
Exemple
Y
C
parten
0,2
t
D?nition

ob
haque
probabiliste
ann?e
une
habiter
sur
X
?tats
p

our
t?e
a
ligne.
v
l'exemple
oir
un
un
ourrait
meilleur
herc

al?atoire,
de
oluen
vie,
p
et
des
5%
t
des
D?nition
habitan
de
ts
matrice
de
graphe
X
don
parten
son
t
de

,
haque

ann?e
probabilistes
habiter
guran
Y
ligne
p
t
our

augmen
sommet
ter
aut
leur
p
niv
?tat
eau
si
de
v
vie.
.
P
7
ouv
B
ons-nous
0,9
imaginer
0,3
l'?v
0,5
olution
0,8
des
7
p
pr
opulations
abiliste
de
?tat

d'un
deux
est
villes
loi
au
probabilit?

l'ensem
du
des
temps
p
?
:
P
loi
our
repr?sen
y
par
r?p
matrice
ondre,
Remarque
nous
Dans
aurons
des
b
villes,
esoin
?tat

p
toujours,
?tre
d'un
he
p

etit
et
p
mani?re
eu
t
de
?v
v
,
o
our

r?partition
D?nition
un
6
d'habitan
Gr
des
aphe
villes.
pr
8
ob
e
abiliste
tr
Un
La
graphe
de
p
d'un
obabiliste
probabiliste
en
breuses
et
t
la
sommets
?tre
t
?gal
um?rot?s
p
1
de
nom
allan
est
de
matrice
v
de
dans
De
,
Graphes
ou
o?
visag?
terme

t
Matrice
la
transition
est
un
?
graphe

orien
est
t?
au
et
oids
p
l'ar?te
ond?r?
t
4
don
t
ers
la
,
somme
sinon
des
.
p
1
oids
de
des
du
ar?tes
pr?c?den
issues
5M P0
P nn
........................
M
P n P Pn 0
P
........................
2
P
our
un

de
tout

graphe
(
probabiliste
et
d'ordre
p
2
A
don
d'une
t
le
la
goto
matrice

de

transition
v
Propri?t?
1968
ne
against

t
orte
rebaptise
par
).
de

0,
ultiplien
l'?tat
par
:
EWD
a
else
?
duites
l'?tap
et
e
ossibles
on
l'usage

mation,
v
Comm
erge
qu'il
v
t
ers
GOTO
un

?tat
l'?diteur
,
Statemen
ind?p
o
endan
titre
t

de
de
l'?tat

initial
Dijkstra
e
marginalis?e,
l'?tap

.
en
De

plus,

l'?tat
do,
stable
furen
?
Algol
v
une
?rie

:
sys-
probabiliste
d?g?ts
l'?tat
qu?s
et

initial
en
l'?tat
r?dige
t
our
an
of

un
ligne
A
matrice
GOTO
la
Un
est
tre
si
V
probabiliste,
rapidemen
graphe
la
d'un
?
transition
Wirth
de
T
matrice
Considered
la
Go
est
n
Si
nouv
1
t
le
os
Des
t
en
le
imp
Les
tr?e
forme

se
la
jusqu'?
qui

orte
rapidemen
a
presque
syn
pro-
(v
de
Hoare)
pr?sen
?
autres

En
Eiel.
goto
ait
des
imp
then
le
while
t
eat
?

ann?es
in
elopp
Wirth
la
:
des
tien

en
t
seule
notre
rend

des
tation
exhaustifs
t
v
Propri?t?
de
5
p
Annexe.
aussi
Une
?
biographie
et
d'Edsger
ostul?es
Dijkstra
unique,
Sour
la

des
e
?
:

Wikip
Logique
?
plus
dia.
programmation
Apr?s
du
des
a
?tudes
un
de
t
ph
elopp
ysique
langage
th?orique,
n
il
et
s'engage
ensuite
d?s
et
1955
de
dans

le
t
domaine
de
de
leur
l'infor-
de
matique
les
alors
pro
naissan
o
te,
par
don

t
de
il
goto
est
program-
l'un
il
des
en
pionniers
p
les
les
plus
unications
?clair?s.
the
P
CM
armi

ses
nomme


tributions
the
se
statemen
trouv
(
e
pro
un

algorithme

de
).

oulan
du
publier
plus
t

sous

forme
hemin
lettre
dans
l'?diteur,
les
Niklaus
graphes,
le

Go
u
o
sous
t
le
Harmful
nom

d'algorithme
T
de
jug?e
Dijkstra.
uisible
Enseignan
Ce
t
eau
?
autan
l'univ
que
ersit?
prop

de
hnique
devien
d'Eindho
alors
v
dans
en,
milieu
il
l'informatique.

titres
?
la
se
X
faire
harmful

m
en
t,
ma-
un
ti?re

de

syst?mes
est
a
t
v
et
ec
?limin?e,
THE
la
Op
grammation
erating

system,
Wirth
un
Dijkstra,
syst?me
t?

tre
en
dans

268).
hes
programmation

le

est
es
par
et

id?al
if...
p
...
our
...,
l'enseignemen
...
t
rep
(
...
THE
til

elles
est
t
un
tro
jeu
par
de
dans
mot
W
sur

l'acron

yme
t
de
seule
son
tr?e
univ
une
ersit?
sortie,
T
qui
ec
enn

ossible
he
tests
Hogesc
t?matiques
ho
imp
ol
a
Eindho
ec
v
"co
en,
spaghetti".
?cole

p
euv
olytec
t
hnique).
?tre
F
os?es
ort
l'en
de
unique
l'exp
des
?rience
p
d'?cri-
?
ture
sortie
de


ouvre
syst?me,
p
il
?
formalise
outils
le
jout?s

la
a
taxe,
v
assert
an
oir
t
de
lui
et
dius,
tard
de
la
s?maphore
par
puis
trat
in
langage
tro
Dijkstra
duit
v
le
jou?

r?le
de
ortan

dans

d?v
a
emen
v
du
ec
Algol
deux
la
exemples
des
dev
1950
en
d?v
us
?


:
science
le
l'art
probl?me
langages
des
programmation

,
et
tribuan
des
grandemen

?
et

le
leur
d?ner
de
des
repr?sen
philosophes.
et
Constatan
6◦







du
b
el
algorithme,
t?lescop

bugs
y
demander

Autrefois
p
d'essa
our
demander
des
une
sujets
sur
diciles
rassurer.
?
tailler
traiter

en
ulle
programmation
est

aussi

p
les
que
p
morceaux
erles
exp
de
OR
Dijkstra
des
(disp
une
oser
faire
des
science
p
l'on
erles
n'existe
de
p
trois
t

p
sur
par
un
mauv
l
qu'en
de
seron
fa?on
ouv
?
les

ex?cutable.
qu'il
r?p
n'y

ait
adh?ren
jamais
hangen
deux


est

on
tes
Il
iden
la
tiques).
dix
Le
n'est
discours
l'astronomie
qu'il
n'est

eut
en
plupart
1972

lorsqu'il
un
re?oit
p
le
in
prix
de
T
un
uring,
nager.
The
La
Hum
jets
ble

Program-
qui
mer[4],
ait
est

rest?
progr?s

p
lui
nous
aussi.

Il
programmes
s'agit

?galemen

t
[3].
d'un
ph

t
d'auto
de
d?rision,
our
le
ui
professeur
?
Dijkstra
et
s'?tan
leurs
t

toujours
prop
mon
:
tr?
ossible
tr?s


v
t
he
de
v
la
er,
v
de
aleur
v
de
hes
ses

tra
plus
v
ordinateurs
aux

En

1974,

Dijkstra
il
publie
de

et
fondateur
temps
de

l'autostabilisation[5],
Se
propri?t?
si
d'un
ordinateur
syst?me
eut
r?parti
enser
?
aussi
retrouv
t?ressan
er
que
un
se

si
ortemen
sous-marin
t
eut


apr?s

toute
programmation
d?faillance
ob
transitoire.
est
En
id?e
2002,
t
il
aise
re?oit
ne
le
ouv
prix
na?tre
P
Californie.
oDC
C'est
de
Les

ne
inuen
t
t
ossibles
p
si
our
p

ons

hir
Il
les
meurt
sans
p
imaginer
eu
des
apr?s.
de
Ce
de
prix

est

renomm?
les
prix
ysiciens
Dijkstra
?taien
en
les
son
?riences
honneur
leurs
d?s
p
l'ann?e
se
suiv
Aujourd'h
an
ils
te.
t
Quelques
F

TRAN
de
s'?c
Dijkstra.
t
Dijkstra,
programmes,


u
tation
p
?
our
os
son
langages

il
dicile
imp
et
de
son
un
in
y

a
?tait
ec
r?put?

p
?mouss?e.
our
est
ses
ain
aphorismes
y
qui
?
r?sumaien
place,
t
le
sa
a
vision
ec
de

la
?mouss?es.
science
impl?men
informatique.
L'informatique
adepte
pas

la
T
des
un
que

n'est
plus
des

es.
d'un
ester
un
Le
programme

p
hemin
eut
graphe
d?mon
jamais
trer
que
la


p
de
surgir
bugs,
n
jamais
part,
leur
la
absence
du

il
.
pas.
leur
7

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.