Mines Informatique MP 2012

Thème de l'épreuve Langages rationnels. Recherche d'un couplage maximum dans un graphe biparti.
Principaux outils utilisés langages rationnels, programmation impérative, graphes
Mots clefs fermeture, facteurs, parcours, couplage, maximal, maximum, algorithme hongrois, graphe biparti

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


A 2012 INFO. MP ECOLE DES PONTS PARISTECH, SUPAERO (ISAE), ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES DE SAINT-ETIENNE, MINES DE NANCY, TELECOM BRETAGNE, ENSAE PARISTECH (FILIERE MP) ECOLE POLYTECHNIQUE (FILIERE TSI) CONCOURS 2012 EPREUVE d'INFORMATIQUE Filière : MP Durée de l'épreuve : 3 heures. L'utilisation d'une calculatrice est autorisée. Sujet mis à la disposition des concours : CYCLE INTERNATIONAL, ECOLES DES MINES, TELECOM SUDPARIS, TPE-EIVP. L'énoncé de cette épreuve comporte 14 pages. Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : INFORMATIQUE - MP 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 L'épreuve comporte : · un exercice sur les langages rationnels : page 2 · un problème d'algorithmique et programmation : pages 3 à 14 Page 1 sur 14 Épreuve d'informatique 2012 Exercice sur les langages rationnels Un alphabet est un ensemble fini non vide d'éléments appelés lettres. Un mot sur est une suite finie de lettres de ; la longueur d'un mot u est le nombre de lettres composant u ; le mot de longueur nulle est noté . On désigne par * l'ensemble des mots sur , y compris le mot . Un langage sur est une partie de *. On dit qu'un mot f sur , de longueur non nulle, est un facteur d'un mot u sur s'il existe deux mots x et y sur avec u = xfy ; si x est le mot de longueur nulle, on dit que f est un préfixe de u ; si y est le mot de longueur nulle, on dit que f est un suffixe de u. Un mot peut posséder plusieurs occurrences d'un même facteur f. Supposons que l'on ait = {a, b} et f = aabaa. Le mot baabaabbaabaaa contient deux occurrences disjointes du facteur f, de même que le mot aabaaaabaaa. Le mot abaabaaabaabb contient deux occurrences non disjointes du facteur f, de même que le mot aabaabaa ; dans ce dernier cas, la première occurrence de f est un préfixe du mot aabaabaa alors que la seconde occurrence en est un suffixe. Dans tout l'exercice, désigne un alphabet et f désigne un mot de longueur non nulle sur . 1 ­ Montrer que le langage L1 sur des mots qui contiennent au moins une occurrence du facteur f est rationnel. 2 ­ Montrer que le langage L2 sur des mots qui contiennent au moins deux occurrences disjointes du facteur f est rationnel. 3 ­ Montrer que le langage L3 sur des mots qui contiennent au moins deux occurrences non disjointes du facteur f est rationnel. 4 ­ Montrer que le langage L4 sur des mots qui contiennent exactement une occurrence du facteur f est rationnel. Page 2 sur 14 Épreuve d'informatique 2012 Problème d'algorithmique et programmation Préliminaire concernant la programmation Il faudra écrire des fonctions ou des procédures à l'aide d'un langage de programmation qui pourra être soit Caml, soit Pascal, tout autre langage étant exclu. Indiquer en début d'épreuve 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 cela est nécessaire. Lorsque le candidat écrira une fonction ou une procédure, il pourra faire appel à une autre fonction ou procédure définie dans les questions précédentes. Enfin, si les paramètres d'une fonction ou d'une procédure à écrire sont supposés vérifier certaines hypothèses, il ne sera pas utile dans l'écriture de cette fonction ou de cette procédure de tester si les hypothèses sont bien vérifiées. Dans les énoncés du problème, un même identificateur écrit dans deux polices de caractères différentes désignera la même entité, mais du point de vue mathématique pour la police en italique (par exemple n) et du point de vue informatique pour celle en romain (par exemple n). Un graphe G est défini par deux ensembles X et E. L'ensemble X est un ensemble fini d'éléments appelés sommets. L'ensemble E est un ensemble de paires de sommets. Un élément {x, y} de E est appelé arête de G ; x et y sont les extrémités de l'arête. L'ordre d'un graphe G est le nombre de sommets de G. Un graphe est représenté par un dessin où des cercles représentent les sommets et un trait joignant deux cercles représente une arête composée des deux sommets correspondant aux cercles. Si {x, y} est une arête de G, on dit que x et y sont voisins. Le degré d'un sommet x est le nombre de voisins de x. On dit que deux arêtes d'un graphe G sont incidentes si elles ont une extrémité en commun. On appelle couplage dans G un ensemble d'arêtes de G deux à deux non incidentes. Un graphe G est dit biparti si on peut partitionner son ensemble de sommets X en deux sous-ensembles A et B (A , B , A B = X, A B = ) de sorte que toute arête ait une extrémité dans A et une extrémité dans B. Si les ensembles A et B ont même cardinal, on dit qu'il s'agit d'un graphe biparti équilibré. Dans tout le problème, on ne considère que des graphes bipartis équilibrés. On note n le cardinal commun aux ensembles A et B ; l'ordre du graphe est donc égal à 2n. On suppose que l'on a toujours n 1. Les sommets de A sont numérotés de 0 à n ­ 1 et nommés 0A, 1A, 2A, ..., (n ­ 1)A ; les sommets de B sont numérotés de 0 à n ­ 1 et nommés 0B, 1B, 2B, ..., (n ­ 1)B. Une arête de G est toujours écrite en mettant d'abord l'extrémité qui est dans A puis celle qui est dans B. On représente les graphes bipartis équilibrés par des schémas comme on peut le voir dans la figure 1 avec le graphe G0, en représentant les sommets de A à gauche et les sommets de B à droite. Page 3 sur 14 Épreuve d'informatique 2012 Pour G0, n vaut 4 et l'ordre de G0 vaut 8. Les arêtes de G0 sont : {0A, 0B}, {0A, 1B}, {0A, 2B}, {1A, 3B}, {2A, 0B}, {2A, 1B}, {2A, 2B}, {2A, 3B}, {3A, 3B}. Le sommet 0A est de degré 3. Le sommet 1A est de degré 1. Le sommet 2A est de degré 4. Le sommet 3A est de degré 1. Les sommets 0B, 1B et 2B sont de degré 2. Le sommet 3B est de degré 3. Dans le graphe G0, les arêtes {0A, 0B} et {2A, 3B} étant non incidentes, elles forment un couplage, nommé C0, dont les arêtes sont dessinées en gras ci-contre ; on dit alors que dans ce couplage : · le sommet 0A est couplé au sommet 0B, et réciproquement ; · le sommet 2A est couplé au sommet 3B, et réciproquement ; · les sommets 1A, 3A, 1B et 2B sont non couplés. 0A 0B 1A 1B 2A 2B 3A 3B Figure 1 : le graphe G0 00A 0B 1A 1B 2A 2B 3A 3B Figure 2 : le graphe G0 et le couplage C0 Le cardinal d'un couplage est le nombre d'arêtes de celui-ci ; par exemple le cardinal de C0 vaut 2. Première partie : généralités 5 ­ Exhiber un couplage de cardinal 3 dans G0. 6 ­ Indiquer s'il existe dans G0 un couplage de cardinal 4. Justifier la réponse. Un graphe biparti équilibré d'ordre 2n est représenté par une matrice carrée de dimension n × n dont les lignes correspondent aux éléments de A et les colonnes aux éléments de B. Les cases de cette matrice sont indicées par (i, j) avec 0 i n ­ 1, 0 j n ­ 1 et contiennent des valeurs booléennes : la case d'indice (i, j) contient la valeur « vrai » (ou true dans le langage de programmation) si {iA, jB} est une arête du graphe ; elle contient la valeur « faux » (ou false dans le langage de programmation) dans le cas contraire. Le graphe G0 ci-dessus est donc représenté par la matrice suivante : Page 4 sur 14 Épreuve d'informatique 2012 i j 0 1 2 3 0 vrai vrai vrai faux 1 faux faux faux vrai 2 vrai vrai vrai 3 faux faux faux vrai vrai Figure 3 : la matrice représentant G0 Un couplage est représenté par un tableau d'entiers indicé de 0 à n ­ 1. Soit i vérifiant 0 i n ­ 1 ; si le sommet iA est couplé avec le sommet jB, la case d'indice i contient la valeur j ; si le sommet iA n'est pas couplé, la case d'indice i contient une valeur égale à ­1. Le couplage C0 de G0, formé des arêtes {0A, 0B} et {2A, 3B}, est représenté par le tableau cidessous : 0 1 2 3 0 ­1 3 ­1 Figure 4 : le tableau représentant C0 i Indications pour la programmation Caml : Un vecteur est par la suite nommé aussi tableau. On nomme matrice un tableau à deux dimensions (un vecteur de vecteurs). La matrice représentant un graphe biparti équilibré d'ordre 2n est codée en Caml par une matrice n × n de booléens. La matrice représentant G0 est ainsi codée par : let G0 = [|[|true; true; true; false|]; [|false; false; false; true|]; [|true; true; true; true|]; [|false; false; false; true|];|];; Un couplage est codé par un vecteur de n entiers ; le couplage C0 est ainsi codé par : let C0 = [|0; -1; 3; -1|];; Une arête a est codée par un vecteur a de deux entiers, avec a.(0) dans A et a.(1) dans B. Fin des indications pour Caml Pascal : on utilise les définitions suivantes : const MAX = 100; type Matrice = array[0 .. MAX - 1, 0 .. MAX - 1] of Boolean; type Tableau = array[0 .. MAX - 1] of Integer; type Arete = array[0 .. 1] of Integer; La constante MAX donne une borne supérieure du cardinal des parties A et B des graphes bipartis équilibrés considérés, c'est-à-dire de la moitié de l'ordre du graphe ; il ne sera pas utile de vérifier cette condition dans la programmation. Le type Matrice sert à coder les graphes bipartis équilibrés. La matrice représentant le graphe G0 est ainsi codée par G0 de type Matrice avec : Page 5 sur 14 Épreuve d'informatique 2012 G0[0,0]:= G0[1,0]:= G0[2,0]:= G0[3,0]:= true; false; true; false; G0[0,1]:= G0[1,1]:= G0[2,1]:= G0[3,1]:= true; false; true; false; G0[0,2]:= G0[1,2]:= G0[2,2]:= G0[3,2]:= true; false; true; false; G0[0,3]:= G0[1,3]:= G0[2,3]:= G0[3,3]:= false; true; true; true; Le type Tableau a plusieurs usages. Il sert entre autres à coder un couplage ; le couplage C0 est ainsi codé par C0 de type Tableau avec : C0[0] := 0; C0[1] := -1; C0[2] := 3; C0[3] := -1; Une arête a est codée par un tableau a de type Arete, avec a[0] dans A et a[1] dans B. Fin des indications pour Pascal 7 ­ Soit G un graphe biparti équilibré d'ordre 2n. On considère un tableau C d'entiers de longueur n et contenant dans ses cases indicées de 0 à n ­ 1 soit la valeur ­1, soit une valeur comprise entre 0 et n ­ 1. Il s'agit de savoir si ce tableau C représente ou non un couplage dans G. Caml : Écrire en Caml une fonction verifie telle que, · si G est une matrice codant le graphe G, · si C est un vecteur codant le tableau C, alors verifie G C renvoie true si le tableau C représente un couplage dans G et false sinon. Indiquer la complexité de la fonction verifie. Pascal : Écrire en Pascal une fonction verifie telle que, · si G, de type Matrice, code le graphe G, · si C, de type Tableau, code le tableau C, · si n, de type Integer, contient la valeur de n, alors verifie(G, C, n) renvoie true si le tableau C représente un couplage dans G et false sinon. Indiquer la complexité de la fonction verifie. 8 ­ On considère un tableau C, de longueur n, codant un couplage d'un graphe G. Il s'agit d'écrire une fonction qui calcule le cardinal de ce couplage. Caml : Écrire en Caml une fonction cardinal telle que, si C est un vecteur codant un couplage, alors cardinal C renvoie le cardinal de ce couplage. Indiquer la complexité de la fonction cardinal. Pascal : Écrire en Pascal une fonction cardinal telle que, · si C, de type Tableau, code un couplage C, · si n, de type Integer, contient la valeur de n, alors cardinal(C, n) renvoie le cardinal de C. Indiquer la complexité de la fonction cardinal. Page 6 sur 14 Épreuve d'informatique 2012 Deuxième partie : un algorithme pour déterminer un couplage maximal On dit qu'un couplage C dans un graphe G est maximal si toute arête de G n'appartenant pas à C est incidente à au moins une arête de C. Par exemple, le couplage C0 de G0 est maximal. Un couplage maximal de G n'est pas forcément de cardinal maximum parmi les couplages de G. On cherche à concevoir un algorithme qui détermine un couplage maximal dans un graphe biparti équilibré G. L'algorithme, nommé algo_approche, est le suivant : · on commence avec un couplage vide C ; · tant que G possède au moins une arête : - on choisit une arête a de G dont la somme des degrés des extrémités soit minimum ; - on ajoute l'arête a au couplage C ; - on retire de G l'arête a et toutes les arêtes incidentes à a. On admettra que le résultat est, par construction, un couplage maximal. 9 ­ Appliquer algo_approche au graphe G0 (voir la figure 1 page 4). On considère par la suite le graphe biparti équilibré G1 d'ordre 12 représenté sur la figure 5. 0A 0B 1A 1B 2A 2B 3A 3B 4A 4B 5A 5B Figure 5 : le graphe G1 10 ­ On applique algo_approche au graphe G1. Déterminer la première arête a1 choisie par algo_approche ; tracer le graphe obtenu après suppression de a1 et des arêtes incidentes à a1. Montrer que le couplage obtenu par algo_approche est de cardinal au plus 5 et indiquer s'il est de cardinal maximum parmi les couplages de G1. 11 ­ Soit G un graphe biparti équilibré d'ordre 2n. Il s'agit d'écrire en langage de programmation une fonction arete_min qui détermine une arête de G dont la somme des degrés des extrémités soit minimum. Si le graphe possède au moins une arête, cette fonction modifie un tableau a de deux entiers reçu en paramètre pour mettre dans les deux cases de a les numéros des deux extrémités d'une arête qui atteint ce minimum ; dans ce cas, la fonction renvoie la valeur « vrai » (true) ; sinon, elle renvoie la valeur « faux » (false). Caml : Écrire en Caml une fonction arete_min telle que : · si G est une matrice codant le graphe G, · si a est un vecteur de deux entiers, alors arete_min G a effectue les opérations décrites ci-dessus, en modifiant le tableau a dans le cas où G possède au moins une arête. Indiquer la complexité de la fonction arete_min. Page 7 sur 14 Épreuve d'informatique 2012 Pascal : Écrire en Pascal une fonction arete_min telle que : · si G, de type Matrice, code le graphe G, · si n, de type Integer, contient la valeur de n, · si a est de type Arete, alors arete_min(G, n, a) effectue les opérations décrites ci-dessus en modifiant le tableau a dans le cas où G possède au moins une arête. Indiquer la complexité de la fonction arete_min. 12 ­ Il s'agit d'écrire en langage de programmation une fonction ou une procédure supprimer qui supprime d'un graphe biparti équilibré une arête a donnée et toutes les arêtes incidentes à a. Caml : Écrire en Caml une fonction supprimer telle que : · si G est une matrice codant un graphe biparti équilibré G, · si a est un vecteur de deux entiers codant une arête a de G, alors supprimer G a modifie G pour que, après modifications, G code le graphe obtenu à partir de G en supprimant a et toutes les arêtes incidentes à a. Indiquer la complexité de la fonction supprimer. Pascal : Écrire en Pascal une procédure supprimer telle que : · si G, de type Matrice, code un graphe biparti équilibré G d'ordre 2n, · si n, de type Integer, contient la valeur de n, · si a, de type Arete, code une arête a de G, alors supprimer(G, n, a) modifie G pour que, après l'appel à la procédure, G code le graphe obtenu à partir de G en supprimant a et toutes les arêtes incidentes à a. Indiquer la complexité de la procédure supprimer. 13 ­ Il s'agit de définir en langage de programmation l'algorithme algo_approche décrit au début de la deuxième partie. Caml : Écrire en Caml une fonction algo_approche telle que, si G est une matrice qui code un graphe biparti équilibré G, algo_approche G effectue algo_approche à partir d'une copie de G et renvoie un vecteur codant le couplage obtenu. Indication : on pourra utiliser sans la définir une fonction dupliquer_matrice telle que, si G est une matrice codant un graphe biparti équilibré G, dupliquer_matrice G renvoie une matrice identique à G. Cette fonction sera utilisée pour que la fonction algo_approche ne modifie pas le contenu de la matrice reçue en paramètre. Indiquer la complexité de la fonction algo_approche. Pascal : Écrire en Pascal une fonction algo_approche telle que : · si G, de type Matrice, code un graphe biparti équilibré G d'ordre 2n, · si n, de type Integer, contient la valeur de n, alors algo_approche(G, n) effectue algo_approche et renvoie un tableau de type Tableau codant le couplage obtenu. On fera en sorte que la fonction ne modifie pas la matrice G. Indiquer la complexité de la fonction algo_approche. Page 8 sur 14 Épreuve d'informatique 2012 Troisième partie : recherche exhaustive d'un couplage de cardinal maximum 14 ­ Soit G un graphe biparti équilibré d'ordre 2n. Il s'agit d'écrire en langage de programmation une fonction nommée une_arete qui recherche une arête quelconque de G. Si G possède au moins une arête, la fonction mémorise la première arête rencontrée a dans un tableau (ou vecteur en Caml) de deux entiers reçu en paramètre ; elle arrête alors sa recherche et renvoie la valeur « vrai » (true) ; sinon, la fonction renvoie la valeur « faux » (false). Caml : Écrire en Caml une fonction une_arete telle que : · si G est une matrice codant le graphe G, · si a est un vecteur de deux entiers destiné à coder l'arête a, alors une_arete G a effectue les opérations décrites ci-dessus, en modifiant le vecteur a dans le cas où G possède au moins une arête. Pascal : Écrire en Pascal une fonction une_arete telle que : · si G, de type Matrice, code le graphe G, · si n, de type Integer, contient la valeur de n, · si a, de type Arete, est destiné à coder l'arête a, alors une_arete(G, n, a) effectue les opérations décrites ci-dessus en modifiant le tableau a dans le cas où G possède au moins une arête. 15 ­ On cherche à établir un algorithme récursif, nommé meilleur_couplage, qui permette de déterminer un couplage de cardinal maximum dans un graphe biparti équilibré. Le principe est le suivant. Si le graphe courant ne contient aucune arête, le cardinal maximum d'un couplage est 0 et aucun sommet n'est couplé. Dans le cas contraire, l'algorithme considère une arête quelconque a du graphe courant et recherche successivement : · un couplage de cardinal maximum parmi les couplages du graphe courant ne contenant pas a · un couplage de cardinal maximum parmi les couplages du graphe courant contenant a. L'algorithme déduit alors un couplage de cardinal maximum. Caml : Écrire en Caml une fonction récursive meilleur_couplage telle que, si G est une matrice codant un graphe biparti équilibré G, meilleur_couplage G renvoie un vecteur codant un couplage de cardinal maximum dans G. La fonction utilisera le principe décrit plus haut. Indication : on pourra utiliser sans la définir une fonction dupliquer_matrice telle que, si G est une matrice codant un graphe biparti équilibré G, alors dupliquer_matrice G renvoie une matrice identique à G. Pascal : Écrire en Pascal une fonction récursive meilleur_couplage telle que : · si G, de type Matrice, code un graphe biparti équilibré G d'ordre 2n, · si n, de type Integer, contient la valeur de n, alors meilleur_couplage(G, n) renvoie un tableau de type Tableau codant un couplage de cardinal maximum dans G. La fonction utilisera le principe décrit plus haut. Page 9 sur 14 Épreuve d'informatique 2012 Quatrième partie : l'algorithme hongrois On considère un graphe biparti équilibré G et un couplage C. Une chaîne de G est une suite x0, x1, ..., xk, ..., xp (p 0) de sommets distincts telle que, pour k compris entre 0 et p ­ 1, {xk, xk + 1} est une arête de G. Le sommet x0 s'appelle l'origine de la chaîne et le sommet xp l'extrémité de la chaîne. Une chaîne x0, x1, ..., xk, ..., xp de G, avec p 0, est dite alternée relativement à C si : · pour tout indice k pair, xk est dans A, · pour tout indice k impair, xk est dans B, · le sommet x0 n'est pas couplé, · pour tout entier i vérifiant 0 2i p ­ 1, l'arête {x2i, x2i + 1} n'appartient pas à C, · pour tout entier i vérifiant 2 2i p, l'arête {x2i ­ 1, x2i} appartient à C. Autrement dit : · l'origine de la chaîne est dans A et n'est pas couplée, · la première arête de la chaîne n'est pas dans C, la deuxième est dans C, la troisième n'est pas dans C et ainsi de suite. Une chaîne x0, x1, ..., xp alternée relativement au couplage C est dite chaîne alternée augmentante relativement à C si on a p 1 et si de plus xp n'est pas couplé, ce qui entraîne que xp est dans B. Par exemple, dire qu'une chaîne x0, x1, x2, x3, x4, x5 constitue une chaîne alternée augmentante relativement à un couplage C signifie que : · x0, x2 et x4 sont des sommets de A, x1, x3 et x5 sont des sommets de B ; · {x0, x1}, {x1, x2}, {x2, x3}, {x3, x4}, {x4, x5} sont des arêtes de G ; · x0 n'est pas couplé dans C, x5 n'est pas couplé dans C ; · x1 est couplé avec x2, x2 n'est pas couplé avec x3 et x3 est couplé avec x4. 16 ­ On considère le graphe G1 et le couplage C1 constitué des arêtes {0A, 0B}, {1A, 1B}, {3A, 2B}, {4A, 3B}, {5A, 5B} représentées sur la figure 6 en gras. Après avoir indiqué le seul sommet de A qui puisse être l'origine d'une chaîne alternée augmentante relativement à C1 et le seul sommet de B qui puisse être l'extrémité d'une chaîne alternée augmentante relativement à C1, déterminer une chaîne alternée augmentante relativement à C1. 0A 0B 1A 1B 2A 2B 3A 3B 4A 4B 5A 5B Figure 6 : le graphe G1 et le couplage C1 17 ­ On considère un graphe biparti équilibré G et un couplage C dans G. Montrer que s'il existe une chaîne alternée augmentante relativement à C, alors il existe dans G un couplage dont le cardinal est égal au cardinal de C augmenté de 1. On admet le théorème suivant : un couplage C d'un graphe biparti équilibré G est de cardinal maximum si et seulement s'il n'existe pas dans G de chaîne alternée augmentante relativement à C. Page 10 sur 14 Épreuve d'informatique 2012 Soit G un graphe biparti équilibré. L'algorithme hongrois s'appuie sur le théorème ci-dessus et détermine un couplage de cardinal maximum dans G. L'algorithme débute avec un couplage C de cardinal nul ; tant qu'il existe une chaîne augmentante relativement à C, l'algorithme modifie C pour incrémenter de 1 le cardinal du couplage en utilisant une telle chaîne augmentante. La suite du problème a pour objectif de programmer cet algorithme. On commence par étudier la recherche d'une chaîne alternée augmentante. On considère un graphe biparti équilibré G et un couplage C dans G. On va chercher s'il existe une chaîne alternée augmentante relativement à C. Pour cela, on recherche les sommets qui sont extrémités de chaînes alternées en procédant de proche en proche à partir des sommets de A non couplés. Un sommet y est dit atteint si une chaîne alternée relativement à C et d'extrémité y est mise en évidence. Au départ, tous les sommets non couplés de A (un tel sommet est extrémité d'une chaîne alternée réduite à ce sommet) sont considérés comme atteints ; aucun autre sommet n'est considéré comme atteint. Un sommet y non encore atteint peut être atteint à partir d'un de ses voisins x déjà atteint si on a : · soit y est dans B (et donc x est dans A) et l'arête {x, y} n'est pas dans le couplage C ; · soit y est dans A (et donc x est dans B) et l'arête {y, x} est dans le couplage C. On utilise des marques attribuées aux sommets. Ces marques sont des entiers initialisés à ­1 pour tous les sommets. Lorsqu'un sommet y est atteint à partir d'un sommet x, la marque de y devient égale au numéro de x (on rappelle que le numéro d'un sommet iA ou d'un sommet iB vaut i) ; x est alors l'avant-dernier sommet dans la chaîne alternée Ch(y) d'extrémité y mise en évidence. La chaîne Ch(y) peut être retrouvée à l'envers, de proche en proche, grâce aux marques ; dans cette chaîne, seule l'origine porte une marque de valeur ­1. Si un sommet non couplé y de B est atteint, Ch(y) est une chaîne alternée augmentante relativement à C. Dans le cas où simultanément : · il n'y a plus de sommet non encore atteint qui puisse être atteint, · aucun sommet non couplé de B n'est atteint, on admet qu'il n'existe pas de chaîne alternée augmentante relativement à C. Remarque : les valeurs des marques peuvent dépendre de l'ordre dans lequel on atteint les sommets, sans que cela n'ait d'importance pour la suite du problème. 18 ­ On considère le graphe G1 et un couplage nommé C1 constitué des arêtes {0A, 0B}, {2A, 1B}, {3A, 2B}, {4A, 4B}, {5A, 5B}, en gras sur la figure 7. Certains sommets ont été atteints ; sur la figure 7, les marques attribuées sont portées à côté des sommets, les sommets atteints sont encadrés. Utiliser les marques pour reconstituer la chaîne alternée arrivant dans le sommet 3B et correspondant aux marques. Indiquer s'il s'agit d'une chaîne alternée augmentante relativement à C1. 0 0A 0B 1 ­1 1A 1B 0 1 2A 2B 2 2 3A 3B 3 ­1 4A 4B ­1 ­1 5A 5B ­1 Figure 7 : le graphe G1 et le couplage C1 Page 11 sur 14 Épreuve d'informatique 2012 On considère quatre tableaux : · Un tableau nommé C codant un couplage C. · Un tableau nommé R (pour réciproque) indicé par 0, 1, ..., n ­ 1 ; soit j vérifiant 0 j n ­ 1 ; si le sommet jB n'est pas couplé dans C, la case d'indice j du tableau R contient la valeur ­1 ; si le sommet jB est couplé avec le sommet iA, la case d'indice j du tableau R comporte la valeur i. · Un tableau nommé mA indicé par 0, 1, ..., n ­ 1 servant à contenir les marques des sommets de A. · Un tableau nommé mB indicé par 0, 1, ..., n ­ 1 servant à contenir les marques des sommets de B. 19 ­ On suppose qu'une chaîne Ch(xp) = x0, x1, ..., xp alternée augmentante relativement à un couplage C a été déterminée et codée grâce aux marques. D'après la question 17, il existe un couplage de cardinal égal à celui de C augmenté de 1. La fonction ou procédure actualiser reçoit en paramètres les quatre tableaux décrits ci-dessus ainsi que le numéro de xp ; elle transforme alors les tableaux C et R pour qu'ils correspondent à un couplage, obtenu à partir de C et de Ch(xp), dont le cardinal est celui du couplage C augmenté de 1. Caml : Écrire en Caml une fonction actualiser telle que : · si C, R, mA, mB sont des vecteurs de n entiers qui correspondent à la description donnée plus haut, · si numero est un entier donnant le numéro de xp, alors actualiser C R mA mB numero modifie les vecteurs C et R pour obtenir un couplage de cardinal égal à celui de C augmenté de 1. Pascal : Écrire en Pascal une procédure actualiser telle que : · si les tableaux C, R, mA, mB, de type Tableau, correspondent à la description donnée plus haut, · si numero est un entier donnant le numéro de xp, alors actualiser(C, R, mA, mB, numero) modifie les tableaux C et R pour obtenir un couplage de cardinal égal à celui de C augmenté de 1. 20 ­ On considère le graphe G2 ci-contre et un couplage, nommé C2, constitué des arêtes {0A, 0B}, {2A, 2B}, {3A, 3B}, {4A, 4B} en gras sur la figure 8. Recopier la figure, encadrer tous les sommets qui peuvent être atteints et préciser à côté des sommets les marques obtenues. Indiquer s'il existe dans G2 une chaîne alternée augmentante relativement à C2. 0A 0B 1A 1B 2A 2B 3A 3B 4A 4B Figure 8 : le graphe G2 et le couplage C2 Indication : on procédera de proche en proche à partir du seul sommet non couplé de A, c'est-à-dire à partir du sommet 1A. L'ordre dans lequel on atteint les sommets n'a pas d'importance. Page 12 sur 14 Épreuve d'informatique 2012 On suppose donnés un graphe biparti équilibré G et un couplage C dans G. Les chaînes alternées considérées dans la suite sont toujours des chaînes alternées relativement à C. Les questions 21 et 22 ont pour objectif de programmer un algorithme qui cherche une chaîne alternée augmentante en atteignant les sommets de proche en proche à partir des sommets non couplés de A. 21 ­ On suppose que certains sommets de G peuvent déjà avoir été atteints et les marques calculées en conséquence. On note x un sommet de A ou de B déjà atteint. On définit deux nouvelles fonctions, les fonctions chercherA et chercherB. Appliquée au sommet x, appelé sommet de départ, la fonction chercherA (si x est dans A) ou la fonction chercherB (si x est dans B) détermine des sommets non encore atteints qui peuvent être atteints, de voisin en voisin, récursivement, à partir de x, modifie les marques de ces sommets nouvellement atteints et s'arrête dans les cas suivants : · un sommet y de B non couplé a été atteint ; elle renvoie alors le numéro du sommet y ; · tous les sommets qui peuvent être atteints de voisin en voisin à partir de x l'ont été et aucun sommet non couplé de B n'est atteint ; elle renvoie alors la valeur ­1. Il s'agit d'écrire les deux fonctions chercherA et chercherB en utilisant une récursivité croisée, chacune des deux fonctions pouvant faire appel à l'autre. Caml : Définir ce qu'on appelle récursivité croisée et indiquer comment elle peut être implémentée en Caml. Écrire en Caml les deux fonctions chercherA et chercherB ; chacune de ces deux fonctions reçoit en paramètres : · une matrice G codant le graphe G ; · quatre vecteurs de longueur n pour les quatre tableaux décrits plus haut : C, R, mA et mB ; · un entier codant le numéro du sommet de départ de la recherche. Ces deux fonctions modifient les vecteurs mA et mB conformément à la description cidessus. Elles renvoient le numéro d'un sommet atteint non couplé de B ou la valeur ­1 selon le cas. Pascal : Définir ce qu'on appelle récursivité croisée et indiquer comment elle peut être implémentée en Pascal. Écrire en Pascal les deux fonctions chercherA et chercherB ; chacune de ces deux fonctions reçoit en paramètres : · une matrice G, de type Matrice, codant le graphe G ; · quatre tableaux de type Tableau pour les quatre tableaux décrits plus haut : C, R, mA et mB ; · un entier n contenant la valeur de n donnant le cardinal commun à A et B ; · un entier codant le numéro du sommet de départ de la recherche. Ces deux fonctions modifient les tableaux mA et mB conformément à la description cidessus. Elles renvoient le numéro d'un sommet atteint non couplé de B ou la valeur ­1 selon le cas. Page 13 sur 14 Épreuve d'informatique 2012 22 ­ On suppose donnés un graphe biparti équilibré G d'ordre 2n et un couplage C dans G. Tous les sommets de G possèdent une marque égale à ­1. La fonction chaine_alternee cherche s'il existe une chaîne alternée augmentante en appliquant la fonction chercherA successivement à partir des sommets non couplés de A. Caml : Écrire en Caml la fonction chaine_alternee telle que : · si G est une matrice codant le graphe G, · si C, R, mA et mB correspondent à la description donnée précédemment, toutes les cases de mA et mB étant initialisées à ­1, alors chaine_alternee G C R mA mB renvoie : · ­1 s'il n'existe pas de chaîne alternée augmentante, · le numéro de l'extrémité d'une chaîne alternée augmentante dans le cas contraire. De plus, la fonction modifie les vecteurs mA et mB pour qu'ils contiennent les marques des sommets à la fin de l'exécution de la fonction. Pascal : Écrire en Pascal la fonction chaine_alternee telle que : · si G, de type Matrice, code le graphe G, · si C, R, mA et mB, de type Tableau, correspondent à la description donnée précédemment, les cases de mA et mB d'indices compris entre 0 et n ­ 1 étant initialisées à ­1, · si n, de type Integer, contient la valeur de n, alors chaine_alternee(G, C, R, mA, mB, n) renvoie : · ­1 s'il n'existe pas de chaîne alternée augmentante, · le numéro de l'extrémité d'une chaîne alternée augmentante dans le cas contraire. De plus, la fonction modifie les tableaux mA et mB pour qu'ils contiennent les marques des sommets à la fin de l'exécution de la fonction. 23 ­ Dans cette question, on programme l'algorithme hongrois. Caml : Écrire en Caml la fonction algorithme_hongrois telle que, si G est une matrice codant un graphe biparti équilibré G, alors algorithme_hongrois G renvoie un vecteur codant le couplage obtenu par l'algorithme hongrois. Pascal : Écrire en Pascal la fonction algorithme_hongrois telle que : · si G, de type Matrice, code un graphe biparti équilibré G d'ordre 2n, · si n, de type Integer, contient la valeur de n, alors algorithme_hongrois(G, n) renvoie un tableau de type Tableau codant le couplage obtenu par l'algorithme hongrois. Page 14 sur 14

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


 Mines Informatique MP 2012 -- Corrigé Ce corrigé est proposé par Gautier Marti (ENS Lyon) ; il a été relu par Benjamin Monmege (ENS Cachan) et Guillaume Batog (Professeur agrégé). Ce sujet est composé d'un exercice portant sur la théorie des langages et d'un problème consacré aux graphes. L'exercice invite à montrer que quatre langages donnés sont rationnels. Ils sont définis comme l'ensemble des mots contenant une ou plusieurs occurrences d'un mot fixé. Cette exercice permet de vérifier la maîtrise des différentes techniques de preuve de rationalité d'un langage. Le problème aborde, quant à lui, des problèmes de couplage sur les graphes bipartis équilibrés. Un couplage, comme son nom l'indique, est un ensemble de couples. Ces couples doivent vérifier certaines propriétés. Considérons par exemple n femmes et n hommes. Chaque femme a ou n'a pas une affinité pour un homme donné. De la même manière, un homme aime ou n'aime pas une femme donnée. En tant qu'agence matrimoniale, l'objectif est de former le maximum de couples en respectant les affinités de chacun. · La première partie permet de bien s'approprier la définition de couplage en traitant un exemple et en écrivant des fonctions simples qui seront réutilisées par la suite. · Le sujet aborde ensuite, en deuxième partie, la notion de couplage maximal, intuitivement un couplage qu'il est impossible de faire croître. Un algorithme permettant de le construire est donné dans le sujet. Le but de la partie est de l'implémenter, en commençant par l'appliquer à la main sur deux exemples. Les fonctions à écrire sont courtes et ne présentent pas de difficultés majeures. · La troisième partie consiste en l'implémentation d'un algorithme naïf de construction d'un couplage de cardinal maximum. · Enfin la partie 4, la plus difficile, présente l'algorithme hongrois, qui est la version polynomiale de l'algorithme en temps exponentiel de la partie précédente. Les questions sont diverses : des applications de l'algorithme sur des exemples, une question théorique et des programmes à écrire. Ce sujet est de longueur raisonnable, il était possible de le traiter en majeure partie le jour du concours. L'aspect programmation y est bien représenté. Le travail sur des tableaux incite naturellement à la programmation impérative alors que les parcours de graphe s'effectuent plus aisément avec la récursivité. La principale difficulté du sujet consiste en l'assimilation des nombreuses définitions ; les applications sur les exemples ont pour but d'aider à les intégrer. Les graphes ne figurent pas explicitement au programme mais apparaissent de manière récurrente dans les sujets des Mines. Bien que les notions utiles à la résolution du problème soient parfaitement définies dans le sujet, une familiarité avec ces dernières est un avantage certain le jour du concours. Indications Exercice 1 Écrire une expression rationnelle décrivant L1 . 3 Déterminer la forme de f . Se souvenir qu'un langage fini est rationnel. 4 Utiliser les propriétés de clôture des langages rationnels. Problème 6 Remarquer que les sommets 1A et 3A jouent un rôle particulier. 7 Ne pas oublier de vérifier que les arêtes du couplage sont effectivement des arêtes du graphe. 10 Se rendre compte que le graphe est coupé en deux sous-graphes disjoints bipartis non équilibrés. 11 Créer deux tableaux qui contiennent le degré d'un sommet, un pour A et un pour B. Penser à utiliser 2 boucles for imbriquées pour considérer toutes les arêtes possibles du graphe. 15 Pour une arête donnée, déterminer récursivement les meilleurs couplages obtenus en choisissant cette arête ou non puis comparer leurs cardinaux. 17 Construire un couplage C en considérant les arêtes d'une chaîne alternée augmentante relativement au couplage C qui ne sont pas dans C. 19 Utiliser une fonction récursive qui prend en paramètre un sommet de B, celle-ci saute un sommet sur deux (les sommets de A) de la chaîne alternée augmentante. Exercice sur les langages rationnels 1 L'expression rationnelle · f · décrit le langage L1 , donc L1 est rationnel. Rappelons que tout langage rationnel est décrit par une infinité d'expressions rationnelles équivalentes. L'expression rationnelle ci-dessus est la réponse la plus naturelle. On pourrait répondre aux questions de l'exercice, grâce au théorème de Kleene, par un automate fini A. Il faudrait alors prouver que le langage reconnu par l'automate fini est bien le langage L de la question en montrant la double inclusion L(A) L et L L(A). C'est une perte de temps le jour du concours. Par exemple, pour f = aba, le langage reconnu par l'automate suivant est L1 . a,b a,b 0 a 1 b 2 a 3 2 L'expression rationnelle · f · · f · décrit le langage L2 . Par conséquent, L2 est rationnel. 3 Soit C(f ) l'ensemble des mots de préfixe et suffixe f non disjoints. Formellement, C(f ) = {uvw | f = uv = vw avec u, v, w et v 6= } Un mot w appartient à L3 si et seulement si w possède un facteur dans C(f ). Comme f est fini, C(f ) est fini. Par conséquent, C(f ) est rationnel puisque tout langage fini est rationnel car c'est une union finie des singletons des mots qui la composent. Le langage est aussi rationnel. Puisque la famille des langages rationnels est fermée par concaténation, il vient que L3 = {x · c · y | x , y , c C(f )} est rationnel. 4 Les mots qui contiennent exactement une occurrence du facteur f sont les mots qui contiennent au moins une occurrence de f mais qui ne contiennent pas au moins c deux occurrences disjointes ou non de f , par conséquent L4 = L1 (L2 L3 ). D'après les questions 1, 2 et 3 les langages L1 , L2 et L3 sont rationnels. Puisque la famille des langages rationnels est fermée par union, intersection et complémentaire, L4 est un langage rationnel. La clôture par intersection et complémentaire des langages reconnaissables par automate fini se montre facilement et le théorème de Kleene permet de conclure pour les langages rationnels. Problème d'algorithmique et programmation I. Généralités 5 Le couplage {(0A , 0B ), (1A , 3B ), (2A , 1B )} convient. 6 Il n'existe pas de couplage de cardinal 4. En effet, supposons par l'absurde qu'un tel couplage existe. Chaque sommet de A est alors couplé avec un unique sommet de B. Considérons le sommet 1A . Le degré de ce sommet est 1, il est donc couplé avec 3B son unique voisin. L'arête (1A , 3B ) appartient au couplage. Considérons à présent le sommet 3A , son degré est 1, il est nécessairement couplé à son unique voisin 3B . L'arête (3A , 3B ) appartient donc au couplage. Or, (1A , 3B ) et (3A , 3B ) sont incidentes ce qui contredit la définition de couplage. 0A 0B 1A 1B 2A 2B 3A 3B Il n'existe pas de couplage de cardinal 4 dans G0 . 7 Pour vérifier que le tableau C représente un couplage dans G, il suffit de vérifier qu'une arête du couplage C est effectivement une arête du graphe G et que chaque sommet de B apparaît au plus une fois dans le couplage C à l'aide d'un tableau de booléens indicé par les sommets de B. let verifie G C = let n = vect_length G in let resultat = ref true in let couple = make_vect n false in let sommet = ref 0 in while !sommet < n && !resultat do if C.(!sommet) <> -1 then begin if not G.(!sommet).(C.(!sommet)) || couple.(!sommet) then resultat := false; couple.(!sommet) <- true end; incr sommet done; !resultat;; La fonction verifie est constituée d'une boucle exécutée au plus n fois et le corps de cette boucle contient un test et des instructions réalisés en temps constant. La fonction verifie a une complexité en O(n).