Centrale Informatique MP 2013

Thème de l'épreuve Diagrammes de décision
Principaux outils utilisés logique, arbres binaires, automates finis

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


(, % Informatique

"à «
--/ MP

EÜNEÜUHS EENTHHLE°SUPËLEE 4 heures Calculatrices autorisées

2013

Les candidats indiqueront en tête de leur copie le langage de programmation 
choisi (Pascal on 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 noeud 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 noeud interne (racine comprise), on regarde quelle 
est la valeur de la variable associée
au noeud : 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.

Oonventionnellement, on représente l'arête menant au sous--arbre pour le << cas 
vrai >> en trait plein ; l'arête me--

nant au sous--arbre << cas faux >> en pointillés. Schématiquement, un arbre est 
structuré comme indiqué ci--dessous

a gauche.

variable e
\ \ / \ \
\ \ . N
\ \ 4 vrai a
\
sous--arbre sous--arbre / \.,
si variable si variable 7° \ faux
vraie fausse _/ \«
vrai faux

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 V (a /\ r).
On envisage une représentation simple d'un arbre de décision, a l'aide d'un 
tableau. On numérote les noeuds : la
racine reçoit le numéro 0, les autres noeuds sont numérotés arbitrairement par 
des entiers consécutifs à partir de
1. On crée un tableau contenant autant de cases que de noeuds, indicé a 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 noeud numéro i est un noeud
interne, soit un booléen si le noeud numéro i est une feuille.
En Caml, on définit le type :
type noeud =
Feuille of bool
l Decision of string * int * int;;

Un arbre de décision est donc représenté par un vecteur de noeuds (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 noeuds sera donc de type array [O. 
.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.

2013--01-21 18:29:03 Page 1/4 GC) BY--NC-SA

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 a 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 a la 
décision finale.

Il Diagrammes de décision

On souhaite compacter la représentation en mémoire des arbres de décision. Si 
plusieurs sous--arbres sont iden--
tiques, 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 75 et j sont identiques, on peut (par 
exemple) au niveau du parent }) de j
indiquer comme numéro de fils 75 au lieu de j et ainsi éliminer j de la 
représentation.

Ce faisant, on ne représente plus un arbre (car 75 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

b
pour aborder ce problème. On dira qu'il existe un arc de 19 vers 75 et on le 
notera }) --> 75 avec 19 EUR {T, F} (pour
mai ou fauoe), selon que l'arc est suivi dans le cas où 19 est vrai 
(précédemment : fils gauche) ou dans le cas où 19

est faaa: (précédemment : fils droit). Lorsque }) --> 75, on note 75 : succb(p).

Exemple : l'expression (z1 /\ 23) V (272 /\ @) admet (entre autres) les 
diagrammes de décision ci--dessous.

21 21 21
/ \ \ \ \ 3 / \ >l / \ &
Z2 Z2 Z2 Z2 23 Z2
\ \ / / \ \_/ /
/ \N / \>l l/// // \/ _\J //
23 23 23 23 23 " // vrai faux « * /
\ \ \ \ \ /
/ \: / \: / \: / \: / \: / :/
vrai faux vrai faux vrai faux faux faux vrai faux <" ' /
II .A -- Créer une fonction (Caml) ou procédure (Pascal) redirige a trois 
paramètres -- un diagramme ainsi
b
que deux indices @ et w -- qui supprime le noeud @ dans le graphe et transforme 
tous les arcs u --> @ en arcs

b
a --> w. Les cases du tableau qui dev1ennent 1noccupees sont remplies avec la 
valeur speciale Vide.

Pour ce faire en Caml on complète :

