pfaFinals - Alexandros Singh's Academic Homepage

Préambule :

Chaque question donne droit à un maximum de 2 points. Il y a 10 questions, regroupées en 4 exercices, de sorte que la note maximale finale est de 20/20.

Vous devez soumettre un fichier, appelé exo_n.ml où n \(\in \{0,1,2,3\}\), par exercice contenant l'ensemble des solutions proposées.

Au cours des exercices suivants, vous aurez besoin d'utiliser certains modules fournis par le module mods.ml que j'ai mis à votre disposition dans le repo git du cours.

Vous ne devez pas copier le code contenu dans mods.ml ! Si vous voulez utiliser l'un des modules de mods.ml, vous devez l'importer de manière appropriée dans votre fichier exo_n.ml.

Pour vérifier que vos soumissions sont valides, vous pouvez exécuter la procédure suivante :

ocamlc -c mods.ml exo_0.ml exo_1.ml exo_2.ml exo_3.ml

Si vous utilisez ocaml ou utop pour tester votre code (bien que je vous suggère plutôt d'utiliser Dune !) , n'oubliez pas de démarrer la session avec la commande suivante :

#mod_use "mods.ml"

avant de charger les fichiers de vos solutions, comme par example avec la commande #use exo_n.ml.

et vérifier que la compilation s'est déroulée sans erreur.

Exercice 0 - Polynômes

Notions utiles pour cet exercice : les flottants, les listes et le module List, la récursivité, les opérations arithmétiques.

Cet exercice traite des polynômes à coefficients réels, c'est-à-dire des sommes de la forme \(\sum_{0 \leq i \leq n} a_i x^i = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0, a_i \in \mathbb{R}\).

Nous représenterons un polynôme par une liste de longueur égale à son degré, de telle sorte que le i-ème élément de cette liste soit un float représentant de \(a_i\).

Par exemple, le polynôme \(x^2-5\) donne la liste [1.;0.;-5.] .

-Problème 0 : Rappelons que la dérivée d'un polynôme \(\sum_{0 \leq i \leq n} a_i x^i\) est \(\sum_{1 \leq i \leq n} i a_i x^{i-1}\) (la dérivée d'une constante correspondant à la somme vide, donc étant 0).

