Centrale-Supélec 2025 MP Option informatique : sujet en PDF

Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2025, filière MP, en 4 heures. Thème : Meilleurs itinéraires dans un réseau ferroviaire : tas d'appariement, optimums de Pareto, langages réguliers et algorithme de Dijkstra adapté.

Ce que traite le sujet, partie par partie

• Partie I : une file de priorité. En OCaml, tas d'appariement représentés par des arbres n-aires : valeur minimale, fusion, insertion, fusion par paires, suppression du minimum et complexités, puis tri par tas et étude de son meilleur cas.
• Partie II : optimums de Pareto. Ordre lexicographique et ordre produit. En OCaml, éléments minimaux en dimension 1 et 2, encadrement de leur nombre, trace, terminaison, complexité et correction d'une fonction récursive donnée, puis cas d'un ordre partiel quelconque avec au plus O(nk) comparaisons, k étant la largeur de l'ensemble.
• Partie III : éléments minimaux d'un langage régulier. Ordre partiel sur les mots, existence d'éléments minimaux, régularité de L et de min(L) sur des exemples, algorithme d'élimination des états, automates marqués et passage à un automate ordinaire, construction d'un automate marqué menant à la régularité de min(L) quand L est régulier.
• Partie IV : meilleurs chemins dans un graphe. Graphe orienté dont les arcs portent un temps et un prix, algorithme de Dijkstra adapté avec une file de priorité sur des triplets : déroulement sur un exemple, fonction dijkstra_pareto en OCaml, chemins non élémentaires et préfixes de chemins optimaux, optimisation, correction et terminaison, liste de tous les chemins dont le poids est un optimum de Pareto.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Complexité des algorithmes itératifs et récursifs
• Récursivité
• Logique, ensembles et applications
• Tri par fusion et tri rapide

Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.