Option informatique MP 2025 4 heures Calculatrice autorisée 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 -- 1 of 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 nœuds possèdent un nombre quelconque d’enfants. La figure 1 présente un exemple de tas d’appariement comportant 12 nœuds. Dans ce sujet, un arbre est soit un arbre vide, soit un nœud formé d’une étiquette et d’une liste éventuellement vide d’arbres non vides, qui sont les enfants de ce nœud parent. Une feuille est un nœud 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 nœud 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 nœud est inférieure ou égale à celle de tous ses enfants. 2 4 10 6 7 8 9 5 8 11 14 13 Figure 1 – Un tas d’appariement à 12 nœuds. 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 -- 2 of 10 -- 4 10 6 7 8 9 5 8 11 14 13 4 7 8 10 6 5 9 8 11 14 13 5 13 9 8 11 14 4 5 13 9 8 11 14 7 8 10 6 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 -- 3 of 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 durée (h) nombre de correspondances prix (e) (a) 6 0 60 (b) 5 1 50 (c) 4 2 110 (d) 5 1 40 (e) 5 1 90 (f ) 5 2 100 (g) 4 1 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), antisy- métrique (∀(x, y) ∈ E2, x y ∧ y x ⇒ x = y) et transitive (∀(x, y, z) ∈ E3, 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) ∈ E2, 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 (x′ 1, x′ 2, . . . , x′ d) si et seule- ment si (x1, x2, . . . , xd) = (x′ 1, x′ 2, . . . , x′ d) ou bien, en notant k = min{i ∈ J1, dK|xi 6 = x′ i}, 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 let elements_minimaux ens = 2 let rec w u = 3 match u with 4 | x :: y :: z -> 5 if inferieur x y then w (x :: z) 6 else x :: w (y :: z) 7 | v -> v 8 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 -- 5 of 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 compo- sé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 : u1u2 . . . un v1v2 . . . 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 = {aibj | (i, j) ∈ (N∗)2} et L2 = {aibj 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 -- 6 of 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))i∈J1,nK ∈ ∆n, d’état de départ q0 ∈ Q, d’état d’arrivée qn ∈ Q et d’étiquette u = u1u2 . . . 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. 0 1 2 c a c 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 . Un exemple d’automate marqué AM 2 est représenté sur la figure 5. Le langage L(AM 2 ) 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. 0 1 2 a b a b a b, c 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 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′) | (q, x, q′) ∈ M } ∪ {(¨q, x, ¨q′) | (q, x, q′) ∈ ∆ \ 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 -- 7 of 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 ∆′ = {(q, x, q′) | (q, x, q′) ∈ ∆ 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′) ∈ ∆′, on ajoute (si nécessaire) et on marque les transitions (q, y, q′), pour chaque lettre y ∈ Σ telle que x < y. Formellement, on note M ′ = {(q, y, q′) | ∃(q, x, q′) ∈ ∆′, ∃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 ′′ = {(q, x, q) | q ∈ T, x ∈ Σ}. On pose ˘∆ = ∆′ ∪ M ′ ∪ M ′′ et M = M ′ ∪ M ′′. On note ˘ A = (Q, I, T, ˘∆) et ˘ AM = ( ˘ A, M ) l’automate marqué obtenu. 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 nœuds, 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. s = 0 1 2 3 4 t = 5 1 h, 44 e 3 h, 88 e 3 h, 6 e 4 h, 84 e 6 h, 60 e 5 h , 76 e 1 h , 32 e 4 h, 6 e 3 h , 5 e 1 h, 6 e 1 h, 32 e 1 h, 6 e 2 h, 34 e Figure 6 – Un exemple de réseau ferroviaire. 8 / 10 -- 8 of 10 -- 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 : w(C) = ( T ∑ k=1 t(ek), T − 1, T ∑ k=1 p(ek) ) . 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 ′, C′, P ′) = (T + T ′, C + C′, P + P ′). 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 7 : Supprimer de d[v] tous les éléments plus grands que πv 8 : Ajouter πv dans d[v] 9 : pour chaque arc e de v vers w faire 10 : Enfiler w dans Q avec la priorité πv ⊕ (t(e), 1, p(e)) 11 : fin pour 12 : fin si 13 : fin tant que 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 nœud 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é (3, 0, 88) (4, 0, 84) (4, 2, 110) (5, 1, 40) (5, 1, 50) (6, 0, 60) (6, 1, 120) Sommet 2 4 5 5 5 5 4 et le tableau d contient les valeurs suivantes : d.(0) d.(1) d.(2) d.(3) d.(4) d.(5) [(0,-1,0)] [(1,0,44)] [] [(3,0,6); (2,1,76)] [] [] Q36. Détailler l’évolution de Q et d lors des 3 itérations suivantes de l’algorithme 1. 9 / 10 -- 9 of 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 ren- voient 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 -- 10 of 10 --