ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE, 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 D'ADMISSION 2008
ÉPREUVE D'INFORMATIQUE
Filière MPDurée de l'épreuve : 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 sont priés de mentionner de façon apparente sur la première page de la copie :
INFORMATIQUE - MP
L'énoncé de cette épreuve comporte 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
L'épreuve comporte deux problèmes indépendants :
un problème sur les automates, pages 2 et 3 ;
un problème d'algorithmique et programmation, pages 3 à 10 .
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 d'éléments appelés lettres. Un mot sur est une suite finie de lettres de . La longueur d'un mot , notée , 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 l'ensemble des mots sur , y compris le mot vide. Un langage sur est une partie de .
Un automate est décrit par une structure , où :
est un alphabet ;
est un ensemble fini et non vide appelé ensemble des états de ;
est appelé l'ensemble des transitions ; étant donnée une transition ( ) , on dit qu'elle va de l'état à l'état et qu'elle est d'étiquette ; on pourra la noter ;
est appelé ensemble des états initiaux de ;
est appelé ensemble des états finals de .
Un calcul de est une suite de la forme où, pour , est une transition; est l'origine du calcul, son extrémité. L'étiquette de est le mot formé par la suite des étiquettes des transitions successives.
Un calcul d'origine , d'extrémité et d'étiquette peut être noté . Un calcul de est dit réussi si on a et . Un mot de est reconnu par s'il est l'étiquette d'un calcul réussi. Le langage reconnu par , noté , est l'ensemble des mots reconnus par . Un langage est dit reconnaissable s'il existe un automate qui le reconnaît.
Un état d'un automate est dit accessible s'il existe dans au moins un calcul dont l'origine est un état initial et dont l'extrémité est .
L'automate est dit déterministe si contient exactement un élément et si, pour tout et tout , il existe au plus un état avec . L'automate est dit complet si, pour tout et tout , il existe au moins un état avec .
Pour les exemples de ce problème, on utilisera l'alphabet .
1 - Soit le langage sur des mots qui commencent par . Représenter graphiquement un automate déterministe et complet noté qui reconnaît , c'est-à-dire vérifiant ; cet automate aura trois états nommés . L'état 1 sera l'unique état initial et l'état 2 l'unique état final.
2 - Soit ex le langage sur des mots dont la longueur est multiple de 3. Représenter graphiquement un automate déterministe et complet noté qui reconnaît , c'est-à-dire vérifiant ex ex ; cet automate aura trois états nommés 4, 5, 6. L'état 4 sera l'unique état initial et l'unique état final.
Les questions et sont consacrées à une première méthode pour calculer un automate reconnaissant l'intersection de deux langages reconnaissables.
3 - On considère deux langages et sur un alphabet quelconque . On suppose que est reconnu par un automate ; on suppose que est reconnu par un automate . Montrer que le langage est reconnu par un automate pour lequel :
;
;
.
En particulier, on précisera l'ensemble des transitions de .
4 - En utilisant la construction de la question précédente, représenter graphiquement un automate noté ex ex. On ne représentera que les états accessibles de cet automate.
La suite du problème propose d'appliquer une seconde façon de calculer un automate reconnaissant l'intersection de deux langages reconnaissables.
5 - On considère un langage sur un alphabet quelconque . On suppose que est reconnu par un automate déterministe et complet , où est l'unique état initial de . Montrer que le langage complémentaire de , constitué des mots de qui ne sont pas dans , est reconnu par un automate déterministe et complet ; on précisera les ensembles et ; on justifiera la réponse. En déduire un automate déterministe et complet ex qui reconnaît et un automate déterministe et complet ex qui reconnaît ; ces deux automates seront décrits par leur représentation graphique.
Soient deux automates et reconnaissant respectivement des langages et ; on suppose que les ensembles et sont disjoints; l'union de ces automates est par définition l'automate . On admet que cet automate reconnaît le langage .
6 - On note ex l'automate obtenu par union de et . Représenter graphiquement un automate déterministe et complet obtenu en appliquant à un algorithme classique de déterminisation. On ne représentera que les états accessibles de cet automate.
7 - Déduire de l'automate obtenu à la question , un automate reconnaissant .
2. Problème d'algorithmique et programmation (temps conseillé : 2 h 20 mn )
On s'inté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 à l'aide d'un 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 qu'il explicitera ou faire appel à d'autres fonctions ou procédures définies dans les questions précédentes.
Dans l'é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 ) et du point de vue informatique pour celle écrite en romain (par exemple : ).
Un graphe est défini par un ensemble fini, noté , d'éléments appelés sommets et par l'ensemble de ses arêtes; une arête est une paire de sommets distincts et 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 d'un graphe s'appelle l'ordre du graphe ; tous les graphes considérés dans ce problème sont d'ordre au moins 3. Si un graphe est d'ordre , ses sommets sont nommés dans ce problème. Les graphes considérés ici seront des graphes complets valués, ce qui signifie qu'on attribue à chaque arête un entier naturel nommé poids de cette arête. Dans tout ce problème, les graphes considérés seront d'ordre au plus 100 et les poids ne dépasseront pas 100 .
Un graphe complet valué d'ordre peut être représenté par une matrice carrée symétrique de dimension dont les cases sont indicées par ( ) avec et ; on notera poids cette matrice indiquant dans la case d'indice et le poids poids( ) de l'arête ; par convention, cette matrice a des zéros sur la diagonale. On représente ci-après un graphe complet valué et la matrice poids_ex correspondante.
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
poids_ex
Soit un graphe complet d'ordre . Soit ( ) une permutation de l'ensemble des sommets de . Par définition, le tour induit par cette permutation est un graphe ayant comme ensemble de sommets et dont l'ensemble des arêtes est : . Par exemple, le tour induit par la permutation est représenté en gras ci-dessus.
On appelle poids d'un tour d'un graphe complet valué , et on note poids , la somme des poids des arêtes de dans :
Ainsi : .
Le problème auquel on s'intéresse ici est celui de la détermination d'un tour de tel que poids ( ) soit minimum. On dit alors qu'il s'agit d'un tour de poids minimum.
On appelle dans ce problème chaîne à sommets d'un graphe complet une suite ordonnée de sommets distincts de ; en notant l'ordre de , on a alors nécessairement . Le poids d'une telle chaîne vaut:
Par exemple, pour la chaîne du graphe .
On pourra sans ambiguité évoquer le poids d'une arête, ou le poids d'un tour, ou le poids d'une chaîne.
Indications pour la programmation
Caml : On définit l'identificateur 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) (où est l'ordre du graphe) ; la matrice poids_ex représentant le graphe 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 l'arête du graphe par : poids_ex. (i) . (j).
Un tour est codé par un tableau (vecteur) de dimension égale à l'ordre du graphe et contenant la suite des sommets d'une permutation induisant ce tour. Le tour 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 par :
let C_ex = [|0; 3; 1|];;
On remarque donc qu'une 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
connaître la dimension d'un 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 de l'ensemble des sommets d'un graphe d'ordre est codé par un tableau de longueur donnant la fonction caractéristique de cet ensemble ; ainsi, en notant S ce tableau et un entier compris entre 0 et . (i) vaut 1 si le sommet appartient à et vaut 0 si le sommet n'appartient pas à .
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 l'ordre 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 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 d'un graphe, de type Matrice, s'appelle poids, on peut accéder au poids de l'arête 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 l'indice 0 , la suite des sommets d'une permutation induisant ce tour ;
pour coder une chaîne, on utilise un tableau de type Table contenant, à partir de l'indice 0 , la suite des sommets de cette chaîne ;
un sous-ensemble de l'ensemble des sommets d'un graphe d'ordre ( 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 un entier compris entre 0 et vaut 1 si le sommet appartient à et vaut 0 si le sommet n'appartient pas à .
Fin des indications pour Pascal
Première partie : questions préliminaires
8 - On considère un graphe complet d'ordre . Donner le nombre de tours différents de . 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 vaut 50 ; dire si cette méthode est raisonnable d'un point de vue pratique en justifiant brièvement la réponse.
9 - Il s'agit de calculer le poids d'un 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 d'un graphe complet valué et T un tableau codant un tour de , 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 d'un graphe complet valué , si n est un entier donnant
l'ordre de et si T , de type Table, code un tour de , poids_tour (poids, ) 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 un graphe complet valué d'ensemble de sommets . On considère un sous-ensemble de ; on suppose que est non vide et différent de . Soit un sommet de n'appartenant pas à . Il s'agit de déterminer un sommet de tel que, pour tout sommet de , on ait: poids poids ; si plusieurs sommets sont candidats, on prend pour celui dont le nom est le plus petit. On dira alors que est le sommet de le plus proche de .
Caml : Écrire en Caml une fonction nommée plus_proche telle que,
si poids est la matrice donnant les poids des arêtes d'un graphe complet valué d'ensemble de sommets ,
si S est un tableau codant un sous-ensemble de non vide et différent de ,
si x est un entier correspondant à un sommet de n'appartenant pas à , alors plus_proche poids renvoie un entier correspondant au sommet de le plus proche de .
Pascal : Écrire en Pascal une fonction nommée plus_proche telle que,
si poids, de type Matrice, contient les poids des arêtes d'un graphe complet valué d'ensemble de sommets ,
si n est un entier donnant l'ordre de ,
si S , de type Table, code un sous-ensemble de non vide et différent de ,
si x est un entier correspondant à un sommet de n'appartenant pas à , alors plus_proche(poids, ) renvoie un entier correspondant au sommet de le plus proche de .
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 s'appelle une heuristique.
L'heuristique décrite ci-après s'appelle l'heuristique du plus proche voisin. On dispose d'un graphe complet valué d'ordre et on souhaite déterminer un tour de «faible poids». Pour construire un tel tour , on détermine comme suit une permutation des sommets de induisant ce tour. On choisit d'abord un sommet quelconque du graphe et on le note . On cherche alors, parmi les sommets de autres que , le sommet le plus proche de . On note un tel sommet. On continue ainsi : quand, pour , on a déterminé successivement les sommets , on cherche le sommet de le plus proche de parmi les sommets n'appartenant pas à l'ensemble . Le résultat de l'heuristique du plus proche voisin dépend donc uniquement du choix du sommet de départ, c'est-à-dire de .
13 - Indiquer le tour obtenu par l'heuristique du plus proche voisin si on l'applique au graphe en choisissant le sommet 0 comme sommet de départ. Préciser le poids de ce tour.
14 - Indiquer le tour obtenu par l'heuristique du plus proche voisin si on l'applique au graphe en choisissant le sommet 1 comme sommet de départ. Préciser le poids de ce tour.
15 - L'objectif de cette question est de programmer l'heuristique 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 d'un graphe complet valué d'ordre ,
si depart est une valeur entière vérifiant ,
alors tour_plus_proche poids depart renvoie un tableau de longueur contenant un codage du tour obtenu par l'heuristique 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 d'un graphe complet valué ,
si n est un entier donnant l'ordre de ,
si depart est un entier vérifiant ,
si tour est de type Table,
alors tour_plus_proche(poids, n, depart, tour) remplit le tableau tour pour qu'il contienne un codage du tour obtenu par l'heuristique du plus proche voisin appliquée au sommet de nom depart.
16 - Calculer la complexité de l'algorithme de la question précédente.
17 - À l'aide d'un graphe complet valué d'ordre 4 et en choisissant un sommet de départ de façon appropriée, montrer que l'heuristique 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 d'un tour en un autre; on appelle transformation 2-opt cette transformation; elle est définie comme suit. On note une permutation induisant un tour . Pour définir une transformation 2-opt de , on précise deux entiers et vérifiant : , et ; on définit plus précisément une transformation notée 2-opt ; on pose et modulo ; le tour -opt est le tour dont les arêtes sont obtenues à partir de celles de :
en retirant de les arêtes et ;
en ajoutant les arêtes et .
Les paramètres et de la transformation 2-opt ne sont donc pas des sommets mais des indices de sommets relativement à ; on rappelle que les indices dans commencent à 0 .
18 - Dans un graphe complet d'ordre 8 , on considère le tour induit par la permutation . On pose -opt . Dessiner le tour comme cicontre et représenter le tour sur la même figure par un tracé qui se différencie de celui de (autre couleur, trait plus gras...). Indiquer explicitement une permutation induisant ; on remarquera que cette permutation peut commencer par c'est ce début qui sera retenu. - Il s'agit d'écrire en langage de programmation le calcul d'un tour obtenu par une transformation 2-opt à partir d'un tour donné.
Caml : Écrire en Caml une fonction nommée deux_opt telle que,
si T est un tableau codant un tour d'un graphe d'ordre ,
si i et j sont deux entiers vérifiant et , alors deux_opt T i j transforme le tableau T pour que celui-ci code le tour obtenu par la transformation 2-opt( ).
La fonction ne vérifiera pas que les entiers et 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 d'un graphe d'ordre ,
si i et j sont deux entiers vérifiant et ,
Abstract
alors deux_opt (T, i, j) transforme le tableau T pour que celui-ci code le tour obtenu par la transformation 2-opt( ). L'ordre du graphe n'intervient pas dans l'é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 l'ordre 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 un tour de «faible poids», on peut envisager l'heuristique suivante : on choisit un tour initial qu'on note ; tant qu'il existe une transformation 2-opt transformant en un tour de poids strictement plus petit, on choisit une telle transformation qu'on applique à pour obtenir un nouveau tour qu'on substitue à et qu'on nomme encore . Ainsi, quand l'algorithme se termine, il n'existe aucune transformation 2-opt permettant de transformer le tour final 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 ; appliquer la méthode par amélioration itérative décrite cidessus au tour initial induit par la permutation ( ).
22 - On considère encore le graphe ; appliquer la méthode par amélioration itérative décrite ci-dessus au tour initial induit par la permutation ( ). 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 à l'issue 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 d'abord définir puis utiliser l'évaluation d'une chaîne.
Soit une chaîne constituée de sommets distincts d'un graphe complet valué d'ordre ; en supposant , on utilise les notations ci-dessous :
est l'ensemble des sommets de qui ne sont pas dans ; autrement dit, ;
pour ou , on considère une arête la plus légère parmi les arêtes dont une extrémité est et l'autre est dans désigne le poids de cette arête ;
pour , on considère deux arêtes les plus légères parmi celles dont une extrémité est et l'autre (distincte de est dans désigne la somme des poids de ces deux arêtes ;
, où, si représente un nombre réel, représente la partie entière par excès de , c'est-à-dire le plus petit entier supérieur ou égal à .
24 - Dans le graphe , on considère la chaîne ; calculer .
On dit qu'un tour contient une chaîne s'il est induit par une permutation avec pour tout vérifiant .
25 - On considère un graphe complet valué d'ordre , un entier vérifiant , une chaîne de et un tour contenant la chaîne . Montrer la relation: .
L'objectif est maintenant de construire un algorithme récursif permettant de déterminer un tour de poids minimum dans un graphe complet valué.
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 considérées, on a toujours .
On définit un algorithme tour_min qui a pour données :
la matrice des poids d'un graphe d'ordre ,
une chaîne avec ,
un tableau nommé meilleur_tour codant un tour.
S'il existe parmi les tours contenant la chaîne un tour de poids strictement inférieur à celui de meilleur_tour, l'algorithme, appliqué aux données précédentes, remplace le contenu du tableau meilleur_tour par une permutation induisant un tour de poids minimum parmi les tours de contenant la chaîne . Le principe de cet algorithme est décrit ci-dessous :
si , la chaîne définit une permutation induisant un tour ; on remplace si nécessaire le contenu de meilleur_tour par celui de la chaîne et l'algorithme se termine ;
sinon, on calcule ; si cette évaluation est supérieure ou égale au poids de meilleur_tour, il n'existe aucun tour contenant qui soit de poids strictement inférieur à celui de meilleur_tour et dans ce cas l'algorithme se termine ;
si l'algorithme ne s'est pas terminé ci-dessus, on résout le problème en appliquant l'algorithme tour_min successivement à chacune des chaînes prolongeant la chaîne d'un sommet ne figurant pas dans . - Détailler l'application de l'algorithme tour_min au graphe avec la chaîne et le tableau meilleur_tour qui contient initialement la permutation .
Les questions suivantes ont pour objectif la programmation de l'algorithme tour_min. - On considère un graphe complet valué d'ensemble de sommets , un sous-ensemble de non vide et différent de , et un sommet n'appartenant pas à . Par définition, la fonction somme_deux_plus_legeres calcule le minimum de la somme des poids de deux arêtes distinctes dont une extrémité est et l'autre est dans . Il s'agit de programmer cette fonction en utilisant nécessairement la fonction plus_proche qui a fait l'objet de la question .
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 d'un graphe complet valué d'ensemble de sommets ,
si S est un tableau codant un sous-ensemble de non vide et différent de ,
si est un entier correspondant à un sommet de n'appartenant pas à , alors somme_deux_plus_legeres poids renvoie la valeur de la fonction somme_deux_plus_legeres appliquée au graphe , à l'ensemble et à .
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 d'un graphe complet valué d'ensemble de sommets ,
si n est un entier donnant l'ordre de ,
si S , de type Table, code un sous-ensemble de non vide et différent de ,
si x est un entier correspondant à un sommet de n'appartenant pas à , alors somme_deux_plus_legeres(poids, ) renvoie la valeur de la fonction somme_deux_plus_legeres appliquée au graphe , à l'ensemble et à . - Il s'agit de programmer le calcul de l'évaluation d'une chaîne.
Caml : Écrire en Caml une fonction nommée eval telle que,
si poids est la matrice donnant les poids des arêtes d'un graphe complet valué ,
si C est un tableau codant une chaîne ne contenant pas tous les sommets de , alors eval poids C renvoie la valeur de .
Pascal : Écrire en Pascal une fonction nommée eval telle que,
si poids, de type Matrice, contient les poids des arêtes d'un graphe complet valué ,
si n est un entier donnant l'ordre de ,
si C, de type Table, code une chaîne ne contenant pas tous les sommets de ,
si p est un entier donnant le nombre de sommets de , alors eval(poids, n, C, p) renvoie la valeur de .
29 - Il s'agit de programmer l'algorithme récursif tour_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 d'un graphe complet valué ,
si C est un tableau codant une chaîne ,
si meilleur_tour est un tableau codant un tour meilleur_tour de , alors tour_min poids C meilleur_tour modifie le tableau meilleur_tour selon ce qui est indiqué plus haut concernant l'algorithme tour_min appliqué à et meilleur_tour.
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 d'un graphe complet valué ,
si n est un entier donnant l'ordre de ,
si C , de type Table, contient les sommets d'une chaîne ,
si p est un entier donnant le nombre de sommets de ,
si meilleur_tour, de type Table, code un tour meilleur_tour de , alors tour_min(poids, n, c, p, meilleur_tour) modifie le tableau meilleur_tour selon ce qui est indiqué plus haut concernant l'algorithme tour_min appliqué à , et meilleur_tour.
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 d'écrire cette méthode en langage de programmation.
Mines Option Informatique MP 2008 - Version Web LaTeX | WikiPrépa | WikiPrépa