type noeud =
Feuille of bool
l Decision of string * int * int
l Vide;;
De même en Pascal on ajoute une sorte de noeuds (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.

-- Elimination : Si pour un noeud @ on a such(v) : succT(v) : w alors on 
élimine @ et on transforme les arcs

b ()
u-->venu-->w.

est transformé en

/\
(\_//
s<----------

-- Isomorphisme : Soit @ et w deux noeuds, @ # w. Si ce sont des feuilles avec 
valeur(v) : valeur(w) ou si ce
sont des noeuds internes tels que variable(v) : variable(w) et such(v) : 
such(w) et succT(v) : succT(w)
b b

alors on élimine @ et on transforme les arcs u --> @ en a _) w.

a a a a
\ \ \ \
/ \" \/ \\ / \--*l \/ \\
S f ' S
.. v(z1) w(z1) est trans orme en w(z1)
\ | \
\ \ l \ \
\ | \ >l
\ | .
" V . faux vrai
faux vrai
II .B -- Créer une fonction trouve_elimination, prenant en paramètre un 
diagramme et renvoyant l'indice

d'un noeud pouvant être supprimé par élimination, s'il en existe un. Sinon, 
elle doit renvoyer --1.

2013--01-21 18:29:03 Page 2/4 @C) BY--NC-SA

II.C -- De même, créer une fonction trouve_isomorphisme, prenant en paramètre 
un diagramme, et ren--
voyant un couple d'indices correspondant a deux noeuds 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 noeuds 
différents qui correspondent a 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 pa--
ramè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 a 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 a la construction d'arbres de décision a 
partir de formules logiques.

Étant données des formules logiques t, el et 62, on définit l'opérateur t --> 
61,62 par :
t--> 61,62 : (t/\EUR1)V(--lt/\EUR2)

III .A -- Soient :E et y des formules logiques quelconques. Montrer que les 
trois formules logiques suivantes

wc, oeVy, oe/\y

peuvent s'écrire en utilisant uniquement les constantes 0 (faux), 1 (vrai), 
l'opérateur - --> -, - défini précédemment
et les variables :E et y.

III.B -- Montrer que (a --> b,c) --> d, e = a --> (19 --> d, e), (c --> d, 6).

III .C -- Déduire de ce qui précède une méthode systématique de construction 
d'un arbre de décision a partir
d'une formule logique quelconque.

III .D -- Soient t une variable booléenne et e une formule logique. Que vaut 75 
--> e, e ?

Un diagramme de décision est dit ordonné si, pour un ordre donné entre les 
variables 5151 < OE2 < . . . < 515... 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 ".

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 75, une expression 6 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 75 --> f[t : 1],f[t : O] ?

III .F -- En déduire une méthode de construction d'un diagramme de décision 
réduit ordonné a 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 
5151 < OE2 < . .. < 515... il existe
un unique diagramme de décision réduit ordonné u tel que f " = f .

III .I-I -- À 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 minterme3, 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 : z1 /\ (272 V --uz3) s'écrit en forme normale disjonctive : f = 
(271 /\ --\22 /\ --\23) V (271 /\ Z2 /\ --\23) V
(271 /\ Z2 /\ 233). C'est une disjonction de trois mintermes.

I V.A -- Pour une fonction booléenne f , évaluer le nombre de portes logiques 
nécessaires a sa réalisation directe
a partir de sa forme normale disjonctive, en fonction du nombre de variables de 
f .

2013--01-21 18:29:03 Page 3/4 @C) BY--NC-SA

On appelle multipleoeeur a deux entrées un circuit logique qui recopie sur sa 
sortie 3 l'une de ses deux entrées,
eo ou el, en fonction de la valeur (resp. 0 ou 1) d'un signal de commande 0.

c
eo si c = 0 l
el si c = 1 mult1plexeur % 3
61 -->

I V.B -- Donner la table de vérité du multiplexeur a deux entrées.
IV. C' -- Donner un schéma pour réaliser le multiplexeur a deux entrées a 
partir de portes logiques élémentaires.

