<jupyter_start><jupyter_text>Table of Contents 1&nbsp;&nbsp;Texte d'oral de modélisation - Agrégation Option Informatique1.1&nbsp;&nbsp;Préparation à l'agrégation - ENS de Rennes, 2016-171.2&nbsp;&nbsp;À propos de ce document1.3&nbsp;&nbsp;Question de programmation1.4&nbsp;&nbsp;Réponse à l'exercice requis1.4.1&nbsp;&nbsp;Structures de données1.4.2&nbsp;&nbsp;Opérations de base, $\oplus$ et $\otimes$1.4.2.1&nbsp;&nbsp;Intersection1.4.2.2&nbsp;&nbsp;Composition1.4.2.3&nbsp;&nbsp;Union1.4.2.4&nbsp;&nbsp;Exemples1.4.2.5&nbsp;&nbsp;Une étape de plus : ne pas inclure des intervalles inclus dans ceux déjà présents1.4.3&nbsp;&nbsp;L'algorithme PC1.4.3.1&nbsp;&nbsp;Structure de données pour les réseaux STP1.4.3.2&nbsp;&nbsp;L'algorithme PC1.4.4&nbsp;&nbsp;Exemple de réseau non distributif1.4.5&nbsp;&nbsp;D'autres exemples1.5&nbsp;&nbsp;Conclusion  Texte d'oral de modélisation - Agrégation Option Informatique Préparation à l'agrégation - ENS de Rennes, 2016-17- *Date* : 7 avril 2017- *Auteur* : [<NAME>](https://GitHub.com/Naereen/notebooks/)- *Texte*: Annale 2009, "Contraintes temporelles"  À propos de ce document- 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/).- 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.- L'implémentation sera faite en OCaml, version 4+ :<jupyter_code>Sys.command "ocaml -version";;<jupyter_output>The OCaml toplevel, version 4.04.2<jupyter_text>> 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.> J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers. ---- Question de programmationLa question de programmation pour ce texte était donnée en question 1 en page 9 :> "Programmer l'algorithme PC. Faites le tourner sur l'exemple de réseau non distributif."La consigne était très courte, mais avec aucune indication.Notez qu'il est rare que le texte exige un exemple particulier. ---- Réponse à l'exercice requisÇa va être assez rapide :1. D'abord, il faut définir les types de données avec lesquels on va travailler,2. Ensuite, implémenter les deux opérations $\oplus$ et $\otimes$ sur les ensembles d'intervalles,3. Puis implémenter l'algorithme PC (similaire à Floyd-Warshall),4. Et enfin, l'exécuter sur l'exemple de réseau non distributif donné en page 8.Si possible, on va essayer de faire des *tests* pour chaque fonction intermédiaire, et un exemple de plus à la fin. ---- Structures de donnéesOn se restreint aux intervalles à coordonnées *entières*, et on considère des listes d'intervalles.Tous les intervalles sont fermés à gauche et à droite.<jupyter_code>type intervalle = (int * int);;  (* (a, b) représente l'intervalle [a, b] *)
type intervalles = intervalle list;;<jupyter_output><empty_output><jupyter_text>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).Cela permettra de vérifier les opérations $\oplus$ et $\otimes$. - $T_a = \{ [1, 4], [6, 8] \}$ et $S_a = \{ [0, 1], [3, 5], [6, 7] \}$.<jupyter_code>let t_a : intervalles = [
    (1, 4);
    (6, 8)
];;

let s_a : intervalles = [
    (0, 1);
    (3, 5);
    (6, 7)
];;<jupyter_output><empty_output><jupyter_text>- $T_b = \{ [-1, 0], [2, 4] \}$ et $S_b = \{ [0, 1], [4, 4] \}$.<jupyter_code>let t_b : intervalles = [
    (-1, 0);
    (2, 4)
];;

let s_b : intervalles = [
    (0, 1);
    (4, 4)  (* Intervalle de longueur nulle *)
];;<jupyter_output><empty_output><jupyter_text>---- Opérations de base, $\oplus$ et $\otimes$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.On suit les définitions de l'énoncé. Intersection$$\forall T = (I_1,\dots,I_l),\forall S = (J_1,\dots,J_m),\\T \oplus S := \{ K_1, \dots, K_n\}\;\;\text{Où}\;\; K_k = I_i \cap J_j.$$Notez que $n \leq l + m$ ici. 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]$.<jupyter_code>let intersection (i : intervalle) (j : intervalle) : intervalle option =
    let a = fst i and b = snd i in
    let c = fst j and d = snd j in
    if b < c || d < a then
        None
    else
        Some (max a c, min b d)
