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 noud 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 noud 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 noud 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 noud 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 ?
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.
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 central (un
déplacement direct de A vers C ou de C vers A est interdit 1.
1 . Déterminer et prouver l'équation de récurrence correspondant au nombre
minimum de déplacements de disques
2. Résoudre cette équation
Exercice 3
Un
exercice sur les graphes
Le complémentaire d'un graphe non orienté G=(V,E) est le
graphe G'=(V, E') tel qu'il existe une arête entre
x et y dans G'
si et seulement si il n'y a pas d'arête entre x et y dans
G.
Montrer que si G n'est pas connexe alors G' l'est.
2. La réciproque est elle vraie ?
3.
On dit que deux graphes G1 et G2 d'ordre n sont
isomorphes si et seulement si ils sont égaux à la numérotation des sommets
près.
Montrer que si un graphe G est auto-complémentaire
(c'est-à-dire isomorphe à son complémentaire) alors le nombre de sommets de
G est soit un multiple de 4 soit un multiple de 4 plus un.
4. Trouver les deux plus petits
graphes qui sont auto-complémentaires