Top piège du sujet
Coût de deux multiplications matricielles ≠ produit des coûts (Q II.1)
Statistiques jury
Comment les candidats s'en sont sortis
Notes brutes officielles publiées par le jury — non harmonisées.
Moyenne
9.63
Médiane
9.6
Écart-type
3.66
Q1 (25%)
7.2
Q3 (75%)
12.1
Candidats présents
960
Calculateur
Où je me situe sur ce sujet ?
Entrez votre note brute. Le percentile et la position se mettent à jour en temps réel.
Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Sujet OCaml en 5 parties. Partie I : fonctions utilitaires de multiplication de matrices. Partie II : optimisation de l'ordre de multiplication d'une suite finie de matrices (problème classique de programmation dynamique). Partie III : différentiation de la composition d'une liste de fonctions. Partie IV : généralisation au cas d'une fonction représentée par un graphe (DAG). Partie V (indépendante) : triangulations de polygones et liens avec la complexité de la…
Structure de l'épreuve
- Partie I — Partie I, Fonctions utilitaires sur les matrices(Q1-Q4)Abordable
Introduction de fonctions utiles pour la multiplication de matrices (produit scalaire, boucles, bonnes bornes). Largement réussie : 99 % de copies, 71-89 % de réussite par question.
- Partie II — Partie II, Multiplication d'une suite finie de matrices (programmation dynamique)(Q1-Q6)Difficile
Montrer que l'ordre de multiplication influence fortement la complexité. Développer un algorithme calculant un ordre optimal. Q4 : 82 % traitée mais 9 % de réussite (oubli des arbres non-peigne). Q6 : 39 % traitée, 13 % réussie.
- Partie III — Partie III, Différentiation de la composition d'une liste de fonctions(Q1-Q7)Difficile
Deux manières de calculer la différentielle d'une composition. Implémentation des algorithmes en utilisant la partie II. Q4 et Q6 sur le coût et la somme géométrique : 6-12 % de réussite.
- Partie IV — Partie IV, Différentiation pour fonctions représentées par un graphe (DAG)(Q1-Q4)Très difficile
Cas plus général d'une fonction représentée par un graphe nécessitant d'ajuster les algorithmes précédents. Question Q4 mal formulée admettait des réponses triviales. Q3 : 20 % traitée, 4 % réussie.
- Partie V — Partie V, Triangulations de polygones et complexité (indépendante)(Q1-Q3)Très difficile
Liens entre triangulations de polygones et la complexité de la multiplication d'une suite de matrices. Q1 : 51 % traitée, 3 % de réussite. Q3 sur les produits vectoriels et orientation : 35 % traitée, 5 % réussie.
Analyse globale du jury
« Sujet OCaml sur la différentiation algorithmique, central pour le calcul formel et la descente de gradient. 5 parties graduelles, la partie V largement indépendante. Pour la note maximale il n'était pas nécessaire de traiter l'intégralité du sujet. Moyenne 9,63/20 (σ=3,66) sur 960 candidats français ; 8,49/20 (σ=4,54) sur 67 candidats étrangers. Les preuves par récurrence ne sont pas maîtrisées par un grand nombre de candidats : oubli/mauvais choix du cas de base, et choix hasardeux de la quantité ou structure sur laquelle on effectue l'induction. Pour les questions sur la correction d'un algorithme, on attend autre chose qu'une simple paraphrase de l'algorithme. »
Top pièges sanctionnés
Coût de deux multiplications matricielles ≠ produit des coûts (Q II.1)-2 pts
« De trop nombreux candidats pensent que le coût pour effectuer deux multiplications de matrice est le produit des coûts pour effectuer chacune d'elles. Par ailleurs, beaucoup de candidats ont conclu que « l'ordre d'évaluation dépend de la taille des matrices », ce qui ne veut rien dire puisque l'ordre d'évaluation dépend de l'algorithme. »
Considérer uniquement les arbres « peignes » (Q II.4), impact sur tout le reste de la partie-3 pts
« Beaucoup de candidats n'ont considéré que les arbres de multiplication qui sont des peignes (c'est-à-dire que chaque nœud interne est nécessairement relié à une feuille). Cette erreur a généralement impacté tout le reste de la partie II. »
Programmation dynamique remplie par lignes croissantes, ne donne pas le bon résultat (Q II.5)-2 pts
« Beaucoup de candidats ont rempli la matrice par programmation dynamique, mais sans se soucier de l'ordre de remplissage. En particulier, remplir la matrice par lignes croissantes ne donne pas le bon résultat. Remplir la matrice par mémoïsation permettait de contourner cette difficulté. »
Mesurer l'orientation par produit scalaire au lieu de produit vectoriel (Q V.3)-2 pts
« De trop nombreux candidats ont tenté de mesurer l'orientation de trois points en utilisant le signe d'un produit scalaire alors que l'énoncé mentionnait explicitement l'utilisation d'un produit vectoriel. »
Preuves par récurrence sans poser la récurrence ou avec « preuve » à base d'exemples (Q V.1)-3 pts
« Cette question a été traitée par de nombreux candidats pensant qu'il s'agissait d'une question facile. Toutefois, de trop nombreuses copies ne posent pas de récurrence, ne précisent pas sur quoi porte la récurrence, voire donnent une « preuve » à base d'exemples. Les correcteurs apprécient les exemples qui peuvent aider à comprendre le raisonnement mais ceux-ci ne peuvent être suffisants. »
Chapitres clés à maîtriser
Bosse chaque chapitre sur d'autres sujets de concours qui le couvrent.
Contexte
L'épreuve en quelques chiffres
Accompagnement personnalisé
Travaillez ce sujet avec un prof de l'équipe
Nos professeurs anciens taupins (Polytechnique, ENS, Centrale) reprennent ce sujet avec toi en cours particulier — corrigé ligne par ligne, méthode, pièges évités.
Trouvez le prof qu'il vous faut
Échangez avec notre équipe pour trouver le professeur idéal selon vos besoins.
Stratégie
Notre approche pour ce sujet
- Partie I, Fonctions utilitaires sur les matrices (Q1-Q4 · facile)
- Partie II, Multiplication d'une suite finie de matrices (programmation dynamique) (Q1-Q6 · dur)
- Partie III, Différentiation de la composition d'une liste de fonctions (Q1-Q7 · dur)
- Partie IV, Différentiation pour fonctions représentées par un graphe (DAG) (Q1-Q4 · tres-dur)
- Partie V, Triangulations de polygones et complexité (indépendante) (Q1-Q3 · tres-dur)
Conseils du jury
Pièges sanctionnés par le rapport
- Coût de deux multiplications matricielles ≠ produit des coûts (Q II.1) : « De trop nombreux candidats pensent que le coût pour effectuer deux multiplications de matrice est le produit des coûts pour effectuer chacune d'elles. Par ailleurs, beaucoup de candidats ont conclu que « l'ordre d'évaluation dépend de la taille des matrices », ce qui ne veut rien... »
- Considérer uniquement les arbres « peignes » (Q II.4), impact sur tout le reste de la partie : « Beaucoup de candidats n'ont considéré que les arbres de multiplication qui sont des peignes (c'est-à-dire que chaque nœud interne est nécessairement relié à une feuille). Cette erreur a généralement impacté tout le reste de la partie II. »
- Programmation dynamique remplie par lignes croissantes, ne donne pas le bon résultat (Q II.5) : « Beaucoup de candidats ont rempli la matrice par programmation dynamique, mais sans se soucier de l'ordre de remplissage. En particulier, remplir la matrice par lignes croissantes ne donne pas le bon résultat. Remplir la matrice par mémoïsation permettait de contourner cette diffi... »
- Mesurer l'orientation par produit scalaire au lieu de produit vectoriel (Q V.3) : « De trop nombreux candidats ont tenté de mesurer l'orientation de trois points en utilisant le signe d'un produit scalaire alors que l'énoncé mentionnait explicitement l'utilisation d'un produit vectoriel. »
- Preuves par récurrence sans poser la récurrence ou avec « preuve » à base d'exemples (Q V.1) : « Cette question a été traitée par de nombreux candidats pensant qu'il s'agissait d'une question facile. Toutefois, de trop nombreuses copies ne posent pas de récurrence, ne précisent pas sur quoi porte la récurrence, voire donnent une « preuve » à base d'exemples. Les correcteurs ... »
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