Mines Informatique MP 2008

Épreuve deinformatique 2008

A 2008 INFO. MP
ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES,
ÉCOLES NATIONALES SUPÉRIEURES DE LeAÉRONAUTIQUE ET DE LeESPACE,
DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY,
DES TÉLÉCOMMUNICATIONS DE BRETAGNE,
ÉCOLE POLYTECHNIQUE (FILIÈRE TSI)
CONCOURS DeADMISSION 2008
ÉPREUVE D'INFORMATIQUE
Filière MP
Durée de l'épreuve : 3 heures.
L'usage de calculettes est autorisé. L'utilisation d'un ordinateur est 
interdite.
Sujet mis à disposition des concours : ENSAE ParisTech, TELECOM SudParis (ex 
INT), TPE-EIVP
Les candidats sunt priés de mentiunner de façun apparente sur la première page 
de la cupie :
INFORMATIQUE - MP

L'énuncé de cette épreuve cumpurte 10 pages.

RECOMMANDATIONS AUX CANDIDATS
· Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une 
erreur d'énoncé, il le signale
sur sa copie et poursuit sa composition en expliquant les raisons des 
initiatives qu'il est amené à
prendre.
· Tout résultat fourni dans l'énoncé peut être utilisé pour les questions 
ultérieures même s'il n'a pas
été démontré.
· Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents 
même lorsque l'énoncé
ne le demande pas explicitement.

COMPOSITION DE L'ÉPREUVE
Leépreuve comporte deux problèmes indépendants :
· un problème sur les automates, pages 2 et 3 ;
· un problème dealgorithmique et programmation, pages 3 à 10.

Page 1 sur 10
Tournez la page S.V.P.

Épreuve deinformatique 2008

1. Problème sur les automates (temps conseillé : 40 mn)
Deux constructions d'un automate reconnaissant l'intersection de deux langages 
reconnaissables
Un alphabet  est un ensemble fini deéléments appelés lettres. Un mot sur  est 
une suite finie de lettres de
. La longueur deun mot m, notée |m|, est le nombre de lettres qui le composent 
; par exemple, la longueur du
mot « abac » vaut 4. Le mot vide est le mot de longueur nulle et est noté . On 
désigne par * leensemble des
mots sur , y compris le mot vide. Un langage sur  est une partie de *.
Un automate A est décrit par une structure <, Q, T, I, F>, où :
·  est un alphabet ;
· Q est un ensemble fini et non vide appelé ensemble des états de A ;
· T  Q ×  × Q est appelé leensemble des transitions ; étant donnée une 
transition (p, x, q)  T, on dit
x

queelle va de leétat p à leétat q et queelle est deétiquette x ; on pourra la 
noter p  q ;
I  Q est appelé ensemble des états initiaux de A ;
F  Q est appelé ensemble des états finals de A.

·
·

x

x

x

1
2
k
p1 
p2 ... 
pk où, pour 1  i  k,
Un calcul c de A est une suite de la forme p0 

x

i
pi - 1 
pi est une transition ; p0 est leorigine du calcul, pk son extrémité. 
Leétiquette de c est le mot
x1x2 ... xk formé par la suite des étiquettes des transitions successives.
m

m

Un calcul deorigine p, deextrémité q et deétiquette m peut être noté p  q. Un 
calcul p  q de A est
dit réussi si on a p  I et q  F. Un mot m de * est reconnu par A seil est 
leétiquette deun calcul réussi. Le
langage reconnu par A, noté L(A), est leensemble des mots reconnus par A. Un 
langage est dit reconnaissable
seil existe un automate qui le reconnaît.
Un état q deun automate A est dit accessible seil existe dans A au moins un 
calcul dont leorigine est un état
initial et dont leextrémité est q.
Leautomate A est dit déterministe si I contient exactement un élément et si, 
pour tout p  Q et tout x  , il
existe au plus un état q Q avec (p, x, q)  T. Leautomate A est dit complet si, 
pour tout p  Q et tout x  , il
existe au moins un état q  Q avec (p, x, q)  T.
Pour les exemples de ce problème, on utilisera lealphabet _ex = {a, b}.
 1 ­ Soit L1_ex le langage sur _ex des mots qui commencent par a. Représenter 
