CorrigeDS1_MPSI2

Corrigé
In [14]: (*type défini au préalable *)

type arbre = E | N of arbre * int * arbre
Out[14]: type arbre = E | N of arbre * int * arbre
In [15]: (*Question 1*)

let minimum t = match t with
| E -> failwith "arbre vide"
| N (tg,r,td) -> r
Out[15]: val minimum : arbre -> int = <fun>
In [16]: (*Question 2 *)
let rec est_un_arbre_croissant t = match t with
| E -> true
| N (E,a,E) -> true
| N (E,a,td) ->
(a <= minimum td) && (est_un_arbre_croissant td)
| N (tg,a,E) ->
(a <= minimum tg) && (est_un_arbre_croissant tg)
| N (tg,a,td) ->
(a <= minimum tg) && (a <= minimum td) &&
(est_un_arbre_croissant tg) && (est_un_arbre_croissant td)
Out[16]: val est_un_arbre_croissant : arbre -> bool = <fun>
Question 3
(Preuve de l'ignorant, par récurrence) Pour tout n ∈ N, on pose (n) la propriété
"pour tout sous-ensemble d'entiers naturels E de cardinal n, le nombre d'arbre binaire croissant à n
noeuds étiqueté par les éléments de E est égal à n!"
vrai pour n = 0 : l'arbre vide est l'unique arbre binaire à 0 noeud et est croissant. De plus, 0! = 1.
Hérédité : soit n ∈ N. On suppose que que pour tout k ≤ n, P (k) est vraie. Montrons que
P (n + 1) est vraie.
Pour tout k ∈ N, et E un ensemble à k éléments, on note Ak (E) l'ensemble des arbres binaires
croissants de taille k et étiquetés par les éléments de E . Remarquons que l'on a la décomposition :
An+1 (E) = ⋃ Ai (Ei ) ∗ (minE)

i∈{0,⋯n},Ei icombi
∗ An−i (E∖(Ei ∪ {minE})
on pourra remarquer que Ei décrit toutes les combinaisons possibles. De plus, il est clair qu'il s'agit
d'une réunion d'ensembles disjoints deux à deux. En passant au cardinal, on obtient :
card(An+1 (E) =
n
n
∑ ( )card(Ai {(1...i})card(An−i ({1..n − i}))
i=0
i
Par hypothèse de récurrence, on a alors :

n
n
card(An+1 (E)) = ∑ ( )i!(n − i)!
i=0
i
D'où
n
car(An+1 )(E) = ∑ n! = (n + 1)!
i=0
Donc P (n + 1) est vraie, ce qui conclut.
On pourra remarquer que la lecture infixe de l'arbre induit une bijection entre cette famille d'arbres et
l'ensemble des permutations correspondant.
Autre preuve possible : On constate que φAn+1 → An consistant à supprimer le n\oe{}ud étiqueté par
n + 1 fournit une surjection où chaque arbre image admet exactement n + 1 antécédants. Donc :
card(An+1 ) = (n + 1)card(An ). Par récurrence directe, on a alors card(An ) = n!.
Question 4
La bijection précédente permet de représenter ce calcul à l'aide d'une liste (fait pour simplifier l'écriture).
On obtient !
[6, 4, 3, 5, 1, 2]
Question 5
Par récurrence sur la taille de T1 et T2 .
Initialisation : au moins un des deux arbres est vide. Dans ce cas, la fusion est égale à l'un des
deux arbres qui est bien croissant.
Hérédité : Soit n ≥ 1. On suppose que la fusion de deux arbres croissants dont la somme des
tailles est inférieure àn vérifien la propriété. soit T1 = N(g1 , x1 , d1 ) et T2 = N(g2 , x2 , d2 )
deux arbres croissants tels que la somme des deux tailles est égale à n + 1.
Cas 1 : x1 ≤ x2 . Par hypothèse de récurrence, g = fusion(d_1,N(g_2,x_2,d_2)) est un arbre
croissant. De plus, x1 est plus petit que la racine de d1 . Donc x1 est bien plus petit que le
minimum de l'arbre g. Or x1 est plus petit que min g1 . Sachant que d1 est un arbre croissant,
on en déduit que l'arbre N(g, x1 , g1 ) est bien croissant.
Cas 2 : x1 > x2 . Dans ce cas on échange le rôle des deux arbres et on reprend le
raisonnemment du cas 1.
On en conlut par le principe de récurrence.
In [17]: (*Question 6*)

let rec fusion t1 t2 = match t1,t2 with
| _,E -> t1
|E,_ -> t2
|N(g1,x1,d1),N(g2,x2,d2) when x1 <= x2 -> N((fusion d1 t2),x1,g1)
|N(g1,x1,d1),N(g2,x2,d2) -> N((fusion d2 t1),x2,g2)
(*Question 7*)
let rec ajoute x t = match t with
| E -> N (E,x,E)
| N(g,y,d) when x <= y -> N(t,x,E)
| N(g,y,d) -> N((ajoute x d),y,g)
(*Question 8*)
let supprime_minimum t = match t with
| E -> failwith "arbre vide"
| N(g,x,d) -> fusion g d
(*Question 9*)
let ajouts_successifs tableau =
let n = Array.length tableau in
let rec aux i acc = match (i=n) with
| true -> acc
| _ -> aux (i+1) (ajoute tableau.(i) acc)
in
aux 0 E
(*Question 12*)
(*idée : on construit une fonction auxiliaire qui calcule simultanément le

nombre de noeuds et le potentiel *)
let potentiel t =
let rec potentiel_aux t = match t with
| E -> 0,0
| N(g,x,d) ->
let n_g,p_g = potentiel_aux g in
let n_d,p_d = potentiel_aux d in
let d_x = if n_g < n_d then 1 else 0 in
(1 + n_g + n_d , d_x + p_g + p_d)
in
snd (potentiel_aux t)
Out[17]: val fusion : arbre -> arbre -> arbre = <fun>
Out[17]: val ajoute : int -> arbre -> arbre = <fun>
Out[17]: val supprime_minimum : arbre -> arbre = <fun>
Out[17]: val ajouts_successifs : int array -> arbre = <fun>
Out[17]: val potentiel : arbre -> int = <fun>

CorrigeDS1_MPSI2

Transféré par

Droits d'auteur :

Formats disponibles

CorrigeDS1_MPSI2

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

CorrigeDS1_MPSI2

Transféré par

Droits d'auteur :

Formats disponibles

Corrigé

In [14]: (type défini au préalable )

Out[14]: type arbre = E | N of arbre * int * arbre

In [15]: (Question 1)

Out[15]: val minimum : arbre -> int = <fun>

Out[16]: val est_un_arbre_croissant : arbre -> bool = <fun>

An+1 (E) = ⋃ Ai (Ei ) ∗ (minE)

∗ An−i (E∖(Ei ∪ {minE})

Par hypothèse de récurrence, on a alors :

Donc P (n + 1) est vraie, ce qui conclut.

In [17]: (Question 6)

(*idée : on construit une fonction auxiliaire qui calcule simultanément le

Out[17]: val fusion : arbre -> arbre -> arbre = <fun>

Out[17]: val ajoute : int -> arbre -> arbre = <fun>

Out[17]: val supprime_minimum : arbre -> arbre = <fun>

Out[17]: val ajouts_successifs : int array -> arbre = <fun>

Out[17]: val potentiel : arbre -> int = <fun>

Vous aimerez peut-être aussi