I V.D -- Donner une méthode simple permettant de déterminer un circuit logique 
réalisant la fonction boo--
lé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 (2oe1 -- 5152 = --4) /\ (7oe1 -- 
35152 = 1) ou de (35151 -- 55152 = 2) V
(--u(4oe1 -- 35152 = 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 a n variables peuvent s'écrire sous la forme <älzî) : 16 
avec d' : (al, . . ., a...) E Z", 16 EUR Z,
a? : (acl, . . ., 51%) E N", et {l) dénotant le produit scalaire usuel entre 
deux vecteurs. On note E = {0,1} et on
prend comme alphabet A l'ensemble E ". Un mot

961,1 OE1,m
oe : : . . . : EUR A*
oen,1 oen,m
m
représente le vecteur d'entiers naturels a? : (acl, . . ., oen) tel que 515, : 
Ë gr...-23_1 pour tout 1 < 75 < n.
J=1

On note 56 le vecteur d'entiers et :E le mot de A* associé a ce vecteur 
d'entiers. On rappelle que << -- >> représente
la concaténation entre deux mots.

V.A -- Résoudre le système (2oe1 -- 5152 = --4) /\ (7oe1 -- 35152 = 1). Écrire 
le mot correspondant.

Etant donnée une équation linéaire <ä'lzî) : k, on souhaite construire un 
automate Aä)k qui reconnaisse seulement
les mots correspondant aux solutions de l'équation.

V.B -- Soit @ un mot de longueur au moins égale a 2 que l'on écrit sous la 
forme @ = b -- v', où 19 est une lettre

--»

et 1)' un mot. Montrer que 17 est solution de l'équation <ä'lzî) : 16 si et 
seulement si k -- <ä'lb) est un entier pair
et "D" est solution de l'équation <älzî) : 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 lc,-- accessibles. On ajoute un
état << rebut >> noté 1. A partir d'un état k,, pour toutes les lettres 19 de 
l'alphabet A, on crée les états le,-, s'ils

--»

n'existent pas encore et les transitions (le,, 19, k,), si le,- -- (5119) est 
un entier pair (la valeur de kj étant le k' de
la question précédente) ou les transitions (k,,b,1) sinon.

V.C -- Préciser, en le justifiant l'état initial de l'automate 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ä)k.
V.E -- Donner un algorithme permettant de déterminer s'il existe des solutions 
de l'équation <ä'lzî) : k.

Justifier que cet algorithme se termine.