graphiquement un
automate déterministe et complet noté A1_ex qui reconnaît L1_ex, ceest-à-dire 
vérifiant
L(A1_ex) = L1_ex ; cet automate aura trois états nommés 1, 2, 3. Leétat 1 sera 
leunique état initial et
leétat 2 leunique état final.
 2 ­ Soit L2_ex le langage sur _ex des mots dont la longueur est multiple de 3. 
Représenter
graphiquement un automate déterministe et complet noté A2_ex qui reconnaît 
L2_ex, ceest-à-dire
vérifiant L(A2_ex) = L2_ex ; cet automate aura trois états nommés 4, 5, 6. 
Leétat 4 sera leunique état
initial et leunique état final.
Les questions  3 et  4 sont consacrées à une première méthode pour calculer un 
automate reconnaissant
leintersection de deux langages reconnaissables.
 3 ­ On considère deux langages L1 et L2 sur un alphabet quelconque . On 
suppose que L1 est
reconnu par un automate A1 = <, Q1, T1, I1, F1> ; on suppose que L2 est reconnu 
par un automate
A2 = <, Q2, T2, I2, F2>. Montrer que le langage L = L1  L2 est reconnu par un 
automate
A = <, Q, T, I, F> pour lequel :
· Q = Q1 × Q2 ;
· I = I1 × I2 ;
· F = F 1 × F 2.
En particulier, on précisera leensemble T des transitions de A.
Page 2 sur 10

Épreuve deinformatique 2008

 4 ­ En utilisant la construction de la question précédente, représenter 
graphiquement un automate
noté A3_ex reconnaissant L1_ex  L2_ex. On ne représentera que les états 
accessibles de cet automate.
La suite du problème propose deappliquer une seconde façon de calculer un 
automate reconnaissant
leintersection de deux langages reconnaissables.
 5 ­ On considère un langage L sur un alphabet quelconque . On suppose que L 
est reconnu par un
automate déterministe et complet A = <, Q, T, {q0}, F>, où q0 est leunique état 
initial de A. Montrer
que le langage complémentaire L de L, constitué des mots de * qui ne sont pas 
dans L, est reconnu
par un automate A = <, Q, T, {q0}, F > déterministe et complet ; on précisera 
les ensembles T et
F ; on justifiera la réponse. En déduire un automate déterministe et complet 
A1_ex qui reconnaît L1
et un automate déterministe et complet A2_ex qui reconnaît L2 ; ces deux 
automates seront décrits
par leur représentation graphique.
Soient deux automates A1 = <, Q1, T1, I1, F1> et A2 = <, Q2, T2, I2, F2> 
reconnaissant respectivement des
langages L1 et L2 ; on suppose que les ensembles Q1 et Q2 sont disjoints ; 
leunion de ces automates est par
définition leautomate A = <, Q1  Q2, T1  T2, I1  I2, F1  F2 >. On admet que cet 
automate A reconnaît le
langage L1  L2.
 6 ­ On note A4_ex leautomate obtenu par union de A1_ex et A2_ex. Représenter 
graphiquement un
automate déterministe et complet A5_ex obtenu en appliquant à A4_ex un 
algorithme classique de
déterminisation. On ne représentera que les états accessibles de cet automate.
 7 ­ Déduire de leautomate A5_ex obtenu à la question  6, un automate 
reconnaissant
L1_ex  L2_ex.

