{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Texte d'oral de modélisation - Agrégation Option Informatique
1.1  Préparation à l'agrégation - ENS de Rennes, 2016-17
1.2  À propos de ce document
1.3  Question de programmation
1.4  Réponse à l'exercice requis
1.4.1  Structures de données
1.4.2  Opérations de base, ⊕\" role=\"presentation\">⊕⊕ et ⊗\" role=\"presentation\">⊗⊗
1.4.2.1  Intersection
1.4.2.2  Composition
1.4.2.3  Union
1.4.2.4  Exemples
1.4.2.5  Une étape de plus : ne pas inclure des intervalles inclus dans ceux déjà présents
1.4.3  L'algorithme PC
1.4.3.1  Structure de données pour les réseaux STP
1.4.3.2  L'algorithme PC
1.4.4  Exemple de réseau non distributif
1.4.5  D'autres exemples
1.5  Conclusion
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Texte d'oral de modélisation - Agrégation Option Informatique\n", "## Préparation à l'agrégation - ENS de Rennes, 2016-17\n", "- *Date* : 7 avril 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: Annale 2009, \"Contraintes temporelles\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## À propos de ce document\n", "- Ceci est une *proposition* de correction, partielle et probablement non-optimale, pour la partie implémentation d'un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n", "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n", "- L'implémentation sera faite en OCaml, version 4+ :" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The OCaml toplevel, version 4.02.3\n" ] }, { "data": { "text/html": [ "
- : int = 0\n",
       "
" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"ocaml -version\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Notez que certaines fonctions des modules usuels [`List`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) et [`Array`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) ne sont pas disponibles en OCaml 3.12.\n", "> J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Question de programmation\n", "La question de programmation pour ce texte était donnée en question 1 en page 9 :\n", "\n", "> \"Programmer l'algorithme PC. Faites le tourner sur l'exemple de réseau non distributif.\"\n", "\n", "La consigne était très courte, mais avec aucune indication.\n", "Notez qu'il est rare que le texte exige un exemple particulier." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Réponse à l'exercice requis\n", "Ça va être assez rapide :\n", "\n", "1. D'abord, il faut définir les types de données avec lesquels on va travailler,\n", "2. Ensuite, implémenter les deux opérations $\\oplus$ et $\\otimes$ sur les ensembles d'intervalles,\n", "3. Puis implémenter l'algorithme PC (similaire à Floyd-Warshall),\n", "4. Et enfin, l'exécuter sur l'exemple de réseau non distributif donné en page 8.\n", "\n", "Si possible, on va essayer de faire des *tests* pour chaque fonction intermédiaire, et un exemple de plus à la fin." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### Structures de données\n", "\n", "On se restreint aux intervalles à coordonnées *entières*, et on considère des listes d'intervalles.\n", "Tous les intervalles sont fermés à gauche et à droite." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
type intervalle = int * int\n",
       "
" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type intervalle = (int * int);; (* (a, b) représente l'intervalle [a, b] *)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
type intervalles = intervalle list\n",
       "
" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type intervalles = intervalle list;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On définit tout de suite deux exemples, $T_a$ et $S_a$ tirés de la Figure 2.a) et $T_b,S_b$ de la Figure 2.b).\n", "Cela permettra de vérifier les opérations $\\oplus$ et $\\otimes$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- $T_a = \\{ [1, 4], [6, 8] \\}$ et $S_a = \\{ [0, 1], [3, 5], [6, 7] \\}$." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val t_a : intervalles = [(1, 4); (6, 8)]\n",
       "
" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val s_a : intervalles = [(0, 1); (3, 5); (6, 7)]\n",
       "
" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t_a : intervalles = [\n", " (1, 4);\n", " (6, 8)\n", "];;\n", "\n", "let s_a : intervalles = [\n", " (0, 1);\n", " (3, 5);\n", " (6, 7)\n", "];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- $T_b = \\{ [-1, 0], [2, 4] \\}$ et $S_b = \\{ [0, 1], [4, 4] \\}$." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val t_b : intervalles = [(-1, 0); (2, 4)]\n",
       "
" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val s_b : intervalles = [(0, 1); (4, 4)]\n",
       "
" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t_b : intervalles = [\n", " (-1, 0);\n", " (2, 4)\n", "];;\n", "\n", "let s_b : intervalles = [\n", " (0, 1);\n", " (4, 4) (* Intervalle de longueur nulle *)\n", "];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### Opérations de base, $\\oplus$ et $\\otimes$\n", "On peut écrire des opérations d'intersection et de composition sur deux intervalles, ensuite il suffira de les généraliser à un ensemble d'intervalle.\n", "\n", "On suit les définitions de l'énoncé.\n", "\n", "#### Intersection\n", "$$\n", "\\forall T = (I_1,\\dots,I_l),\n", "\\forall S = (J_1,\\dots,J_m),\\\\\n", "T \\oplus S := \\{ K_1, \\dots, K_n\\}\n", "\\;\\;\\text{Où}\\;\\; K_k = I_i \\cap J_j.\n", "$$\n", "Notez que $n \\leq l + m$ ici." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour l'intersection de deux intervalles, l'intervalle vide $\\emptyset$ peut être obtenu, donc la fonction suivante renvoie un type `intervalle option` : soit `None` si $I \\cap J = \\emptyset$, soit `Some (x, y)` si $I \\cap J = [x, y]$." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "
val intersection : intervalle -> intervalle -> intervalle option = <fun>\n",
       "
" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let intersection (i : intervalle) (j : intervalle) : intervalle option =\n", " let a = fst i and b = snd i in\n", " let c = fst j and d = snd j in\n", " if b < c || d < a then\n", " None\n", " else\n", " Some (max a c, min b d)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ensuite, il suffit d'explorer tous les couples $(I, J)$ possible, et de ne garder que ceux qui donnent un intervalle.\n", "On supprimera les doublons en vérifiant au fur et à mesure (ça a la même complexité que si on le fait à la fin).\n", "\n", "En manipulant une liste d'intervalle `option`, on doit ruser un peu pour n'ajouter que ceux qui ne sont pas dans `acc` et qui sont des vrais intervalles." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val ajoute_nouveaux_option :\n",
       "  intervalles -> intervalle option list -> intervalle list = <fun>\n",
       "
" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ajoute_nouveaux_option (acc : intervalles) (liste_option : intervalle option list) =\n", " List.map\n", " (fun i -> match i with Some i2 -> i2 | None -> (0, 0))\n", " (List.filter (fun i ->\n", " match i with\n", " | None -> false\n", " | Some i2 -> not (List.mem i2 acc)\n", " ) liste_option)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec tout ça, on a une belle fonction récursive, avec un accumulateur `acc` qui contient la liste des intervalles dans $T \\oplus S$, construite en considérant les intervalles de $S$ les un après les autres.\n", "\n", "On s'assure de n'avoir ni intervalles vide, ni doublon, grâce à `ajoute_nouveaux_option`." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val intersections : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let intersections (t : intervalles) (s : intervalles) : intervalles =\n", " let rec inter_aux acc tx sx =\n", " match sx with\n", " | [] -> acc (* Plus rien à ajouter *)\n", " | j :: s2 -> (* On traite j, puis récursivement la suite de s *)\n", " let t_inter_j = List.map (intersection j) tx in\n", " inter_aux ((ajoute_nouveaux_option acc t_inter_j) @ acc) tx s2\n", " in\n", " List.sort compare (inter_aux [] t s)\n", " (* On trie pour les avoir en ordre croissant, c'est tout *)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour frimer un peu et simplifier l'écriture de l'algorithme PC, on peut définir une opération infixe en raccourci :\n", "$$ T \\oplus S = \\texttt{t ++ s}.$$" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val ( ++ ) : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ( ++ ) = intersections;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Composition\n", "Ce sera plus facile.\n", "$$\n", "\\forall T = (I_1,\\dots,I_l),\n", "\\forall S = (J_1,\\dots,J_m),\\\\\n", "T \\otimes S := \\{ K_1, \\dots, K_n\\}\n", "\\;\\;\\text{Où}\\;\\; K_k = [a + c, b + d], \\;\\text{si}\\; I_i = [a, b], J_j = [c, d].\n", "$$\n", "Notez que $n \\leq l \\times m$ ici." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour la composition de deux intervalles, il n'y pas de difficulté particulière :" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "
val composition : intervalle -> intervalle -> intervalle = <fun>\n",
       "
" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let composition (i : intervalle) (j : intervalle) : intervalle =\n", " let a = fst i and b = snd i in\n", " let c = fst j and d = snd j in\n", " (a + c, b + d)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et on les combine facilement, en gardant la même architecture que pour `intersections`." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val ajoute_nouveaux : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ajoute_nouveaux (acc : intervalles) (liste : intervalles) : intervalles =\n", " List.filter (fun i -> not (List.mem i acc)) liste\n", ";;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val compositions : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let compositions (t : intervalles) (s : intervalles) : intervalles =\n", " let rec compo_aux acc tx sx =\n", " match sx with\n", " | [] -> acc (* Plus rien à ajouter *)\n", " | j :: s2 -> (* On traite j, puis récursivement la suite de s *)\n", " let t_compo_j = List.map (composition j) tx in\n", " compo_aux ((ajoute_nouveaux acc t_compo_j) @ acc) tx s2\n", " in\n", " List.sort compare (compo_aux [] t s)\n", " (* On trie pour les avoir en ordre croissant, c'est tout *)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour frimer un peu et simplifier l'écriture de l'algorithme PC, on peut définir une opération infixe en raccourci :\n", "$$ T \\otimes S = \\texttt{t ** s}.$$" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val ( ** ) : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ( ** ) = compositions;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Union\n", "On peut aussi rapidement définier $T \\cup S$, pour l'union. C'est très facile." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val union : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let union (t : intervalles) (s : intervalles) : intervalles =\n", " List.append t s\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exemples\n", "On aimerait reproduire les exemples de la Figure 2 du texte.\n", "![images/intersection_composition_contraintes.png](images/intersection_composition_contraintes.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Pour les deux intervalles de la Figure 2.a) : $T_a = \\{ [1, 4], [6, 8] \\}$ et $S_a = \\{ [0, 1], [3, 5], [6, 7] \\}$." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : intervalles = [(1, 1); (3, 4); (6, 7)]\n",
       "
" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t_a ++ s_a;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On retrouve bien le résultat de la Figure 2.a)." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : intervalles = [(1, 5); (4, 9); (6, 9); (7, 11); (9, 13); (12, 15)]\n",
       "
" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(1, 4); (6, 8); (0, 1); (3, 5); (6, 7)]\n",
       "
" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t_a ** s_a;;\n", "union t_a s_a;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Pour les deux intervalles de la Figure 2.b) : $T_b = \\{ [-1, 0], [2, 4] \\}$ et $S_b = \\{ [0, 1], [4, 4] \\}$." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : intervalles = [(-1, 1); (2, 5); (3, 4); (6, 8)]\n",
       "
" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t_b ** s_b;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On retrouve bien le résultat de la Figure 2.b).\n", "\n", "L'intervalle $[3, 4]$ est inclus dans $[2, 5]$, donc on devrait ajouter une étape de nettoyage pour donner une forme canonique aux intervalles produit par `composition`. On le fait plus bas." ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : intervalles = [(0, 0); (4, 4)]\n",
       "
" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(-1, 0); (2, 4); (0, 1); (4, 4)]\n",
       "
" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t_b ++ s_b;;\n", "union t_b s_b;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On remarque que les intervalles sont bien donnés dans l'ordre croissant, puisqu'on a pensé à trier la sortie des deux fonctions, mais ça ne change rien." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Une étape de plus : ne pas inclure des intervalles inclus dans ceux déjà présents\n", "\n", "On va raffiner les fonctions définis ci-dessus en ajoutant un test, sur leur résultat final.\n", "\n", "- `est_inclus i j` teste si $I \\subseteq J$." ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val est_inclus : intervalle -> intervalle -> bool = <fun>\n",
       "
" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_inclus (i : intervalle) (j : intervalle) : bool =\n", " let a = fst i and b = snd i in\n", " let c = fst j and d = snd j in\n", " c <= a && b <= d\n", ";;" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : bool = false\n",
       "
" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_inclus (3, 4) (2, 5);; (* true *)\n", "est_inclus (2, 5) (3, 4);; (* false *)\n", "est_inclus (1, 1) (1, 1);; (* true *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- `est_inclus_dans_un i acc` teste si $I \\subseteq J$ pour **un** $J \\neq I \\in \\mathrm{Acc}$." ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val est_inclus_dans_un : intervalle -> intervalles -> bool = <fun>\n",
       "
" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_inclus_dans_un (i : intervalle) (acc : intervalles) : bool =\n", " List.exists (fun j -> (i != j) && (est_inclus i j)) acc\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- On peut écrire une fonction `filtre` qui retire les intervalles inclus dans d'autres, puis retire les doublons." ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val retire_les_inclus : intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val retire_les_doublons : intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val filtre : intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let retire_les_inclus (liste : intervalles) : intervalles =\n", " List.filter (fun i -> not (est_inclus_dans_un i liste)) liste\n", ";;\n", "\n", "let retire_les_doublons (liste : intervalles) : intervalles =\n", " let reponse = ref [] in\n", " List.iter (fun i ->\n", " if not (List.mem i !reponse) then\n", " reponse := i :: !reponse\n", " ) liste;\n", " !reponse\n", ";;\n", "\n", "let filtre liste =\n", " retire_les_doublons (retire_les_inclus liste)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- L'intersection ne devrait pas être impactée." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val intersections2 : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let intersections2 (t : intervalles) (s : intervalles) : intervalles =\n", " List.sort compare (filtre (intersections t s))\n", " (* On trie pour les avoir en ordre croissant, c'est tout *)\n", ";;" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val ( ++ ) : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(1, 1); (3, 4); (6, 7)]\n",
       "
" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ( ++ ) = intersections2;;\n", "\n", "t_a ++ s_a;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Mais la composition va donner la bonne réponse désormais pour l'exemple de la figure 2.b)." ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val compositions2 : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let compositions2 (t : intervalles) (s : intervalles) : intervalles =\n", " List.sort compare (filtre (compositions t s))\n", " (* On trie pour les avoir en ordre croissant, c'est tout *)\n", ";;" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val ( ** ) : intervalles -> intervalles -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(-1, 1); (2, 5); (6, 8)]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ( ** ) = compositions2;;\n", "\n", "t_b ** s_b;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> C'était un peu long, mais c'est propre au moins." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notez que pour obtenir une vraie forme canonique, il faudrait aussi rassembler les intervalles consécutifs ($\\{ [0, 1], [1, 2] \\} \\rightarrow \\{ [0, 1] \\}$) et se recoupant ($\\{ [0, 3], [2, 4] \\} \\rightarrow \\{ [0, 4] \\}$).\n", "\n", "> Ça prendrait trop de temps. Et ce n'était pas exigé." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### L'algorithme PC" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Structure de données pour les réseaux STP\n", "On a besoin désormais de considérer des réseaux STP, qui sont des graphes dont les sommets sont des entiers, et dont les arêtes sont étiquetées par des *listes* (non vides) d'intervalles.\n", "\n", "L'algorithme PC demande de pouvoir accéder rapidement et facilement à l'arête entre deux sommets $x,y$, $T_{x,y}$.\n", "Ainsi, la structure de matrice d'adjacence semble appropriée.\n", "Les arêtes inexistantes dans le réseau auront simplement $T_{x,y} = \\emptyset$, c'est-à-dire `[]` (liste vide).\n", "\n", "> On supposera que toutes les matrices données aux différentes fonctions définies plus bas sont carrées, on ne le vérifie pas (mais ce serait facile)." ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
type sommet = int\n",
       "
" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
type arete = intervalles\n",
       "
" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
type reseauSTP = intervalles array array\n",
       "
" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type sommet = int;;\n", "type arete = intervalles;; (* c'est l'idée *)\n", "\n", "type reseauSTP = intervalles array array;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On essaie tout de suite notre structure de données avec l'exemple du réseau STP de la figure 4 :" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val t_01 : intervalles = [(0, 1); (10, 20)]\n",
       "
" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t_12 : intervalles = [(0, 10)]\n",
       "
" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t_13 : intervalles = [(25, 50)]\n",
       "
" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t_23 : intervalles = [(0, 20); (40, 40)]\n",
       "
" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val stp_4 : reseauSTP =\n",
       "  [|[|[]; [(0, 1); (10, 20)]; []; []|]; [|[]; [(0, 10)]; [(25, 50)]; []|];\n",
       "    [|[]; []; [(0, 20); (40, 40)]; []|]; [|[]; []; []; []|]|]\n",
       "
" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t_01 : intervalles = [(0, 1); (10, 20)];;\n", "let t_12 : intervalles = [(0, 10)];;\n", "let t_13 : intervalles = [(25, 50)];;\n", "let t_23 : intervalles = [(0, 20); (40, 40)];;\n", "\n", "let stp_4 : reseauSTP = [|\n", " [| []; t_01; []; [] |];\n", " [| []; t_12; t_13; [] |];\n", " [| []; []; t_23; [] |];\n", " [| []; []; []; [] |];\n", "|];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut vérifier qu'il n'est pas distributif, en prenant l'exemple du texte (fin page 8) :" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val s_13 : intervalles = [(0, 30); (40, 50)]\n",
       "
" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(25, 30); (40, 50)]\n",
       "
" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(25, 31); (35, 50); (40, 51); (50, 70)]\n",
       "
" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(25, 51); (35, 70)]\n",
       "
" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(0, 31); (10, 50); (40, 51); (50, 70)]\n",
       "
" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : intervalles = [(25, 50); (50, 70)]\n",
       "
" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let s_13 = t_12 ** t_23;;\n", "\n", "t_13 ++ s_13;;\n", "t_01 ** (t_13 ++ s_13);; (* 1er cas *)\n", "\n", "t_01 ** t_13;;\n", "t_01 ** s_13;;\n", "(t_01 ** t_13) ++ (t_01 ** s_13);; (* 2nd cas *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En simplifiant, on obtient :\n", "\n", "- $T_{01} \\otimes (T_{13} \\oplus S_{13} = \\{ [25, 31], [35, 70] \\}$,\n", "- $(T_{01} \\otimes T_{13}) \\oplus (T_{01} \\otimes S_{13}) = \\{ [25, 70] \\}$,\n", "\n", "qui sont bien différents." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Enfin, on peut rapidement vérifier si la matrice d'un graphe est bien carrée :" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val est_carree : 'a array array -> bool = <fun>\n",
       "
" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_carree matrice =\n", " let n = Array.length matrice in\n", " Array.fold_left (fun b x -> b && (n = (Array.length x))) true matrice\n", ";;" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_carree stp_4;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### L'algorithme PC\n", "Ça semble être un bon choix.\n", "Maintenant, passons à l'algorithme PC.\n", "\n", "![images/algorithme_PC.png](images/algorithme_PC.png)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il n'y a pas de boucle `until` en Caml, mais avec une boucle `while` on arrivera presque à la même chose." ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "
exception Fini\n",
       "
" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "exception Fini;; (* Pour faire le [exit]. *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut l'écrire avant pour la rendre plus claire, mais l'étape clé de l'algorithme PC (et Floyd-Warshall) est une opération dite de *relaxation* :\n", "$$ T_{i,j} \\oplus (T_{i,k} \\otimes T_{k,j}).$$" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val relaxe : reseauSTP -> int -> int -> int -> intervalles = <fun>\n",
       "
" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let relaxe (reseau : reseauSTP) i j k =\n", " let t_ij = reseau.(i).(j)\n", " and t_ik = reseau.(i).(k)\n", " and t_kj = reseau.(k).(j)\n", " in t_ij ++ (t_ik ** t_kj)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On a tout ce qu'il faut pour écrire l'algorithme." ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val algorithmePC : reseauSTP -> reseauSTP * intervalles list = <fun>\n",
       "
" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let algorithmePC (reseau : reseauSTP) : (reseauSTP * intervalles list) =\n", " let resT = Array.copy reseau (* on ne modifie pas l'entrée *)\n", " and resS = ref [||] in\n", " let n = Array.length resT\n", " and allseen = ref [] (* Pour débogguer, je veux la liste des Tij vus *)\n", " in\n", " begin\n", " try begin\n", " while !resS != resT do\n", " resS := Array.copy resT; (* S := T *)\n", " for k = 0 to n - 1 do\n", " for i = 0 to n - 1 do\n", " for j = 0 to n - 1 do\n", " resT.(i).(j) <-\n", " relaxe resT i j k;\n", " allseen := (resT.(i).(j)) :: !allseen; (* on l'ajoute *)\n", " if resT.(i).(j) = [] then\n", " raise Fini\n", " done\n", " done\n", " done\n", " done;\n", " end\n", " with Fini -> () (* On ignore l'exception, on a juste terminé. *)\n", " end;\n", " resT, !allseen\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### Exemple de réseau non distributif\n", "On va traiter l'exemple de la Figure 4 du texte, comme défini plus haut :\n", "\n", "![images/reseau_distributif.png](images/reseau_distributif.png)" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "
- : reseauSTP =\n",
       "[|[|[]; [(0, 1); (10, 20)]; []; []|]; [|[]; [(0, 10)]; [(25, 50)]; []|];\n",
       "  [|[]; []; [(0, 20); (40, 40)]; []|]; [|[]; []; []; []|]|]\n",
       "
" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "stp_4;;" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : reseauSTP * intervalles list =\n",
       "([|[|[]; [(0, 1); (10, 20)]; []; []|]; [|[]; [(0, 10)]; [(25, 50)]; []|];\n",
       "   [|[]; []; [(0, 20); (40, 40)]; []|]; [|[]; []; []; []|]|],\n",
       " [[]])\n",
       "
" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "algorithmePC stp_4;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Je ne suis pas sûr de comment interprêter ce résultat...\n", "> \n", "> - soit j'ai fait une erreur dans l'implémentation,\n", "> - soit l'algorithme PC devait ne rien modifier à $T$ sur cet exemple..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "### D'autres exemples\n", "\n", "On peut étudier le STP de la Figure 1., en enlevant la contrainte $[60, \\infty)$, qui ne rentre pas dans notre implémentation.\n", "\n", "![images/stp_figure1.png](images/stp_figure1.png)." ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val t_01 : intervalles = [(10, 20)]\n",
       "
" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t_12 : intervalles = [(30, 40)]\n",
       "
" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t_32 : intervalles = [(10, 20)]\n",
       "
" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t_34 : intervalles = [(20, 30); (40, 50)]\n",
       "
" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t_40 : intervalles = [(60, 70)]\n",
       "
" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val stp_1 : reseauSTP =\n",
       "  [|[|[]; [(10, 20)]; []; []; []|]; [|[]; []; [(30, 40)]; []; []|];\n",
       "    [|[]; []; []; []; []|]; [|[]; []; [(10, 20)]; []; [(20, 30); (40, 50)]|];\n",
       "    [|[(60, 70)]; []; []; []; []|]|]\n",
       "
" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t_01 : intervalles = [(10, 20)];;\n", "let t_12 : intervalles = [(30, 40)];;\n", "let t_32 : intervalles = [(10, 20)];;\n", "let t_34 : intervalles = [(20, 30); (40, 50)];;\n", "let t_40 : intervalles = [(60, 70)];;\n", "\n", "let stp_1 : reseauSTP = [|\n", " [| []; t_01; []; []; [] |];\n", " [| []; []; t_12; []; [] |];\n", " [| []; []; []; []; [] |];\n", " [| []; []; t_32; []; t_34 |];\n", " [| t_40; []; []; []; [] |];\n", "|];;" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : reseauSTP * intervalles list =\n",
       "([|[|[]; [(10, 20)]; []; []; []|]; [|[]; []; [(30, 40)]; []; []|];\n",
       "   [|[]; []; []; []; []|]; [|[]; []; [(10, 20)]; []; [(20, 30); (40, 50)]|];\n",
       "   [|[(60, 70)]; []; []; []; []|]|],\n",
       " [[]])\n",
       "
" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "algorithmePC stp_1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Je ne suis pas sûr de comment interprêter ce résultat...\n", "> \n", "> - soit j'ai fait une erreur dans l'implémentation,\n", "> - soit l'algorithme PC devait ne rien modifier à $T$ sur cet exemple..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Conclusion\n", "\n", "Voilà pour la question obligatoire de programmation :\n", "\n", "- on a décomposé le problème en sous-fonctions,\n", "- on a essayé d'être fainéant, en réutilisant les sous-fonctions,\n", "- on a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n", "- on a testé la fonction exigée sur de petits exemples et sur un exemple de taille réelle (venant du texte)\n", "\n", "Et on a essayé de faire *un peu plus*, en implémentant la vérification d'une contrainte de plus.\n", "\n", "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive." ] } ], "metadata": { "kernelspec": { "display_name": "OCaml", "language": "ocaml", "name": "iocaml-kernel" }, "language_info": { "name": "ocaml", "version": "4.1.0" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "289px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_position": { "height": "610px", "left": "0px", "right": "1223px", "top": "124px", "width": "249px" }, "toc_section_display": "block", "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 2 }