5.1- TP - Graphes en OCaml
Ce TP est lié au cours d'ITC sur les graphes : on verra aussi des graphes en option informatique, et donc il faut savoir les traiter en OCaml.
Il porte sur l'étude de graphes de dépendances.
I. Généralités
Un ordinateur (ou un téléphone) doit exécuter un certain nombre de tâches. On suppose qu'il ne peut exécuter qu'une seule tâche à la fois, et que chaque tâche peut avoir des prérequis.
Dans un premier exemple, les tâches sont les suivantes :
- 1 : Activer le wifi
- 2 : Se connecter au serveur de whatsapp
- 3 : Récupérer les messages entrants
- 4 : Lancer l'application whatsapp
- 5 : Demander à l'utilisateur de confirmer son identité
- 6 : Synchroniser la date et l'heure du téléphone
Et on a les dépendances suivantes :
- 1 n'a pas de dépendances
- 2 dépend de 4 et 1
- 3 dépend de 2 et 5
- 4 n'a pas de dépendances
- 5 dépend de 2
- 6 dépend de 1
On cherche à savoir si il est possible d'exécuter les tâches en respectant les dépendances, et, si oui, dans quel ordre.
On va pour cela modéliser le problème par un graphe, avec pour sommet les tâches, et un arc orienté reliant deux taches t et t' si t dépends de t'.
Q1
On ajoute une tache 0, "allumer le téléphone". Elle ne dépend de rien, mais les tâches 1 et 4 en dépendent. Sur une feuille, ajoutez cette tâche au graphe.
Pour représenter les graphes en OCaml, on va utiliser une représentation par liste d'adjacence, avec le type suivant :
Loading editor...
type graphe = int list array;;
Loading editor...
Parenthèse sur le type array
Le type array en OCaml
En OCaml, en complément des listes, on a un type de tableau : array. Le type s'écrit comme pour les listes : un tableau d'entiers s'écrira int array, un tableau de chaines de caractères string array, etc.
Vous pouvez imaginer le type liste de Python comme une combinaison des types array et list de OCaml :
- On peut ajouter et enlever des éléments assez facilement dans les
listde OCaml - Les tableaux, en revanche, ont une taille fixe. En échange, on peut accéder et modifier les éléments par leur indices.
Loading editor...
(*Les tableaux explicites s'écrivent avec [| et |], et les éléments sont séparés par des point-virgules*) let t: int array = [|1; 2; 4; 8; 16|];; (*On peut accéder au i-ème élément avec t.(i). Les indices commencent à zéro. *) t.(3);;
Loading editor...
(*On peut modifier un élément avec une flèche vers la gauche*) t.(3) <- 6;; (*Cette opération ne renvoie rien (type `unit`) mais elle modifie le tableau*) t;;
Loading editor...
(*Quand plusieurs opérations renvoient un type `unit`, on peut les chainer en les séparant par des point-virgules simples.*) let a = t.(0) <- 3; print_int 5; t;;
Loading editor...
(*On peut accéder à la longueur d'un tableau avec Array.length*) Array.length t;;
Loading editor...
(*On peut aussi créer un tableau de longueur quelconque avec Array.make*) let t2 = Array.make 100 0;; (*Le premier argument est le nombre d'éléments, le deuxième est leur valeur*)
Q2
Créez le tableau de 5 premiers nombres premiers, et accédez au 3ème
Loading editor...
Fin de la parenthèse, et ordre des tâches
Notre type de graphe sera donc un tableau de listes d'entiers. Ainsi, si g est un graphe, g.(i) contient la liste des voisins du sommet i.
Q3
Je vous donne le début de la définition du graphe donné en exemple en OCaml. Complétez-la.
Loading editor...
let g : graphe = [|
[ ];
[0];
[1; 4];
[2; 5];
[0];
(*à compléter : sommets 5 et 6*)
|]Afficher un graphe
La fonction afficher_graphe : graphe -> unit dessine un graphe sous la cellule. Vérifiez que votre graphe correspond bien au dessin (avec la tâche 0 en plus) :
Loading editor...
afficher_graphe g;;
Q4
On propose une fonction pour parcourir un graphe en partant d'un sommet. Essayez de comprendre son fonctionnement, et exécutez-là. Que se passe-il si le graphe contient un cycle ?
Loading editor...
let rec parcours (g: graphe) (depart: int): unit =
let rec aux (l: int list) = match l with
|[] -> ()
|x::q -> parcours g x; aux q
in
aux g.(depart);;
parcours g 0Q5
En vous inspirant de la fonction ci-dessus, écrivez une fonction ordre_prerequis: graphe -> int -> int list qui prend en argument le graphe et un sommet et renvoie une liste contenant l'ensemble de ses dépendances, dans l'ordre inverse d'execution (c'est à dire que le dernier élément de la liste doit être la première tâche executée).
On peut concaténer deux listes, c'est-à-dire les fusionner en les collant l'une après l'autre, avec l'opérateur @. On écrit par exemple l1 @ l2.
Loading editor...
II. Détection de cycle
On s'interesse désormais au cas où le graphe peut avoir un cycle. Voilà un exemple qui vous permettra de tester vos fonctions.
Loading editor...
let g2 = [|
[1; 2];
[];
[3; 4];
[0];
[3]
|];;On propose la méthode suivante pour éviter le problème évoqué en 4) :
- On garde en mémoire un tableau de booléen
visite, tel quevisite.(i)vauttruesi le sommet a déjà été parcouru par la fonction, etfalsesinon. - Lorsqu'on arrive sur un sommet qui a déjà été visité, on s'arrête et on renvoie directement.
Q6
Écrivez une fonction cycle_aux: graphe -> int -> bool array -> bool qui prend en argument un graphe, un sommet de départ, et le tableau visite que l'on supposera initialisé à false et à la bonne taille.
Votre fonction doit renvoyer true si on arrive à un cycle en partant du sommet, et false sinon.
Loading editor...
let rec cycle_aux (g: graphe) (s: int) (visite: bool array): bool = failwith "à compléter";;
Q7
Écrivez une fonction cycle: graphe -> bool qui détermine si le graphe possède un cycle. Votre fonction doit appeler cycle_aux.
Le plus simple est d'appeler cycle_aux sur chaque sommet du graphe (ou, éventuellement, vous pouvez procéder plus finement).
Il existe des boucles for en OCaml, que l'on étudiera prochainement, mais ce n'est pas ce qui est demandé ici. Pour changer l'indice i, vous pouvez faire une fonction récursive, qui prend en argument un i et s'appelle ensuite avec i+1.
Loading editor...
let cycle (g: graphe): bool = failwith "à compléter";;
III. Quelques fonctions en plus
Q8
Ecrivez une fonction rev: int list -> int list qui retourne une liste d'entiers. Votre fonction ne devra pas utiliser @.
L'idée est de passer en argument la liste résultat actuel (sur une fonction auxiliaire), et de la renvoyer une fois qu'on aura traité tous les éléments.
Loading editor...
Q9
Ecrivez une fonction ordre: graphe -> int list qui, si c'est possible, renvoie un ordre d'execution des tâches, et sinon, renvoie une erreur.
Loading editor...
Question bonus
On imagine maintenant que notre ordinateur a 2 processeurs parallèles. Proposez des idées pour répartir les tâches entre les deux processeurs, en prenant toujours en compte les dépendances.
Loading editor...
Entrez le code donné en cours pour accéder à la solution :