X ENS Option Informatique MP 2012Sujet, corrigé et rapport du jury

Arbres combinatoires

Pas encore noté

Structures de données arborescentes (BDD/ZDD)
Récursivité et preuves par récurrence
Complexité algorithmique
Tables d'association et tables de hachage

Explorer les annales

BanqueX-ENS Année2012 FilièreMP MatièreInformatique

Annales X-ENS MP Informatique X-ENS MP 2012 MP Informatique Informatique 2012

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficile

Arbres combinatoires (ZDD) : construction, mémoïsation et dénombrement de pavages

Le problème étudie les arbres combinatoires, une variante des BDD appelée Zero-suppressed Binary Decision Diagram, qui représente un ensemble d'ensembles sous la forme d'un graphe acyclique avec partage maximal. Après avoir introduit la structure et des fonctions élémentaires, le sujet développe un principe de mémoïsation, l'applique au dénombrement des pavages d'un échiquier par des dominos, puis explique comment garantir efficacement le partage maximal à l'aide de tables de hachage.

1Partie I : arbres combinatoiresDéfinition de la structure d'arbre combinatoire et des propriétés d'ordre et de suppression.
2Partie II : fonctions élémentaires sur les arbres combinatoiresÉcriture de fonctions de base (élément arbitraire, singleton, appartenance, cardinal).
3Partie III : mémoïsationIntroduction du principe de mémoïsation à l'aide d'une table d'association.
4Partie IV : dénombrement de pavagesApplication des arbres combinatoires au dénombrement des pavages d'un échiquier par des dominos 2x1.
5Partie V et VI : tables de hachage et partage maximalIntroduction des tables de hachage puis garantie du partage maximal lors de la construction des arbres combinatoires.

Difficile. La moyenne n'est que de 8,13/20 avec un écart-type de 3,38 sur 732 candidats, et plusieurs questions de fin de sujet n'ont été traitées entièrement correctement que par moins de 5 % des candidats.

L'épreuve en chiffres

Moyenne 8,13 / 20 · écart-type 3,38 · 732 copies · où vous situez-vous ?

Moyenne: 8,13/ 20
Écart-type: 3,38
Copies: 732

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

Votre note sur 20 à ce sujet, en conditions de concours.

Source : rapport du jury. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

4 erreurs relevées

Erreur de calcul sur le nombre d'arbres combinatoires · Confusion entre élément arbitraire et élément aléatoire · Erreur d'énoncé sur une complexité

Le sujet, deuxième édition de cette épreuve commune à Polytechnique et aux ENS, demandait de traiter le problème en entier pour obtenir la note maximale. Le jury rappelle que presque toutes les fonctions demandées pouvaient être écrites en moins de dix lignes, et qu'un programme très long contient souvent un grand nombre d'erreurs.

Les erreurs les plus sanctionnées

1
Erreur de calcul sur le nombre d'arbres combinatoiresQ4
La réponse correcte de 2^(2n) a été proposée par beaucoup de candidats, mais peu l'ont justifiée par une bijection ; certains candidats pensent à tort que 2^(2n) = 4n.
« Certains candidats pensent qu e 22n = 4 n. »
2
Confusion entre élément arbitraire et élément aléatoireQ5
Quelques candidats ont été troublés par la consigne de renvoyer un élément arbitraire et l'ont confondu avec un élément aléatoire.
« Ils ont confondu arbitraire et alé atoire. »
3
Erreur d'énoncé sur une complexitéQ8
L'énoncé demandait une complexité impossible à garantir ; les correcteurs en ont tenu compte et aucun candidat n'a semblé gêné par cette erreur.
« il n’est pas possible de garantir une complexité O(card(S(A))). »
4
Question la plus difficile du sujetQ14
Quelques candidats ont compris la structure de l'arbre à construire, mais très peu sont parvenus à garantir la complexité linéaire demandée.
« Il s’agissait probablement là de la question la plus difficile du »

Ce qui a été bien réussi