2. Problème d'algorithmique et programmation (temps conseillé : 2 h 20 mn)
On seintéresse au problème du voyageur de commerce dans un graphe complet 
symétrique valué.
Préliminaire concernant la programmation : il faudra écrire des fonctions ou 
des procédures à leaide deun
langage de programmation qui pourra être soit Caml, soit Pascal, tout autre 
langage étant exclu. Indiquer en
début de problème le langage de programmation choisi ; il est interdit de 
modifier ce choix au cours de
l'épreuve. Certaines questions du problème sont formulées différemment selon le 
langage de programmation ;
cela est indiqué chaque fois que nécessaire. Par ailleurs, pour écrire une 
fonction ou une procédure en langage de
programmation, le candidat pourra définir des fonctions ou des procédures 
auxiliaires queil explicitera ou faire
appel à deautres fonctions ou procédures définies dans les questions 
précédentes.
Dans leénoncé du problème, un même identificateur écrit dans deux polices de 
caractères différentes désigne
la même entité, mais du point de vue mathématique pour la police écrite en 
italique (par exemple : n) et du point
de vue informatique pour celle écrite en romain (par exemple : n).
Un graphe est défini par un ensemble fini, noté X, deéléments appelés sommets 
et par leensemble de ses
arêtes ; une arête {x, y} est une paire de sommets distincts x et y qui sont 
les extrémités de cette arête. Un
graphe est complet si toute paire de sommets distincts est une arête. Le nombre 
de sommets deun graphe
seappelle leordre du graphe ; tous les graphes considérés dans ce problème sont 
deordre au moins 3. Si un graphe
est deordre n, ses sommets sont nommés 0, 1, 2, ..., n ­ 1 dans ce problème. 
Les graphes considérés ici seront
des graphes complets valués, ce qui signifie queon attribue à chaque arête un 
entier naturel nommé poids de
cette arête. Dans tout ce problème, les graphes considérés seront deordre au 
plus 100 et les poids ne dépasseront
pas 100.
Un graphe complet valué deordre n peut être représenté par une matrice carrée 
symétrique de dimension n × n
dont les cases sont indicées par (i, j) avec 0  i  n ­ 1 et 0  j  n ­ 1 ; on 
notera poids cette matrice indiquant
dans la case deindice i et j le poids poids({i, j}) de learête {i, j} ; par 
convention, cette matrice a des zéros sur la
diagonale. On représente ci-après un graphe complet valué G_ex et la matrice 
poids_ex correspondante.
Page 3 sur 10
Tournez la page S.V.P.

Épreuve deinformatique 2008

0
1

4
4

10
3

12
6

9
3

0

1

2

3

4

0

0

1

10

5

4

1

1

0

6

12

7

2

10

6

0

2

3

3

5

12

2

0

9

4

4

7

3

9

0

1

7
5

j

i

2

puids_ex

2

G_ex

Soit G un graphe complet deordre n. Soit (t0, t1, t2, ..., tn ­ 1) une 
permutation de leensemble X des sommets
de G. Par définition, le tour T induit par cette permutation est un graphe 
ayant X comme ensemble de
sommets et dont leensemble des arêtes est : {{ti, ti + 1} | 0  i  n ­ 2}  { tn 
­ 1, t0}. Par exemple, le tour T_ex
induit par la permutation (0, 2, 3, 1, 4) est représenté en gras ci-dessus.
On appelle poids d'un tour T d'un graphe complet valué G, et on note poids(G, 
T), la somme des poids
des arêtes de T dans G :
n -2

puids(G, T) =  puids ({ti , ti +1}) + puids ({tn -1 , t0 }) .
i =0

Ainsi : puids(G_ex, T_ex) = 10 + 2 + 12 + 7 + 4 = 35.
Le problème auquel on seintéresse ici est celui de la détermination deun tour T 
de G tel que puids (G, T) soit
minimum. On dit alors queil seagit deun tour de poids minimum.
On appelle dans ce problème chaîne à p sommets deun graphe complet G une suite 
ordonnée
C = (c0, c1, c2, ..., cp ­ 1) de p sommets distincts de G ; en notant n leordre 
de G, on a alors nécessairement
1  p  n. Le poids deune telle chaîne vaut :
p-2

puids(G, C) =  puids ({ci , ci +1 }) .
i =0

Par exemple, pour la chaîne C_ex = (0, 3, 1) du graphe G_ex, puids(G_ex, C_ex) 
= 5 + 12 = 17.
On pourra sans ambiguïté évoquer le poids deune arête, ou le poids deun tour, 
ou le poids deune chaîne.

Indications pour la programmation
Caml : On définit leidentificateur suivant :
let MAX_POIDS = 100;;
On supposera que les poids des arêtes des graphes traités ne dépassent jamais 
la valeur MAX_POIDS.
La matrice des poids est codée par un tableau à deux dimensions (un vecteur de 
vecteurs) n × n (où n est
leordre du graphe) ; la matrice puids_ex représentant le graphe G_ex est ainsi 
codée par :
let poids_ex = [|[|0; 1; 10; 5; 4|]; [|1; 0; 6; 12; 7|];
[|10; 6; 0; 2; 3|];[|5; 12; 2; 0; 9|];[|4; 7; 3; 9; 0|]|];;
On accède alors au poids de learête {i, j} du graphe G_ex par : 
poids_ex.(i).(j).
Un tour est codé par un tableau (vecteur) de dimension égale à leordre du 
graphe et contenant la suite des
sommets deune permutation induisant ce tour. Le tour T_ex peut être défini par :
let T_ex = [|0; 2; 3; 1; 4|];;
De même, une chaîne est codée par un tableau contenant la suite des sommets de 
la chaîne ; on pourrait
coder la chaîne C_ex = (0, 3, 1) par :
let C_ex = [|0; 3; 1|];;
On remarque donc queune matrice de poids, ou bien un tour, ou bien une chaîne 
sont codés avec des
tableaux ayant la stricte dimension nécessaire, et non avec des tableaux « 
surdimensionnés ». Pour

