X-ENS 2022 MP Informatique A : sujet en PDF
Sujet de l'épreuve de Informatique A du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2022, filière MP, en 4 heures. Thème : Différentiation algorithmique : parenthésage optimal d'un produit de matrices, modes avant et arrière, triangulation de polygones.
Ce que traite le sujet, partie par partie
- Partie I. Fonctions OCaml de base sur les matrices de flottants : matrice identité, produit scalaire, compatibilité des dimensions et produit matriciel avec un nombre imposé de multiplications.
- Partie II. Coût d'un produit de plusieurs matrices selon le parenthésage, produits parenthésés à droite et à gauche, calcul récursif naïf du coût minimal de complexité exponentielle, puis mémoïsation dans une matrice et construction du produit optimal.
- Partie III. Opérateur qui propage la valeur et la différentielle d'une composée, règle de la chaîne sur les jacobiennes, fonctions forward et backward selon le parenthésage, preuve de correction et comparaison des complexités selon les dimensions, lien avec le parenthésage optimal.
- Partie IV. Fonction représentée par un graphe acyclique de fonctions élémentaires, calcul à la main d'un tableau de propagation avant, collecte des valeurs des prédécesseurs, calcul de la différentielle en un point et traitement particulier des opérations linéaires.
- Partie V. Coût minimal d'un produit de matrices vu comme une triangulation de poids minimal d'un polygone convexe, test de convexité par produits vectoriels, triangulation linéaire d'un polygone convexe puis d'un polygone strictement monotone.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Programmation dynamique
- Complexité des algorithmes itératifs et récursifs
- Spécifier, tester, prouver : terminaison et correction
- Récursivité
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.