La question 6, sur une fonction élémentaire, a été dans la plupart des cas très bien traitée.
La question 9, élémentaire sur la taille d'un arbre combinatoire, a été correctement traitée dans la majorité des copies.

Conseils du jury

Préférer un programme court et bien expliqué à un programme long, souvent porteur d'erreurs.
Toujours vérifier les conditions de bord (cas de base, condition de suppression) avant d'appliquer une hypothèse de récurrence.
Commenter les algorithmes proposés, notamment pour les questions de complexité les plus délicates.
Utiliser une seule table d'association commune à tous les appels récursifs, plutôt que d'en recréer une à chaque appel.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

COMPOSITION D'INFORMATIQUE - A - (XULC)

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.

Arbres combinatoires

On étudie dans ce problème des outils pour la combinatoire, qui peuvent être utilisés en particulier pour répondre à des questions telles que : Combien existe-t-il de façons de paver un échiquier

8 \times 8

par 32 dominos de taille

2 \times 1

La partie I introduit la structure d'arbre combinatoire, qui permet de représenter un ensemble d'ensembles d'entiers. La partie II étudie quelques fonctions élémentaires sur cette structure. La partie III propose ensuite un principe de mémorisation, pour définir des fonctions plus complexes sur les arbres combinatoires. La partie IV utilise les résultats précédents pour répondre au problème de dénombrement ci-dessus. Enfin, les deux dernières parties expliquent comment construire et manipuler efficacement des arbres combinatoires, à l'aide de tables de hachage.

Les parties peuvent être traitées indépendamment. Néanmoins, chaque partie utilise des notations et des fonctions introduites dans les parties précédentes. Les tableaux sont indexés à partir de 0 et la notation t

[i]

est utilisée dans les questions pour désigner l'élément d'indice

i

du tableau t , indépendamment du langage de programmation choisi.

La complexité, ou le coût, d'un programme

P

(fonction ou procédure) est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc...) nécessaires à l'exécution de

P

. Lorsque cette complexité dépend d'un paramètre

n

, on dira que

P

a une complexité en

O(f(n))

, s'il existe

K > 0

tel que la complexité de

P

est au plus

Kf(n)

, pour tout

n

. Lorsqu'il est demandé de garantir une certaine complexité, le candidat devra justifier cette dernière si elle ne se déduit pas directement de la lecture du code.

Dans l'ensemble de ce problème, on se fixe une constante entière n , avec

n \geq 1

. On note

E

l'ensemble

{0, 1, \dots, n - 1}

Partie I. Arbres combinatoires

Dans cette partie, on étudie les arbres combinatoires, une structure de données pour représenter un élément de

P(P(E))

, c'est-à-dire un ensemble de parties de

E

. Un arbre combinatoire est un arbre binaire dont les nœuds sont étiquetés par des éléments de

E

et les feuilles par

⊥

⊤

. Voici un exemple d'arbre combinatoire:

Un nœud étiqueté par

i

, de sous-arbre gauche

A_1

et de sous-arbre droit

A_2

sera noté

i \to A_1, A_2

. L'arbre ci-dessus peut donc également s'écrire sous la forme

0 \to (1 \to (2\to⊥, ⊤), ⊤), (1 \to ⊤, (2\to⊥, ⊤)).

Dans ce sujet, on impose la double propriété suivante sur tout (sous-)arbre combinatoire de la forme

i \to A_1, A_2

: d'une part

é é A_1 et A_2 ne contiennent pas d'élément j avec j \leq i

(ordre)
et d'autre part

A_2\neq⊥.

(suppression)
Ainsi les deux arbres

ne correspondent pas à des arbres combinatoires, car celui de gauche ne vérifie pas la condition (ordre) et celui de droite ne vérifie pas la condition (suppression).

À tout arbre combinatoire

A

on associe un ensemble de parties de

E

, noté

S(A)

, défini par

S(⊥), = ∅; S(⊤), = {∅}; S(i → A_1, A_2), = S(A_1) ∪ {{i} ∪ s|s ∈ S(A_2)}

L'interprétation d'un arbre