Page 4 sur 10

Épreuve deinformatique 2008

connaître la dimension deun tableau, on peut utiliser la fonction vect_length. 
Par exemple, avec les
définitions ci-dessus, vect_length poids_ex vaut 5 et vect_length C_ex vaut 3.
Un sous-ensemble S de leensemble des sommets deun graphe G deordre n est codé 
par un tableau de
longueur n donnant la fonction caractéristique de cet ensemble ; ainsi, en 
notant S ce tableau et i un entier
compris entre 0 et n ­ 1, S.(i) vaut 1 si le sommet i appartient à S et vaut 0 
si le sommet i neappartient
pas à S.
Fin des indications pour Caml

Pascal : On utilise les définitions suivantes.
const
MAX_SOMMETS = 100;
MAX_POIDS = 100;
type Matrice = array [0 .. MAX_SOMMETS - 1, 0 .. MAX_SOMMETS - 1] of Integer;
type Table = array [0 .. MAX_SOMMETS - 1] of Integer;
La constante MAX_SOMMETS donne une borne supérieure de leordre des graphes qui 
pourront être traités.
Par ailleurs, on supposera que les poids des arêtes des graphes traités ne 
dépassent jamais la valeur de la
constante MAX_POIDS.
Le type Matrice sert à coder la matrice des poids du graphe considéré. La 
matrice poids_ex
représentant le graphe G_ex est ainsi codée avec une variable poids_ex de type 
Matrice par :
poids_ex[0, 1] := 1; poids_ex[1, 0] := 1; poids_ex[0, 2] := 10;
poids_ex[2, 0] := 10; poids_ex[0, 3] := 5; poids_ex[3, 0] := 5;
poids_ex[0, 4] := 4; poids_ex[4, 0] := 4; poids_ex[1, 2] := 6;
poids_ex[2, 1] := 6; poids_ex[1, 3] := 12; poids_ex[3, 1] := 12;
poids_ex[1, 4] := 7; poids_ex[4, 1] := 7; poids_ex[2, 3] := 2;
poids_ex[3, 2] := 2; poids_ex[2, 4] := 3; poids_ex[4, 2] := 3;
poids_ex[3, 4] := 9; poids_ex[4, 3] := 9; poids_ex[0, 0] := 0;
poids_ex[1, 1] := 0; poids_ex[2, 2] := 0; poids_ex[3, 3] := 0;
poids_ex[4, 4] := 0;
Si la matrice des poids deun graphe, de type Matrice, seappelle poids, on peut 
accéder au poids de
learête {i, j} par poids[i, j].
Le type Table sera utilisé dans les cas suivants :
· pour coder un tour, on utilise un tableau de type Table contenant, à partir 
de leindice 0, la suite
des sommets deune permutation induisant ce tour ;
· pour coder une chaîne, on utilise un tableau de type Table contenant, à 
partir de leindice 0, la suite
des sommets de cette chaîne ;
· un sous-ensemble S de leensemble des sommets deun graphe G deordre n (n  
MAX_SOMMETS) est
codé par un tableau de type Table donnant la fonction caractéristique de cet 
ensemble ; ainsi, en
notant S ce tableau et i un entier compris entre 0 et n ­ 1, S[i] vaut 1 si le 
sommet i appartient à S
et vaut 0 si le sommet i neappartient pas à S.
Fin des indications pour Pascal

Première partie : questions préliminaires
 8 ­ On considère un graphe G complet deordre n. Donner le nombre de tours 
différents de G. Une
méthode pour déterminer un tour de poids minimum consiste à dresser la liste 
exhaustive de tous les
tours possibles, à calculer le poids de chacun des tours et à retenir un tour 
de poids minimum. On
suppose que n vaut 50 ; dire si cette méthode est raisonnable deun point de vue 
pratique en justifiant
brièvement la réponse.
 9 ­ Il seagit de calculer le poids deun tour dans un graphe complet valué 
donné.
Caml : Écrire en Caml une fonction nommée poids_tour telle que, si poids est la 
matrice
donnant les poids des arêtes deun graphe complet valué G et T un tableau codant 
un tour de G,
poids_tour poids T renvoie le poids du tour considéré.
Pascal : Écrire en Pascal une fonction nommée poids_tour telle que, si poids, 
de type
Matrice, contient les poids des arêtes deun graphe complet valué G, si n est un 
entier donnant
Page 5 sur 10
Tournez la page S.V.P.

Épreuve deinformatique 2008

leordre de G et si T, de type Table, code un tour de G, poids_tour(poids, n, T) 
renvoie le
poids du tour considéré.

 10 ­ Indiquer la complexité de la fonction poids_tour écrite dans la question 
précédente.
 11 ­ Soit G un graphe complet valué deensemble de sommets X. On considère un 
sous-ensemble S
de X ; on suppose que S est non vide et différent de X. Soit x un sommet de X 
neappartenant pas à S. Il
seagit de déterminer un sommet p(x) de S tel que, pour tout sommet s de S, on 
ait :
puids({x, p(x)})  puids({x, s}) ; si plusieurs sommets sont candidats, on prend 
pour p(x) celui dont le
nom est le plus petit. On dira alors que p(x) est le sommet de S le plus proche 
de x.
Caml : Écrire en Caml une fonction nommée plus_proche telle que,
· si poids est la matrice donnant les poids des arêtes deun graphe complet 
valué G deensemble
de sommets X,
· si S est un tableau codant un sous-ensemble S de X non vide et différent de X,
· si x est un entier correspondant à un sommet x de G neappartenant pas à S,
alors plus_proche poids S x renvoie un entier correspondant au sommet de S le 
plus proche
de x.
Pascal : Écrire en Pascal une fonction nommée plus_proche telle que,
· si poids, de type Matrice, contient les poids des arêtes deun graphe complet 
valué G
deensemble de sommets X,
· si n est un entier donnant leordre de G,
· si S, de type Table, code un sous-ensemble S de X non vide et différent de X,
· si x est un entier correspondant à un sommet x de G neappartenant pas à S,
alors plus_proche(poids, n, S, x) renvoie un entier correspondant au sommet de 
S le plus
proche de x.
 12 ­ Indiquer la complexité de la fonction plus_proche écrite dans la question 
précédente.

Deuxième partie : l'heuristique du plus proche voisin
On cherche dans cette partie à définir une méthode pour construire « rapidement 
» un tour de « faible poids »
sans être nécessairement de poids minimum. Une telle méthode seappelle une 
heuristique.
Leheuristique décrite ci-après seappelle leheuristique du plus proche voisin. 
On dispose deun graphe G
complet valué deordre n et on souhaite déterminer un tour de « faible poids ». 
Pour construire un tel tour T, on
détermine comme suit une permutation (t0, t1, t2, ..., tn ­ 1) des sommets de G 
induisant ce tour. On choisit
deabord un sommet quelconque du graphe et on le note t0. On cherche alors, 
parmi les sommets de G autres que
t0, le sommet le plus proche de t0. On note t1 un tel sommet. On continue ainsi 
: quand, pour 1  i  n ­ 1, on a
déterminé successivement les sommets t1, t2, ..., ti ­ 1, on cherche le sommet 
ti de G le plus proche de ti ­ 1 parmi
les sommets neappartenant pas à leensemble {t0, t1, t2, ..., ti ­ 1}. Le 
résultat de leheuristique du plus proche
voisin dépend donc uniquement du choix du sommet de départ, ceest-à-dire de t0.

 13 ­ Indiquer le tour obtenu par leheuristique du plus proche voisin si on 
leapplique au graphe G_ex
en choisissant le sommet 0 comme sommet de départ. Préciser le poids de ce tour.
 14 ­ Indiquer le tour obtenu par leheuristique du plus proche voisin si on 
leapplique au graphe G_ex
en choisissant le sommet 1 comme sommet de départ. Préciser le poids de ce tour.
 15 ­ Leobjectif de cette question est de programmer leheuristique du plus 
proche voisin.
Caml : Écrire en Caml une fonction nommée tour_plus_proche telle que,
· si poids est la matrice donnant les poids des arêtes deun graphe complet 
valué G deordre n,
· si depart est une valeur entière vérifiant 0  depart  n ­ 1,

Page 6 sur 10

Épreuve deinformatique 2008

