Mines Informatique MP 2008

Thème de l'épreuve Intersection de langages reconnaissables. Problème du voyageur de commerce.
Principaux outils utilisés langages rationnels, complexité, programmation impérative
Mots clefs Voyageur de commerce, branch and bound, séparation et évaluation, automates

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


É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

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Mines Informatique MP 2008 -- Corrigé Ce corrigé est proposé par Marc Mezzarobba (ENS Ulm) ; il a été relu par Benjamin Monmege (ENS Cachan) et Vincent Puyhaubert (Professeur en CPGE). Comme souvent aux Mines, l'énoncé se compose de deux problèmes indépendants, de tailles inégales. · Le premier, conçu pour occuper un peu moins du quart du temps imparti, est consacré au calcul d'un automate déterministe reconnaissant l'intersection des langages acceptés par deux automates donnés. Proche du cours, il fait appel aux principales opérations sur les automates, comme la déterminisation et la réalisation algorithmique des propriétés de clôture de la classe des langages rationnels. En revanche, il n'utilise pas la notion d'expression rationnelle et ne contient aucune question de programmation. · Le deuxième problème porte sur le thème classique d'optimisation combinatoire dit du voyageur de commerce. C'est principalement un exercice de programmation, centré sur la manipulation de graphes en style impératif. La majorité des questions demandent soit d'écrire des programmes, soit de traiter des exemples à la main ; il faut aussi calculer les complexités de quelques fonctions simples. Ce problème est lui-même divisé en quatre parties de difficulté (lentement) croissante. La première se limite à quelques préliminaires d'algorithmique des graphes. Les deux suivantes abordent deux heuristiques pour calculer des solutions approchées au problème du voyageur de commerce : la méthode du plus proche voisin et la méthode de recherche locale « 2-opt ». Enfin, la dernière partie présente un algorithme de recherche par séparation et évaluation pour résoudre le problème de façon exacte. Dans l'ensemble, il s'agit d'un problème un peu long, d'une difficulté moyenne, que l'on peut recommander pour travailler sur les traits impératifs de Caml (tableaux, références, etc.). Par ailleurs, la méthode séparation et évaluation, mieux connue sous son nom anglais branch and bound, dont l'algorithme de la quatrième partie donne un exemple, est une technique générale de conception d'algorithmes utile dans de nombreuses situations : il faut au moins en connaître l'idée générale. Indications Problème I 3 On souhaite qu'un calcul de A d'étiquette m simule l'exécution en parallèle d'un calcul de A1 et d'un calcul de A2 , tous deux d'étiquette m. Comment choisir T ? 5 Prendre T = T. On se rappellera aussi qu'un automate déterministe complet a un et un seul calcul étiqueté par chaque mot sur son alphabet d'entrée. 7 Utiliser la question 5. Problème II 8 Caractériser les ensembles de permutations qui induisent un même tour. Pour estimer si la méthode proposée est raisonnable, on peut par exemple comparer le nombre de tours dans un graphe de taille 50 au nombre d'opérations élémentaires qu'un microprocesseur actuel fait en un an. 11 Pour parcourir les sommets appartenant à un ensemble S, il suffit de visiter tous les sommets par une boucle du type for s = 0 to n-1, et de tester à chaque itération si s S à l'aide du tableau S représentant S. 15 Utiliser la fonction plus_proche écrite à la question 11, en modifiant convenablement l'ensemble S entre les appels. 16 Utiliser le résultat de la question 12. 19 Observer qu'un vecteur codant le tour 2-opt(T, 1, 6) s'obtient en « retournant » une partie d'un vecteur codant T. 22 Le tour cherché est de poids 18. 23 Comparer les résultats des deux questions précédentes. 25 Montrer l'inégalité 2 n-1 P i=p-1 poids({ti , ti+1 }) > eval1(G, C, c0 ) + eval1(G, C, cp-1 ) P + eval2(G, C, x) xU 27 Appeler deux fois plus_proche, et modifier le tableau S avant et après le second appel. 28 Utiliser les fonctions écrites aux questions 9, 11 et 27 ; introduire un tableau représentant initialement U et le modifier de façon appropriée au cours du calcul, comme à la question 27. 29 Combiner judicieusement les trois méthodes étudiées dans le problème. Les conseils du jury Étant donné que la présentation et la rédaction ont été jugées « bonnes dans l'ensemble », le jury dispense peu de conseils dans son rapport si ce n'est de faire des indentations correctes dans les codes et de réaliser des dessins d'automates que le correcteur puisse interpréter sans difficulté. En outre, le jury regrette que « plusieurs candidats omettent de faire des références explicites aux questions déjà traitées dans le sujet lors de la réponse à une question qui nécessite l'utilisation d'un résultat déjà établi ». I. Problème sur les automates Le rapport du jury déplore de « grosses faiblesses dans le traitement [de ce] problème ». En particulier, les questions 3 et 5 réclamaient des preuves qui sont « rarement bien faite[s] ». Prenez le temps de justifier vos réponses par des démonstrations rigoureuses, à plus forte raison quand l'énoncé le demande explicitement ! Les autres questions sont « souvent bien traitée[s] ». Les correcteurs relèvent cependant des « difficultés surprenantes » par rapport aux années précédentes. « Donner un automate simple semble au-dessus des compétences de nombreux candidats. Beaucoup ont été perturbés par les définitions (pourtant classiques) d'états accessibles et d'automates déterministes et/ou complets. » 1 L'automate A1 _ex représenté ci-dessous reconnaît le langage L1 _ex . a 1 2 b a, b 3 a, b Malgré la simplicité de la question, le rapport du jury constate « un nombre important de mauvaises réponses ». 2 L'automate A2 _ex ci-dessous reconnaît le langage L2 _ex . 4 a, b 5 a, b 6 a, b 3 Adoptons T = (p1 , p2 ), x, (q1 , q2 ) Q × × Q (p1 , x, q1 ) T1 et (p2 , x, q2 ) T2 Pour tout mot m et tous états p1 , q1 Q1 , p2 , q2 Q2 , cette définition entraîne m m m que (p1 , p2 ) -- (q1 , q2 ) est un calcul de A si et seulement si p1 -- q1 et p2 -- q2 sont des calculs, respectivement, de A1 et A2 . De plus, au vu des définitions de I m m et F, le calcul (p1 , p2 ) -- (q1 , q2 ) est réussi (dans A) si et seulement si p1 -- q1 m (dans A1 ) et p2 -- q2 (dans A2 ) le sont tous les deux. Ainsi un mot m est reconnu par A si et seulement s'il est reconnu à la fois par A1 et par A2 , autrement dit l'automate A reconnaît le langage L1 L2 . En conclusion, on obtient un automate qui reconnaît L en prenant T = (p1 , p2 ), x, (q1 , q2 ) Q × × Q (p1 , x, q1 ) T1 et (p2 , x, q2 ) T2 Donner la bonne expression pour T n'est pas suffisant ! Le rapport de jury signale la formule est souvent correcte, mais qu'il y a deux inclusions à prouver pour la justifier. Cette question présente un exemple de construction d'automate produit reconnaissant l'intersection de deux langages. Des constructions similaires s'appliquent à diverses autres opérations ensemblistes sur les langages rationnels, et reviennent fréquemment dans les sujets de concours. 4 On construit les états accessibles de proche en proche, en suivant toutes les transitions possibles à partir de l'état initial. L'automate A3 _ex obtenu est représenté ci-dessous. Informellement, on peut raisonner comme suit : « Au début du calcul, on est dans l'état 1 dans le calcul de A1 _ex et dans l'état 4 dans celui A2 _ex, soit dans l'état (1, 4) du produit. De là, en lisant un a, on se retrouve dans les états 2 (dans le premier calcul) et 5 (dans le deuxième) ; tandis qu'en lisant un b, on aboutit en 3 et en 5 ; donc les transitions de A3 _ex issues de (1, 4) a b sont (1, 4) -- (2, 5) et (1, 4) -- (3, 5). Maintenant, depuis l'état 2, on reste sur place quoi qu'on lise, tandis que depuis 5 on va en 6... » Naturellement, il est aussi possible de commencer par dessiner tous les états, puis toutes les transitions données par la définition, et de supprimer ensuite les états inaccessibles. Mais sur un gros automate, c'est beaucoup moins efficace. Attention si vous répondez à ce genre de question directement au propre, le rapport de jury a relevé « des dessins d'automates difficiles à interpréter ». (1, 4) a b (2, 4) a, b (2, 5) a, b (2, 6) a, b (3, 4) a, b (3, 5) a, b (3, 6) a, b A3 _ex Les états (3, q2 ) de A3 _ex ne sont pas coaccessibles mais sont accessibles, il est demandé de les dessiner. On pourrait cependant les remplacer par un unique état puits sans changer le langage reconnu par l'automate.