A

de la forme

i \to A_1, A_2

est donc la suivante :

i

est le plus petit élément appartenant à au moins un ensemble de

S(A), A_1

est le sous-ensemble de

S(A)

des ensembles qui ne contiennent pas

i

, et

A_2

est le sous-ensemble de

S(A)

des ensembles qui contiennent

i

auxquels on a enlevé

i

. Ainsi, l'arbre

est interprété comme l'ensemble

{\emptyset, {0, 1}}

Question 1 Donner l'ensemble défini par l'arbre combinatoire de l'exemple (1).
Question 2 Donner les trois arbres combinatoires correspondant aux trois ensembles

{{0}}

{\emptyset, {0}}

{{0, 2}}

Question 3 Soit

A

un arbre combinatoire différent de

⊥

. Montrer que

A

contient au moins une feuille

T

Question 4 Combien existe-t-il d'arbres combinatoires distincts (en fonction de n ) ? On justifiera soigneusement la réponse.

Partie II. Fonctions élémentaires sur les arbres combinatoires

On se donne le type ac suivant pour représenter les arbres combinatoires.

    (* Caml *)
type ac = Zero | Un
| Comb of int * ac * ac;;

    { Pascal }
type ac = `noeud;
noeud = record element : integer;
gauche : ac; droit : ac; end;

Le constructeur Zero représente

⊥

et le constructeur Un représente

T

. En Pascal, on suppose que deux constantes Zero et Un de type ac ont été définies. On se donne une fonction cons pour construire un nœud de la forme

i \to A_1, A_2

(* Caml *) cons: int -> ac -> ac -> ac
{ Pascal } function cons(i: integer; a1: ac; a2: ac) : ac;

Cette fonction suppose que les propriétés (ordre) et (suppression) sont vérifiées. On suppose que cette fonction a un coût

O(1)

Dans les questions suivantes, une partie de

E

est représentée par la liste de ses éléments, triée par ordre croissant. On note ensemble le type correspondant, c'est-à-dire

    (* Caml *)
type ensemble == int list;;

        { Pascal }
type ensemble =
    record tete: integer; queue: `ensemble; end;

Question 5 Écrire une fonction un_elt qui prend en argument un arbre combinatoire

A

, supposé différent de

⊥

, et qui renvoie un ensemble

s \in S(A)

arbitraire. On garantira une complexité au plus égale à la hauteur de

A

(* Caml *) un_elt: ac -> ensemble
{ Pascal } procedure un_elt(a: ac; var v: ensemble);

Question 6 Écrire une fonction singleton qui prend en argument un ensemble

s \in P(E)

et qui renvoie l'arbre combinatoire représentant le singleton

{s}

. On garantira une complexité

O(n)

(* Caml *) singleton: ensemble -> ac
{ Pascal } function singleton(s: ensemble) : ac;

Question 7 Écrire une fonction appartient qui prend en arguments un ensemble

s \in P(E)

et un arbre combinatoire

A

et qui teste si

s

appartient à

S(A)

. On garantira une complexité

O(n)

(* Caml *) appartient: ensemble -> ac -> bool
{ Pascal } function appartient(s: ensemble; a: ac) : boolean;

Question 8 Écrire une fonction cardinal qui prend en argument un arbre combinatoire

A

et qui renvoie

card(S(A))

, le cardinal de

S(A)

(* Caml *) cardinal: ac -> int
{ Pascal } function cardinal(a: ac) : integer;

Partie III. Principe de mémorisation

Taille d'un arbre combinatoire. On définit l'ensemble des sous-arbres d'un arbre combinatoire

A

, noté

U(A)

, par

U(⊥), = { ⊥ }; U(⊤), = {⊤}; U(i → A_1, A_2), = {i → A_1, A_2} ∪ U(A_1) ∪ U(A_2)

La taille d'un arbre combinatoire

A

, notée

T(A)

, est définie comme le cardinal de

U(A)

, c'est-à-dire comme le nombre de ses sous-arbres distincts.

