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