alors tour_plus_proche poids depart renvoie un tableau de longueur n contenant 
un
codage du tour obtenu par leheuristique du plus proche voisin appliquée au 
sommet de nom depart.

Pascal : Écrire en Pascal une procédure nommée tour_plus_proche telle que,
· si poids, de type Matrice, contient les poids des arêtes deun graphe complet 
valué G,
· si n est un entier donnant leordre de G,
· si depart est un entier vérifiant 0  depart  n ­ 1,
· si tour est de type Table,
alors tour_plus_proche(poids, n, depart, tour) remplit le tableau tour pour 
queil
contienne un codage du tour obtenu par leheuristique du plus proche voisin 
appliquée au sommet de
nom depart.
 16 ­ Calculer la complexité de lealgorithme de la question précédente.
 17 ­ À leaide deun graphe complet valué deordre 4 et en choisissant un sommet 
de départ de façon
appropriée, montrer que leheuristique du plus proche voisin ne détermine pas 
toujours un tour de poids
minimum.

Troisième partie : méthode par amélioration itérative
On considère une transformation deun tour en un autre ; on appelle 
transformation 2-opt cette
transformation ; elle est définie comme suit. On note T = (t0, t1, t2, ..., tn 
­ 1) une permutation induisant un
tour T. Pour définir une transformation 2-opt de T, on précise deux entiers i 
et j vérifiant : 0  i  n ­ 3,
i + 2  j  n ­ 1 et (i, j)  (0, n ­ 1) ; on définit plus précisément une 
transformation notée 2-upt(T, i, j) ; on pose
i = i + 1 et j = (j + 1) modulo n ; le tour T = 2-upt(T, i, j) est le tour dont 
les arêtes sont obtenues à partir de
celles de T :
· en retirant de T les arêtes {ti , ti} et {tj , tj} ;

· en ajoutant les arêtes {ti , tj} et {ti , tj}.
Les paramètres i et j de la transformation 2-opt ne sont donc pas des sommets 
mais des indices de sommets
relativement à T ; on rappelle que les indices dans T commencent à 0.

 18 ­ Dans un graphe complet deordre 8, on considère le
tour T induit par la permutation T = (3, 4, 0, 6, 2, 7, 1, 5).
On pose T = 2-upt(T, 1, 6). Dessiner le tour T comme cicontre et représenter le 
tour T sur la même figure par un
tracé qui se différencie de celui de T (autre couleur, trait
plus gras...). Indiquer explicitement une permutation
induisant T ; on remarquera que cette permutation peut
commencer par 3, 4, ... ; ceest ce début qui sera retenu.

0

6

4

2

3

7
5

1

 19 ­ Il seagit deécrire en langage de programmation le calcul deun tour obtenu 
par une
transformation 2-opt à partir deun tour donné.
Caml : Écrire en Caml une fonction nommée deux_opt telle que,
· si T est un tableau codant un tour T deun graphe G deordre n,
· si i et j sont deux entiers vérifiant 0  i  n ­ 3, i + 2  j  n ­ 1 et (i, j)  
(0, n ­ 1),
alors deux_opt T i j transforme le tableau T pour que celui-ci code le tour 
obtenu par la
transformation 2-upt(T, i, j).
La fonction ne vérifiera pas que les entiers i et j respectent les inégalités 
indiquées.
Pascal : Écrire en Pascal une procédure nommée deux_opt telle que,
· si T, de type Table, code un tour T deun graphe G deordre n,
· si i et j sont deux entiers vérifiant 0  i  n ­ 3, i + 2  j  n ­ 1 et (i, j)  
(0, n ­ 1),
Page 7 sur 10
Tournez la page S.V.P.

Épreuve deinformatique 2008

alors deux_opt(T, i, j) transforme le tableau T pour que celui-ci code le tour 
obtenu par la
transformation 2-upt(T, i, j).
Leordre n du graphe neintervient pas dans leécriture de cette fonction.
La procédure ne vérifiera pas que les entiers i et j respectent les inégalités 
indiquées.

 20 ­ Indiquer leordre de grandeur de la complexité dans le pire des cas de la 
