Centrale Informatique optionnelle MP 2025

4 heures

MP

Calculatrice autorisée

2025

Option informatique

Meilleurs itinéraires dans un réseau ferroviaire
La recherche de l'itinéraire le plus court entre deux points d'un graphe 
pondéré est un problème facilement résolu par
plusieurs algorithmes. Cette recherche est plus difficile dans un réseau 
ferroviaire, où les trajets sont restreints par des
horaires de départ et d'arrivée à chaque arrêt, et du fait de l'existence de 
correspondances.
De plus, la notion de « meilleur trajet » se fait souvent en considérant non 
pas uniquement la durée totale du trajet,
mais également d'autres critères tels que le prix du billet, le nombre de 
correspondances, l'heure de départ, les services
à bord, etc. Il est rare d'obtenir un trajet qui minimise simultanément tous 
les critères : la minimisation d'un critère
particulier se faisant souvent au détriment d'un autre. Certains trajets sont 
cependant moins bons sur tous les critères :
ceux-ci n'ont pas besoin d'être considérés.
Ce sujet comporte quatre parties :
­ la partie I étudie l'implémentation d'une file de priorité et d'un tri par 
tas ;
­ la partie II définit et étudie la notion d'optimum de Pareto. Les notations 
introduites dans cette partie sont
utilisées dans les parties suivantes ;
­ la partie III étudie le calcul d'optimums de Pareto dans le cas d'un langage 
sur un alphabet fini ;
­ la partie IV étudie le calcul d'optimums de Pareto dans un graphe pondéré.
Les parties III et IV sont indépendantes.
On trouvera dans l'annexe A en page 10 quelques points de rappels de syntaxe et 
de fonctions OCaml.
Consignes aux candidates et candidats Il doit être répondu aux questions de 
programmation en utilisant le langage
OCaml. En cas d'écriture d'une fonction non demandée par l'enoncé, il doit être 
précisé son rôle, ainsi que sa signature
(son type). Lorsque cela est pertinent, la description du fonctionnement des 
programmes qui ont été écrits est également
incitée. On autorise toutes les fonctions des modules Array et List, ainsi que 
les fonctions de la bibliothèque standard
(celles qui s'écrivent sans nom de module, comme max, failwith ainsi que les 
opérateurs comme @). Sauf précision de
l'énoncé, l'utilisation d'autres modules est interdite.
Lorsqu'une question de programmation demande l'écriture d'une fonction, la 
signature de la fonction demandée est
indiquée dans la question. Les candidates et candidats peuvent écrire une 
fonction dont la signature est compatible avec
celle demandée. Par exemple, si l'énoncé demande l'écriture d'une fonction int 
list -> int qui renvoie le premier
élément d'une liste d'entiers, écrire une fonction 'a list -> 'a qui renvoie le 
premier élément d'une liste d'éléments
quelconques sera considéré comme correct.
Il est possible d'admettre le résultat d'une question, y compris de supposer 
qu'une fonction demandée a été écrite,
afin de traiter les questions suivantes.

I ­ Une file de priorité
L'objectif de cette première partie est d'implémenter une file de priorité 
persistante en utilisant une structure de tas
d'appariement. Cette structure de tas permet également d'obtenir un tri de 
complexité optimale.
On peut voir les tas d'appariement comme des arbres n-aires auto-ajustés, 
c'est-à-dire pour lesquels les opérations sur
la structure de données réorganisent l'arbre tout en réalisant globalement une 
forme d'ajustement. Ils disposent d'une
implémentation très simple, tout en étant efficace en pratique, par exemple 
pour une utilisation comme file de priorité
dans l'algorithme de Dijkstra, qui sera étudié dans la partie IV.
Contrairement à une implémentation classique en utilisant un tas binaire 
implémenté dans un tableau, les opérations
sur un tas d'appariement à n éléments pourront avoir un coût en O(n) dans le 
pire cas. Cependant, on peut montrer
qu'une séquence de n opérations consécutives sur cette structure de données a 
un coût total en O(n log n), ce qui rend
l'utilisation de cette structure tout aussi efficace lorsque l'on effectue une 
séquence d'opérations.
1 / 10