V.F -- Construire l'automate pour l'équation : oe1 -- 45152 + 25153 = 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 a 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 1.
al 51
On définit l'ordre lexical sur les lettres de l'alphabet E '" par : si a = f et 
b = { sont dans l'alphabet,
an bn
ona (a
			

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique MP 2013 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par
Charles-Pierre Astolfi (ENS Cachan) et Guillaume Batog (Professeur en CPGE).

Ce problème étudie la représentation de formules logiques à l'aide d'arbres et 
de
diagrammes de décision. Le sujet est composé de cinq parties.
· La partie I introduit les arbres de décision, qui sont des arbres binaires 
permettant de représenter des formules logiques. Un algorithme d'évaluation 
d'un tel
arbre, représenté comme un vecteur, est demandé.
· La partie II demande d'écrire une procédure compactant au maximum un arbre
de décision en construisant un « diagramme de décision » (dit réduit) dont les
noeuds correspondent à des formules logiques différentes.
· La partie III commence par donner une méthode directe (sans passer par les
arbres de décision) construisant un diagramme de décision à partir d'une 
formule logique. On s'intéresse ensuite aux diagrammes de décision ordonnés,
qui ont la propriété qu'une formule logique admet un unique diagramme de
décision ordonné réduit, ce qui permet de décider facilement si deux formules
logiques sont équivalentes, ou si l'une est une tautologie.
· La partie IV cherche à construire un circuit logique à partir d'une formule,
d'abord directement, puis en utilisant les diagrammes de décision. Pour cela,
on introduit et étudie des multiplexeurs, qui sont des petits circuits basiques
permettant de réaliser physiquement des diagrammes de décision.
· Enfin, la partie V, très différente des précédentes, s'intéresse à la 
représentation
des solutions de combinaisons booléennes d'équations linéaires sur les entiers
grâce à des automates finis. Une construction est proposée et il est demandé de
l'appliquer à un exemple d'équation linéaire.
Les parties sont indépendantes, même si les parties II et III utilisent des 
définitions des parties précédentes. Le sujet aborde largement les notions de 
logique au
programme ; plus accessoirement, la partie I utilise des arbres binaires, et la 
partie V
des automates finis. Il s'agit d'un problème relativement facile et classique : 
en effet,
plusieurs sujets de concours se sont déjà intéressés aux diagrammes de décision,
par exemple les sujets 1999 et 2012 de l'X. Il contient assez peu de questions 
de
programmation (celles-ci sont toutes regroupées dans les deux premières 
parties).
Quelques questions théoriques de logique sont cependant difficiles, d'autant 
que la
formulation de l'énoncé est parfois très floue.

Indications
Partie I
I.C Utiliser une fonction récursive auxiliaire qui parcourt le chemin de la 
racine
à une feuille, en fonction de la valuation des variables rencontrées, que l'on
calcule grâce à la fonction de la question I.B.
Partie II
II.B Parcourir le vecteur représentant le diagramme à l'aide d'une boucle while 
à
la recherche d'un noeud où la règle d'élimination peut s'appliquer. On sortira
de la boucle dès qu'un tel noeud est trouvé.
II.C Procéder de même que dans la question II.B, mais en utilisant deux boucles
while imbriquées pour parcourir l'ensemble des couples de noeuds.
II.D Attention, l'énoncé de cette question est erroné. Prouver seulement la 
condition
nécessaire de l'assertion : si le diagramme est réduit, alors aucune des deux
règles de simplification ne peut lui être appliquée. Trouver ensuite un 
contreexemple à la réciproque.
Partie III
III.B Développer la formule (a  b, c)  d, e pour trouver sa forme normale 
disjonctive, la simplifier puis la factoriser afin de voir apparaître 
l'opérateur (a  ·, ·).
III.C Commencer par utiliser les questions III.A et III.B pour transformer toute
formule logique en une formule n'utilisant que l'opérateur (x  ·, ·) avec x
une variable.
III.E Montrer que pour toute valuation v des variables de f ,
(t  f [t = 1], f [t = 0])(v) = f (v)
III.F Expliquer comment construire un diagramme de décision ordonné à partir
d'une formule logique. En appliquant les règles de simplification de la partie 
II,
on obtient alors un diagramme de décision ordonné où ni la règle d'élimination 
ni la règle d'isomorphisme ne peuvent s'appliquer. Conclure en supposant
que l'équivalence de la question II.D est vraie pour les diagrammes de décision 
ordonnés.
III.G Faire une récurrence sur le nombre n de variables de la fonction 
booléenne.
III.H Utiliser la construction de la question III.F, et l'unicité prouvée dans 
la question III.G.
Partie IV
IV.A Commencer par dénombrer les mintermes sur un ensemble à n variables.
Partie V
-
V.C Faire en sorte que le langage reconnu par un état k  de l'automate A
a ,k soit

-

-

-

l'ensemble des mots v  A tels que v est une solution de h a | x i = k  .
-
V.D En partant de l'état initial de A
a ,k , montrer que l'on construit uniquement
des états de la forme
p
P
k
i
-
p
p-i+1
2
2
i=1

avec p un entier naturel, et (i )16i6p des entiers que l'on borne uniformément.

I. Arbres de décision
I.A Pour construire un arbre de décision, on peut, par exemple, créer un vecteur
de type noeud de taille égale au nombre de noeuds de l'arbre, que l'on 
initialise par
exemple avec des feuilles vrai. On remplace ensuite les noeuds un par un avec 
leur
valeur réelle. Pour information, on a représenté à droite la numérotation 
choisie pour
créer l'arbre.
let monAD
monAD.(0)
monAD.(2)
monAD.(3)
monAD.(4)
monAD.(6)

= make_vect 7 (Feuille true);;
<- Decision ("e",1,2);
<- Decision ("a",3,4);
<- Decision ("r",5,6);
<- Feuille false;
<- Feuille false;;

0
1

2
3

5

4
6

I.B On parcourt la liste l des seules variables vraies à la recherche de la 
variable x,
grâce à une fonction récursive. Si on trouve la variable x, on renvoie true ; 
si on arrive
à la fin de la liste l sans l'avoir trouvée, on renvoie false. La fonction 
eval_var
est de type 'a -> 'a list -> bool : en particulier, si on suppose que son 
premier
argument est une chaîne de caractères, on obtient une fonction de type string ->
string list -> bool.
let rec eval_var x l =
match l with
|[] -> false
|y::l' -> (y = x) || (eval_var x l');;
I.C On utilise une fonction auxiliaire parcours récursive de type int -> bool 
telle
que parcours v renvoie l'évaluation du sous-arbre de racine d'indice v. Si v 
est une
feuille, l'évaluation est immédiate. Sinon, on calcule la valuation de la 
variable à la
racine grâce à la fonction eval_var puis on évalue le sous-arbre gauche si la 
variable
s'évalue à vrai et le sous-arbre droit dans le cas contraire. La fonction 
parcours est
appelée à partir de la racine d'indice 0. La fonction eval est de type noeud 
vect ->
string list -> bool.
let eval arbre l =
let rec parcours v =
match arbre.(v) with
|Feuille b -> b
|Decision (x,w,w') ->
if (eval_var x l) then parcours w else parcours w'
in parcours 0;;

II. Diagrammes de décision
II.A La fonction diag commence par supprimer le noeud v en associant la valeur 
Vide à l'élément correspondant du vecteur codant le diagramme de décision.
On parcourt ensuite ce vecteur à l'aide d'une boucle for à la recherche d'un 
noeud
u tel qu'au moins l'un de ses sous-arbres est v : dans ce cas, le (ou les) 
sous-arbre(s)
est (sont) remplacé(s) par w. La fonction redirige est de type noeud vect -> int
-> int -> unit.
let redirige diag v w =
diag.(v) <- Vide;
for u = 0 to vect_length diag - 1
match diag.(u) with
|Decision (x,v1,v2) when v1 = v
diag.(u) <- Decision (x,w,w)
|Decision (x,v1,v2) when v1 = v
diag.(u) <- Decision (x,w,v2)
|Decision (x,v1,v2) when v2 = v
diag.(u) <- Decision (x,v1,w)
|_ -> ()
done;;

do
&& v2 = v ->
->
->

II.B La fonction trouve_elimination, de type noeud vect -> int, parcourt le
vecteur codant le diagramme de décision à la recherche d'un noeud v pouvant être
éliminé. On réalise ce parcours à l'aide d'une boucle while. On initialise 
ainsi deux
références v et b enregistrant l'indice courant et un booléen vrai si et 
seulement si
un noeud pouvant être éliminé a déjà été trouvé. La référence v est initialisée 
à 0
et b à false. On sort de la boucle lorsque la référence v atteint la fin du 
vecteur ou
lorsque b devient égal à true.
let trouve_elimination diag =
let m = vect_length diag in
let v = ref 0 and b = ref false in
while !v < m && not !b do
match diag.(!v) with
|Decision (x,w,w') when w = w' -> b := true
|_ -> v := !v + 1
done;
if !b then !v else -1;;
II.C La fonction trouve_isomorphisme, de type noeud vect -> int * int, réalise 
un parcours similaire à la fonction de la question II.B. À l'aide de deux 
boucles
while imbriquées, l'ensemble des couples d'indices (v, w), avec v < w, est 
parcouru : une boucle externe parcourt l'ensemble des indices v dans l'ordre 
croissant,
et une boucle interne parcourt l'ensemble des indices de v + 1 au dernier dans 
l'ordre
croissant. Pour chaque couple, on cherche si v et w sont deux feuilles de même 
valeur,
ou deux noeuds vérifiant les conditions décrites dans l'énoncé.