Corrige Polytechnique X Informatique 1999 MP

Informations

• Publié par: shin
• Nombre de lectures: 197
• Langue: Français

Extrait

Rapport de M. Luc MARANGET, correcteur. De l’épreuve L’épreuve a été normalement réussie et classante, 219 candidats admissibles ont choisi cette option, dont 29 (13%) ont composé en Pascal et 190 (87%) en Caml. On constate donc un recul de Pascal par rapport aux années précédentes. La moyenne générale de l’épreuve est de 11,1 et l’écart type de 2,9. Les notes N se répartissent comme suit : 0≤N< 5 1% 5≤N<10 33% 10≤N<15 56% 15≤ N≤ 20 10% Le faible nombre de copies rédigées en Pascal ne permet pas de tirer de conclusions des différences de résultat entre les deux langages. Du problème Le problème présentait une version simplifiée des diagrames de décision (Binary De- cision Diagrams ou BDD). Cette technique de représentation des fonctions booléennes est aujourd’hui largement employée et reconnue comme une des plus efficaces. Les arbres binaires de décision évitent le délicat problème du partage des sous arbres identiques (systématique dans le cas des BDD), mais permettent d’aborder les principales difficultés conceptuelles des BDD sans compliquer outre mesure leur programmation. Les candidats ont été gênés par la multiplicité des concepts et notations du problème, par exemple les booléens sont notés 0 et 1 dans les preuves, puis false et true dans
les programmes, ou encore test (v,f) est un arbre, tandis que test(x,g,g) est une ap-x ii plication. L’énoncé prenait pourtant soin de commencer par définir un unique objet du ndiscours : il s’agissait tout simplement des applications deB dansB. Produit cartésien et application sont des notions bien connues des candidats, mais en mathématiques... Or il apparaît clairement que bien des candidats ont pensé plutôt en termes d’expressions boo- léennes, notion abordée dans le cours d’informatique. Malheureusement, les applications se montrent ici bien plus commodes que les expressions, en raison justement des change- ments des descriptions concrètes des applications booléenes (expressions booléennes dans la partie I, arbres de décision par la suite). Il est vrai que ce type de distinction entre essence et représentation est omniprésent en informatique et plus rarement abordé en ma- thématiques. Il est donc normal que les candidats éprouvent des difficultés sur ce point. Il convient également d’insister sur l’importance cruciale d’une lecture complète de l’énoncé, disons partie par partie, mais aussi, il paraît banal de le dire, d’une lecture at- tentive de chaque question avant d’y répondre. Cette démarche a des avantages évidents dans toutes les matières : perception de la logique du problème, compréhension exacte de ce qui est demandé à chaque question, appréciation de la difficulté des questions. Engr ammation o et Syntaxe outre, dans le cas de l’informatique, domaine récent où les notations mais aussi les défini- tions sont variables selon les auteurs et les contextes, une lecture attentive des définitions de l’énoncé est indispensable. En effet, il y a un risque réel que la définition donnée dans l’énoncé ne soit pas exactement la même que celle vue en cours, la définition de la tau- tologie de ce problème en est un bon exemple. De même, les notations des connecteurs logiques sont variables. Il est fortement recommandé aux candidats de ne pas utiliser de notations personnelles et suicidaire d’y recourir sans les avoir définies au préalable. Présentation La présentation concrète des copies est, à de rares exceptions près, très satisfaisante, l’écriture est lisible, les ratures sont propres, les résultats soulignés. Le discours lui-même est souvent plus embrouillé, certains candidats semblent jouer une course de vitesse et écrivent preuves et programmes au fil du stylo, c’est généralement un mauvais calcul. Rapport détaillé Dans le rapport détaillé qui suit est indiqué, pour chaque question, le pourcentage des candidats qui ont obtenu au moins la moitié des points. [64%] Le barème choisi comptabilise à part des points de pénalitépourles erreurs de syntaxe, jusque dans une certaine limite. Ontété sanctionnées, les erreurs qui traduisent des méconnaissances graves du langage adopté (cf. ci-dessous). Près de 20% des candidats perdent tous leurs points. Le correcteur est d’abord frappé par la fréquence ahurissante des erreurs portant sur les types. Un nombre important de candidats confondent allègrement entiers et booléens. Dans le même ordre d’idée, trop de candidats produisent des fonctions qui n’ont pas le type demandé. Le concept même de type n’est pas compris des candidats, qui doivent se former sur ce point. Si les candidats connaissent les arbres et le parcours d’arbre simple, on note beaucoup d’erreurssur l’emploi des types concrets et des constructeurs (Caml), etdes variantset des enregistrements (Pascal). C’est assez étonnant car on ne peut effectivement programmer les arbres sans maîtriser ces constructions. Pour ce qui est de Caml, le filtrage donnait en théorieun certain avantage,caril permet d’écrire des analyses parcas defaçonplus simple et intuitive que les cascades de if ou de case de Pascal. Dans la pratique, de nombreux candidats qui composaient en Caml ont perdu des points par manque de maîtrise de cette construction, dont les pouvoirs ne doivent pas être surestimés. Par exemple le compilateur refuse cette fonction : let mon_egal = fun (x,x) -> true | (_,_) -> false Tandis que cette autre renvoie toujours true : let autre_egal x = fun x -> true | _ -> false Enfin, en Pascal, la distinction entre fonction et procédure est mal connue. On notera pr1. Question Question 3. Question aussi une inattention assez fréquente dans les deux langages : l’oubli d’un paramètre ré- duit à une variable qui ne change pas lors d’un appel récursif. Quelques candidats semblent tout ignorer du langage dans lequel ils rédigent leur co- pie, on ne peut que leur conseiller de ne pas paniquer et d’utiliser un pseudo-code clair et régulier. En effet, si le correcteur ne comprend pas ce que le candidat a voulu programmer, ou si il doit s’accommoder d’erreurs à chaque question nouvelles et écrire le programme à la place du candidat, il n’accorde aucun point. D’autres, au contraire et particulièrement enCaml,tiennentà montrerleur expertise etabusentdes constructions deprogrammation dites avancées (par exemple, les exceptions) et des fonctions de librairie. C’est toujours inutile et souvent dangereux. [33%] Plus de 60% des candidats n’obtiennent aucun point à cette ques- tion, par faute d’avoir bien compris l’énoncé, qui restreignait sévèrement les constructions autorisées. Dès lors, l’emploi des opérateurs logiques (or et & en Caml, or et and en Pas- cal) a été pénalisé, tout comme l’usage de l’opérateur d’égalité, if x = true then ... étant rigoureusement équivalent à if x then .... Cette dernière faute, très fréquente, traduit une confusion classique : rappelons que l’expression e testée par la construction if e then ... est n’importe quelle expression de type booléen et qu’un test explicite n’est pas nécessaire (ici, il était nuisible). [95%] La question 2-a) a posé quelques difficultés. Il s’agissait surtout de se justifier par un argument convaincant et simple utilisant les définitions de l’énoncé, par exemple pour les deux premières affirmations, des tables de vérité, et pour la dernière, un contre-exemple (l’application booléenne 0 convenait très bien). À ce stade évoquer le tiers-exclu ou le raisonnement par l’absurde laisse un peu perplexe. Certains candidats ou- blient de préciser si les affirmations sont exactes ou inexactes. Ces deux points expliquent que seulement 56% des candidats obtiennent la note maximale à cette question. Enfin quelques candidats perdent du temps à s’inquiéter du cas n=0(exclu par l’énoncé) ou supposent que les booléens pourraient être égaux (exclu, carB est un ensemble). Rassu- 0rons les premiers en signalant qu’il est bien pratique de considérerB réduit à un unique 0élément, de sorte queB →Bcontient deux applications notées 0 et 1... [90%] Il fallait ici transcrire chacune des conditions en une expression boo- léenne, dont p est la conjonction. La première condition a troublé les candidats, pourtant il semble clair qu’elle ne dit rien sur la taille des peluches : de « les jouets doivent être petits, sauf les peluches », on ne peut que déduire « les peluches peuvent être petites », ce qui n’impose certainement pas les grandes peluches. Beaucoup de candidats peinent à reconnaître une implication dans les règles 3 et 5, ou la négation d’une conjonction dans la règle 4, la plupart s’en tirent en utilisant d’autres connecteurs, mais pas tous. Certains candidats entreprennent de réduire p, c’est inutile, car non-demandé par l’énoncé (lecture de l’énoncé, toujours). Plus grave, d’autres proposent seulement cette expression réduite, leur réponse n’a été acceptée qu’accompagnée d’une preuve convaincante, car la formule réduite de p se déduit facilement de l’arbre de décision donné à la question 5. 2.Question 4. [35%] Les parties b) et c) de cette question se sont révélées sélectives, car, si la technique d’induction structurelle sur les arbres est connue, on sent qu’elle n’est pas maîtrisée. La première partie a été généralement bien réussie, sauf par quelques candidats pani- qués ou distraits. Quelques candidats ont interprété les quatrième et cinquième fonctions commeuneseule conjonction,confondantleconnecteur∧etlemotfrançais«et».Notons également que la commutativité de∧ (qui justifiait l’égalité du troisième et du quatrième arbre) s’est parfois transformée en associativité ou même en réflexivité. Il s’agissait ensuite de prouver l’unicité de la représentation de la tautologie. La plu- part des candidats proposent des preuves par récurrence, délicates pour eux, car il s’agit de montrer la non-existence d’un arbre d’une taille donnée. Dans les cas extrêmes, les preuves des candidats sont des coquilles vides, dont les conditions de bonne formation des arbres sont absentes. Et pourtant, l’arbre mal formé test (1,test (0,1)) représente bienx x0 0 une tautologie. Rappelons au passage que