Consignes

Vous devrez soumettre votre travail (un unique fichier Caml valide) en utilisant l'interface TPLab.

Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

  1. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
  2. la présence de commentaires aux endroits appropriés,
  3. ...

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

Liens utiles

1. Arbres, tas, encore du tri (2h)

1.1. Arbres

Déclarez un type 'a arbre pour les arbres binaires ; et programmez les fonctions suivantes :

Programmez une fonction equilibre : 'a arbre -> bool qui vérifie si un arbre est équilibré (càd si la différence de longueurs entre la branche la plus longue et la branche la plus courte est au plus 1).

1.2. Tas

Un tas est une structure de donnée permettant d'optimiser la recherche du minimum dans un ensemble de données.

Un tas est simplement un arbre binaire qui vérifie la propriété inductive suivante :

Contrairement aux arbres binaires de recherche que l'on a vu en TD, cette structure ne permet pas d'optimiser la recherche d'un élément car on ne sait pas dans quel sous-arbre il faut chercher.

Déclarez un type 'a tas pour les tas et écrivez une fonction qui teste si un élément de ce type est effectivement un tas.

Pour ceci, vous pourrez utiliser une fonction auxiliaire aux (n:'a) (a:'a arbre) : bool qui vérifie en même temps :

Écrivez une fonction tas_equilibre : 'a tas -> bool qui vérifie si un arbre est un tas équilibré.

Écrivez une fonction pop_tas : 'a tas -> 'a tas permet de supprimer le le minimum d'un tas (tout en conservant la propriété d'être un tas).

Vous aurez pour ceci besoin d'une fonction fusionne : 'a tas -> 'a tas -> 'a tas qui fonctionne un peu comme la fonction fusion sur les liste triée.

L'insertion dans un arbre de recherche équilibré est un peu compliquée. Pour les tas, on peut utiliser le fait que les fils gauche et droit peuvent être permutés pour créer des tas équilibrés !

Écrivez la fonction insere : 'a -> 'a tas -> 'a tas qui insère un élément dans un tas.

Attention : cette fonction devra toujours insérer l'élément dans le fils droit, mais elle permutera le fils droit et le fils gauche. Cela permet de mélanger le tas et de le garder équilibré.

Remarque : la propriété importante est qu'un tas créé uniquement grâce à la fonction insere est équilibré q. Il est par contre possible que insere a t ne soit pas équilibré même si t est équilibré.

Vérifiez que les tas créés avec la fonction insere sont bien équilibrés. Pour ceci, vous pouvez partir du tas vide, insérer des éléments aléatoires (avec la fonction Random.int) et vérifier à chaque insertion que le tas obtenu est bien équilibré.

1.3. Tri par tas

Programmez le tri par tas : pour trier une liste par ordre croissant, on insère tous les éléments dans un tas, puis on vide le tas avec la fonction pop_tas pour récupérer les éléments dans l'ordre.

Comparez ce tri avec le tri fusion et le tri par insertion du TP1.

Dans les langages impératifs (C, Java, Python), les tas sont en général implémentés de manière très différente en utilisant des tableaux...

2. Crible d'Eratosthene (1 h)

2.1. Première version

Le crible d'Eratosthène est une méthode pour générer tous les nombres premiers plus petits qu'une limite choisie :

Par exemple, pour 10, les étapes seront : 

0/	p = [ ]                 l = [ 2; 3; 4; 5; 6; 7; 8; 9; 10 ]
2 passe dans p, et on supprime les multiples de 2

1/	p = [ 2 ]               l = [ 3; 5; 7; 9 ]
3 passe dans p, et on supprime les multiples de 3


2/ 	p = [ 2; 3 ]            l = [ 5 ; 7 ]
5 passe dans p, et on supprime les multiples de 5

3/	p = [ 2; 3; 5 ]         l = [ 7 ]
7 passe dans p, et on supprime les multiples de 7

4/	p = [ 2; 3; 5; 7 ]      l = [ ]
l est vide, on arrête

Les nombres premiers entre 1 et 10 sont effectivement 2, 3, 5 et 7.

Écrivez une fonction suppr_mult : int -> int list -> int list qui permet de supprimer tous les multiples d'un nombre dans une liste.

Écrivez une fonction crible1 : int -> int list qui calcule la liste des nombres premiers entre 0 et son premier argument (en utilisant l'algorithme ci-dessus).

Pour ceci, vous aurez probablement besoin d'une fonction récursive auxiliaire locale crible_aux : int list -> int list -> int list :

Jusqu'à quelle valeur de n pouvez-vous calculer crible1 n en un temps raisonnable ?

évitez les choses inutilement complexes comme les insertions d'un élément en fin de liste...

2.2. Optimisations

On peut améliorer la complexité de cette fonction en constatant deux choses :

Écrivez la fonction crible2 : int -> int list qui avec ces améliorations.

Comparez les fonctions crible1 et crible2.

Note : pour calculer la partie entière de la racine carrée d'un nombre entier, il faudra utiliser

On peut encore améliorer la fonction précédente en précalculant directement les 2 premières étapes, càd en supprimant directement les multiples de 2 et de 3. Pour ceci, la liste l doit contenir 

  [ 5; 7; 11; 13; 17; 19; 23; 25; ...]

Pour calculer l, on commence à 5 et on ajoute alternativement 2 et 4 au nombre précédent :

Si on veut précalculer l'étape suivante en utilisant la liste des entiers non multiples de 2, 3 ou 5 pour l, il faut commencer avec 7 et ajouter successivement 4, 2, 4, 2, 4, 6, 2 et 6.

Écrivez une fonction tourne : int list -> int -> int -> int list qui permet de calculer une telle liste : pour ``tourne l i n'', on commence à i, on ajoute successivement les éléments de l en boucle et on s'arrête quand on dépasse n.

Écrivez une fonction crible3 correspondante, que vous comparerez avec les précédentes.

Remarque : pour précalculer l'étape suivante, il faut commencer à 11 et utiliser la liste 

[ 2; 4; 2; 4; 6; 2; 6; 4; 2; 4; 6; 6; 2; 6; 4; 2; 6; 4; 6; 8;
  4; 2; 4; 2; 4; 8; 6; 4; 6; 2; 4; 6; 2; 6; 6; 4; 2; 4; 6; 2;
  6; 4; 2; 4; 2; 10; 2; 10 ]