Dans toute cette partie on utilise la relation d'ordre totale implicite en 
OCaml sur les objets de type 'a donnée par
les opérateurs < ou <= ou encore par les fonctions min et max. En particulier, si les objets considérés sont des tuples, alors cet ordre correspond à l'ordre lexicographique sur les composantes de ces tuples. I.1 ­ Tas d'appariement Pour implémenter un tas d'appariement, on utilise des arbres n-aires étiquetés, dont les noeuds possèdent un nombre quelconque d'enfants. La figure 1 présente un exemple de tas d'appariement comportant 12 noeuds. Dans ce sujet, un arbre est soit un arbre vide, soit un noeud formé d'une étiquette et d'une liste éventuellement vide d'arbres non vides, qui sont les enfants de ce noeud parent. Une feuille est un noeud qui ne possède pas d'enfants, c'est-à-dire dont la liste d'enfants est la liste vide. On représente en OCaml un arbre à l'aide du type suivant : type 'a arbre = | Vide | Noeud of 'a * 'a arbre list On remarquera que le constructeur Vide sert uniquement à dénoter l'arbre vide et ne peut pas apparaître dans une liste d'enfants puisque les enfants d'un noeud sont systématiquement supposés non vides. Un tas d'appariement est un arbre vérifiant la propriété de tas minimum : l'étiquette d'un noeud est inférieure ou égale à celle de tous ses enfants. 2 7 4 10 6 9 8 5 8 13 14 11 Figure 1 ­ Un tas d'appariement à 12 noeuds. Q1. Écrire une fonction min_valeur : 'a arbre -> 'a qui renvoie la valeur 
minimale d'un tas supposé non vide.
Quelle est sa complexité dans le pire cas ?
Pour fusionner deux tas non vides, il suffit d'ajouter le tas dont l'étiquette 
de la racine est la plus grande comme
nouvel enfant de l'arbre dont l'étiquette de la racine est la plus petite. Un 
nouvel enfant est ajouté en tête de la liste
des enfants, donc devient le premier enfant à gauche. La complexité de cette 
opération est donc en O(1) dans le pire
cas. La figure 2 illustre un certain nombre de fusions : les deux arbres 
au-dessus d'une accolade sont fusionnés pour
obtenir l'arbre sous celle-ci.
Q2. Écrire une fonction fusion : 'a arbre -> 'a arbre -> 'a arbre qui réalise 
la fusion de deux tas. On gèrera
les cas où l'un ou les deux tas sont vides.
Pour ajouter un élément à un tas, on crée un nouveau tas contenant cet élément 
et on le fusionne avec le tas initial.
Q3. Écrire une fonction insere : 'a -> 'a arbre -> 'a arbre qui réalise 
l'insertion d'un élément dans un tas.
Quelle est sa complexité dans le pire cas ?
Pour supprimer l'élément minimal d'un tas, il suffit de supprimer la racine et 
de fusionner les enfants de celle-ci. Pour
obtenir une forme d'auto-ajustement, on procède en deux étapes pour fusionner 
une liste de k arbres :
(a) on fusionne, de gauche à droite, les arbres deux par deux, tant que c'est 
possible ;
(b) on fusionne progressivement, en un seul arbre, les dk/2e arbres ainsi 
obtenus en prenant les arbres un par un,
de la droite vers la gauche, en partant de l'arbre de droite.
Cette opération en deux étapes est appelée fusion par paires et donne le nom à 
cette structure de tas d'appariement.
La figure 2 illustre la suppression de la racine d'étiquette 2 du tas de la 
figure 1. Lors de la première étape de la fusion
par paires, on effectue la fusion des enfants de gauche à droite deux par deux. 
Les arbres de racine 4 et 7 sont fusionnés
entre eux, puis les arbres de racines 9 et 5 sont fusionnés entre eux. L'arbre 
de racine 13 étant seul, il reste inchangé.
Lors de la deuxième étape de la fusion par paires, on fusionne les arbres ainsi 
obtenus de droite à gauche. Les arbres
de racine 5 et 13 sont fusionnés, puis le résultat de cette fusion est fusionné 
avec l'arbre de racine 4.
2 / 10

10

9

7

4
6

5

8

8

13
14

11
5

4
10

7

6

9

13

8

8

14

11
5
13

9

8

14

11
4
5
13

9

10

7
8

6

14 8

11
Figure 2 ­ Fusion par paires des enfants de la racine d'étiquette 2 du tas de 
la figure 1.
Q4. On insère successivement et dans cet ordre les éléments 0, 1, 2, 3, 4, 5 et 
6 dans un tas initialement vide, puis
on supprime deux fois le minimum. Représenter le tas d'appariement obtenu.
Q5. Écrire une fonction fusion_par_paires : 'a arbre list -> 'a arbre qui 
réalise la fusion par paires d'une
liste d'arbres. Cette fonction devra renvoyer Vide pour une liste vide.
Q6. En déduire une fonction suppression_min : 'a arbre -> 'a arbre qui supprime 
l'élément minimal d'un tas.
Quelle est sa complexité dans le pire cas ?
On admet qu'une séquence quelconque de n opérations min_valeur, insere et 
suppression_min sur cette structure
de données, à partir d'un tas initialement vide, a une complexité totale en O(n 
log n).