Question 9 Quelle est la taille de l'arbre combinatoire de l'exemple (1) ?

Principe de mémorisation. Pour écrire efficacement une fonction sur les arbres combinatoires, on va mémoriser tous les résultats obtenus par cette fonction, de manière à ne pas refaire deux fois le même calcul. Pour cela, on suppose donnée une structure de table d'association indexée par des arbres combinatoires. Plus précisément, on suppose donné un type table1 représentant une table associant à des arbres combinatoires des valeurs d'un type quelconque et les quatre fonctions suivantes :

cree1() renvoie une nouvelle table, initialement vide;
ajoute1 $(t, a, v)$ ajoute l'association de la valeur $v$ à l'arbre $a$ dans la table $t$ ;
present1( $t, a$ ) renvoie un booléen indiquant si l'arbre $a$ est associé à une valeur dans la table $t$ ;
trouve1 $(t, a)$ renvoie la valeur associée à l'arbre $a$ dans la table $t$ , en supposant qu'elle existe.
On suppose que les trois fonctions ajoute1, present1 et trouve1 ont toutes un coût constant $O(1)$ . On suppose de même l'existence d'un type table2 représentant des tables d'association indexées par des couples d'arbres combinatoires et quatre fonctions similaires cree2, ajoute2, present2 et trouve2, également de coût constant. (Les parties V et VI expliqueront comment de telles tables peuvent être construites.)

Question 10 Réécrire la fonction cardinal de la question 8 à l'aide du principe de mémorisation pour garantir une complexité

O(T(A))

. Justifier soigneusement la complexité du code proposé.

(* Caml *) cardinal: ac -> int
{ Pascal } function cardinal(a: ac) : integer;

Question 11 Écrire une fonction inter qui prend en arguments deux arbres combinatoires

A_1

A_2

et qui renvoie l'arbre combinatoire représentant leur intersection, c'est-à-dire l'arbre

A

tel que

S(A) = S(A_1) \cap S(A_2)

(* Caml *) inter: ac -> ac -> ac
{ Pascal } function inter(a1: ac; a2: ac) : ac;

Question 12 Montrer que, pour tous arbres combinatoires

A_1

A_2

, on a

T(inter(A_1, A_2)) \leq T(A_1) \times T(A_2).

Partie IV. Application au dénombrement

On en vient maintenant au problème de dénombrement évoqué dans l'introduction. Soit

p

un entier pair supérieur ou égal à 2 . On cherche à déterminer le nombre de façons de paver un échiquier de dimensions

p \times p

avec

(p^2)/2

dominos de taille

2 \times 1

. Voici un exemple de tel pavage pour

p = 8

Pour cela, on va construire un arbre combinatoire

A

tel que le cardinal de

S(A)

est exactement le nombre de pavages possibles.

Question 13 Combien existe-t-il de façons différentes de placer un domino

2 \times 1

sur l'échiquier?

Dans ce qui suit, on suppose que

n

est égal à la réponse à la question précédente, et que chaque élément

i \in E

représente un placement possible de domino. Chaque case de l'échiquier est représentée par un entier

j

tel que

0 \leq j < p^2

, les cases étant numérotées de gauche à droite, puis de haut en bas. On se donne une matrice de booléens m de taille

n \times p^2

. Le booléen

m_(i, j)

vaut true si et seulement si la ligne

i

correspond à un placement de domino qui occupe la case

j

. (On suppose avoir rempli ainsi la matrice m , qui est une variable globale.)

Un élément

s

P(E)

représente un ensemble de lignes de la matrice m. Il correspond à un pavage si et seulement si chaque case de l'échiquier est occupée par exactement un domino, i.e. si et seulement si pour toute colonne

j

il existe une unique ligne

i \in s

telle que

m[i][j] =

true. On parle alors de couverture exacte de la matrice m.

Question 14 Écrire une fonction colonne qui prend en argument un entier

j

, avec

0 \leq j < p^2

, et qui renvoie un arbre combinatoire

A

tel que, pour tout

s

s \in S(A) si et seulement si il existe un unique i \in s tel que m[i][j] = true.

On garantira une complexité

O(n)

(* Caml *) colonne: int -> ac
{ Pascal } function colonne(j: integer) : ac;

Question 15 En déduire une fonction pavage qui renvoie un arbre combinatoire

A

tel que le cardinal de

S(A)

est égal au nombre de façons de paver l'échiquier, et majorer le coût de pavage en fonction de n .

(* Caml *) pavage: unit -> ac
{ Pascal } function pavage : ac;

Partie V. Tables de hachage

Dans cette partie, on explique comment réaliser les structures de données table1 et table2, qui ont notamment permis d'obtenir des fonctions inter et cardinal efficaces. L'idée consiste à utiliser des tables de hachage.

On abstrait le problème en considérant qu'on cherche à construire une structure de table d'association pour des clés d'un type clé et des valeurs d'un type valeur, ces deux types étant supposés déjà définis. On se donne un entier

H > 1

et on suppose l'existence d'une fonction hache de coût constant, des clés vers les entiers, telle que pour toute clé

k

0 \leq hache (k) < H

L'idée consiste alors à utiliser un tableau de taille

H

et à stocker dans la case

i

les entrées correspondant à des clés

k

pour lesquelles hache

(k) = i

. Chaque case du tableau est appelée un seau. Comme plusieurs clés peuvent avoir la même valeur par la fonction hache, un seau est une liste d'entrées, c'est-à-dire une liste de couples (clé, valeur). On adopte donc le type suivant :

    (* Caml *)
type table == (clé * valeur) list
vect;;

        { Pascal }
type table = array[0..H-1] of `seau;
type seau = record k: clé; v: valeur;
    suivant: `seau; end;

On suppose par ailleurs qu'on peut comparer deux clés à l'aide d'une fonction egal à valeurs dans les booléens, également de coût constant, telle que pour toutes clés

k_1

k_2

si egal (k_1, k_2) alors hache (k_1) = hache(k_2)

Question 16 Écrire une fonction ajoute qui prend en argument une table de hachage

t

, une clé

k

et une valeur

v

, et ajoute l'entrée (

k, v

) à la table

t

. On ne cherchera pas à tester si l'entrée

(k, v)

existe déjà dans

t

et on garantira une complexité

O(1)

(* Caml *) ajoute: table -> clé -> valeur -> unit
{ Pascal } procedure ajoute(t: table; k: clé; v: valeur);

Question 17 Écrire une fonction present qui prend en argument une table de hachage

t

et une clé

k

, et qui teste si la table

t

contient une entrée pour la clé

k

(* Caml *) present: table -> clé -> bool
{ Pascal } function present(t: table; k: clé) : boolean;

Question 18 Écrire une fonction trouve qui prend en argument une table de hachage

t

et une clé

k

, et qui renvoie la valeur associée à la clé

k

dans

t

, en supposant qu'elle existe.

(* Caml *) trouve: table -> clé -> valeur
{ Pascal } function trouve(t: table; k: clé) : valeur;

Question 19 Sous quelles hypothèses sur la valeur de

H

et la fonction hache peut-on espérer que le coût des fonctions ajoute, present et trouve soit effectivement

O(1)

Partie VI. Construction des arbres combinatoires

Il reste enfin à expliquer comme réaliser une fonction de hachage, une fonction d'égalité et une fonction cons sur les arbres combinatoires, qui soient toutes les trois de complexité

O(1)

L'idée consiste à associer un entier unique à chaque arbre combinatoire

A

, noté unique

(A)

, et à garantir la propriété suivante pour tous arbres combinatoires

A_1

A_2

A_1 = A_2 si et seulement si unique (A_1) = unique(A_2).

Pour cela, on pose unique(Zero)

= 0

et unique(Un)

= 1

. Pour un arbre

A

de la forme

i \to A_1, A_2

, on choisira pour unique

(A)

une valeur arbitraire supérieure ou égale à 2 , stockée dans le nœud de l'arbre. On modifie donc ainsi la définition du type ac :

    (* Caml *)
