Exercices

Les exercices 4, 5, 6, 9, 12 et 13 sont plus importants. Les autres sont davantage destinés à se familiariser avec le langage.

Exercice 1 (Quelques fonctions simples)
1-1. Écrire une fonction prenant un entier x et calculant la valeur de 2x² + 3x - 2.
1-2. Écrire la fonction entière power telle que power x y calcule x^y selon l'algorithme suivant

n⁰

n¹

n^p

ì
í
î

aux²	si p est pair
aux²× n	sinon

avec aux = n^p/2

1-3. Écrire une fonction affichant les (ou rendant la liste des) nombres inférieurs à 1000 et dont la valeur est égale à la somme du cube du chiffre des centaines, du cube du chiffre des dizaines et du cube du chiffre des unités.

Exercice 2 (Représentation et manipulation de matrices)
2-1. Écrire une fonction calculant le produit scalaire de deux vecteurs de taille n.
2-2. Écrire une fonction calculant le produit de deux matrices de taille n × n.

Exercice 3 (Les listes simples, filtrage et itérateurs)
3-1. Écrire une fonction retournant le deuxième élément d'une liste.
3-2. Écrire une fonction sommant les valeurs contenues dans une liste d'entiers.
3-3. Écrire une fonction affichant tous les éléments d'une liste d'entiers.
3-4. Écrire une fonction incrémentant d'une valeur entière, passée en paramètre, tous les éléments d'une liste d'entiers.
3-5. Écrire une fonction incrémentant d'une valeur entière, passée en paramètre, toutes les premières composantes d'une liste de couples d'entiers.
3-6. Écrire une fonction qui prend en argument une liste de couples et retourne la liste de leur première composante.
3-7. Écrire une fonction incrémentant d'une valeur entière, passée en paramètre, tous les premiers éléments d'une liste de listes d'entiers. Que se passe-t-il lorsque l'on passe une liste d'entiers en argument ? Et une liste de listes de listes d'entiers ?

Exercice 4 (Exceptions)

Que répond Caml aux phrases suivantes:

    exception pas_grave of int;;
    exception grave of string;;
    let pseudo_id x =
       if (x < 0) then raise (pas_grave (-x))
       else if (x = 0) then raise (grave "Argh !!!") else x ;;
    pseudo_id(-4);;
    pseudo_id(0);;
    pseudo_id(2);;
    let f = let val = 10 in function x ->
       try let val = 100 in pseudo_id(x) - val with
          | pas_grave n -> if (n < 0) then raise(grave "impossible ?") else n + val
          | grave "Argh !!!" -> raise(pas_grave(10))
          | grave s -> raise(grave "possible ?");;
    f(-100);;
    f(0);;
    f(100);;
    f(grave "Ouf !!!");;
    f(raise(grave "Ouf !!!"));;