;;<jupyter_output><empty_output><jupyter_text>Ensuite, il suffit d'explorer tous les couples $(I, J)$ possible, et de ne garder que ceux qui donnent un intervalle.On supprimera les doublons en vérifiant au fur et à mesure (ça a la même complexité que si on le fait à la fin).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.<jupyter_code>let ajoute_nouveaux_option (acc : intervalles) (liste_option : intervalle option list) =
    List.map
    (fun i -> match i with Some i2 -> i2 | None -> (0, 0))
    (List.filter (fun i ->
        match i with
        | None -> false
        | Some i2 -> not (List.mem i2 acc)
    ) liste_option)
;;<jupyter_output><empty_output><jupyter_text>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.On s'assure de n'avoir ni intervalles vide, ni doublon, grâce à `ajoute_nouveaux_option`.<jupyter_code>let intersections (t : intervalles) (s : intervalles) : intervalles =
    let rec inter_aux acc tx sx =
        match sx with
        | [] -> acc    (* Plus rien à ajouter *)
        | j :: s2 ->   (* On traite j, puis récursivement la suite de s *)
            let t_inter_j = List.map (intersection j) tx in
            inter_aux ((ajoute_nouveaux_option acc t_inter_j) @ acc) tx s2
    in
    List.sort compare (inter_aux [] t s)
    (* On trie pour les avoir en ordre croissant, c'est tout *)
;;<jupyter_output><empty_output><jupyter_text>Pour frimer un peu et simplifier l'écriture de l'algorithme PC, on peut définir une opération infixe en raccourci :$$ T \oplus S = \texttt{t ++ s}.$$<jupyter_code>let ( ++ ) = intersections;;<jupyter_output><empty_output><jupyter_text>CompositionCe sera plus facile.$$\forall T = (I_1,\dots,I_l),\forall S = (J_1,\dots,J_m),\\T \otimes S := \{ K_1, \dots, K_n\}\;\;\text{Où}\;\; K_k = [a + c, b + d], \;\text{si}\; I_i = [a, b], J_j = [c, d].$$Notez que $n \leq l \times m$ ici. Pour la composition de deux intervalles, il n'y pas de difficulté particulière :<jupyter_code>let composition (i : intervalle) (j : intervalle) : intervalle =
    let a = fst i and b = snd i in
    let c = fst j and d = snd j in
    (a + c, b + d)
;;<jupyter_output><empty_output><jupyter_text>Et on les combine facilement, en gardant la même architecture que pour `intersections`.<jupyter_code>let ajoute_nouveaux (acc : intervalles) (liste : intervalles) : intervalles =
    List.filter (fun i -> not (List.mem i acc)) liste
;;
let compositions (t : intervalles) (s : intervalles) : intervalles =
    let rec compo_aux acc tx sx =
        match sx with
        | [] -> acc    (* Plus rien à ajouter *)
        | j :: s2 ->   (* On traite j, puis récursivement la suite de s *)
            let t_compo_j = List.map (composition j) tx in
            compo_aux ((ajoute_nouveaux acc t_compo_j) @ acc) tx s2
    in
    List.sort compare (compo_aux [] t s)
    (* On trie pour les avoir en ordre croissant, c'est tout *)
;;<jupyter_output><empty_output><jupyter_text>Pour frimer un peu et simplifier l'écriture de l'algorithme PC, on peut définir une opération infixe en raccourci :$$ T \otimes S = \texttt{t ** s}.$$<jupyter_code>let ( ** ) = compositions;;<jupyter_output><empty_output><jupyter_text>UnionOn peut aussi rapidement définier $T \cup S$, pour l'union. C'est très facile.<jupyter_code>let union (t : intervalles) (s : intervalles) : intervalles =
    List.append t s
;;<jupyter_output><empty_output><jupyter_text>ExemplesOn aimerait reproduire les exemples de la Figure 2 du texte.![images/intersection_composition_contraintes.png](images/intersection_composition_contraintes.png) - Pour les deux intervalles de la Figure 2.a) : $T_a = \{ [1, 4], [6, 8] \}$ et $S_a = \{ [0, 1], [3, 5], [6, 7] \}$.<jupyter_code>t_a ++ s_a;;<jupyter_output><empty_output><jupyter_text>On retrouve bien le résultat de la Figure 2.a).<jupyter_code>t_a ** s_a;;
union t_a s_a;;<jupyter_output><empty_output><jupyter_text>- Pour les deux intervalles de la Figure 2.b) : $T_b = \{ [-1, 0], [2, 4] \}$ et $S_b = \{ [0, 1], [4, 4] \}$.<jupyter_code>t_b ** s_b;;<jupyter_output><empty_output><jupyter_text>On retrouve bien le résultat de la Figure 2.b).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.<jupyter_code>t_b ++ s_b;;
union t_b s_b;;<jupyter_output><empty_output><jupyter_text>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.  Une étape de plus : ne pas inclure des intervalles inclus dans ceux déjà présentsOn va raffiner les fonctions définis ci-dessus en ajoutant un test, sur leur résultat final.- `est_inclus i j` teste si $I \subseteq J$.<jupyter_code>let est_inclus (i : intervalle) (j : intervalle) : bool =
    let a = fst i and b = snd i in
    let c = fst j and d = snd j in
    c <= a && b <= d