transformation
deux_opt programmée dans la question précédente.
Pour déterminer dans un graphe G un tour de « faible poids », on peut envisager 
leheuristique suivante : on
choisit un tour initial queon note T ; tant queil existe une transformation 
2-opt transformant T en un tour de poids
strictement plus petit, on choisit une telle transformation queon applique à T 
pour obtenir un nouveau tour queon
substitue à T et queon nomme encore T. Ainsi, quand lealgorithme se termine, il 
neexiste aucune transformation
2-opt permettant de transformer le tour final T en un tour de poids strictement 
plus petit. Cette méthode est
qualifiée de méthode par amélioration itérative.

 21 ­ On considère le graphe G_ex ; appliquer la méthode par amélioration 
itérative décrite cidessus au tour initial induit par la permutation (0, 1, 2, 
3, 4).
 22 ­ On considère encore le graphe G_ex ; appliquer la méthode par 
amélioration itérative décrite
ci-dessus au tour initial induit par la permutation (1, 0, 4, 2, 3). On pourra 
commencer par redessiner
le graphe de façon que le tour considéré soit le « tour extérieur » du dessin 
du graphe.
 23 ­ Indiquer si le tour obtenu à leissue de la méthode par amélioration 
itérative est ou non toujours
de poids minimum. Justifier la réponse.

