Université Blaise Pascal – UFR S.T. – L1 S1 informatique A+B

TP final noté de Caml : groupe I3 – jeudi 8 décembre 2016, 10h15-11h15 (durée : une heure).
 
Important : Les questions devront être traitées, autant que possible, dans l'ordre. Il est attendu des réponses fonctionnelles cohérentes construites dans les règles de l'art pour la partie traitée par le binôme dans le temps imparti.
Envoyer successivement à la fin de la séance, dans le support correspondant sur l'ENT, deux fichiers texte (extension .txt) :
– Un fichier copiant intégralement l'exécution de votre travail dans l'interpréteur Caml, et
– un fichier contenant uniquement le code source de votre travail.

Introduction : On veut pouvoir représenter l'arbre généalogique d'une personne. Il s'agit d'un arbre binaire où chaque noeud représente un individu. Chaque noeud est relié à deux autres noeuds correspondant respectivement à son père et à sa mère (s'ils sont connus). Si un individu a le numéro généalogique n, sont père a le numéro 2n et sa mère le numéro 2n+1. L'individu racine a le numéro 1.

Première partie

1.1. Créer un type date en utilisant l'ordre ISO : Année, mois, jour.
Définir une date dj correspondant à la date du jour.

1.2. Créer un type individu contenant, dans l'ordre, un nom, un prénom,et une date de naissance.
Créer une variable dm de ce type correspondant à Danielle Martin, agée de 19 ans aujourd'hui.

1.3. Créer un type genearbre correspondant à un arbre généalogique, sans oublier que l'étiquette d'un noeud contient un individu ET son numéro généalogique.
En utilisant la variable dm, créer l'arbre généalogique dmGA de Danielle Martin, sachant qu'elle est née de père et de mère inconnus.

1.4. Créer des variables individus en prévision de votre arbre généalogiques : moi, papa, maman, et grands-parents...

1.5. Avec les variables précédentes, créer un arbre généalogique monarbre remontant à partir de vous jusqu'à vos grands parents.
N.B. pour éviter les données confidentielles, vous pouvez mettre des informations fictives pour vos ascendants.

Deuxième partie : Créer les fonctions primitives suivantes.

2.1. estvide qui vérifie si un arbre est vide

2.2. estorphelin qui vérifie dans son arbre généalogique si une personne est orpheline de père et de mère, c'est-à-dire que ses deux parents sont inconnus.

2.3. perede qui retourne l'arbre généalogique du père.

2.4. merede qui retourne l'arbre généalogique de la mère.

2.5. ajoutpere qui ajoute un père à une personne sans père.

2.6. ajoutmere qui ajoute une mère à une personne sans mère.

2.7.Utiliser ces fonctions pour reconstruire votre arbre généalogique à partir des variables de la question 1.4.

Troisième partie

3.1. Créer un type indiliste qui est une liste d'individus.

3.2. Définir une fonction listergenea qui retourne la liste des individus présents dans un arbre généalogique, par numéro généalogique croissant. L'appliquer à monarbre.

3.3. Définir une fonction verinum qui vérifie et éventuellement corrige la numérotation d'un arbre généalogique en attribuant à la racine un numéro n passé en paramètre.
Appliquer cette fonction à votre mère et votre arbre généalogique.

3.4. Créer une fonction quelnumero qui vérifie si un individu est présent dans un arbre généalogique en retournant son numéro. La fonction retournera 0 si l'individu n'est pas dans l'arbre.
Appliquer cette fonction à votre père et votre arbre généalogique.

Quatrième partie (ne traiter que si toutes les questions précédentes l'ont été)

4.1. Créer une fonction materniser qui remplace tous les individus d'une liste d'individus par leur mère dans un arbre généalogique, quand c'est possible.

4.2. Créer une fonction afficher qui affiche un arbre généalogique sous forme de chaine de caractères, selon le même principe que ce qui a été fait en TD.

4.3. Créer une fonction sousgenea qui à partir d'une liste d'individus et d'un arbre généalogique donnant leur parenté, retourne le sous-arbre minimal de l'arbre contenant tous ces individus.