;;
est_inclus (3, 4) (2, 5);; (* true *)
est_inclus (2, 5) (3, 4);; (* false *)
est_inclus (1, 1) (1, 1);; (* true *)<jupyter_output><empty_output><jupyter_text>- `est_inclus_dans_un i acc` teste si $I \subseteq J$ pour **un** $J \neq I \in \mathrm{Acc}$.<jupyter_code>let est_inclus_dans_un (i : intervalle) (acc : intervalles) : bool =
    List.exists (fun j -> (i != j) && (est_inclus i j)) acc
;;<jupyter_output><empty_output><jupyter_text>- On peut écrire une fonction `filtre` qui retire les intervalles inclus dans d'autres, puis retire les doublons.<jupyter_code>let retire_les_inclus (liste : intervalles) : intervalles =
    List.filter (fun i -> not (est_inclus_dans_un i liste)) liste
;;

let retire_les_doublons (liste : intervalles) : intervalles =
    let reponse = ref [] in
    List.iter (fun i ->
        if not (List.mem i !reponse) then
        reponse := i :: !reponse
    ) liste;
    !reponse
;;

let filtre liste =
    retire_les_doublons (retire_les_inclus liste)
;;<jupyter_output><empty_output><jupyter_text>- L'intersection ne devrait pas être impactée.<jupyter_code>let intersections2 (t : intervalles) (s : intervalles) : intervalles =
    List.sort compare (filtre (intersections t s))
    (* On trie pour les avoir en ordre croissant, c'est tout *)
;;
let ( ++ ) = intersections2;;

t_a ++ s_a;;<jupyter_output><empty_output><jupyter_text>- Mais la composition va donner la bonne réponse désormais pour l'exemple de la figure 2.b).<jupyter_code>let compositions2 (t : intervalles) (s : intervalles) : intervalles =
    List.sort compare (filtre (compositions t s))
    (* On trie pour les avoir en ordre croissant, c'est tout *)
;;
let ( ** ) = compositions2;;

t_b ** s_b;;<jupyter_output><empty_output><jupyter_text>> C'était un peu long, mais c'est propre au moins. 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] \}$).> Ça prendrait trop de temps. Et ce n'était pas exigé. ---- L'algorithme PC  Structure de données pour les réseaux STPOn 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.L'algorithme PC demande de pouvoir accéder rapidement et facilement à l'arête entre deux sommets $x,y$, $T_{x,y}$.Ainsi, la structure de matrice d'adjacence semble appropriée.Les arêtes inexistantes dans le réseau auront simplement $T_{x,y} = \emptyset$, c'est-à-dire `[]` (liste vide).> 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).<jupyter_code>type sommet = int;;
type arete = intervalles;; (* c'est l'idée *)

type reseauSTP = intervalles array array;;<jupyter_output><empty_output><jupyter_text>On essaie tout de suite notre structure de données avec l'exemple du réseau STP de la figure 4 :<jupyter_code>let t_01 : intervalles = [(0, 1); (10, 20)];;
let t_12 : intervalles = [(0, 10)];;
let t_13 : intervalles = [(25, 50)];;
let t_23 : intervalles = [(0, 20); (40, 40)];;

let stp_4 : reseauSTP = [|
    [| []; t_01; [];   [] |];
    [| []; t_12; t_13; [] |];
    [| []; [];   t_23; [] |];
    [| []; [];   [];   [] |];
|];;<jupyter_output><empty_output><jupyter_text>On peut vérifier qu'il n'est pas distributif, en prenant l'exemple du texte (fin page 8) :<jupyter_code>let s_13 = t_12 ** t_23;;

t_13 ++ s_13;;
t_01 ** (t_13 ++ s_13);;  (* 1er cas *)

