Rapport de M. Luc MARANGET, correcteur.De l’épreuveL’épreuve a été normalement réussie et classante, 219 candidats admissibles ont choisicette option, dont 29 (13%) ont composé en Pascal et 190 (87%) en Caml. On constatedonc un recul de Pascal par rapport aux années précédentes. La moyenne générale del’é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 conclusionsdes différences de résultat entre les deux langages.Du problèmeLe 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éennesest aujourd’hui largement employée et reconnue comme une des plus efficaces. Les arbresbinaires 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ésconceptuelles 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 dansles programmes, ou encore test (v,f) est un arbre, tandis que test(x,g,g) est une ap-x iiplication. L’énoncé prenait pourtant soin de commencer par définir un unique objet dundiscours : il s’agissait tout simplement des applications ...
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. Engr
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
pr1.
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