Mines Option Informatique MP 2012Sujet, corrigé et rapport du jury

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

• un exercice sur les langages rationnels : page 2
• un problème d'algorithmique et programmation : pages 3 à 14

Exercice sur les langages rationnels

Problème d'algorithmique et programmation

Préliminaire concernant la programmation

Figure 1 : le graphe G_0

• le sommet 0_A est couplé au sommet 0_B, et réciproquement ;
• le sommet 2_A est couplé au sommet 3_B, et réciproquement ;
• les sommets 1_A, 3_A, 1_B et 2_B sont non couplés.

Figure 2 : le graphe G_0 et le couplage C_0

Première partie : généralités

Indications pour la programmation

let G0 = [|[|true; true; true; false|];
    [|false; false; false; true|];
    [|true; true; true; true|];
    [|false; false; false; true|];|];;

let C0 = [|0; -1; 3; -1|];;

Fin des indications pour Caml

const MAX = 100;

G0[0,0]:= true; G0[0,1]:= true; G0[0,2]:= true; G0[0,3]:= false;
G0[1,0]:= false; G0[1,1]:= false; G0[1,2]:= false; G0[1,3]:= true;
G0[2,0]:= true; G0[2,1]:= true; G0[2,2]:= true; G0[2,3]:= true;
G0[3,0]:= false; G0[3,1]:= false; G0[3,2]:= false; G0[3,3]:= true;

• 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.

Deuxième partie : un algorithme pour déterminer un couplage maximal

• 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.

Figure 5 : le graphe G_1

• 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.

• 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.

• 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.

Troisième partie : recherche exhaustive d'un couplage de cardinal maximum

• 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.

• 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.

• 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 .

• 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.

Quatrième partie : l'algorithme hongrois

• pour tout indice k pair, x_k est dans A,
• pour tout indice k impair, x_k est dans B,
• le sommet x_0 n'est pas couplé,
• pour tout entier i vérifiant 0 ≤ 2i ≤ p − 1, l'arête {x_(2i), x_(2i + 1)} n'appartient pas à C,
• pour tout entier i vérifiant 2 ≤ 2i ≤ p, l'arête {x_(2i − 1), x_(2i)} appartient à C.

• 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.

• x_0, x_2 et x_4 sont des sommets de A, x_1, x_3 et x_5 sont des sommets de B;
• {x_0, x_1}, {x_1, x_2}, {x_2, x_3}, {x_3, x_4}, {x_4, x_5} sont des arêtes de G;
• x_0 n 'est pas couplé dans C, x_5 n 'est pas couplé dans C;
• x_1 est couplé avec x_2, x_2 n'est pas couplé avec x_3 et x_3 est couplé avec x_4.
  ◻16 - On considère le graphe G_1 et le couplage C_1 constitué des arêtes {0_A, 0_B}, {1_A, 1_B}, {3_A, 2_B}, {4_A, 3_B}, {5_A, 5_B} 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 à C_1 et le seul sommet de B qui puisse être l'extrémité d'une chaîne alternée augmentante relativement à C_1, déterminer une chaîne alternée augmentante

Figure 6 : le graphe G_1 et le couplage C_1

• 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.

• 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 G_1 et un couplage nommé C_1^′ constitué des arêtes {0_A, 0_B}, {2_A, 1_B}, {3_A, 2_B}, {4_A, 4_B}, {5_A, 5_B}, 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 3_B et correspondant aux marques. Indiquer s'il s'agit d'une chaîne alternée augmentante relativement à C_1^′.

Figure 7 : le graphe G_1 et le couplage C_1^′

• 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 j_B n'est pas couplé dans C, la case d'indice j du tableau R contient la valeur -1 ; si le sommet j_B est couplé avec le sommet i_A, 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(x_p) = x_0, x_1, …, x_p 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 x_p; elle transforme alors les tableaux C et R pour qu'ils correspondent à un couplage, obtenu à partir de C et de Ch(x_p), 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 x_p, alors actualiser CRmAmB numero modifie les vecteurs C et R pour obtenir un couplage de cardinal égal à celui de C augmenté de 1 .

• 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 x_p,
  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 .

Figure 8 : le graphe G_2 et le couplage C_2

• 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.

• 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.

• 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.

• 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.

• 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.