X-ENS 2023 MPI Informatique C : sujet en PDF
Sujet de l'épreuve de Informatique C du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2023, filière MPI, en 4 heures. Thème : Ordonnabilité des espaces métriques : distances push-pop sur les mots, listes doublement chaînées, graphes et automates poêle.
Ce que traite le sujet, partie par partie
- Partie I : préliminaires. Ordonnabilité des espaces finis, distance push-pop-droite en temps linéaire en OCaml, programmes push-pop en C produisant des d-ordres sur des langages simples, non-ordonnabilité d'un langage pour la distance push-pop-droite et NP-complétude de la t-ordonnabilité par réduction depuis le chemin hamiltonien dans un graphe grille.
- Partie II : implémentation en C des programmes push-pop. Liste doublement chaînée globale en C : test de vacuité, ajout et retrait aux deux extrémités avec assertions et libération de la mémoire, affichage et vidage de la liste, complexité de chaque opération.
- Partie III : ordonnabilité des graphes. Distance de plus court chemin dans un graphe connexe, calcul d'un arbre couvrant par parcours sur matrice d'adjacence, fonction récursive alternant ordre préfixe et postfixe selon la parité de la profondeur, preuve qu'elle donne un 3-ordre, complexité et dérécursivation par une pile.
- Partie IV : ordonnabilité des langages réguliers pour la distance push-pop-droite. Automates déterministes émondés, automates poêle (au plus un cycle et un seul chemin strict vers lui), écriture du langage sous la forme F | u v* F', programme push-pop-droite en OCaml, branches lourdes de l'arbre des mots et caractérisation des langages réguliers ordonnables.
Chapitres à revoir avant de traiter ce sujet
- Langage C : types, tableaux, pointeurs, allocation
- Langage OCaml : expressions, types, filtrage, récursivité
- Piles, files et deques
- Récursivité
- Spécifier, tester, prouver : terminaison et correction
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.