t_01 ** t_13;;
t_01 ** s_13;;
(t_01 ** t_13) ++ (t_01 ** s_13);; (* 2nd cas *)<jupyter_output><empty_output><jupyter_text>En simplifiant, on obtient :- $T_{01} \otimes (T_{13} \oplus S_{13} = \{ [25, 31], [35, 70] \}$,- $(T_{01} \otimes T_{13}) \oplus (T_{01} \otimes S_{13}) = \{ [25, 70] \}$,qui sont bien différents. Enfin, on peut rapidement vérifier si la matrice d'un graphe est bien carrée :<jupyter_code>let est_carree matrice =
    let n = Array.length matrice in
    Array.fold_left (fun b x -> b && (n = (Array.length x))) true matrice
;;
est_carree stp_4;;<jupyter_output><empty_output><jupyter_text>L'algorithme PCÇa semble être un bon choix.Maintenant, passons à l'algorithme PC.![images/algorithme_PC.png](images/algorithme_PC.png). Il n'y a pas de boucle `until` en Caml, mais avec une boucle `while` on arrivera presque à la même chose.<jupyter_code>exception Fini;; (* Pour faire le [exit]. *)<jupyter_output><empty_output><jupyter_text>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* :$$ T_{i,j} \oplus (T_{i,k} \otimes T_{k,j}).$$<jupyter_code>let relaxe (reseau : reseauSTP) i j k =
    let t_ij = reseau.(i).(j)
    and t_ik = reseau.(i).(k)
    and t_kj = reseau.(k).(j)
    in t_ij ++ (t_ik ** t_kj)
;;<jupyter_output><empty_output><jupyter_text>On a tout ce qu'il faut pour écrire l'algorithme.<jupyter_code>let algorithmePC (reseau : reseauSTP) : (reseauSTP * intervalles list) =
    let resT = Array.copy reseau (* on ne modifie pas l'entrée *)
    and resS = ref [||] in
    let n = Array.length resT
    and allseen = ref []   (* Pour débogguer, je veux la liste des Tij vus *)
    in
    begin
        try begin
        while !resS != resT do
            resS := Array.copy resT; (* S := T *)
            for k = 0 to n - 1 do
                for i = 0 to n - 1 do
                    for j = 0 to n - 1 do
                        resT.(i).(j) <-
                        relaxe resT i j k;
                        allseen := (resT.(i).(j)) :: !allseen; (* on l'ajoute *)
                        if resT.(i).(j) = [] then
                            raise Fini
                    done
                done
            done
        done;
        end
        with Fini -> () (* On ignore l'exception, on a juste terminé. *)
    end;
    resT, !allseen
;;<jupyter_output><empty_output><jupyter_text>---- Exemple de réseau non distributifOn va traiter l'exemple de la Figure 4 du texte, comme défini plus haut :![images/reseau_distributif.png](images/reseau_distributif.png)<jupyter_code>stp_4;;
algorithmePC stp_4;;<jupyter_output><empty_output><jupyter_text>> Je ne suis pas sûr de comment interprêter ce résultat...> > - soit j'ai fait une erreur dans l'implémentation,> - soit l'algorithme PC devait ne rien modifier à $T$ sur cet exemple... ---- D'autres exemplesOn peut étudier le STP de la Figure 1., en enlevant la contrainte $[60, \infty)$, qui ne rentre pas dans notre implémentation.![images/stp_figure1.png](images/stp_figure1.png).<jupyter_code>let t_01 : intervalles = [(10, 20)];;
let t_12 : intervalles = [(30, 40)];;
let t_32 : intervalles = [(10, 20)];;
let t_34 : intervalles = [(20, 30); (40, 50)];;
let t_40 : intervalles = [(60, 70)];;

let stp_1 : reseauSTP = [|
    [| []; t_01; []; []; [] |];
    [| []; []; t_12; []; [] |];
    [| []; []; []; []; []   |];
    [| []; []; t_32; []; t_34 |];
    [| t_40; []; []; []; [] |];
|];;
algorithmePC stp_1;;<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13720455208637292, 'fraction_numerical': 0.02100962941348118, 'mean_word_length': 3.8434143583945732, 'pattern_counts': {'":': 0, '<': 126, '<?xml version=': 0, '>': 147, 'https://': 4, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 7, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '30', 'dir': 'jupyter-structured-clean-dedup', 'id': '194322', 'license': 'MIT', 'n_tokens_mistral': 6656, 'n_tokens_neox': 6361, 'n_words': 1990, 'path': 'agreg/Contraintes_temporelles.ipynb', 'repo_name': 'operade/notebooks', 'size': '17142'}