I.2 ­ Tri par tas
On peut utiliser les fonctions précédentes pour implémenter un tri par tas de 
complexité O(n log n) pour trier une
liste de n éléments.
Q7. Écrire une fonction tri : 'a list -> 'a list permettant de trier une liste 
dans l'ordre croissant en utilisant
un tri par tas d'appariement.
Q8. Quelle est la complexité dans le meilleur cas de cette fonction tri ? 
Donner, en justifiant, une forme de liste
correspondant à cette complexité.

II ­ Optimums de Pareto
Dans un problème d'optimisation classique, on cherche généralement à minimiser 
une certaine quantité parmi un
ensemble de solutions possibles. Par exemple, on peut vouloir déterminer le 
trajet le plus court parmi tous les trajets
possibles entre deux points. Lorsque l'on dispose de plusieurs objectifs à 
minimiser simultanément, ce problème devient
cependant bien plus délicat : certains objectifs peuvent être contradictoires 
et il peut être impossible de les minimiser
tous simultanément.
3 / 10

Considérons l'exemple de la figure 3, correspondant à la recherche d'un billet 
de train entre la gare de Lyon Part Dieu
et la gare de Tours sur le réseau ferroviaire national. Pour chaque trajet 
possible, on retient dans cet exemple trois
critères : sa durée, le nombre de correspondances (c'est-à-dire le nombre de 
fois où l'on doit descendre d'un train pour
continuer le trajet avec un autre) et son prix. Idéalement, on souhaite obtenir 
à la fois un trajet dont la durée est
minimale, qui comporte le moins de correspondances possibles et qui est le 
moins cher.
On observe sur la figure 3 qu'il n'est pas possible de minimiser simultanément 
tous ces critères. En revanche, il est
clairement inutile de considérer le trajet (e) qui a la même durée et le même 
nombre de correspondances que le trajet
(d), mais qui est strictement plus cher que celui-ci.
identifiant
(a)
(b)
(c)
(d)
(e)
(f )
(g)

durée (h)
6
5
4
5
5
5
4

nombre de correspondances
0
1
2
1
1
2
1

prix (e)
60
50
110
40
90
100
120

Figure 3 ­ Une liste de trajets proposés par un moteur de recherche 
d'itinéraires pour aller d'une gare à une autre.
On ne sait pas a priori quels seront les critères privilégiés par le voyageur. 
L'objectif est alors de lui présenter l'ensemble
des solutions minimales, au sens où aucune autre solution n'est strictement 
meilleure : il s'agit des optimums de Pareto.
Par exemple, dans la figure 3 on retiendrait les quatre trajets (a), (c), (d) 
et (g), qui sont ici les quatre optimums de
Pareto. Remarquons que le trajet (a) minimise le nombre de correspondances, que 
le trajet (d) minimise le prix et que
les deux trajets (c) et (g) minimisent la durée, sans pour autant qu'aucun des 
deux ne soit meilleur que l'autre sur les
deux autres attributs.
Q9. Montrer que les trajets (b) et (f) ne sont pas des optimums de Pareto, en 
explicitant pour chacun d'entre eux
un trajet strictement meilleur.

II.1 ­ Notion d'optimum de Pareto et ordre partiel
On rappelle qu'une relation d'ordre  sur un ensemble E est une relation binaire 
réflexive (x  E, x  x), antisymétrique ((x, y)  E 2 , x  y  y  x  x = y) et 
transitive ((x, y, z)  E 3 , x  y  y  z  x  z). Une relation
d'ordre est totale si tous les éléments sont deux à deux comparables, 
c'est-à-dire si (x, y)  E 2 , x  y  y  x. On dit
que l'ordre est partiel sinon. On note  la relation d'ordre stricte associée, 
définie par : x  y si x  y  x 6= y.
Si X  E est une partie de E, un élément minimal de X est un élément x  X qui 
n'est strictement supérieur à aucun
autre élément de X. On note min(X) l'ensemble des éléments minimaux de X, 
c'est-à-dire :
min(X) = {x  X | @y  X, y  x} = {x  X | y  X, y  x  y = x}.
Notons que si la relation d'ordre  n'est pas totale, il peut y avoir plusieurs 
éléments minimaux, qui sont alors deux
à deux non comparables.
Soient d  N et d ensembles totalement ordonnés (A1 , 1 ), (A2 , 2 ), . . . , 
(Ad , d ), appelés attributs. Pour i  J1, dK,
i est donc un ordre total sur Ai . On peut munir E = A1 × A2 × · · · × Ad de 
différentes relations d'ordre construites
à partir des ordres i .
Ordre lexicographique On définit l'ordre lexicographique v sur E par (x1 , x2 , 
. . . , xd ) v (x01 , x02 , . . . , x0d ) si et seulement si (x1 , x2 , . . . , 
xd ) = (x01 , x02 , . . . , x0d ) ou bien, en notant k = min{i  J1, dK|xi 6= 
x0i }, xk  int qui renvoie 
l'élément minimal d'une liste non vide
d'entiers.

