Table of Contents¶

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.
Ce document est un notebook Jupyter, et est open-source sous Licence MIT sur GitHub, comme les autres solutions de textes de modélisation que j'ai écrite cette année.
L'implémentation sera faite en OCaml, version 4+ :

In [2]:

Sys.command "ocaml -version";;

The OCaml toplevel, version 4.02.3

Out[2]:

- : int = 0

Notez que certaines fonctions des modules usuels List et Array 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 programmation¶

La 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 :

D'abord, il faut définir les types de données avec lesquels on va travailler,
Ensuite, implémenter les deux opérations $\oplus$ et $\otimes$ sur les ensembles d'intervalles,
Puis implémenter l'algorithme PC (similaire à Floyd-Warshall),
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ées¶

On 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.

In [3]:

type intervalle = (int * int);;  (* (a, b) représente l'intervalle [a, b] *)

Out[3]:

type intervalle = int * int

In [4]:

type intervalles = intervalle list;;

Out[4]:

type intervalles = intervalle list

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] \}$.

In [5]:

let t_a : intervalles = [
    (1, 4);
    (6, 8)
];;

let s_a : intervalles = [
    (0, 1);
    (3, 5);
    (6, 7)
];;

Out[5]:

val t_a : intervalles = [(1, 4); (6, 8)]

Out[5]:

val s_a : intervalles = [(0, 1); (3, 5); (6, 7)]

$T_b = \{ [-1, 0], [2, 4] \}$ et $S_b = \{ [0, 1], [4, 4] \}$.

In [6]:

let t_b : intervalles = [
    (-1, 0);
    (2, 4)
];;

let s_b : intervalles = [
    (0, 1);
    (4, 4)  (* Intervalle de longueur nulle *)
];;

Out[6]:

val t_b : intervalles = [(-1, 0); (2, 4)]

Out[6]:

val s_b : intervalles = [(0, 1); (4, 4)]

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]$.

In [7]:

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)
;;

Out[7]:

val intersection : intervalle -> intervalle -> intervalle option = <fun>

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.

In [8]:

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)
;;

Out[8]:

val ajoute_nouveaux_option :
  intervalles -> intervalle option list -> intervalle list = <fun>

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.

In [9]:

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 *)
;;

Out[9]:

val intersections : intervalles -> intervalles -> intervalles = <fun>

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}.$$

In [10]:

let ( ++ ) = intersections;;

Out[10]:

val ( ++ ) : intervalles -> intervalles -> intervalles = <fun>

Composition¶

Ce 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 :

In [11]:

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)
;;

Out[11]:

val composition : intervalle -> intervalle -> intervalle = <fun>

Et on les combine facilement, en gardant la même architecture que pour intersections.

In [12]:

let ajoute_nouveaux (acc : intervalles) (liste : intervalles) : intervalles =
    List.filter (fun i -> not (List.mem i acc)) liste
;;

Out[12]:

val ajoute_nouveaux : intervalles -> intervalles -> intervalles = <fun>

In [13]:

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 *)
;;

Out[13]:

val compositions : intervalles -> intervalles -> intervalles = <fun>

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}.$$

In [14]:

let ( ** ) = compositions;;

Out[14]:

val ( ** ) : intervalles -> intervalles -> intervalles = <fun>

Union¶

On peut aussi rapidement définier $T \cup S$, pour l'union. C'est très facile.

In [15]:

let union (t : intervalles) (s : intervalles) : intervalles =
    List.append t s
;;

Out[15]:

val union : intervalles -> intervalles -> intervalles = <fun>

Exemples¶

On aimerait reproduire les exemples de la Figure 2 du texte. 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] \}$.

In [16]:

t_a ++ s_a;;

Out[16]:

- : intervalles = [(1, 1); (3, 4); (6, 7)]

On retrouve bien le résultat de la Figure 2.a).

In [17]:

t_a ** s_a;;
union t_a s_a;;

Out[17]:

- : intervalles = [(1, 5); (4, 9); (6, 9); (7, 11); (9, 13); (12, 15)]

