Il va sans dire que vous êtes libres d'utiliser un autre éditeur de texte, à partir du moment où vous le maîtrisez et êtes à même de développer efficacement en Ocaml avec cet éditeur.
Ceux d'entre vous qui se sentent à l'aise avec Caml peuvent attaquer directement à la question tri par tas.
Écrire une fonction insertion_sort : int list -> int list qui réalise le tri par insertion d'une liste d'entiers. On rappelle que cela consiste à extraire le premier élément de la liste, à trier récursivement le reste de la liste, puis à insérer l'élément isolé (avec la fonction insertion).
Tester avec les exemples ci-dessous :
insertion_sort [1; 2; 3];; insertion_sort [3; 2; 1];; insertion_sort [];; insertion_sort [1];; insertion_sort [2; 1; 1;];;
Écrire une fonction fusion : int list * int list -> int list prenant en arguments deux liste supposées triées en ordre croissant et les fusionne en une unique liste triée.
En utilisant les deux fonctions précédentes, écrire une fonction mergesort : int list -> int list réalisant le tri fusion. On rappelle que le principe consiste à couper la liste en deux, à trier récursivement chacune des deux listes obtenues, puis à fusion les deux listes triées.
Écrire une fonction quicksort : int list -> int list réalisant le tri rapide (quicksort). On rappelle que le principe consiste à isoler un élément particulier de la liste (ici le premier), à partionner les éléments restants en utilisant la fonction partition ci-dessus, à trier récursivement les deux listes obtenues, et enfin à recoller les morceaux. Pour cette dernière étape on pourra utiliser la fonction de bibliothèque List.append qui effectue la concaténation de deux listes.
1 / \ 2 5 / \ 4 2 \ 6
Le but de cette question est de réaliser les deux opérations élémentaires sur la structure de tas que sont l'insertion d'un nouvel élément et l'extraction du plus petit élément (c'est-à-dire la racine). On se donne le type heap suivant pour représenter les tas :
type heap = Null | Fork of int * heap * heapOn commence par une opération plus complexe, merge : heap -> heap -> heap, qui réalise la fusion de deux tas a et b. Le principe est le suivant. Si a ou b est Null, le résultat est immédiat. Sinon, on compare la racine de a et celle de b ; supposons que la racine de a soit la plus petite (sinon, on échange les rôles de a et b). Le résultat est alors un tas dont la racine est celle de a, dont le sous-arbre gauche est le sous-arbre droit de a, et dont le sous-arbre droit est obtenu en fusionnant récursivement le sous-arbre gauche de a et l'arbre b. Écrire la fonction merge.
À l'aide de la fonction merge, écrire une fonction add : int -> heap -> heap qui insère un nouvel élément dans un tas. (On pourra se servir du tas Fork (x, Null, Null) qui contient uniquement x.)
De même, utiliser la fonction merge pour écrire une fonction extract_min : heap -> int * heap qui extrait le plus petit élément d'un tas (sa racine) et retourne le tas constitué par tous les autres éléments. Lorsque le tas est vide, on pourra lever l'exception EmptyHeap ainsi déclarée :
exception EmptyHeap
Note : ces tas s'appellent des skew heaps et sont à la fois persistants, élégants et très efficaces.
Pour cela, commencer par écrire une fonction heap_of_list : int list -> heap qui construit un tas avec tous les éléments d'une liste.
Écrire ensuite la fonction inverse list_of_heap : heap -> int list qui construit une liste triée avec tous les éléments d'un tas.
Enfin, combiner les deux fonctions précédentes en une fonction heapsort : int list -> int list réalisant le tri par tas.
sort : ('a -> 'a -> bool) -> 'a list -> 'a listoù la fonction passée en argument correspond à la relation « inférieur ou égal à ». On pourra tester ainsi :
sort (<=) [1;2;3;2;4;1];;
module Sort(X : sig type t val le : t -> t -> bool end) : sig val sort : X.t list -> X.t list endOn pourra tester ainsi :
module S = Sort(struct type t = int let le = (<=) end);; S.sort [1;2;3;2;4;1];;
Par exemple, en tapant successivement les touches 2, 6, 6, 5, 6, 8 et 7 vous obtenez le mot bonjour. Il est possible qu'une suite de touches corresponde à plusieurs mots. Ainsi, la suite 5, 6, 4 et 3 correspond aux mots joie et loge et la suite 2, 5, 3 et 3 à clef et bled.
Le but de cet exercice est de programmer une solution efficace pour la recherche des mots du dictionnaire qui correspondent à une séquence de touches. Pour cela, nous allons représenter le dictionnaire par un arbre digital (en anglais trie) c'est-à-dire un arbre où chaque branche est étiquetée par le numéro d'une touche du téléphone et chaque noeud par les mots du dictionnaire correspondant à la séquence des touches menant de la racine de l'arbre à ce noeud.
Par exemple, l'arbre que l'on obtient pour le petit dictionnaire d'informatique composé des mots {hd, if, in, get, to, void, unit} est le suivant :
{} / \ 4/ \8 / \ {} {} / \ \ 6/ \3 \6 / \ \ {in} {if,hd} {to} | | |8 |4 | | {get} { } / \ 3/ \8 / \ {void} {unit}Pour représenter un tel arbre digital, on se donne le type Caml suivant :
type trie = { words : string list ; branches : (int * trie) list }i.e. chaque noeud de l'arbre est un enregistrement où le champ words contient la liste des mots correspondant à ce noeud et où le champ branches est une liste de paires associant des arbres digitaux à des entiers (on appelle précisément cela une liste d'association).
change_assoc : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) listqui modifie (ou étend) une liste d'association.
let dict = [ "lex"; "key"; "void" ; "caml" ; "unix" ; "for" ; "while" ; "done" ; "let" ; "fold"; "val"; "exn" ; "rec" ; "else" ; "then" ; "type" ; "try" ; "with" ; "to"; "find" ; "do" ; "in" ; "if" ; "hd" ; "tl" ; "iter" ; "map" ; "get"; "copy" ; "and"; "as" ; "begin" ; "class" ; "downto" ; "end" ; "exception" ; "false" ; "fun" ; "function" ; "match" ; "mod" ; "mutable" ; "open" ; "or" ; "true" ; "when" ; "load" ; "mem" ; "length" ; "bash" ; "unit" ; "site"; "php"; "sql"; "ssh"; "spam"; "su"; "qt"; "root"; "bsd"; "boot"; "caml"; "bash"; "ocaml"; "kde"; "gtk" ; "gcc" ](On pourra utiliser pour cela la fonction de bibliothèque List.fold_left.)
Tester avec les exemples suivants (la réponse attendue est indiquée entre parenthèses) :
let _ = find t [2;2;6;5];; (* ["caml"] *) let _ = find t [4;3];; (* ["hd"; "if"] *) let _ = find t [4;3;8];; (* ["get"] *) let _ = find t [8;6;4;3];; (* ["void"] *) let _ = find t [8;6;4;8];; (* ["unit"] *)