PROGRAMMATION - Exercices de programmation fonctionnelle en OCaml - Lois macroscopiques et applications concrètes. Cours et exercices corrigés (Niveau A)

L’ouvrage aborde notamment les notions de correction, de complexité et
d’efficacité d’un algorithme fonctionnel, à travers les solutions dét
aillées d’une quarantaine d’exercices. Pour chacun de ces exercices, p
lusieurs solutions sont systématiquement proposées. Pour chaque soluti
on, une analyse des temps de calcul et une preuve de correction sont e
ntièrement rédigées.
Les exercices traités sont classés en plusieurs catégories en fonction
de la nature des données qu’ils manipulent: entiers, listes, arboresc
ences. Cette distinction permet de mettre en avant un mode de programm
ation et de raisonnement guidé par la structure des données, si nature
l en programmation fonctionnelle.
Si les exercices proposés peuvent sembler simples et classiques au pre
mier abord, ils ont été choisis pour permettre, par l’étude de leurs s
olutions, une découverte en profondeur de la programmation fonctionnel
le, ce qui constitue l’originalité du livre.
Au sommaire:
1: Définitions et notations: Notations et rappels en Ocaml; Preuve de
terminaison et de correction; Complexité d'une fonction; Notation des
fonctions. 2: Fonctions sur des entiers: Somme des n premiers entiers;
Somme des n premiers entiers impairs; Somme des entiers entre p et q;
Dernier chiffre de 2n; Y a-t-il un 0 dans la représentation binaire d
'un entier?; Division euclidienne; Factorielle; Coefficients binomiaux
; Puissance d'un entier; Puissance d'une fonction. 3: Fonctions sur de
s listes: Longueur d'une liste; Somme des entiers d'une liste; La fonc
tion fold; La fonction map; La fonction find; Maximum d'une liste non
vide d'entiers; Nombre d'occurrences d'un élément dans une liste; Y a-
t-il plus de 0 que de 1 dans une liste?; Concaténer deux listes; Renve
rser une liste. 4: Fonctions sur des arbres binaires: Nombre de nœuds
d'un arbre binaire; Hauteur d'un arbre binaire?; Un élément est-il pré
sent dans un arbre binaire?; Nombre de nœuds d'un niveau donné; Un arb
re binaire est-il équilibré?; Construire le symétrique d'un arbre; Ord
re supérieur et arbres.