let rec mystere z = match z with
(* La fonction mystere calcule ... *)
| [] -> max_int
| [a] -> a
| a::b::y -> mystere ((if a <= b then a else b)::y);;
val mystere : int list -> int = <fun>
Q2. À chaque appel récursif de mystere
, la taille de la liste en argument diminue de $1$. Si z
est une liste de taille $n$, il faut donc $n$ appels de mystere
avant d'arriver sur le cas de base de la liste réduit à un élément.
Q3. Posons, pour $n \geq 1$ : $$H_n \text{ : Si z est une liste d'entiers de taille } n, \text{ mystere z renvoie le minimum de z}$$ On peut démontrer $H_n$ par récurrence sur $n$.
Q4. Comme mystere
est récursif terminal (l'appel récursif est la dernière opération réalisée), la fonction est automatiquemen dérécursifiée. Il n'y a donc pas de problème de pile d'appel. De plus, une liste étant persistante, chaque ajout à une liste (...::y
) demande une complexité en espace O($1$) (la mémoire est partagée : il n'y a pas besoin de copier la liste).
Comme on le fait $n$ fois, on obtient une complexité mémoire en O($n$).
Il faut aussi prendre en compte l'espace mémoire pour stocker l'entrée (d'après l'énoncé) qui est aussi O($n$).
D'où la complexité totale en espace : $\boxed{\text{O}(n)}$.
Distance d'édition de Levenshtein¶
type mot = char list;;
type mot = char list
(* Q7 *)
let array_of_mot w =
let t = Array.make (List.length w) ' ' in
let rec aux l n = match l with
| [] -> ()
| e::q -> t.(n) <- e; aux q (n + 1) in
aux w 0;
t;;
val array_of_mot : char list -> char array = <fun>
array_of_mot ['t'; 'e'; 's'; 't']
- : char array = [|'t'; 'e'; 's'; 't'|]
(* Q8 *)
let distance b c =
let b, c = array_of_mot b, array_of_mot c in
let nb, nc = Array.length b, Array.length c in
let d = Array.make_matrix nb nc (-1) in
let rec aux i j = (* renvoie d(i, j) *)
if i = -1 then j + 1
else if j = -1 then i + 1
else if d.(i).(j) <> -1 then d.(i).(j)
else if b.(i) = c.(j) then (d.(i).(j) <- aux (i - 1) (j - 1); d.(i).(j))
else (d.(i).(j) <- 1 + min (aux (i - 1) j) (min (aux (i - 1) (j - 1)) (aux i (j - 1)));
d.(i).(j)) in
aux (nb - 1) (nc - 1)
val distance : char list -> char list -> int = <fun>
distance ['c'; 'o'; 'r'; 'e'; 'k'; 't'; 'e'] ['c'; 'o'; 'r'; 'r'; 'e'; 'c'; 't']
- : int = 3
distance ['n';'u';'i';'t'] ['b'; 'r';'u';'i';'t']
- : int = 2
Fouille dans un trie¶
Q12. ABR ou table de hachage. Insertion dans un ABR en O($h$) (O($\log(n)$) si équilibré). Insertion dans une table de hachage en O(1).
module CharMap = Map.Make(Char)
module CharMap : sig type key = Char.t type 'a t = 'a Map.Make(Char).t val empty : 'a t val is_empty : 'a t -> bool val mem : key -> 'a t -> bool val add : key -> 'a -> 'a t -> 'a t val update : key -> ('a option -> 'a option) -> 'a t -> 'a t val singleton : key -> 'a -> 'a t val remove : key -> 'a t -> 'a t val merge : (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool val iter : (key -> 'a -> unit) -> 'a t -> unit val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b val for_all : (key -> 'a -> bool) -> 'a t -> bool val exists : (key -> 'a -> bool) -> 'a t -> bool val filter : (key -> 'a -> bool) -> 'a t -> 'a t val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t val cardinal : 'a t -> int val bindings : 'a t -> (key * 'a) list val min_binding : 'a t -> key * 'a val min_binding_opt : 'a t -> (key * 'a) option val max_binding : 'a t -> key * 'a val max_binding_opt : 'a t -> (key * 'a) option val choose : 'a t -> key * 'a val choose_opt : 'a t -> (key * 'a) option val split : key -> 'a t -> 'a t * 'a option * 'a t val find : key -> 'a t -> 'a val find_opt : key -> 'a t -> 'a option val find_first : (key -> bool) -> 'a t -> key * 'a val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option val find_last : (key -> bool) -> 'a t -> key * 'a val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option val map : ('a -> 'b) -> 'a t -> 'b t val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t val to_seq : 'a t -> (key * 'a) Seq.t val to_seq_from : key -> 'a t -> (key * 'a) Seq.t val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t val of_seq : (key * 'a) Seq.t -> 'a t end
type trie = Node of trie CharMap.t
type trie = Node of trie CharMap.t
(* Q13 *)
let trie_vide = Node CharMap.empty;;
let trie_mot_vide = Node (CharMap.add '$' trie_vide CharMap.empty)
val trie_vide : trie = Node <abstr>
val trie_mot_vide : trie = Node <abstr>
(* Q14 *)
let trie_singleton x = Node (CharMap.add x trie_mot_vide CharMap.empty)
val trie_singleton : CharMap.key -> trie = <fun>
(* Q15 *)
let rec trie_mem (c : char list) (Node tcm) = match c with
| [] -> CharMap.find_opt '$' tcm <> None
| e::q -> match CharMap.find_opt e tcm with
| None -> false
| Some a -> trie_mem q a
val trie_mem : char list -> trie -> bool = <fun>
(* Q16 *)
let rec trie_add c (Node tcm) = match c with
| [] -> Node (CharMap.add '$' trie_vide tcm)
| e::q ->
let t_e = match CharMap.find_opt e tcm with
| None -> trie_vide
| Some a -> a in
Node (CharMap.add e (trie_add q t_e) tcm)
val trie_add : CharMap.key list -> trie -> trie = <fun>
let t = trie_add ['a'; 'b'; 'c'] (trie_singleton 'a')
val t : trie = Node <abstr>
trie_mem ['a'; 'b'; 'c'] t && trie_mem ['a'] t && not (trie_mem ['a'; 'b'] t) && not (trie_mem ['b'] t)
- : bool = true