Corrige Polytechnique X Informatique 1999 MP

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 ...