Implémentez en OCaml une fonction diff : float list -> float list qui calcule la liste correspondant à la dérivée du polynôme représenté en entrée. Par exemple, pour le polynôme \(p_0 = x^2+2x+1\) dont la dérivée est \((p_0)' = 2x+2\), on a :

# diff [1.;2.;1.]; ;
- : float list = [2. ; 2.]

-Problème 1 : Implémentez une fonction eval_poly : float list -> float -> float qui prend en entrée une liste représentant un polynôme et un float représentant un certain point et retourne un float représentant la valeur du polynôme évaluée en ce point.

Par exemple, \(-3x^2+\frac{6x}{7} + (3.14)\) évalué à \(0.5772\) donne :

# eval_poly [-3. ; 6. /. 7. ; 3.14] 0.5772; ;

- : float = 2.63526333714285688

-Problème 2 : La méthode Newton-Raphson, nommée d'après Isaac Newton et Joseph Raphson, est un algorithme d'approximation des racines d'une fonction \(f(n)\) différentiable à valeur réelle. Elle est décrite par l'itération :

\(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\),

où \(f'(x)\) est la dérivée de \(f(x)\).

Implémentez en OCaml une fonction newton_raphson : float list -> float -> float -> float qui prend en entrée:

une liste p : float list représentant un polynôme,
une valeur numérique x : float représentant un point initial,
et une valeur numérique err : float qui représente une erreur additive,

et retourne comme résultat un float qui est l'approximation d'une racine du polynôme d'entrée, calculée en utilisant l'itération de Newton-Raphson
L'approximation doit être telle que (newton_raphson p x err) |> eval_poly p) < err, c'est-à-dire que le résultat du polynôme évalué à cette approximation est inférieur à \(\pm\)err.

# let poly = [1.; 0.; -5.];;
val poly : float list = [1.; 0.; -5.]
# newton_raphson poly (-1.) 0.01;;
- : float = -2.23809523809523814
# newton_raphson poly (-1.) 0.0001;;
- : float = -2.23606889564336342
# newton_raphson poly (-1.) 0.000001;;
- : float = -2.2360679774999781
# newton_raphson poly 1. 0.01;;
- : float = 2.23809523809523814
# newton_raphson poly 1. 0.0001;;
- : float = 2.23606889564336342
# newton_raphson poly 1. 0.000001;;
- : float = 2.2360679774999781

Exercice 1 - Arbres de recherche binaires

Notions utiles pour cet exercice : les types de données algébriques, les arbres, les listes et le module List, la Monade Writer.

Cet exercice concerne les arbres binaires de recherche, qui sont des arbres binaires tels que :

La valeur de la racine est supérieure à toutes les valeurs de son fils gauche (sous-arbre gauche).
La valeur de la racine est inférieure à toutes les valeurs de son fils droit (sous-arbre droit).
Les enfants de gauche et de droite de la racine sont des arbres de recherche binaires.

Nous représenterons les arbres de recherche binaires à l'aide du type de données algébrique :

type abr =
    | Empty 
    | Node of int * abr * abr

-Problème 3 : Implémenter une fonction insert : int -> abr -> abr qui prend en entrée un entier et un arbre et renvoie un nouvel arbre de recherche binaire qui contient toutes les valeurs de l'ancien en plus de la nouvelle valeur.

Par exemple, l'insertion successive des valeurs 4,8,6,1,3,5 dans un arbre initialement vide donne :

C'est-à-dire :

# List.fold_right (fun x y -> insert x y) [4;8;6;1;3;5] Empty;;
- : abr =
Node (5, Node (3, Node (1, Empty, Empty), Node (4, Empty, Empty)),
 Node (6, Empty, Node (8, Empty, Empty)))

-Problème 4 : Implémenter une fonction search qui prend en entrée:

un entier,
et un arbre

et renvoie:

un booléen correspondant au fait que la valeur existe (ou non) dans un arbre,
ainsi qu'une chaîne composée des lettres "l" et "r" représentant le chemin (la succession de visites d'enfants gauche et droite) nécessaire pour y accéder, en partant de la racine (une chaîne vide si l'entier n'existe pas dans l'arbre).

La fonction que vous implémentez doit être de l'un des deux types suivants :

recherche : int -> abr -> bool * string,
recherche : int -> abr -> bool StringWriter.t où StringWriter est un module (que vous devez créer) implémentant une monade Writer manipulant des chaînes de caractères.

Les réponses du premier type seront notées avec un maximum de 1 point, les réponses du deuxième type seront notées avec un maximum de 2 points. Si vous choisissez la seconde option, vous pouvez créer une monade Writer en utilisant le foncteur MakeWriter fourni.

A titre d'exemple, considérez une implémentation de la fonction search utilisant une monade Writer, ainsi que l'exemple d'arbre ci-dessus. Nous avons alors :

# let ex = List.fold_right (fun x y -> insert x y) [4;8;6;1;3;5] Empty;;
val example : abr =
  Node (5, Node (3, Node (1, Empty, Empty), Node (4, Empty, Empty)),
   Node (6, Empty, Node (8, Empty, Empty)))
# search 6 ex;;
- : bool t = Writer (true, "r")
# search 4 ex;;
- : bool t = Writer (true, "rl")
# search 8 ex;;
- : bool t = Writer (true, "rr")
# search 42 ex;;
- : bool t = Writer (false, "")

-Problème 5 : Implémentez une fonction tree_sort: int list -> int list qui trie une liste d'entrée en utilisant l'algorithme de tri par arbre :

Construire un arbre de recherche binaire à partir de la liste d'entrée et renvoyer une nouvelle liste contenant les éléments de cet arbre dans l'ordre où ils sont visités par l'algorithme de parcours infixe.

Par exemple :

# tree_sort [5;2;1;3;4];;
- : int list = [1; 2; 3; 4; 5]

Exercice 2 - Piles

Notions utiles pour cet exercice : récursion, listes et module List, modules et structures, monade Maybe.

-Problème 6 : Implémenter une fonction rev_list : 'a list -> 'a list qui inverse une liste (c'est-à-dire qui retourne une nouvelle liste dont les éléments sont ceux de l'entrée dans l'ordre inverse) en utilisant le module Stack fourni.

Vous pouvez (ou non) utiliser la monade Maybe pour mettre en œuvre la fonction ci-dessus. Les réponses élégantes et simples seront mieux notées.

Par exemple :

# rev_list [1;2;3;4;5];;
- : int list = [5; 4; 3; 2; 1]

Hint

Insérez tous les éléments de la liste dans une pile, puis pop la pile jusqu'à ce qu'elle soit vide, en stockant chaque élément retiré dans une nouvelle liste.

-Problème 7: Implémentez une fonction sort_stack : 'a ListStack.t -> 'a ListStack.t qui prend en entrée une pile et la trie par ordre décroissant (c'est-à-dire qu'elle retourne une pile qui contient les mêmes éléments par ordre décroissant).

Pour ce faire, votre fonction doit mettre en œuvre l'algorithme suivant :

Soit s une pile que nous voulons trier et t une seconde pile qui est initialement vide.
Si s est vide, renvoyez t.
Si t est vide, alors dépilez le premier élément de la pile s, insérez-le dans t, et appliquer l'algortithme récursivement aux deux nouvelles piles.
Si aucune des deux piles n'est vide alors, notons a l'élément au sommet de la pile s et b l'élément au sommet de la pile t:
1. Si b > a, alors dépilez les piles s et t pour obtenir deux nouvelles piles popped_s et popped_t. Insérez les éléments b puis a dans popped_s et appelez l'algorithme récursivement avec cette nouvelle pile et popped_t comme seconde pile.
2. Si ce n'est pas le cas, dépilez la pile s pour obtenir popped_s, insérer l'élément a dans t, et appeler l'algorithme respectivement sur les deux nouvelles listes.

Une fois encore, vous pouvez choisir d'utiliser (ou non) la monade Maybe pour implémenter votre fonction. Les implémentations utilisant la monade seront mieux notées.

Par exemple :

# sort_stack (List.fold_right (fun x y -> push x y) [4;3;1;2;5] empty);;
- : int list = [5; 4; 3; 2; 1]

Exercice 3 - Parsing (Basé sur "Advent of Code 2023 - Day 1")

Notions utiles pour cet exercice : les chaînes de caractères et la bibliothèque String (en particulier les fonctions starts_with et sub), la monade MaybeMonadPlus.

Cet exercice concerne l'analyse syntaxique des chaînes de caractères.

Vous êtes libre d'implémenter ces fonctions comme vous le souhaitez, tant qu'elles affichent les résultats désirés.

-Problème 0 : Implémenter une fonction parse qui prend en entrée une chaîne de caractères et imprime tous les chiffres trouvés dans la chaîne, dans l'ordre de gauche à droite.

Par exemple, l'application de parse à "good1luck2everyone3!" résulte en l'impression de ce qui suit :

1
2
3

et son application à "j0y3us3s_f3t3s_4_t0us" donne:

-Problème 9 : Implémentez une fonction parse_2 qui prend en entrée une chaîne de caractères et fait comme ci-dessus, mais cette fois-ci elle imprime aussi tous les chiffres correspondant aux sous-mots de la chaîne d'entrée qui signifient un chiffre (i.e. "zero", "one", "two", ..., "nine").

Par exemple, l'application de parse_2 à "thirtytwoplus5givesthirtyseven" résulte en l'impression de ce qui suit :

2
5
7

et son application à "today_is_december_15_twothousandandtwentythree!" donne:

Bonus: Votre fonction peut analyser des sous-mots qui se chevauchent (par exemple (parse_2 "eightwone") affiche 8 puis 2 puis 1 dans la console).