Out[17]:

- : intervalles = [(1, 4); (6, 8); (0, 1); (3, 5); (6, 7)]

Pour les deux intervalles de la Figure 2.b) : $T_b = \{ [-1, 0], [2, 4] \}$ et $S_b = \{ [0, 1], [4, 4] \}$.

In [18]:

t_b ** s_b;;

Out[18]:

- : intervalles = [(-1, 1); (2, 5); (3, 4); (6, 8)]

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.

In [19]:

t_b ++ s_b;;
union t_b s_b;;

Out[19]:

- : intervalles = [(0, 0); (4, 4)]

Out[19]:

- : intervalles = [(-1, 0); (2, 4); (0, 1); (4, 4)]

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ésents¶

On 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$.

In [20]:

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
;;

Out[20]:

val est_inclus : intervalle -> intervalle -> bool = <fun>

In [21]:

est_inclus (3, 4) (2, 5);; (* true *)
est_inclus (2, 5) (3, 4);; (* false *)
est_inclus (1, 1) (1, 1);; (* true *)

Out[21]:

- : bool = true

Out[21]:

- : bool = false

Out[21]:

- : bool = true

est_inclus_dans_un i acc teste si $I \subseteq J$ pour un $J \neq I \in \mathrm{Acc}$.

In [22]:

let est_inclus_dans_un (i : intervalle) (acc : intervalles) : bool =
    List.exists (fun j -> (i != j) && (est_inclus i j)) acc
;;

Out[22]:

val est_inclus_dans_un : intervalle -> intervalles -> bool = <fun>

On peut écrire une fonction filtre qui retire les intervalles inclus dans d'autres, puis retire les doublons.

In [23]:

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)
;;

Out[23]:

val retire_les_inclus : intervalles -> intervalles = <fun>

Out[23]:

val retire_les_doublons : intervalles -> intervalles = <fun>

Out[23]:

val filtre : intervalles -> intervalles = <fun>

L'intersection ne devrait pas être impactée.

In [24]:

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 *)
;;

Out[24]:

val intersections2 : intervalles -> intervalles -> intervalles = <fun>

In [25]:

let ( ++ ) = intersections2;;

t_a ++ s_a;;

Out[25]:

val ( ++ ) : intervalles -> intervalles -> intervalles = <fun>

Out[25]:

- : intervalles = [(1, 1); (3, 4); (6, 7)]

Mais la composition va donner la bonne réponse désormais pour l'exemple de la figure 2.b).

In [26]:

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 *)
;;

Out[26]:

val compositions2 : intervalles -> intervalles -> intervalles = <fun>

In [27]:

let ( ** ) = compositions2;;

t_b ** s_b;;

Out[27]:

val ( ** ) : intervalles -> intervalles -> intervalles = <fun>

Out[27]:

- : intervalles = [(-1, 1); (2, 5); (6, 8)]

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 STP¶

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.

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).

In [28]:

type sommet = int;;
type arete = intervalles;; (* c'est l'idée *)

type reseauSTP = intervalles array array;;

Out[28]:

type sommet = int

Out[28]:

type arete = intervalles

Out[28]:

type reseauSTP = intervalles array array

On essaie tout de suite notre structure de données avec l'exemple du réseau STP de la figure 4 :

In [29]:

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; [] |];
    [| []; [];   [];   [] |];
|];;

Out[29]:

val t_01 : intervalles = [(0, 1); (10, 20)]

Out[29]:

val t_12 : intervalles = [(0, 10)]

Out[29]:

val t_13 : intervalles = [(25, 50)]

Out[29]:

val t_23 : intervalles = [(0, 20); (40, 40)]

Out[29]:

val stp_4 : reseauSTP =
  [|[|[]; [(0, 1); (10, 20)]; []; []|]; [|[]; [(0, 10)]; [(25, 50)]; []|];
    [|[]; []; [(0, 20); (40, 40)]; []|]; [|[]; []; []; []|]|]