Exercice 5 (Itérateurs classiques sur les listes)
5-1. Écrire la fonction it_list de Caml Light (fold_left en Objective Caml), de type
('a -> 'b -> 'a) -> 'a -> 'b list -> 'a telle que it_list f a [b1; ...; bn] correspond à f (... (f (f a b1) b2) ...) bn.

5-2. Écrire la fonction list_it de Caml Light (fold_right en Objective Caml), de type
('a -> 'b -> 'b) -> 'a list -> 'b -> 'b telle que list_it f [a1; ...; an] b correspond à f a1 (f a2 (... (f an b) ...)).

Exercice 6 (Itérateurs map et do_ sur les arbres binaires)
6-1. Définir un type 'a tree d'arbres binaires
6-2. Définir la fonction print_tree_prefix qui imprime un arbre par un parcours préfixe.
6-3. Écrire l'itérateur map_tree, ainsi que do_tree_infix. En déduire la fonction print_tree_infix.
6-4. Définir la fonction tree_list qui rend la liste correspondant au parcours infixe de l'arbre.
6-5. Écrire la fonction insert_tree qui insère un élément dans un arbre binaire de recherche.
6-6. En déduire sans utiliser les itérateurs list_it et it_list la fonction tree_sort_list qui trie une liste en utilisant un arbre binaire de recherche.
6-7. Exprimer cette fonction à l'aide de l'itérateur list_it vu dans l'exercice précédent.
6-8. Redéfinir la fonction d'insertion d'un élément dans un arbre de telle sorte que la fonction tree_sort_list s'écrive aisément à l'aide de l'itérateur it_list vu dans l'exercice précédent.

Exercice 7 (Utilisation des listes pour une version naïve du crible d'Eratosthene, de la factorisation d'entiers et calcul du pgcd)

Pour bon nombre de ces fonctions, on pourra utiliser des itérateurs.
7-1. Écrire la fonction ote_multiples qui supprime tous les diviseurs de n de la liste l.
7-2. Écrire la fonction ote_diviseurs qui supprime tous les nombres qui ne divisent pas n de la liste l.
7-3. Écrire la fonction interval qui retourne la liste des entiers compris entre i et j. Votre fonction termine-t-elle toujours?
7-4. Écrire une fonction Eratosthene qui retourne la liste des nombres premiers inférieurs à n en vous aidant des fonctions ote_multiples et interval.

En déduire la fonction liste_diviseurs_premiers qui retourne la liste des diviseurs premiers de n.
7-5. Écrire la fonction power_m_in_n qui retourne la plus grande puissance de m qui divise n.

En déduire la fonction liste_diviseurs qui à partir de la liste triée des diviseurs premiers de n calcule la liste triée de tous les diviseurs premiers de n avec leur exposants respectifs.
7-6. En supposant que les listes l1 et l2 représentent la liste triée par ordre croissant des couples (diviseur_premier, exposant) des nombres n1 et n2, écrire la fonction power_min qui calcule la liste des diviseurs premiers qui divisent n1 et n2 avec le plus grand exposant possible.
7-7. Écrire la fonction prod qui calcule le produit des éléments d'une liste.
7-8. En utilisant la fonction power écrite la semaine dernière et ce qui précède, en déduire la fonction pgcd qui calcule le plus grand commun diviseur de deux entiers.

Exercice 8 (Comment utiliser les itérateurs pour réaliser un crible d'Ératosthène)

Dans la lignée de l'exercice précédent, nous considérons ici une version utilisant des itérateurs et même, n'ayons peur de rien, es itérateurs appliqués à des itérateurs.
8-1. Écrire l'itérateur filter tel que filter p l est la sous-liste des éléments de la liste l qui vérifient le prédicat p.
8-2. Écrire la fonction pseudo_non_multiple telle que pseudo_non_multiple n m rend vrai si m=n ou si m n'est pas divisible par n.
8-3. En déduire la fonction pseudo_non_multiples_liste qui à n associe la liste des fonctions pseudo_non_multiple i pour i allant de 2 à n.
8-4. Écrire la fonction liste_n qui construit la liste des entiers de 2 à n.
8-5. En utilisant les itérateurs list_it et filter en déduire la fonction liste_premiers telle que liste_premiers n donne la liste des nombres premiers compris entre 1 et n.

Exercice 9 (Typage, ordre supérieur, fonctions anonymes)

9-1. Écrire les fonctions curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c et uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c qui permettent de transformer une fonction à deux arguments en une fonction à un seul argument couple et inversement.
9-2. On rappelle le type de la fonction compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b.

Pour chacune des expressions suivantes, vous indiquerez son type ainsi qu'une fonction anonyme sémantiquement équivalente: uncurry compose, compose curry uncurry et compose uncurry curry.

Exercice 10 (La date du lendemain: découpage d'un problème)

On souhaite déterminer la date du lendemain, c'est-à-dire définir une fonction lendemain qui prend en argument une date d et calcule la date correspondant au lendemain du jour décrit par la date d. On représente une date par un triplet de 3 entiers (ou un enregistrement) (jour, mois, année).

Il convient de s'assurer que le triplet (jour, mois, année), argument de la fonction, correspond à une date valide c'est-à-dire que mois est un entier entre 1 et 12, que jour est un entier compris entre 1 et le nombre de jours de mois en tenant compte des années bissextiles.

On ne s'intéresse qu'aux dates du calendrier grégorien c'est-à-dire au delà du 15 octobre 1582. Depuis cette date, une année est bissextile si elle est un multiple de 400 ou un multiple de 4 qui n'est pas un multiple de 100.

Exercice 11 (Les légumes: structures de données)

L'état du rayon « légumes » d'un supermarché est tenu à jour par l'ordinateur central d'après les informations fournies par les caisses.

Chaque légume est représenté par son nom, la quantité présente en rayon, le seuil à partir duquel il faut réapprovisionner le rayon, ainsi que son prix. La quantité peut être soit un nombre de pièces (par 2 céleris), soit un nombre de kilos (par exemple 1.5 kilo de carottes). Selon les saisons les légumes varient et sont plus ou moins nombreux.

11-1. (Types)

Définissez le type légume. Pour cela vous pouvez définir tous les types intermédiaires que vous souhaitez. Indiquez la représentation des tomates, à 5,50 francs le kilo, avec 20 kilos en rayon et un seuil de commande de 5 kilos.

11-2. (Quantités)

Écrire une fonction vérifie_quantité qui vérifie pour un légume que la quantité de légume présente en rayon et le seuil à partir duquel il faut réapprovisionner sont exprimer dans la même unité (pièce ou kilo).
Écrire une fonction inférieur_quantités qui compare deux quantités de même nature q1 et q2 et rend true si q1 < q2 et échoue sinon.
Écrire une fonction différence_entre_quantités qui calcule la différence de deux quantités de même nature q1 et q2 et échoue sinon.

11-3. (Panier)

Une ménagère achète des légumes pour son pot au feu: quelques carottes, des pommes de terre, une botte de poireaux, un oignon, un bouquet d'herbes. Par quelle structure de données représentez-vous le panier de cette ménagère?

11-4. (Prix)

Écrire une fonction info_légume qui fournit les informations concernant un légume de nom n dans le rayon r.
Écrire une fonction prix_légume qui trouve le prix d'un légume de nom n dans le rayon r.
Compte tenu de la description du rayon r, écrire une fonction prix_pannier qui évalue le prix à payer à la caisse pour un panier de légumes p.

11-5. (Mise à jour)

Écrire une fonction mise_à_jour_légume qui retire une quantité q d'un légume de nom n du rayon.
Écrire une fonction mise_à_jour_pannier qui met le stock à jour après passage en caisse d'un panier de légumes.

11-6. (Commande)

Écrire une fonction légumes_à_commander qui compose la commande après mise à jour du stock du rayon r.

Exercice 12 (Définir soi-même les listes)

12-1. Définissez le type des listes d'entiers.
12-2. Écrivez (définir, typer et évaluer) les fonctions suivantes :

length qui calcule la longueur d'une liste.
head, tail et nth qui retournent respectivement le premier, le dernier et le nth-ième élément d'une liste.
reverse qui renverse une liste.
append qui met deux listes bout à bout.
member qui détermine si un élément est ou non présent dans une liste.
for_all qui détermine si un prédicat est vérifié par tous les éléments d'une liste.

Dans la suite on donnera les solutions pour ce type en définissant ses propres fonctions puis pour le type prédéfini des listes en s'appuyant sur la bibliothèque disponible en Caml.
12-3. Écrivez la fonction merge qui fusionne deux listes triées. En déduire une fonction de tri par dichotomie.

Exercice 13 (Arbres d'expression (évaluation, simplification))

On considère les formules du calcul propositionnel obtenues à partir des formules atomiques (P_i)_{i Î IN} et des connecteurs usuels Ù (« et »), Ú (« ou »), ¬ (« non »), Þ (« implique ») et ÜÞ (« équivalent à »).

On rappelle les lois de Morgan de distibutivité de Ù et Ú l'un par rapport à l'autre:

F₁ Ù (F₂ Ú F₃)	º	(F₁ Ù F₂) Ú (F₁ Ù F3)
F₁ Ú (F₂ Ù F₃)	º	(F₁ Ú F₂) Ù (F₁ Ú F3)

De même,

¬ (F₁ Ù F₂)	º	¬ F₁ Ú ¬ F₂
¬ (F₁ Ú F₂)	º	¬ F₁ Ù ¬ F₂

13-1. Définissez un type Caml pour représenter ces formules. Donnez la représentation des formules suivantes :

P₁, (¬ P₁), (P₁ Ù (¬ P₂)), (¬ (P₁ Þ P₂)), ((¬ P₁) ÜÞ P₂), ((P₁ Þ P₂) ÜÞ ¬ ((¬ P₁) Ú (¬ P₂))).

13-2. Écrire une fonction string_of_formule: formule -> string qui imprime une formule. Par exemple, on pourra utiliser \/ pour le connecteur Ú, /\ pour le connecteur Ù, => pour le connecteur Þ , <=> pour le connecteur ÜÞ et ! pour le connecteur ¬.
13-3. On rappelle que si F₁ et F₂ sont deux formules propositionnelles, F₁ Þ F₂ º (¬ F₁) Ú F₂ et F₁ ÜÞ F₂ º (F₁ Ù F2) Ú ((¬ F1) Ù (¬ F2)).

Écrire une fonction normalize qui transforme une formule avec les connecteurs Þ et ÜÞ en une formule équivalente sans ces connecteurs.
13-4. Écrire une fonction liste_variables: formule -> int list qui détermine la liste des variables d'une formule. Chaque variable ne devra apparaître qu'une seule fois. Vous écrirez cette fonction à l'aide de la fonction de la bibliothèque standard union: 'a list -> 'a list -> 'a list. Vous en écrirez ensuite une autre version utilisant un accumulateur et la fonction mem: 'a -> 'a list -> bool.
13-5. Écrire une fonction éval: (int * bool) list -> formule -> bool qui compte tenu de la valeur des variables qui apparaissent dans une formule détermine la valeur de vérité de la formule. Par exemple, éval [(1,true); (2,true)] (Ou (Var 1, Var 2)) rendra la valeur true. Vous déclencherez une exception, que vous définirez, lorsque la formule contient une variables qui n'est pas dans la liste.
13-6. Écrire une version fonctionnelle de la fonction éval qui prenne en argument une fonction de type int -> bool au lieu d'une liste d'associations.
13-7. Écrire une fonction substituer: formule -> int -> formule -> formule telle que substituer F i v retourne la formule obtenue en substituant à la variable d'indice i la formule v dans la formule F.
13-8. Écrire une fonction substitue_fun: (int -> formule) -> formule -> formule telle que substitue_fun f F est la formule obtenue en substituant toutes les occurences de Var i dans F par f i.
13-9. Écrire une fonction éval_sans_var : formule -> bool qui évalue une formule sans variables, vous déclencherez une exception que vous définirez lorsque la formule contient des variables. En déduire une autre version de la fonction éval précédente qui utilise substituer.

Nous allons à présent écrire deux versions de la fonction est_tautologie qui teste si une formule est une tautologie, c'est-à-dire si la valeur de vérité de cette formule est true quelle que soit la valeur des variables qu'elle contient.

Chaque ligne de la table de vérité est décrite par la liste d'associations formée des couples (nom_de_variable, valeur). Par exemple, pour la formule P₁ Ú P₂, la première ligne est décrite par [(1,true); (2,true)].
13-10. Écrire une fonction énumération_cas_liste qui énumère toutes les tables d'associations correspondant à toutes les lignes de la table de vérité d'une formule.
13-11. En déduire une première version de la fonction est_tautologie.

13-12. (Algorithme de Shannon)

L'algorithme de Shannon pour tester si une formule est une tautologie est le suivant: pour déterminer si une formule F contenant les variables v₁, ... v_n est une tautologie nous allons créer deux formules F_t et F_f obtenues en substituant v₁ respectivement à Vrai et Faux et déterminer si F_t et F_f qui contiennent alors les variables v₂, ... v_n sont des tautologies. Nous utiliserons la fonction éval_sans_var précédente lorsque la formule ne contient pas de variables.

Écrire une fonction est_tautologie : formule -> int list -> bool qui vérifie si une formule F contenant au plus les variables de la liste l est une tautologie.

This document was translated from L^AT_EX by H^EV^EA.