DS 4 (MPSI option 2021-2022) — Tas¶

Devoir surveillé · MPSI (option informatique) · 2021-2022 · partie II du DS 4 (2 h au total)

Cours : Tas

Autres parties : I. Logique

Corrigés

La source ne comporte pas de corrigé. Les corrigés des questions de programmation ci-dessous sont soit repris du fichier de code de l'auteur (DS_OI4.ml), soit des propositions (testées), à relire.

II. Tas¶

Dans cette partie, on cherche à créer une structure de données immuable appelée un tas-max pouvant contenir des éléments d'un type 'a ordonné totalement et défini par le type 'a tas des tas et les opérations suivantes :

tas_vide : 'a tas une valeur représentant un tas vide ;
ajoute : 'a tas -> 'a -> 'a tas telle que ajoute t x ajoute l'élément x sur le tas t ;
retire : 'a tas -> 'a * 'a tas telle que retire t renvoie un couple (x, t') où x est un plus grand élément parmi les éléments de t et t' est un tas dans lequel on a retiré x.

Tri par tas¶

Sans même savoir implémenter un tas, on peut l'utiliser pour obtenir un algorithme de tri :

Étant donné des éléments à trier, on les ajoute tous dans un tas.
Tant que le tas est non vide, on retire un élément du tas et on le place dans la sortie.

Comme on a la garantie d'avoir un élément plus grand que ceux qui restent à chaque fois qu'on en retire un, on est certain que la sortie sera triée dans l'ordre décroissant.

Question 6

Écrire une fonction remplit : 'a list -> 'a tas -> 'a tas qui prend en entrée une liste l et un tas t et renvoie un tas t' obtenu en ajoutant tous les éléments de l au tas t.

Corrigé

let rec remplit l t =
  match l with
  | [] -> t
  | x :: q -> remplit q (ajoute t x)

Question 7

Écrire une fonction vide : 'a tas -> 'a list qui vide un tas pour obtenir la liste de ses éléments dans l'ordre décroissant.

Question 8

Écrire une fonction tri : 'a list -> 'a list qui renvoie une liste triée dans l'ordre décroissant à l'aide d'un tas.

Question 9

Si on considère que ajoute et retire sont en complexité temporelle \(f(n)\) où \(n\) est la taille du tas et où \(f\) est croissante, quelle est la complexité de ce tri ?

Implémentation naïve¶

Pour représenter un tas, on va ici choisir une implémentation naïve :

type 'a tas = 'a list

let tas_vide = []
let ajoute t x = x :: t

Pour retirer, il va donc être nécessaire de trouver le maximum et de l'extraire. On décompose cela en deux fonctions.

Question 10

Écrire une fonction maximum : 'a list -> 'a qui renvoie la plus grande valeur dans la liste donnée en entrée.

Question 11

Écrire une fonction supprime : 'a list -> 'a -> 'a list qui supprime la première occurrence d'un élément dans une liste si elle le contient (sinon, on renvoie la liste inchangée).

Exemple : supprime [2;1;3;1] 1 renvoie [2;3;1].

Question 12

Écrire la fonction retire avec cette implémentation de tas à l'aide des deux fonctions précédentes.

Question 13

Quelle est la complexité de la fonction précédente ?

Question 14

Quelle est alors la complexité du tri par tas avec cette implémentation ?

Tas binaires¶

On va maintenant donner une implémentation des tas avec des arbres binaires.

On considère le type :

type 'a tas = Noeud of 'a tas * 'a * 'a tas | Nil

let tas_vide = Nil

Et on ne va considérer que des arbres dont l'étiquette de la racine est toujours la plus grande des étiquettes et dont les fils gauches et droits sont aussi des tas.

Si on note \(\eta(t)\) les étiquettes des nœuds de \(t\), on a donc la propriété \(tas\) définie ainsi :

\[ tas(t) := t = Nil \vee (t = Noeud(g,x,d) \wedge x = \max \eta(t) \wedge tas(g) \wedge tas(d)) \]

Ainsi l'arbre

est un tas mais

n'en est pas un.

Question 15

Écrire une fonction arbre_max : 'a tas -> 'a qui renvoie le plus grand élément d'un arbre non vide.

Attention : on ne suppose pas encore que l'arbre est un tas.

Question 16

En déduire une fonction est_un_tas : 'a tas -> bool qui indique si un arbre est bien un tas.

Pour l'ajout et l'extraction de la racine, on va utiliser une même opération : la fusion de deux tas. Il s'agit d'une opération qui, étant donnés deux tas \(t_1\) et \(t_2\) va renvoyer un tas comportant tous les éléments de \(t_1\) et de \(t_2\).

Pour cela, on procède ainsi :

Si \(t_1\) est vide, on renvoie \(t_2\).
Si \(t_2\) est vide, on renvoie \(t_1\).
Si \(t_1 = Noeud(g_1,x,d_1)\) et \(t_2 = Noeud(g_2,y,d_2)\) et \(x > y\), on va fusionner \(d_1\) et \(t_2\) pour obtenir \(t'\) et on renvoie \(Noeud(g_1,x,t')\).
On procède symétriquement si \(x \le y\) en renvoyant \(Noeud(g_2,y,t')\).

Question 17

Réaliser la fusion des deux tas

et

Question 18

Écrire une fonction fusionne : 'a tas -> 'a tas -> 'a tas qui fusionne deux tas.

Corrigé

let rec fusionne t1 t2 =
  match t1, t2 with
  | Nil, _ -> t2
  | _, Nil -> t1
  | Noeud (g1, x, d1), Noeud (g2, y, d2) ->
    if x > y
    then Noeud (g1, x, fusionne t2 d1)
    else Noeud (g2, y, fusionne t1 d2)

Question 19

Exprimer la complexité de cette fonction en fonction des deux arbres de tas fusionnés.

Pour ajouter un élément à un tas, on va fusionner le tas avec une feuille étiquetée par l'élément.

Question 20

Écrire une fonction ajoute : 'a tas -> 'a -> 'a tas.

Corrigé

let ajoute t x = fusionne t (Noeud (Nil, x, Nil))

Pour retirer un élément d'un tas non vide, on renvoie l'étiquette de la racine et le tas obtenu par fusion de ses deux sous-arbres.

Question 21

Écrire une fonction retire : 'a tas -> 'a * 'a tas.

Corrigé

let retire t =
  match t with
  | Nil -> failwith "vide"
  | Noeud (g, x, d) -> x, fusionne g d

Question 22

Exprimer la complexité de ajoute et retire.

Question 23

Détailler l'exécution du tri par tas avec la liste [1;6;2;4;3;7]. On donnera tous les tas apparaissant au cours du déroulement.