Quatrième partie : méthode par séparation et évaluation
On souhaite dans cette partie développer une méthode qui détermine un tour de 
poids minimum. Pour cela,
on va deabord définir puis utiliser leévaluation d'une chaîne.
Soit une chaîne C = (c0, c1, c2, ..., cp ­ 1) constituée de p sommets distincts 
deun graphe complet valué G
deordre n ; en supposant 1  p < n, on utilise les notations ci-dessous : · U est leensemble des sommets de G qui ne sont pas dans C ; autrement dit, U = X ­ {c0, c1, c2, ..., cp ­ 1} ; · pour x = c0 ou x = cp ­ 1, on considère une arête la plus légère parmi les arêtes dont une extrémité est x et leautre est dans U ; eval1(G, C, x) désigne le poids de cette arête ; · pour x  U, on considère deux arêtes les plus légères parmi celles dont une extrémité est x et leautre (distincte de x) est dans U  {c0, cp ­ 1} ; eval2(G, C, x) désigne la somme des poids de ces deux arêtes ; 1 · eval(G, C) = puids(G, C) +   eval 1(G, C , c0 ) + eval 1(G, C , c p -1 ) + eval 2(G, C , x )  , où, si r représente 2 x U un nombre réel, r  représente la partie entière par excès de r, ceest-à-dire le plus petit entier supérieur ou égal à r. 24 ­ Dans le graphe G_ex, on considère la chaîne C_ex = (0, 3, 1) ; calculer eval(G_ex, C_ex). On dit queun tour contient une chaîne C = (c0, c1, c2, ..., cp ­ 1) seil est induit par une permutation (t0, t1, t2, ..., tp ­ 1, tp, ..., tn ­ 1) avec ti = ci pour tout i vérifiant 0 i  p ­ 1. 25 ­ On considère un graphe complet valué G deordre n, un entier p vérifiant 1 p < n, une chaîne C = (c0, c1, c2, ..., cp ­ 1) de G et un tour T contenant la chaîne C. Montrer la relation : puids(G, T)  eval(G, C). Leobjectif est maintenant de construire un algorithme récursif permettant de déterminer un tour de poids minimum dans un graphe complet valué. Page 8 sur 10 Épreuve deinformatique 2008 Dans cette fin de problème, on code tous les tours avec des permutations commençant par le sommet 0 et, pour les chaînes (c0, c1, c2, ..., cp ­ 1) considérées, on a toujours c0 = 0. On définit un algorithme tuur_min qui a pour données : · la matrice des poids deun graphe G deordre n, · une chaîne C = (c0, c1, c2, ..., cp ­ 1) avec 1  p  n, · un tableau nommé meilleur_tuur codant un tour. Seil existe parmi les tours contenant la chaîne C un tour de poids strictement inférieur à celui de meilleur_tuur, lealgorithme, appliqué aux données précédentes, remplace le contenu du tableau meilleur_tuur par une permutation induisant un tour de poids minimum parmi les tours de G contenant la chaîne C. Le principe de cet algorithme est décrit ci-dessous : · si p = n, la chaîne C définit une permutation induisant un tour ; on remplace si nécessaire le contenu de meilleur_tuur par celui de la chaîne C et lealgorithme se termine ; · sinon, on calcule eval(G, C) ; si cette évaluation est supérieure ou égale au poids de meilleur_tuur, il neexiste aucun tour contenant C qui soit de poids strictement inférieur à celui de meilleur_tuur et dans ce cas lealgorithme se termine ; · si lealgorithme ne seest pas terminé ci-dessus, on résout le problème en appliquant lealgorithme tuur_min successivement à chacune des n ­ p chaînes (c0, c1, c2, ..., cp ­ 1, x) prolongeant la chaîne C deun sommet x ne figurant pas dans C. 26 ­ Détailler leapplication de lealgorithme tuur_min au graphe G_ex avec la chaîne (0, 3) et le tableau meilleur_tuur qui contient initialement la permutation (0, 1, 2, 3, 4). Les questions suivantes ont pour objectif la programmation de lealgorithme tuur_min. 27 ­ On considère un graphe complet valué G deensemble de sommets X, un sous-ensemble S de X non vide et différent de X, et un sommet x neappartenant pas à S. Par définition, la fonction summe_deux_plus_legeres calcule le minimum de la somme des poids de deux arêtes distinctes dont une extrémité est x et leautre est dans S. Il seagit de programmer cette fonction en utilisant nécessairement la fonction plus_proche qui a fait leobjet de la question  11. Caml : Écrire en Caml une fonction nommée somme_deux_plus_legeres telle que, · si poids est la matrice donnant les poids des arêtes deun graphe complet valué G deensemble de sommets X, · si S est un tableau codant un sous-ensemble S de X non vide et différent de X, · si x est un entier correspondant à un sommet x de G neappartenant pas à S, alors somme_deux_plus_legeres poids S x renvoie la valeur de la fonction summe_deux_plus_legeres appliquée au graphe G, à leensemble S et à x. Pascal : Écrire en Pascal une fonction nommée somme_deux_plus_legeres telle que : · si poids, de type Matrice, contient les poids des arêtes deun graphe complet valué G deensemble de sommets X, · si n est un entier donnant leordre de G, · si S, de type Table, code un sous-ensemble S de X non vide et différent de X, · si x est un entier correspondant à un sommet x de G neappartenant pas à S, alors somme_deux_plus_legeres(poids, n, S, x) renvoie la valeur de la fonction summe_deux_plus_legeres appliquée au graphe G, à leensemble S et à x. 28 ­ Il seagit de programmer le calcul de leévaluation deune chaîne. Caml : Écrire en Caml une fonction nommée eval telle que, · si poids est la matrice donnant les poids des arêtes deun graphe complet valué G, · si C est un tableau codant une chaîne C ne contenant pas tous les sommets de G, alors eval poids C renvoie la valeur de eval(G, C). Pascal : Écrire en Pascal une fonction nommée eval telle que, · si poids, de type Matrice, contient les poids des arêtes deun graphe complet valué G, Page 9 sur 10 Tournez la page S.V.P. Épreuve deinformatique 2008 · si n est un entier donnant leordre de G, · si C, de type Table, code une chaîne C ne contenant pas tous les sommets de G, · si p est un entier donnant le nombre de sommets de C, alors eval(poids, n, C, p) renvoie la valeur de eval(G, C). 29 ­ Il seagit de programmer lealgorithme récursif tuur_min. Caml : Écrire en Caml une fonction récursive nommée tour_min telle que, · si poids est la matrice donnant les poids des arêtes deun graphe complet valué G, · si C est un tableau codant une chaîne C, · si meilleur_tour est un tableau codant un tour meilleur_tuur de G, alors tour_min poids C meilleur_tour modifie le tableau meilleur_tour selon ce qui est indiqué plus haut concernant lealgorithme tuur_min appliqué à G, C et meilleur_tuur. Pascal : Écrire en Pascal une procédure récursive nommée tour_min telle que, · si poids, de type Matrice, contient les poids des arêtes deun graphe complet valué G, · si n est un entier donnant leordre de G, · si C, de type Table, contient les sommets deune chaîne C, · si p est un entier donnant le nombre de sommets de C, · si meilleur_tour, de type Table, code un tour meilleur_tuur de G, n, C, p, meilleur_tour) modifie le tableau alors tour_min(poids, meilleur_tour selon ce qui est indiqué plus haut concernant lealgorithme tuur_min appliqué à G, C et meilleur_tuur. 30 ­ Proposer une méthode pour déterminer un tour de plus petit poids dans un graphe complet valué en utilisant les algorithmes étudiés dans ce problème. On ne demande pas deécrire cette méthode en langage de programmation. Page 10 sur 10