II.3 ­ Cas de la dimension 2
Dans cette partie, on s'intéresse à des éléments de Z2 ordonnés avec l'ordre 
produit . On manipule donc des objets
du type :
type tuple = int * int
On représente un ensemble de couples par une liste sans doublons. On considère 
l'exemple suivant :
let ex1 = [(4, 1); (5, 7); (3, 3); (1, 3); (2, 9); (1, 4); (2, 2)]
Q12. Donner, sans justification, le ou les éléments minimaux de l'ensemble 
représenté par la liste de couples ex1.
Q13. Écrire une fonction inferieur : tuple -> tuple -> bool telle que inferieur 
x y pour deux couples (x, y) 
(Z2 )2 s'évalue à true si x  y et false sinon, c'est-à-dire si y  x ou si x et 
y ne sont pas comparables.
Q14. On considère X  Z2 un ensemble qui contient n  1 couples d'entiers. 
Donner, en justifiant, un encadrement
de card(min(X)), dont les bornes sont atteintes.
On suppose disposer d'une fonction de tri de signature tri_lexico : tuple list 
-> tuple list qui permet de
trier une liste d'éléments dans l'ordre croissant pour l'ordre lexicographique. 
On suppose que cette fonction termine
toujours et que la complexité de cette fonction de tri est en O(n log n) sur 
une liste de taille n. La fonction réalisée
dans la partie I convient à cet effet.
On considère la fonction suivante, de type tuple list -> tuple list, associée à 
la spécification : si ens est une
liste de couples représentant un ensemble X d'éléments de Z2 , l'appel 
elements_minimaux ens s'évalue en une liste
contenant exactement les éléments minimaux de X.
1
2
3
4
5
6
7
8

let elements_minimaux ens =
let rec w u =
match u with
| x :: y :: z ->
if inferieur x y then w (x :: z)
else x :: w (y :: z)
| v -> v
in w (tri_lexico ens)
Les noms de variables de cette fonction ont été volontairement rendus 
inintelligibles.
Pour représenter la trace d'exécution d'un appel à une fonction, on note ligne 
par ligne dans l'ordre chronologique
d'exécution : -> f args pour indiquer qu'on commence un appel à f sur les 
paramètres args ; ou <- valeur de retour pour indiquer la fin de l'appel et la valeur renvoyée. On indente les appels imbriqués. Voici un exemple de fonction et la trace associée à l'appel cardinal [32; 52] : let rec cardinal l = match l with | [] -> 0
| _ :: tl -> 1 + cardinal tl

-> cardinal [32; 52]
-> cardinal [52]
-> cardinal []
<- 0 <- 1 <- 2 Q15. Donner la trace d'exécution de la fonction w lors de l'appel à elements_minimaux ex1. On pourra se contenter de noter uniquement le début de la liste à chaque appel s'il n'y a pas ambiguïté sur la valeur de la fin, par exemple ex1 = [(4, 1); (5, 7) ;...]. Q16. Justifier soigneusement la terminaison de la fonction elements_minimaux. Q17. Déterminer la complexité de la fonction elements_minimaux. Q18. Justifier soigneusement la correction de la fonction elements_minimaux. 5 / 10 II.4 ­ Cas général On se place désormais dans le cadre de la dimension d  N et même, plus généralement, dans le cadre d'un ordre partiel quelconque sur un ensemble. On suppose ainsi uniquement disposer d'un type abstrait element et d'une fonction inferieur : element -> element -> bool qui détermine si un élément est 
inférieur ou égal à un autre pour cet
ordre partiel.
Si (E, ) est un ensemble partiellement ordonné et si X  E, la largeur de X est 
le nombre maximal d'éléments
simultanément deux à deux non comparables de X ; c'est-à-dire le cardinal 
maximal d'une partie de X composée
uniquement d'éléments deux à deux non comparables :
largeur(X) = max{card(Y ) | Y  X et (x, y)  Y 2 , x 6= y  x 6 y  y 6 x}.
Q19. Écrire une fonction existe_plus_petit de signature element -> element list 
-> bool telle que l'appel
existe_plus_petit u liste s'évalue à true si et seulement s'il existe un 
élément de la liste inférieur ou égal
à l'élément u.
Q20. Écrire une fonction ajoute_plus_petit de signature element -> element list 
-> element list telle que
ajoute_plus_petit u liste ajoute l'élément u à une liste en supprimant de cette 
liste tous les éléments
supérieurs ou égaux à u.
Q21. En déduire une fonction elements_minimaux : element list -> element list 
qui renvoie une liste composée des éléments minimaux d'une liste passée en 
paramètre. On suppose que la liste passée en paramètres ne
comporte pas de doublons et représente un ensemble X d'éléments. Cette fonction 
doit effectuer au plus O(nk)
appels à la fonction inferieur, où n est le cardinal de X et k la largeur de X, 
ce que l'on justifiera brièvement.

