Exercice 1 : Fonctionnelles
Écrire des fonctions en Ocaml pour les spécifications suivantes :
une fonction max calculant le maximum de deux entiers,
une fonction argmax qui prend un fonction $f$ de type int -> int et deux entiers $a$ et $b$, et qui renvoie celui des deux entiers dont l'image par $f$ est maximum,
une fonction im_max, avec les mêmes arguments que la fonction précédente, mais qui renvoie cette fois le maximum de f a et f b,
une fonction develop, prenant f : int -> int et deux entiers $a < b$ en arguments, et tel que $\text{develop}\;f\;a\;b = f\;a\;(f\;(a+1)\;(f \ldots (f\;(b-1)\;b)))$,
en déduire des fonctions max_interval et argmax_interval, calculant la maximum et l'argument maximum d'une fonction $f$ sur un intervalle entier. Ces fonctions ont le type (int -> int -> int) -> int -> int -> int,
une fonction argmax_rectangle, d'arguments f : int -> int -> int, $x$, $l$, $y$, et $h$ de types entiers, tel que $\text{max_rectangle}\;f\;x\;l\;y\;h = (i,j)$ tel que $(i,j)$ maximise $f\;i\;j$ pour $i \in [x,x+l]$ et $j \in [y,y+h]$ (cette fonction calcule donc le point maximum d'un rectangle d'entiers).
Exercice 2 : Typage
Trouver les types des fonctions suivantes (les noms de variables ont été choisis pour ne pas vous donner d'indice, mais utilisez toujours des noms de variables explicitant le rôle de chaque variable dans vos programmes) :
let a b c d e = (b d) + (c e) + e - int_of_float d
let d f x h = (f (x +. h) -. (f x)) /. h
let rec d f l u e =
if u -. l < e then l
else
let m = l +. u /. 2. in
if f m > 0. then d f l m e
else d f m u e
let a b c d e = (e (b c) d) + (b c d) + (b d c) + (e (fun _ -> d) c)
Exercice 3 : Typage
Trouver les erreurs de types dans les fonctions suivantes :
let a b c d = (b c) + (b d c)
let h f x = (f 1.) + (f 2.) + (f x) + (f (f x))
let e f g h x = (f (g x)) +. float_of_int (g (h x)) +. (h (f x))
Exercice 4 : Polymorphisme
Nous souhaitons écrire un algorithme de multiplication matriciel. Nous rappelons que l'élément $m_{ij}$ d'une matrice $M$ obtenu par multiplication de deux matrices $A$ et $B$ s'écrit:
$$ m_{ij} = \sum_{k = 1}^{n} a_{ik} \times b_{kj}$$
où $A$ est de dimension $m \times n$ et $B$ de dimension $n \times p$, $i \in [1,m]$, $j \in [1,p]$.
Nous disposons des types et valeurs suivantes :
type 'a matrice
val dim : 'a matrice -> int * int
val get : 'a matrice -> i -> j -> 'a
val make : int -> int -> (int -> int -> 'a) -> 'a matrice
Notre algorithme étant polymorphe, il doit prendre des fonctions d'addition et de multiplication en argument, la première ligne est donc :
let mat_prod zero add prod mat_a mat_b =
avec mat_a et mat_b les matrices à multiplier, prod le produit d'éléments des deux matrices, add la somme et zero l'élément neutre pour add.
Quel est le type de la fonction mat_prod ? Compléter son code. Ensuite, dériver la multiplication de matrices entières, celle de matrices flottantes et celle de matrices booléennes.
