Exercice 1 : OCamlgraph

OCamlgraph est une librairie d'algorithmes de graphes. Son principe est de proposer des foncteurs, qui prennent une interface représentant des graphes et produisent un module définissant un algorithme. On se propose d'écrire un mini OCamlgraph.

1. Proposez une interface pour les graphes orientés.
2. Proposez une interface pour un module contenant l'algorithme de parcours en profondeur. L'algorithme doit retourner la liste des sommets parcourus, dans l'ordre de leur découverte.
3. Écrivez un foncteur des graphes orientés vers les algorithmes de parcours en profondeur.
4. Tous les parcours suivent le même algorithme, mais avec une gestion différente des arcs en attente de traitement (la frontière). Comment utiliser cette idée pour écrire le programme de parcours une fois pour toutes, et ensuite pouvoir en déduire les divers algorithmes : parcours en largeur ou profondeur, algorithme de Dijkstra, etc ?

Exercice 2 : monade d'état.

Voici l'interface d'une monade d'état :

Il faut comprendre que 'value t est une action produisant une valeur de type 'value. Par ailleurs, cette action a accès à un état qu'elle peut lire ou modifier. De même, une valeur de type 'arg -> 'res t peut se comprendre comme une fonction de type 'arg -> 'res, mais pouvant utiliser ou modifier l'état.

On suppose disposer d'une monade d'état dont le type stateest int.

1. Définissez l'action print_state : unit t affichant la valeur de l'état.
2. Définissez l'action incr : unit t augmentant de 1 la valeur de l'état.
3. Définissez une suite d'actions, consistant à incrémenter deux fois le compteur, l'afficher, l'incrémenter une fois et l'afficher de nouveau.
4. Soit une fonction apply : int -> unit t. On souhaite créer l'action consistant à faire successivement apply ipour i valant de lower à upper. Définissez une telle boucle for.
5. Écrivez l'action permettant de calculer la factorielle d'un entier $n$ à l'aide de la question précédente. Vous pouvez modifier l'état arbitrairement.

   1. val fact : int -> int t
      
6. Créez une implémentation des monades d'état.

Exercice 3 : Programmation dynamique.

Nous avons vu en cours d'algorithmique qu'un programme dynamique est un algorithme récursif auquel on ajoute un mécanisme qui permet de mémoriser pour chaque instance quelle est la solution associée. Ainsi, sur les récursions exigent le calcul de la solution d'une même instance plusieurs fois, seul le premier calcul prend du temps.

La technique étant toujours la même, il doit être possible de la factoriser. Nous allons le faire en utilisant un foncteur. Pour cela, nous allons définir ce qu'est un problème typique de programmation dynamique, ce qui nous définit une interface, puis comment depuis une telle interface on peut dériver automatiquement le programme dynamique. Il est nécessaire d'avoir fait l'exercice sur les monades d'états pour faire cet exercice.

Voici l'interface d'un problème solvable par programmation dynamique :

resolve prend une fonction en argument, qui est en fait la fonction à utiliser pour les appels récursifs. Comme ceux-ci ultimement auront à utiliser la mémoire, nous les définissons dans une monade d'état.

1. Rappeler ce qu'est Map.OrderedType.
2. Créer un module de signature Problem pour le calcul des termes de la suite de Fibonacci.

   Voici le foncteur créant le programme dynamique.

   1. module DynProg : functor (Prob : Problem) -> sig
      
   2. type state
      
   3. val solve : Prob.t -> (Prob.solution, state) State.t
      
   4. val solve_once : Prob.t -> Prob.solution
      
   5. end
      
3. Pour le type des états, nous allons utiliser une table d'association des instances vers les solutions. Écrire la définition du type state.
4. La fonction solve se programme en récupérant l'état de la mémoire, et en y cherchant l'instance. Si l'instance n'y est pas, on utilise la fonction de résolution du problème et on ajoute la solution en mémoire. Ajoutez une fonction enregistrant une solution en mémoire

   1. val memoize_solution : Prob.t -> Prob.solution -> (unit,state) State.t
      
5. Puis programmez la fonction solve.
6. Et finissez avec la fonction solve_once, qui résoud l'instance en partant d'une mémoire vide.