Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Sujet d'informatique commune (MP/PC/PSI) sur l'utilisation de différentes méthodes de résolution du problème du sac à dos : algorithme glouton, programmation dynamique, algorithme par séparation et évaluation, optimisation par colonie de fourmis. Algorithme glouton et programmation dynamique au programme CPGE — adaptation des algorithmes connus au sac à dos. Les autres méthodes inconnues mettent en évidence la capacité à comprendre un nouvel algorithme.…
Structure de l'épreuve
- Partie I — Q1-Q5 — SQL et bases (booléens)(Q1-Q5)Niveau attendu
Q1-Q2 syntaxe SQL — confusion ordre, AND vs virgule entre attributs SELECT, virgule vs AND entre conditions WHERE, ORDER BY sans attribut. Q3-Q4 manipulation des booléens (return a==b plutôt que if/else). Q5 bien traitée.
- Partie II — Q6-Q11 — Complexité, glouton et tris(Q6-Q11)Difficile
Q6 complexité dépend du nombre de feuilles ET des fonctions profit/contrainte. Q7 conciser les justifications. Q9 complexité du tri par insertion confondue avec tri à bulles ; complexité linéaire ou quadratique à reconnaître.…
- Partie III — Q12-Q18 — Programmation dynamique et dictionnaires(Q12-Q18)Difficile
Q13 dépendre de n et b (rien ne dit b=O(n)). Q14 complexité de la partie ajoutée en O(n). Q15 dictionnaire ≠ liste — a[0] renvoie la valeur associée à la clé 0, pas le « premier » élément (un dict n'est pas ordonné). Q16 mutabilité des listes — S=Sk = même objet.…
- Partie IV — Q19-Q24 — Sac à dos avancé et analyses(Q19-Q24)Très difficile
Q19 recherche de l'indice du maximum — bonnes variables. Q20 bien traitée. Q21-Q23 peu traitées. Q24 analyses sur optimalité et rapidité des différents algorithmes.
Analyse globale du jury
« 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. Plusieurs calculs de complexité sont demandés dans le sujet — il est demandé de faire preuve d'esprit critique : certains candidats proposent des complexités plus importantes pour le tri par insertion dans le meilleur cas que dans le pire cas. Il est attendu que la réponse soit sous forme de complexité asymptotique : O(n²) et non (n+3)(n+10)/2. »
Top pièges sanctionnés
Q1 — SQL : virgule au lieu de AND, AND au lieu de virgule-1 pts
« La syntaxe SQL n'est pas entièrement maîtrisée pour une majorité de candidats. 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. »
Q3 — return a==b plutôt que if/else-1 pts
« La manipulation des booléens n'est pas optimale : sans être fausse l'utilisation du code if a == b : return True ... else : return False au lieu de return a == b montre le manque de familiarisation avec cet objet. »
Q11 — solution « plus/moins optimale »-2 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 — a[0] sur un dictionnaire = valeur de la clé 0-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 — S=Sk fait la même liste-2 pts
« La notion de mutabilité des listes n'est pas maîtrisé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. »
Q18 — « for i in T : i = i*rho » ne modifie pas T-1 pts
« Plusieurs candidats ont proposé le code for i in T : i=i*rho qui ne modifie pas les éléments de la liste T. »
Complexité : tri par insertion avec meilleur cas > pire cas (faux)-1 pts
« Plusieurs calculs de complexité sont demandés dans le sujet. Il est demandé de faire preuve d'esprit critique dans les réponses qu'ils proposent : par exemple, certains candidats proposent des complexités plus importantes pour le tri par insertion dans le meilleur cas que dans le pire cas. »
Chapitres clés à maîtriser
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ
