Diagrammes de décision (réduction, construction ordonnée), circuits logiques et automates pour résoudre des systèmes d'équations linéaires entières
Afficher ou masquer la section
Le sujet d'informatique de l'option info, Centrale MP 2013, étudie les arbres puis les diagrammes de décision représentant des formules booléennes, leur réduction par élimination et isomorphisme, leur construction ordonnée à partir d'une fonction booléenne donnée, leur traduction en circuits logiques, puis la construction d'automates permettant de résoudre des systèmes d'équations linéaires à coefficients entiers combinées par des opérateurs logiques.
1Partie I : arbres de décisionReprésentation d'un arbre de décision par un tableau de nœuds, écriture des fonctions d'évaluation d'une variable puis d'une décision complète.
2Partie II : diagrammes de décisionCompactage de la représentation en fusionnant les sous-arbres identiques, écriture des règles d'élimination et d'isomorphisme, puis d'une fonction réduisant complètement un diagramme.
3Partie III : diagrammes de décision ordonnésIntroduction d'un opérateur ternaire, méthode systématique de construction d'un diagramme réduit ordonné à partir d'une formule logique quelconque, puis test d'égalité entre deux fonctions booléennes et de tautologie.
4Partie IV : circuits logiquesDénombrement des portes logiques nécessaires à la réalisation directe d'une fonction booléenne, étude du multiplexeur à deux entrées, puis traduction d'un diagramme de décision en circuit logique.
5Partie V : automatesConstruction d'un automate reconnaissant, sous forme de mots écrits en binaire par position, les solutions d'une équation linéaire entière, algorithme de résolution et extension aux quantificateurs du premier ordre.
Accessible. Le rapport indique que le sujet a été globalement bien traité, avec une longueur volontairement raisonnable pour laisser le temps de programmer, et que les meilleurs candidats ont correctement traité plus de 90 % du problème.
Ce qu'a observé le jury
6 erreurs relevées
Construction des arbres de décision non comprise · Multiplication inutile de fonctions auxiliaires · Diagramme supposé ordonné à tort
Afficher ou masquer la section
Le sujet, sans être de difficulté croissante, offrait de nombreuses questions de tout niveau et a été globalement bien traité. Quelques candidats n'ont toutefois pas compris la nature de la construction des arbres de décision et n'ont pas pu programmer correctement en conséquence. Le jury relève aussi des habitudes de programmation problématiques (multiplication de fonctions auxiliaires, indentation incorrecte) ainsi que des hypothèses implicites non justifiées, notamment sur le caractère ordonné d'un diagramme.
Les erreurs les plus sanctionnées
1
Construction des arbres de décision non comprisePartie I
Quelques candidats n'ont pas du tout compris la nature de la construction des arbres de décision et n'ont de ce fait pas pu programmer correctement les questions correspondantes.
« Quelques candidats cependant n’ont pas du tout compris la nature de la construction des arbres de décision »
2
Multiplication inutile de fonctions auxiliaires
Bien que le sujet décompose les algorithmes pour que chaque fonction reste simple, certains candidats créent une multitude de fonctions auxiliaires qui rendent la lecture du code totalement incompréhensible et multiplient les risques d'effet de bord.
« certains tiennent absolument à créer une multitude de fonctions auxiliaires rendant la lecture totalement incompréhensible »
3
Diagramme supposé ordonné à tortII.D
Le résultat de cette question est faux si le diagramme n'est pas ordonné, ce qui n'est a priori pas le cas à ce stade du sujet. La plupart des candidats ont implicitement supposé que le diagramme était ordonné, ce que le jury regrette.
« La plupart a implicitement supposé que le diagramme était ordonné. Le jury regrette cette erreur. »
4
Termes logiques « oubliés » plutôt que justifiés comme équivalentsPartie III
Les réponses sont souvent partielles en partie III, certains termes des expressions logiques étant simplement « oubliés » au lieu de constater explicitement qu'ils étaient équivalents ; le jury identifie cette méthode et reste attentif.
« certains termes dans les expressions logiques étant « oubliés » au lieu de constater explicitement qu’ils étaient équivalents »
5
Diagramme construit non réduitIII.F
Beaucoup de candidats oublient de réduire le diagramme qu'ils viennent de construire, alors que cette réduction était nécessaire pour répondre correctement à la question.
« beaucoup oublient de réduire le diagramme construit »
6
Concaténation de lettres non comprise comme numération positionnellePartie V
De nombreux candidats ne réalisent pas que la concaténation de lettres correspond ici à de la numération par position, ce qui traduit une incompréhension du rôle des automates étudiés dans cette partie.
« beaucoup de candidats ne réalisent pas que la concaténation de lettres correspond ici à de la numération par position »
Ce qui a été bien réussi
Le sujet a été globalement bien traité par les candidats.
Les meilleurs candidats ont traité correctement plus de 90 % du problème avec une rédaction propre et claire.
Le jury a apprécié que les candidats sortent directement des boucles dès que la solution est trouvée, et non à la fin.
Certaines copies sont jugées tout à fait excellentes, avec des connaissances solides.
Conseils du jury
Suivre le découpage en fonctions simples proposé par l'énoncé plutôt que de multiplier les fonctions auxiliaires.
Indenter correctement le code, en particulier les boucles, pour éviter des erreurs sur leurs bornes.
Sortir directement d'une boucle dès que la solution recherchée est trouvée, plutôt que d'attendre la fin de la boucle.
Ne jamais supposer implicitement une propriété non donnée par l'énoncé, comme le caractère ordonné d'un diagramme.
Rédiger des démonstrations complètes et claires, sans escamoter les termes ou les cas à justifier.
Écrire un code lisible par des humains : clair, simple, ou correctement commenté s'il ne peut pas l'être davantage.
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.
Les candidats indiqueront en tête de leur copie le langage de programmation choisi (Pascal ou Caml). Les candidats ayant choisi Caml devront donner le type de chaque fonction écrite. Les candidats travaillant en Pascal pourront écrire des fonctions ou des procédures.
I Arbres de décision
Un arbre de décision est un arbre binaire dans lequel :
un nœud interne est associé à une variable, parmi un ensemble V de variables ;
une feuille est associée à un booléen (vrai ou faux).
Si chaque variable de l'ensemble V reçoit une valeur booléenne, un tel arbre permet de prendre une décision en parcourant l'arbre:
on part de la racine ;
quand on arrive sur un nœud interne (racine comprise), on regarde quelle est la valeur de la variable associée au nœud : si elle vaut vrai on poursuit le parcours dans le sous-arbre gauche, sinon on poursuit le parcours dans le sous-arbre droit ;
quand on arrive sur une feuille, le booléen associé constitue la décision.
Conventionnellement, on représente l'arête menant au sous-arbre pour le «cas vrai» en trait plein ; l'arête menant au sous-arbre «cas faux » en pointillés. Schématiquement, un arbre est structuré comme indiqué ci-dessous à gauche.
Le schéma de droite ci-dessus illustre l'exemple : un module de cours est validé si l'examen est réussi ( e ), ou sinon, si l'étudiant a été assidu en cours (a) et qu'il réussit un examen de rattrapage ( r ). Cela revient à définir la validation du module par la formule logique e ∨ (a ∧ r).
On envisage une représentation simple d'un arbre de décision, à l'aide d'un tableau. On numérote les nœuds : la racine reçoit le numéro 0 , les autres nœuds sont numérotés arbitrairement par des entiers consécutifs à partir de 1. On crée un tableau contenant autant de cases que de nœuds, indicé à partir de 0 . La case d'indice i contient soit un triplet (nom de variable, numéro du fils gauche, numéro du fils droit) si le nœud numéro i est un nœud interne, soit un booléen si le nœud numéro i est une feuille.
En Caml, on définit le type :
type noeud =
Feuille of bool
| Decision of string * int * int;;
Un arbre de décision est donc représenté par un vecteur de nœuds (type noeud vect).
En Pascal :
type SorteNoeud = (Feuille, Decision);
type Noeud = record
sorte: SorteNoeud;
variable: string; (* Utilisé si sorte = Decision *)
g, d: integer; (* Utilisés si sorte = Decision *)
valeurFeuille: boolean; (* Utilisé si sorte = Feuille *)
end;
En Pascal un arbre de décision contenant n nœuds sera donc de type array [ 0..n − 1 ] of Noeud.
I. A - Définir une variable monAD représentant l'arbre de décision illustré précédemment.
Dans les deux questions suivantes, on veut faire déterminer une décision en fournissant une valuation des variables, c'est-à-dire la liste des seules variables qui sont vraies dans l'évaluation.
I.B - Définir une fonction eval_var qui, étant donnés le nom d'une variable (string) et une liste (Caml) ou un tableau (Pascal) des seules variables vraies, renvoie un booléen correspondant à la valuation de la variable indiquée.
I. C - Définir une fonction eval qui, étant donnés un arbre de décision et une liste (Caml) ou un tableau (Pascal) des seules variables vraies, renvoie un booléen correspondant à la décision finale.
II Diagrammes de décision
On souhaite compacter la représentation en mémoire des arbres de décision. Si plusieurs sous-arbres sont identiques, on n'a pas envie de les stocker plusieurs fois.
En raisonnant sur la représentation informatique des arbres de décision, on voit assez facilement une façon de procéder : si les arbres de numéros i et j sont identiques, on peut (par exemple) au niveau du parent p de j indiquer comme numéro de fils i au lieu de j et ainsi éliminer j de la représentation.
Ce faisant, on ne représente plus un arbre (car i a maintenant deux parents), mais un graphe orienté: on parle de diagrammes de décision. Néanmoins aucune connaissance particulière en théorie des graphes n'est requise pour aborder ce problème. On dira qu'il existe un arc de p vers i et on le notera p → ^b i avec b ∈ {T, F} (pour vrai ou faux), selon que l'arc est suivi dans le cas où p est vrai (précédemment : fils gauche) ou dans le cas où p est faux (précédemment : fils droit). Lorsque p → ^b i, on note i = succ_b(p).
Exemple : l'expression (z_1 ∧ z_3) ∨ (z_2 ∧ z_3) admet (entre autres) les diagrammes de décision ci-dessous.
II.A - Créer une fonction (Caml) ou procédure (Pascal) redirige à trois paramètres - un diagramme ainsi que deux indices v et w - qui supprime le nœud v dans le graphe et transforme tous les arcs u → ^b v en arcs u → ^b w. Les cases du tableau qui deviennent inoccupées sont remplies avec la valeur spéciale Vide.
Pour ce faire en Caml on complète :
type noeud =
Feuille of bool
| Decision of string * int * int
| Vide;;
De même en Pascal on ajoute une sorte de nœuds (le type Noeud lui-même reste inchangé) :
type SorteNoeud = (Feuille, Decision, Vide);
Pour transformer un arbre en diagramme sans répétition, on applique deux règles de simplification.
Élimination: Si pour un nœud v on a succ_F(v) = succ_T(v) = w alors on élimine v et on transforme les arcs u → ^b v en u → ^b w.
est transformé en
Isomorphisme : Soit v et w deux nœuds, v ≠ w. Si ce sont des feuilles avec valeur (v) = valeur(w) ou si ce sont des nœuds internes tels que variable (v) = variable(w) et succ_F(v) = succ_F(w) et succ_T(v) = succ_T(w) alors on élimine v et on transforme les arcsu → ^b v en u → ^b w.
est transformé en
est transformé en
II.B - Créer une fonction trouve_elimination, prenant en paramètre un diagramme et renvoyant l'indice d'un nœud pouvant être supprimé par élimination, s'il en existe un. Sinon, elle doit renvoyer -1 .
II. C - De même, créer une fonction trouve_isomorphisme, prenant en paramètre un diagramme, et renvoyant un couple d'indices correspondant à deux nœuds pouvant être simplifiés par isomorphisme, s'il en existe un. Sinon, elle doit renvoyer le couple (− 1, − 1).
Les candidats qui composent en Caml peuvent directement manipuler des couples. Les candidats qui composent en Pascal créeront une procédure recevant en paramètres deux variables entières transmises par référence :
procedure trouve_isomorphisme(diagramme: array of noeud; var i, j: integer);
On dit que le diagramme est sous forme réduite s'il n'existe pas de nœuds différents qui correspondent à la même formule logique.
II.D - Prouver l'assertion suivante :
Un diagramme est sous forme réduite si, et seulement si, ni la règle d'élimination ni la règle d'isomorphisme ne peuvent lui être appliquées.
II.E - Créer une fonction sans résultat (Caml) ou une procédure (Pascal) appelée reduit, prenant en paramètre un diagramme, qui détecte les deux simplifications possibles, effectue les redirections correspondantes, jusqu'à ce qu'il ne soit possible de faire aucune simplification supplémentaire.
On obtient à ce stade une représentation du diagramme simplifié sous forme d'un tableau dans lequel certaines cases ne sont plus utilisées : elles sont marquées Vide.
III Diagrammes de décision ordonnés
Nous nous intéressons maintenant à la construction d'arbres de décision à partir de formules logiques.
Étant données des formules logiques t, e_1 et e_2, on définit l'opérateur t → e_1, e_2 par :
t → e_1, e_2 = (t ∧ e_1) ∨ (¬t ∧ e_2)
III.A - Soient x et y des formules logiques quelconques. Montrer que les trois formules logiques suivantes
¬x, x ∨ y, x ∧ y
peuvent s'écrire en utilisant uniquement les constantes 0 (faux), 1 (vrai), l'opérateur ⋅ → ⋅, ⋅ défini précédemment et les variables x et y.
III. B - Montrer que (a → b, c) → d, e = a → (b → d, e), (c → d, e).
III. C - Déduire de ce qui précède une méthode systématique de construction d'un arbre de décision à partir d'une formule logique quelconque.
III.D - Soient t une variable booléenne et e une formule logique. Que vaut t → e, e ?
Un diagramme de décision est dit ordonné si, pour un ordre donné entre les variables x_1≺x_2≺…≺x_n, alors tout chemin partant de la racine vers les feuilles parcourt les variables dans cet ordre.
La fonction booléenne représentée par un diagramme de décision u est notée f^u.
La méthode de construction d'un arbre de décision imaginée en III.C ne respecte pas forcément un certain ordre des variables. Dans cette partie nous proposons une autre méthode de construction, un ordre étant donné a priori.
Pour une variable t, une expression e et une fonction booléenne f, on note f[t = e] la fonction déduite de f en remplaçant toutes les occurrences de t par e.
III. E - Que vaut t → f[t = 1], f[t = 0] ?
III.F - En déduire une méthode de construction d'un diagramme de décision réduit ordonné à partir d'une fonction booléenne sur un ensemble ordonné de variables.
III. G - Montrer que pour toute fonction booléenne f de n variables ordonnées x_1≺x_2≺…≺x_n, il existe un unique diagramme de décision réduit ordonné u tel que f^u = f.
III.H - À l'aide de ce qui précède, donner une méthode simple permettant de décider de l'égalité entre deux fonctions booléennes portant sur le même ensemble de n variables.
III.I - Comment déterminer facilement si une formule logique est une tautologie ?
IV Circuits logiques
On sait que toute fonction booléenne peut se mettre sous forme normale disjonctive: f s'écrit comme une disjonction (un ou) de mintermes, sachant qu'un minterme est une conjonction (un et) entre toutes les variables de f, chacune d'entre elles pouvant éventuellement être niée.
Par exemple, f = z_1 ∧ (z_2 ∨ ¬z_3) s'écrit en forme normale disjonctive : f = (z_1 ∧ ¬z_2 ∧ ¬z_3) ∨ (z_1 ∧ z_2 ∧ ¬z_3) ∨ ( z_1 ∧ z_2 ∧ z_3 ). C'est une disjonction de trois mintermes.
IV.A - Pour une fonction booléenne f, évaluer le nombre de portes logiques nécessaires à sa réalisation directe à partir de sa forme normale disjonctive, en fonction du nombre de variables de f.
On appelle multiplexeur à deux entrées un circuit logique qui recopie sur sa sortie s l'une de ses deux entrées, e_0 ou e_1, en fonction de la valeur (resp. 0 ou 1) d'un signal de commande c.
s = {e_0, si c = 0; e_1, si c = 1
IV.B - Donner la table de vérité du multiplexeur à deux entrées.
IV.C - Donner un schéma pour réaliser le multiplexeur à deux entrées à partir de portes logiques élémentaires.
IV.D - Donner une méthode simple permettant de déterminer un circuit logique réalisant la fonction booléenne représentée par un diagramme de décision.
V Automates
On s'intéresse dans cette partie aux combinaisons booléennes d'équations linéaires sur les entiers. Par exemple, avec deux variables, la résolution du système (2x_1 − x_2 = − 4) ∧ (7x_1 − 3x_2 = 1) ou de (3x_1 − 5x_2 = 2) ∨ (¬(4x_1 − 3x_2 = 1)). Les combinaisons logiques peuvent être traitées par l'arbre de décision précédent. On veut construire des automates permettant de résoudre les équations linéaires. Dans le cas général, pour n un entier positif, ces équations à n variables peuvent s'écrire sous la forme ⟨a⃗|x⃗⟩ = k avec a⃗ = (a_1, …, a_n) ∈ ℤ^n, k ∈ ℤ, x⃗ = (x_1, …, x_n) ∈ ℕ^n, et ⟨ ⋅ | ⋅ ⟩ dénotant le produit scalaire usuel entre deux vecteurs. On note E = {0, 1} et on prend comme alphabet A l'ensemble E^n. Un mot
représente le vecteur d'entiers naturels x⃗ = (x_1, …, x_n) tel que x_i = ∑_(j = 1)^m x_(i, j)2^(j − 1) pour tout 1 ⩽ i ⩽ n.
On note x⃗ le vecteur d'entiers et x le mot de A^∗ associé à ce vecteur d'entiers. On rappelle que ⟨ ⋅ ⟩ représente la concaténation entre deux mots. V.A - Résoudre le système (2x_1 − x_2 = − 4) ∧ (7x_1 − 3x_2 = 1). Écrire le mot correspondant.
Étant donnée une équation linéaire ⟨a⃗|x⃗⟩ = k, on souhaite construire un automate A_(a⃗, k) qui reconnaisse seulement les mots correspondant aux solutions de l'équation. V ⋅ B - Soit v un mot de longueur au moins égale à 2 que l'on écrit sous la forme v = b ⋅ v ', où b est une lettre et v^′ un mot. Montrer que v⃗ est solution de l'équation ⟨a⃗|x⃗⟩ = k si et seulement si k − ⟨a⃗|b⃗⟩ est un entier pair et v⃗ ' est solution de l'équation ⟨a⃗|x⃗⟩ = k ', pour une valeur de k ' que l'on précisera.
On peut donc ainsi construire l'automate. Les états sont indexés par les valeurs k_i accessibles. On ajoute un état «rebut» noté ⊥. À partir d'un état k_i, pour toutes les lettres b de l'alphabet A, on crée les états k_j, s'ils n'existent pas encore et les transitions ( k_i, b, k_j ), si k_i − ⟨a⃗|b⃗⟩ est un entier pair (la valeur de k_j étant le k^′ de la question précédente) ou les transitions ( k_i, b, ⊥ ) sinon. V.C - Préciser, en le justifiant l'état initial de l'automate A_(a⃗, k), ainsi que le (les) état(s) final(aux). V.D - Montrer que l'on construit ainsi un nombre fini d'états de l'automate A_(a⃗, k). V.E - Donner un algorithme permettant de déterminer s'il existe des solutions de l'équation ⟨a⃗|x⃗⟩ = k. Justifier que cet algorithme se termine. V.F − Construire l'automate pour l'équation : x_1 − 4x_2 + 2x_3 = 1. Donner également le tableau indiquant les transitions: en ligne les états accessibles ; en colonne les différentes lettres de l'alphabet (dans l'ordre lexical précisé ci-dessous) ; chaque case du tableau contient l'état atteint par lecture de la lettre à partir de l'état correspondant.
Pour éviter de surcharger le dessin de l'automate, on pourra ne pas représenter les transitions vers
l'état ⊥.
On définit l'ordre lexical sur les lettres de l'alphabet E^n par : si a = (a_1; ⋮; a_n) et b = (b_1; ⋮; b_n) sont dans l'alphabet, on a (a≺b) ⇔ [(a_1 < b_1) ou (∃i, 2 ⩽ i ⩽ n/∀j, 1 ⩽ j < i, a_j = b_j et a_i < b_i)]. V.G - En déduire toutes les solutions du problème avec x_1 < 8, x_2 < 8 et x_3 < 8.
V.H - Comment peut-on modifier l'automate précédent pour prendre en compte les quantificateurs du premier ordre, c'est-à-dire des formules comme ∃x_1, ∀x_2, (x_1 − 4x_2 + 2x_3 = 1) ?
Questions fréquentes
4 questions
Sur quels chapitres porte l'épreuve d'informatique (option info) Centrale MP 2013 ?
Afficher ou masquer la section
Sur quels chapitres porte l'épreuve d'informatique (option info) Centrale MP 2013 ?
+
Le sujet porte sur les arbres et diagrammes de décision, leur réduction et leur construction ordonnée, les circuits logiques (multiplexeur, formes normales), et les automates pour résoudre des systèmes d'équations linéaires entières.
Quelle est la moyenne à l'épreuve d'informatique (option info) Centrale MP 2013 ?
+
Le rapport ne communique aucune moyenne ni écart-type chiffrés ; il indique seulement que les meilleurs candidats ont traité correctement plus de 90 % du problème.
Quelles erreurs le jury a-t-il le plus relevées à cette épreuve d'informatique (option info) Centrale MP 2013 ?
+
Le jury relève une construction des arbres de décision non comprise par certains, un code rendu illisible par une multiplication de fonctions auxiliaires, une hypothèse implicite erronée sur le caractère ordonné d'un diagramme, et des démonstrations incomplètes en partie III.
Cette épreuve d'informatique (option info) Centrale MP 2013 est-elle difficile ?
+
Le rapport la juge globalement bien traitée par les candidats, avec une longueur volontairement raisonnable et des questions de tout niveau, même si certaines notions structurelles ont posé des difficultés à une partie des candidats.
Pas de description pour le moment
Commentaires• Centrale Option Informatique MP 2013
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Structures de données… (+2)CCINP Option Informatique MP 2026CCINP · 2026Sujet seul
Même année, X-ENSX ENS Option Informatique MP 2013X-ENS · 2013Corrigé
Même année, MinesMines Option Informatique MP 2013Mines · 2013Corrigé
.jpg)
.jpg)
.jpg)
.jpg)