type unique == int;;
type ac = Zero | Un
    | Comb of unique * int * ac *
ac;;

    { Pascal }
type ac = ^noeud;
noeud = record unique: integer;
element: integer; gauche: ac; droit: ac;
end;

On propose alors la fonction hache suivante sur les arbres combinatoires :

hache (⊥), = 0; hache (⊤), = 1; hache (i \to A_1, A_2), = (19^2 \times i + 19 \times unique(A_1) + unique(A_2))modH.

(Le choix de cette fonction, et du coefficient 19 en particulier, relève de considérations pratiques uniquement.) De même, on propose la fonction egal suivante sur les arbres combinatoires :

egal(⊥, ⊥) =, true,; egal(⊤, ⊤) =, true,; egal((i_1 \to L_1, R_1), (i_2 \to L_2, R_2)) =, i_1 = i_2 et unique (L_1) = unique (L_2); et unique (R_1) = unique (R_2),; egal(A_1, A_2) =, false, sinon.

Question 20 Montrer que les fonctions hache et egal ci-dessus vérifient bien la propriété (2).
Question 21 Proposer un code pour la fonction cons qui garantisse la propriété (3), en supposant que les arbres combinatoires sont exclusivement construits à partir de Zero, Un et de la fonction cons. On garantira un coût

O(1)

en utilisant une table globale de type table1 contenant les arbres combinatoires déjà construits. (On suppose que le type table1 et ses opérations ont été adaptés au nouveau type ac.)
(* Caml *) cons: int -> ac -> ac -> ac
{ Pascal } function cons(i: integer; a1: ac; a2: ac) : ac;

Pour résoudre le problème de pavage de la partie IV, on construit au total 22518 arbres combinatoires. Si on prend

H = 19997

et la fonction de hachage proposée ci-dessus, la longueur des seaux dans la table utilisée par la fonction cons n'excède jamais 7. Plus précisément, les arbres se répartissent dans cette table de la manière suivante :

longueur du seau

nombres de seaux

de cette longueur

6450

7340

4080

1617

400

Question 22 Quel est, dans cet état, le nombre moyen d'appels à la fonction egal réalisés par un nouvel appel à la fonction cons

dans le cas où l'arbre doit être construit pour la première fois;
dans le cas où l'arbre apparaissait déjà dans la table?

On donnera les valeurs avec deux décimales, en les justifiant soigneusement.

Note : La solution au problème du pavage est obtenue en quelques secondes avec la technique proposée ici; on trouve 12988816. L'intérêt de cette technique est qu'elle s'applique facilement à d'autres problèmes de combinatoire. Par ailleurs, le problème de la couverture exacte peut être attaqué par d'autres techniques, telle que les << liens dansants >> de Knuth.

Questions fréquentes

4 questions

Sur quels chapitres porte la composition d'informatique MP X-ENS 2012 ?

Le sujet porte sur les arbres combinatoires (une variante des BDD), la récursivité, la mémoïsation, les tables de hachage et une application au dénombrement des pavages d'un échiquier par des dominos.

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet d'informatique MP X-ENS 2012 ?

Le jury relève une erreur de calcul sur le nombre d'arbres combinatoires, une confusion entre élément arbitraire et élément aléatoire, et une difficulté généralisée à garantir les complexités demandées, notamment à la question 14.

Ce sujet d'informatique MP X-ENS 2012 est-il difficile ?

Oui, la moyenne n'est que de 8,13/20 sur 732 candidats, et plusieurs questions de fin de sujet n'ont été résolues entièrement que par une très faible proportion des candidats.

Ce sujet de X-ENS MP 2012 nécessite-t-il de bien maîtriser la récursivité ?

Oui, la plupart des fonctions demandées sont récursives et le rapport souligne l'importance de vérifier les cas de base et les conditions de bord, sources fréquentes d'erreurs dans les copies.

Pas de description pour le moment

Commentaires• X ENS Option Informatique MP 2012

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...