Exercice 1 - Examen corrige

Mathématiques Discrètes
ESSI 1
Bref corrigé de l'examen de Janvier 2002 Exercice 1 Un peu d'induction
On défini l'ensemble des arbres binaires de recherche de nombres comme
suit :
Base : l'arbre binaire réduit à un seul n?ud contenant un entier quelconque
est un élément de ABR
Règles
R1 :Si T est dans ABR et si n est un entier plus grand que tous les
nombres contenus dans T, alors l'arbre binaire de racine un n?ud contenant
n, de sous arbre gauche T et de sous arbre droit vide est dans ABR
R2 : Si T est dans ABR et si n est un entier plus petit que tous les
nombres contenus dans T, alors l'arbre binaire de racine un n?ud contenant
n, de sous arbre gauche vide et de sous arbre droit T est dans ABR
R3 : Si T et T' sont dans ABR et si n est un entier plus grand que
tous les nombres contenus dans Tet plus petit que tous les nombres contenus
dans T', alors l'arbre binaire de racine un n?ud contenant n, de sous arbre
gauche T et de sous arbre droit T' est dans ABR
1- Si on utilise uniquement les nombres 1,2,3 et 4, combien y a-t-
il d'arbres binaires de recherche de nombres ayant 4 sommets
On peut les énumérer tous, mais alors on risque d'en oublier. Le mieux
c'est de dire : soit cn le nombre d'ABR ayant n sommets et contenant
les nombres de 1 à n. On a
[pic] à condition de poser c0=1.
On reconnaît là l'équation des nombres de catalans et l'on trouve
c4=14.
Ou bien on utilise cette équation pour calculer c2, c3 et c4, et l'on
trouve c2=1+1=2, c33=2+1+2=5 et c4=5+2+2+4=14 2. Soit A dans ABR définir inductivement une fonction qui teste si n
est contenu dans A. Essayez d'écrire une fonction dont la complexité soit
la meilleure possible. Prouvez votre fonction
Appelons appartient la fonction de NxABR dans {vrai,faux} , telle que
appartient(n,A) est vrai si et seulement si n est contenu dans A. Notons A(n) l'ABR réduit à un seul n?ud contenant l'entier n, A(T,n),
R1(T,n) l'ABR construit par la règle R1, R1(T,n) l'ABR construit par la
règle R2, R3(T,T',n) l'ABR construit par la règle R31, Soit App la fonction de NxABR dans {vrai,faux} définie inductivement par
App(n,A(m))=(n=m)
App(n,R1(T,m))=[pic]
App(n,R2(T,m))=[pic]
App(n,R3(T,T',m))=[pic]
On montre facilement par induction structurelle que App et Appartient
sont égaux.
On demandait une fonction dont la complexité soit la meilleure
possible. Pour véritablement parler de la complexité il faudrait programmer
ces fonctions et regarder le coût des primitives qui permettent de
« découper » un ABR en ses sous-arbres gauches et droits. Avant cela tout
ce que l'on peut dire c'est que si l'on programme récursivement en suivant
cette définition inductive le calcul de App(n,T) induira un nombre d'appels
récursifs en Omega(hauteur(T)).
Exercice 2 Tour de Hanoï On considère une variante des tours de Hanoï avec trois piquets 1,B,C et n
disques.
- les n disques sont de taille différente
- initialement les n disques sont rangés sur le piquet A, du plus
grand en bas, au plus petit en haut
- on désire amener les n disques dans le même ordre sur le piquet C
- on ne peut déplacer qu'un seul disque à la fois
- on ne peut pas poser un disque sur un disque de taille inférieure
- tous les mouvements de disques doivent se faire via le piquet
centrql (un déplacement direct de A vers C ou de C vers A est
interdit 1. Déterminer et prouver l'équation de récurrence correspondant au nombre
minimum de déplacements de disques Commençons par donner un algorithme récursif A(n,A,C) pour déplacer les n
disques de A vers C :
Si n=0, ne rien faire,
Sinon :
- A(n-1,A,C)
- déplacer le grand disque de A vers B
-A(n-1,C,A)
- déplacer le grand disque de B vers C
-A(n-1,A,C) A et C jouant des rôles identiques le nombre de mouvements minimum pour
déplacer n tours de A vers C ou de C vers A est le même. Soit mn ce
nombre, on a
-m0=0
-mn