III ­ Éléments minimaux d'un langage régulier
Dans cette partie, on se propose de généraliser la notion d'optimum de Pareto 
dans le cas d'un nombre variable
d'attributs. On pourra ainsi être amené à comparer des tuples de longueurs 
différentes. À cet effet, on modélise un
tuple par un mot sur un alphabet fini.

III.1 ­ Éléments minimaux d'un langage
On considère un alphabet  fini non vide muni d'un ordre total  sur les lettres. 
On rappelle que  désigne l'ensemble
de tous les mots sur  et que + =  \ {} désigne l'ensemble des mots de longueur 
non nulle sur .
On considère la relation d'ordre  sur  définie par : u1 u2 . . . un  v1 v2 . . 
. vm si et seulement si n  m et  i 
J1, nK, ui  vi . Si  comporte au moins deux lettres, cette relation d'ordre est 
seulement partielle. On remarquera que
la restriction de  aux mots de d , c'est-à-dire aux tuples de longueur d fixée, 
correspond à l'ordre partiel étudié dans
la partie précédente.
Pour les exemples, on considérera l'alphabet 3 = {a, b, c}, avec a < b < c. Pour 3 , on a ab  bc  bca  ccab  ccbca  ccbcb. En revanche ab, ca, bac et aaab, babab sont deux à deux incomparables. On note min(L) le langage des éléments minimaux de L, c'est-à-dire : min(L) = {u  L | @v  L, v  u}. Par exemple, min(3 ) = {}, min(+ 3 ) = {a}, min({ab, bc, ca, bac, ccab}) = {ab, ca, bac}. Q22. Montrer que   L  min(L) = {}. Il est ainsi trivial de déterminer les éléments minimaux d'un langage contenant . On supposera dans toute la suite que les langages considérés ne contiennent pas . Q23. Montrer que si L  + est non vide, alors min(L) 6= . Autrement dit, l'ordre partiel  est bien fondé. On considère, sur 3 , les langages L1 = {ai bj | (i, j)  (N )2 } et L2 = {ai bj ck | (i, j, k)  (N )3 , i  k  j  k}. Q24. Donner min(L1 ) sans justification puis montrer que les langages L1 et min(L1 ) sont réguliers. Q25. (a) Déterminer min(L2 ), en expliquant brièvement comment ce langage est obtenu. (b) Montrer que les langages L2 et min(L2 ) ne sont pas réguliers. On détaillera uniquement la preuve montrant que L2 n'est pas régulier, et on justifiera brièvement cette propriété pour min(L2 ). Q26. Montrer que min(L) peut être régulier même si L  + n'est pas régulier. On se propose dans la suite de cette partie de montrer que si L  + est régulier alors min(L) est également régulier. 6 / 10 III.2 ­ Automates finis non déterministes Un automate sur un alphabet  est un quadruplet A = (Q, I, T, ) avec Q un ensemble fini non vide, I  Q un ensemble d'états initiaux, T  Q un ensemble d'états terminaux et   Q ×  × Q une relation de transition. Un chemin d'un tel automate est une suite de transitions ((qi-1 , ui , qi ))iJ1,nK n , d'état de départ q0  Q, d'état d'arrivée qn  Q et d'étiquette u = u1 u2 . . . un   . Un mot u   est reconnu par A s'il existe un chemin d'un état initial à un état terminal dans A. On note L(A) le langage des mots reconnus par A. Un exemple d'automate est représenté sur la figure 4. a 0 c 1 c 2 Figure 4 ­ L'automate A1 sur 3 . Les états initiaux, ici 0 et 1, sont indiqués par une flèche et les états terminaux, ici 2, sont doublement cerclés. Q27. Appliquer l'algorithme d'élimination des états à l'automate A1 de la figure 4, en éliminant successivement, dans cet ordre, les états 0, 1 puis 2. En déduire une expression régulière qui dénote le langage L(A1 ). III.3 ­ Automates marqués Un automate marqué sur un alphabet  est un couple AM = (A, M ) formé d'un automate A = (Q, I, T, ) sur  et d'un sous-ensemble M   de transitions dites marquées. Un mot u   est reconnu par un automate marqué AM s'il existe un chemin dans A d'un état initial à un état terminal qui passe par au moins une transition marquée de M . On note L(AM ) le langage des mots reconnus par un automate marqué AM . M Un exemple d'automate marqué AM 2 est représenté sur la figure 5. Le langage L(A2 ) reconnu par cet automate marqué est le langage des mots de 3 d'au moins deux lettres qui commencent et terminent par a ou b et qui comportent au moins un a. On remarquera que même si l'état 0 est à la fois un état initial et un état terminal, le mot vide n'est pas reconnu par cet automate marqué, puisque l'on impose aux chemins de passer par au moins une transition marquée. b, c b b 0 1 a 2 a a Figure 5 ­ Un automate marqué AM 2 sur 3 . Les états initiaux, ici seulement 0, sont indiqués par une flèche et les états terminaux, ici 0 et 2, sont doublement cerclés. Les transitions marquées, ici celles d'étiquette a, sont représentées par une ligne épaisse en traits et points. On se propose de commencer par montrer que tout langage reconnaissable par un automate marqué est reconnaissable par un automate ordinaire. Soit AM = (A, M ) un automate marqué sur  avec A = (Q, I, T, ). On construit un automate ordinaire A qui reconnaît le même langage que l'automate marqué AM . Pour cela on duplique l'automate A, avec une première copie de A, sans états terminaux, avec les mêmes transitions non marquées, mais dont les transitions marquées mènent vers une deuxième copie de A, identique à A mais sans états initiaux. Formellement, on note Q = {q | q  Q} une copie des états de Q. L'ensemble des états de A est Q  Q. L'ensemble ¨ = {(q, x, q 0 ) | des états initiaux de A est I¨ = {q | q  I} et l'ensemble des états terminaux de A est T . On note ¨  . (q, x, q 0 )  M }  {(q, x, q 0 ) | (q, x, q 0 )   \ M }. Les transitions de A sont Q28. Appliquer cette construction sur l'automate marqué AM 2 de la figure 5 et représenter l'automate ordinaire A2 ainsi obtenu. Q29. Montrer, de manière générale, que L(AM ) = L(A). 7 / 10 III.4 ­ Automate des minimaux Soit L  + un langage régulier. On note L = {u  + | v  L, v  u} le langage des mots qui sont strictement plus grands qu'au moins un mot de L. Q30. Montrer qu'il suffit de montrer que L est régulier pour montrer que min(L) est régulier. On se propose de construire un automate marqué AM qui reconnaît L à partir d'un automate A qui reconnaît L. Considérons un automate A = (Q, I, T, ) qui reconnaît L. (a) On commence par supprimer dans  toutes les transitions sortantes d'un état terminal de A. Formellement, on note 0 = {(q, x, q 0 ) | (q, x, q 0 )   et q 6 T } l'ensemble des transitions de A qui ne partent pas d'un état terminal ; (b) Ensuite, pour chaque transition (q, x, q 0 )  0 , on ajoute (si nécessaire) et on marque les transitions (q, y, q 0 ), pour chaque lettre y   telle que x < y. Formellement, on note M 0 = {(q, y, q 0 ) | (q, x, q 0 )  0 , y  , x < y} ; (c) Enfin, on ajoute et on marque les transitions (q, x, q) pour chaque état terminal q  T et pour chaque lettre x  . Formellement on note M 00 = {(q, x, q) | q  T, x  }. = 0  M 0  M 00 et M = M 0  M 00 . On note A = (Q, I, T, ) et AM = (A, M ) l'automate marqué obtenu. On pose Q31. Appliquer cette construction sur l'automate A1 de la figure 4, avec l'alphabet 3 , et représenter l'automate marqué AM 1 ainsi obtenu. Q32. Montrer, de manière générale, que L  L(AM ). Q33. Montrer, de manière générale, que L(AM )  L. Q34. En déduire que si L  + est un langage régulier alors min(L) est également un langage régulier. IV ­ Meilleurs chemins dans un graphe On s'intéresse à présent à la recherche d'itinéraires dans un réseau ferroviaire, afin d'optimiser différents critères pour un trajet. Le réseau ferroviaire est modélisé par un graphe orienté G = (V, E) dont les noeuds, dans V , sont les gares. Il existe un arc d'une gare v1  V vers une gare v2  V lorsqu'il est possible de faire le trajet directement de v1 à v2 sans changer de train. Chaque arc e  E est étiqueté par un couple d'entiers positifs (t(e), p(e)) où t(e) donne le temps de trajet de la gare de départ de e vers la gare d'arrivée de e, et p(e) donne le prix du billet à payer pour prendre le train représenté par e. Un exemple d'un tel réseau est donné en figure 6. On remarquera que les trajets obtenus dans la figure 3 correspondent à certains des chemins entre le sommet s = 0 et le sommet t = 5. 2 e 4 h, 4 2 h, 34 e 2e 3 h, 3 e ,6 4h e 1 4e 5 h, 76 e 1h ,4 1h ,6 84 e 3 h, 6 e s=0 2e 6 h, 8 h, 3 h, 5 e 3 1h ,3 1 8e 1 6 h, 60 e Figure 6 ­ Un exemple de réseau ferroviaire. 8 / 10 t=5 Soit C = (e1 , e2 , · · · , eT ) un chemin orienté dans G, donné par la liste de ses arcs. Le poids de ce chemin, noté w(C) est le triplet : ! T T X X w(C) = t(ek ), T - 1, p(ek ) . k=1 k=1 La deuxième composante du triplet donne le nombre de correspondances, c'est-à-dire de changements de trains. Les poids sont représentés par un triplet d'entiers, qui sont ordonnés en OCaml selon l'ordre lexicographique : type poids = int * int * int On définit l'opération  sur les triplets d'entiers par : (T, C, P )  (T 0 , C 0 , P 0 ) = (T + T 0 , C + C 0 , P + P 0 ). On rappelle cependant que cet opérateur n'est pas défini a priori par le langage OCaml. On représente un arc du graphe par un enregistrement de type arc : type arc = {dest : int; temps : int; prix : int} Ainsi, si train est une valeur de type arc représentant un arc e, l'expression train.dest donne le numéro de la gare d'arrivée de e, l'expression train.temps permet d'obtenir t(e) et l'expression train.prix permet d'obtenir p(e). On représente les gares du réseau ferroviaire par des entiers de 0 à n - 1, où n est le nombre total de gares. Le graphe du réseau ferroviaire est représenté par ses listes d'adjacence : type reseau_ferroviaire = arc list array Si reseau est une valeur de type reseau_ferroviaire et i un entier entre 0 et n - 1, alors reseau.(i) est la liste des arcs partant du sommet i, dans un ordre arbitraire. L'algorithme de Dijkstra permet, dans un graphe orienté dont les arcs sont pondérés par des entiers positifs, de calculer pour un sommet s donné les longueurs des plus courts chemins de s à tout autre sommet du graphe. On adapte cet algorithme de la façon suivante, afin qu'il calcule, dans un réseau ferroviaire, les trajets dont les poids sont des optimums de Pareto. Algorithme 1 Algorithme de Dijkstra pour les réseaux ferroviaires 1 : Initialiser un tableau d qui à chaque sommet associe la liste vide [] 2 : Soit Q une file de priorité vide 3 : Ajouter s à Q avec priorité (0, -1, 0) 4 : tant que Q n'est pas vide faire 5: Défiler v de Q de priorité v minimale pour l'ordre lexicographique 6: si aucun élément de d[v] n'est plus petit que v alors Supprimer de d[v] tous les éléments plus grands que v Ajouter v dans d[v] pour chaque arc e de v vers w faire Enfiler w dans Q avec la priorité v  (t(e), 1, p(e)) fin pour fin si 13 : fin tant que 7: 8: 9: 10 : 11 : 12 : Dans cette version de l'algorithme de Dijkstra, un sommet peut être présent plusieurs fois dans la file. Q35. Les files de priorité de la partie I stockent a priori uniquement les priorités. Justifier qu'on peut les utiliser pour implémenter l'algorithme 1 si on stocke dans chaque noeud le couple (v , v). On implémente le tableau d par un objet de type : d : poids list array On considère le réseau de transport de la figure 6. Après quatre itérations de la boucle de l'algorithme 1, avec s = 0, la file de priorité Q contient les valeurs suivantes : Priorité Sommet (3, 0, 88) 2 (4, 0, 84) 4 (4, 2, 110) 5 (5, 1, 40) 5 (5, 1, 50) 5 (6, 0, 60) 5 (6, 1, 120) 4 d.(3) [(3,0,6); (2,1,76)] d.(4) [] d.(5) [] et le tableau d contient les valeurs suivantes : d.(0) [(0,-1,0)] d.(1) [(1,0,44)] d.(2) [] Q36. Détailler l'évolution de Q et d lors des 3 itérations suivantes de l'algorithme 1. 9 / 10 Q37. Écrire une fonction dijkstra_pareto : reseau_ferroviaire -> int -> poids 
list array qui prend en
paramètres un graphe orienté décrit par ses listes d'adjacence, un sommet 
d'origine s et qui calcule la liste des
poids optimums de Pareto des chemins de s à tous les autres sommets du graphe. 
On pourra librement utiliser
toutes les fonctions définies dans les parties précédentes, en particulier 
celles de la partie I.1 ainsi que celles de
la partie II.4 en supposant que le type element correspond ici aux triplets 
donnant les poids.
Q38. Montrer qu'un chemin non élémentaire d'un sommet u à un sommet v, 
c'est-à-dire qui passe deux fois par un
même sommet, a un poids qui n'est pas un optimum de Pareto parmi les poids des 
chemins de u à v.
Q39. Soient s et t deux sommets du graphe et Cs,t un chemin de s à t, dont le 
poids est un optimum de Pareto parmi
tous les chemins de s à t. Montrer que le poids de tout chemin Cs,u , allant de 
s à u, préfixe de Cs,t , est un
optimum de Pareto parmi les poids des chemins de s à u.
Q40. Montrer que, dans l'algorithme 1, si v satisfait la condition du test en 
ligne 6, alors v est un optimum de
Pareto parmi les poids des chemins de s à v. En déduire une optimisation de 
l'algorithme 1.
Q41. Démontrer la correction de l'algorithme, c'est-à-dire : d'une part qu'à la 
fin de l'exécution, pour tout sommet v,
d[v] contient exactement tous les poids des chemins de s à v optimums de Pareto 
; et d'autre part que l'algorithme
termine.
Q42. Proposer une fonction en OCaml permettant d'obtenir la liste de tous les 
chemins entre un sommet s et un
sommet t dont le poids est un optimum de Pareto. On indiquera la signature de 
la fonction ainsi qu'une rapide
description de la structure utilisée.

A ­ Annexe : documentation OCaml
I.1 ­ Fonctions usuelles
­ val min : 'a -> 'a -> 'a renvoie le minimum de ses deux paramètres. Lorsque 
les paramètres sont des tuples,
l'ordre utilisé est l'ordre lexicographique.
­ val max : 'a -> 'a -> 'a renvoie le maximum de ses deux paramètres. Lorsque 
les paramètres sont des
tuples, l'ordre utilisé est l'ordre lexicographique.

I.2 ­ Fonctions sur les listes
­ val List.for_all : ('a -> bool) -> 'a list -> bool.
L'appel List.for_all f [a0; a1; ...; an] renvoie true lorsque tous les appels f 
a0, f a1, ..., f an renvoient true, et false sinon.
­ val List.exists : ('a -> bool) -> 'a list -> bool.
L'appel List.exists f [a0; a1; ...; an] renvoie true lorsqu'au moins l'un des 
appels f a0, f a1, ..., f an
renvoie true, et false sinon.
­ val List.filter : ('a -> bool) -> 'a list -> 'a list.
L'appel List.filter f [a0; a1; ...; an] renvoie la liste extraite de [a0; a1; 
...; an] formée uniquement
des éléments x tels que f x est true. Les éléments apparaissent dans la liste 
résultat dans le même ordre que
dans la liste en paramètre.
­ val List.iter : ('a -> unit) -> 'a list -> unit.
L'appel List.iter f [a0; a1; ...; an] exécute f a0, puis f a1, etc., jusque f 
an, dans cet ordre.

I.3 ­ Manipulation des tableaux
­ val Array.make : int -> 'a -> 'a array.
L'appel Array.make n x0 crée un tableau de n entrées, chacune initialisée à la 
valeur x0.
­ val Array.length : 'a array -> int renvoie la longueur d'un tableau.
­ Si t est un tableau et i un indice valide dans le tableau, t.(i) <- x0 modifie la case d'indice i en lui affectant la valeur x0. 10 / 10