Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
24 questions balayant une partie conséquente du programme d'informatique des deux années de CPGE, du niveau élémentaire (recherche d'un indice maximum, multiplication d'une liste par une constante) à des questions exigeant une maîtrise et une compréhension fine. SQL, Python, complexité, structure de données, et algorithmes nouveaux à comprendre. Évalue la capacité à relier différentes notions au problème du sac à dos.
Structure de l'épreuve
- Partie I — Q1-Q4 — SQL et préliminaires Python(Q1-Q4)Abordable
Q1-Q2 : syntaxe SQL pas entièrement maîtrisée — confusion AND/virgule, ORDER BY sans précision d'attribut. Q3-Q4 : manipulation des booléens non optimale (`if a==b: return True else: return False` au lieu de `return a == b`).
- Partie II — Q5-Q9 — Algorithme glouton et tri(Q5-Q9)Niveau attendu
Q5 bien traitée. Q6 complexité dépend du nombre de feuilles ET de la complexité de profit/contrainte. Q7 conseils de concision. Q8 code à trous, structure des données pas comprise. Q9 complexité du tri par insertion non maîtrisée, confusion avec tri à bulles.
- Partie III — Q10-Q14 — Programmation dynamique(Q10-Q14)Niveau attendu
Q11 justifications imprécises : pour montrer que glouton n'est pas optimal, il faut COMPARER les profits glouton/optimal. Confusion optimalité/complexité. Q12 erreurs de calcul. Q13 résultat dépend de n et de b (rien ne dit b = O(n)). Q14 complexité O(n) non indiquée.
- Partie IV — Q15-Q24 — Séparation/évaluation, colonies de fourmis(Q15-Q24)Difficile
Q15 manipulation des dictionnaires avec syntaxe de listes (a[0] renvoie la valeur associée à clé 0, pas le « premier » élément — un dictionnaire n'est pas ordonné). Q16 mutabilité des listes (S=Sk implique alias). Q17 fonction récursive KPpse non comprise comme inspirée de KPforceBrute.
Analyse globale du jury
« L'épreuve abordait donc un large éventail de notions étudiées durant les deux années de préparation tout en évaluant la capacité des candidats à relier ces notions au problème du sac à dos. Dans l'ensemble, les codes Python sont correctement indentés et commentés et les candidats écrivent correctement (en majuscule ou minuscule) les mots clés des différents langages. Une attention particulière est attendue lors de la définition et l'utilisation des variables. »
Top pièges sanctionnés
Q1-Q2 SQL : confusion AND/virgule entre attributs SELECT et conditions WHERE-1 pts
« Erreurs fréquentes : confusion dans l'ordre des instructions, utilisation de AND (au lieu d'une virgule) entre les différents attributs sélectionnés avec SELECT, utilisation d'une virgule (à la place de AND) entre les conditions spécifiées après WHERE, pas de précision de l'attribut utilisé pour le classement lors de l'utilisation de ORDER BY. »
Q9 : confondre tri par insertion et tri à bulles ; ne pas reconnaître complexité linéaire vs quadratique-1 pts
« La complexité du tri par insertion n'est pas maitrisée par un nombre important de candidats et plusieurs candidats le confondent avec le tri à bulles. Les tris sont au programme et une complexité linéaire ou quadratique doit pouvoir être reconnue par les candidats. »
Q11 : « moins/plus optimale » — une solution est optimale ou ne l'est pas-1 pts
« Une solution est optimale ou ne l'est pas ; elle n'est pas "moins/plus optimale" qu'une autre solution. Certains candidats font la confusion entre optimalité et complexité. »
Q15 : manipuler un dictionnaire comme une liste (a[0], « premier » élément)-2 pts
« Trop de candidats manipulent les dictionnaires en utilisant la syntaxe propre aux listes sans réaliser que le résultat ne correspond pas à leurs attentes : par exemple a[0] renvoie l'éventuelle valeur associée à la clé 0 et non le "premier" élément du dictionnaire a. Par ailleurs, il n'est pas possible de parler du "premier" élément d'un dictionnaire car un dictionnaire n'est pas ordonné. »
Q16 : ignorer la mutabilité des listes — S=Sk crée un alias-2 pts
« La notion de mutabilité des listes n'est pas maitrisée par plusieurs candidats. Il est rappelé que l'instruction S=Sk implique que S et Sk désignent la même liste. Par conséquent, une modification de la liste Sk modifie aussi la liste S. »
Complexités fantaisistes ; tri par insertion plus complexe dans le meilleur cas que dans le pire-1 pts
« Plusieurs calculs de complexité sont demandés dans le sujet. Il est demandé de faire preuve d'esprit critique […] : par exemple, certains candidats proposent des complexités plus importantes pour le tri par insertion dans le meilleur cas que dans le pire cas quand d'autres proposent des complexités fantaisistes. De plus, il est attendu que la réponse soit sous forme de complexité asymptotique : O(n²) et non (n+3)(n+10)². »
Chapitres clés à maîtriser
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ
