Prepa HelpMines-Ponts 2024 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2024, filière MP, en 3 heures. Thème : Relations d'ordre : tri topologique, chaînes et couverture minimale.
Ce que traite le sujet, partie par partie
- Section 1 : relation d'ordre et tri topologique. Relation représentée par une matrice de booléens : tests de réflexivité en styles impératif et fonctionnel, d'antisymétrie et de transitivité, degrés sortants, puis tri topologique qui numérote un sommet de degré sortant minimal, avec invariants de correction et complexité.
- Section 2 : chaînes et antichaînes. Correction d'une fonction qui teste si une liste de sommets est une chaîne et sa complexité, version en O(γ log γ) fondée sur une structure de file de priorité à capacité bornée, test d'antichaîne et existence d'un test plus rapide.
- Section 3 : couverture par des chaînes. Inégalité entre le cardinal d'une antichaîne et le nombre de chaînes d'une couverture, graphe biparti des poursuites, chaînes tirées d'un couplage, équivalence entre couverture minimale et couplage de cardinal maximum, calcul de ce couplage et complexité.
Chapitres à revoir avant de traiter ce sujet
- Logique, ensembles et applications
- Langage OCaml : expressions, types, filtrage, récursivité
- Spécifier, tester, prouver : terminaison et correction
- Complexité des algorithmes itératifs et récursifs
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.