On peut vérifier qu'il n'est pas distributif, en prenant l'exemple du texte (fin page 8) :

In [30]:

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 *)

Out[30]:

val s_13 : intervalles = [(0, 30); (40, 50)]

Out[30]:

- : intervalles = [(25, 30); (40, 50)]

Out[30]:

- : intervalles = [(25, 31); (35, 50); (40, 51); (50, 70)]

Out[30]:

- : intervalles = [(25, 51); (35, 70)]

Out[30]:

- : intervalles = [(0, 31); (10, 50); (40, 51); (50, 70)]

Out[30]:

- : intervalles = [(25, 50); (50, 70)]

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 :

In [31]:

let est_carree matrice =
    let n = Array.length matrice in
    Array.fold_left (fun b x -> b && (n = (Array.length x))) true matrice
;;

Out[31]:

val est_carree : 'a array array -> bool = <fun>

In [32]:

est_carree stp_4;;

Out[32]:

- : bool = true

L'algorithme PC¶

Ça semble être un bon choix. Maintenant, passons à l'algorithme PC.

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.

In [33]:

exception Fini;; (* Pour faire le [exit]. *)

Out[33]:

exception Fini

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}).$$

In [34]:

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)
;;

Out[34]:

val relaxe : reseauSTP -> int -> int -> int -> intervalles = <fun>

On a tout ce qu'il faut pour écrire l'algorithme.

In [35]:

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
;;

Out[35]:

val algorithmePC : reseauSTP -> reseauSTP * intervalles list = <fun>

Exemple de réseau non distributif¶

On va traiter l'exemple de la Figure 4 du texte, comme défini plus haut :

images/reseau_distributif.png

In [36]:

stp_4;;

Out[36]:

- : reseauSTP =
[|[|[]; [(0, 1); (10, 20)]; []; []|]; [|[]; [(0, 10)]; [(25, 50)]; []|];
  [|[]; []; [(0, 20); (40, 40)]; []|]; [|[]; []; []; []|]|]

In [37]:

algorithmePC stp_4;;

Out[37]:

- : reseauSTP * intervalles list =
([|[|[]; [(0, 1); (10, 20)]; []; []|]; [|[]; [(0, 10)]; [(25, 50)]; []|];
   [|[]; []; [(0, 20); (40, 40)]; []|]; [|[]; []; []; []|]|],
 [[]])

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 exemples¶

On 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 .

In [38]:

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; []; []; []; [] |];
|];;

Out[38]:

val t_01 : intervalles = [(10, 20)]

Out[38]:

val t_12 : intervalles = [(30, 40)]

Out[38]:

val t_32 : intervalles = [(10, 20)]

Out[38]:

val t_34 : intervalles = [(20, 30); (40, 50)]

Out[38]:

val t_40 : intervalles = [(60, 70)]

Out[38]:

val stp_1 : reseauSTP =
  [|[|[]; [(10, 20)]; []; []; []|]; [|[]; []; [(30, 40)]; []; []|];
    [|[]; []; []; []; []|]; [|[]; []; [(10, 20)]; []; [(20, 30); (40, 50)]|];
    [|[(60, 70)]; []; []; []; []|]|]

In [39]:

algorithmePC stp_1;;

Out[39]:

- : reseauSTP * intervalles list =
([|[|[]; [(10, 20)]; []; []; []|]; [|[]; []; [(30, 40)]; []; []|];
   [|[]; []; []; []; []|]; [|[]; []; [(10, 20)]; []; [(20, 30); (40, 50)]|];
   [|[(60, 70)]; []; []; []; []|]|],
 [[]])

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...

Conclusion¶

Voilà pour la question obligatoire de programmation :

on a décomposé le problème en sous-fonctions,
on a essayé d'être fainéant, en réutilisant les sous-fonctions,
on a fait des exemples et on les garde dans ce qu'on présente au jury,
on a testé la fonction exigée sur de petits exemples et sur un exemple de taille réelle (venant du texte)

Et on a essayé de faire un peu plus, en implémentant la vérification d'une contrainte de plus.

Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.