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

Sys.command "ocaml -version";;

The OCaml toplevel, version 4.04.2

- : int = 0

Question de programmation¶

La question de programmation pour ce texte était donnée au tout début, à la page 2 :

Exercice¶

Dans le langage de votre choix, implémenter un programme qui étant donnés un graphe et une proposition d’éclairage des lampadaires teste si celle-ci est correcte, i.e., si toutes les rues sont bien éclairées.

Le tester sur différents exemples bien choisis (on pourra justifier la/les structures de données utilisée).

Besoin de plusieurs exemples¶

Pour une fois, on voit bien que le jury exige de tester la fonction sur plusieurs exemples.

Solution¶

Représentation du graphe et de la proposition d'éclairage¶

Les graphes ici seront constitués de places (= sommets), reliés entre elles par des rues (= arêtes).

Pour vérifier un éclairage, donné sous forme d'une liste de places, on va devoir vérifier que chaque rue est connectée à une place éclairée.

Une approche très simple, en trois étapes :

compter le nombre de rues,
pour chaque place éclairée, compter le nombre de rues qui en partent (et qui sont donc éclairées),
s'il y a (au moins) une rue non éclairée, renvoyer false, sinon renvoyer true.

Pour être efficace, il faut pouvoir accéder efficacement aux rues qui partent de chaque place (et il suffit de les compter, si on sait qu'elles sont uniques dans la représentation).

$\implies$ À partir de ce constat, on opte pour une représentation du graphe par liste d'adjacence.

Comme les graphes sont non orientés, chaque arête est présente deux fois dans la représentation du graphe : l'arête $u \leftrightarrow v$ est présente comme $v \in V[u]$ (les places voisines de $u$), et $u \in V[v]$ (les places voisines de $v$).
Le fait que les graphes soient planaires n'apportent rien à la représentation.
Par simplicité, on va représenter les places par leur numéros (on pourra aussi prendre des chaînes de caractères, comme "Place de l'étoile", "Nation", "Champd de Mars" etc, mais c'est plus long à écrire).

type place = int;;
type rues = place list;;

type place = int

type rues = place list

type ville = rues list;;

type ville = rues list

On donne tout de suite un exemple de graphe, en prenant le 3ème exemple de la Figure 1 du texte.

Graphes de la Figure 1 du texte

let graphe1 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 4];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [5; 7];        (* place 8 *)
];;

val graphe1 : ville =
  [[2]; [2; 3; 6]; [0; 1]; [1; 4]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
   [5; 7]]

On a besoin que les indices commence à $0$ et jusqu'à $n-1$ (où $n$ est le nombre de places), puisque la liste des rues utilisent implicitement la numérotation des places.

type eclairage = place list;;

type eclairage = place list

Trois exemples d'éclairages, deux satisfaisant donc l'un trivialement, et l'autre non satisfaisant :

let eclairage1_sat : eclairage = [
    0; 1; 2; 3; 4; 5; 6; 7; 8
];;

let eclairage2_sat : eclairage = [
    1; 2; 3; 5; 6; 8
];;

val eclairage1_sat : eclairage = [0; 1; 2; 3; 4; 5; 6; 7; 8]

val eclairage2_sat : eclairage = [1; 2; 3; 5; 6; 8]

let eclairage1_nonsat : eclairage = [
    2; 4; 8
];;

let eclairage2_nonsat : eclairage = [
    1; 2; 3; 5; 6
];;

val eclairage1_nonsat : eclairage = [2; 4; 8]

val eclairage2_nonsat : eclairage = [1; 2; 3; 5; 6]

Vérification¶

On pourrait écrire une première fonction pour vérifier que le graphe est bien valide, selon la représentation décrite ci-dessus, en vérifiant :

que les places forment bien l'ensemble $\{0,\dots,n-1\}$,
que chaque rue n'est présente qu'une fois dans les listes d'adjacences $V[u]$,
qu'aucune place inconnue n'est dans une liste $V[u]$,
et que le graphe est bien symétrique non-orienté, i.e., que $u \in V[u] \Leftrightarrow v \in V[u]$.

... Mais le sujet n'exige rien de tout ça, donc on passe directement à la question demandée.

Quelques fonctions utiles :

let somme =
    List.fold_left (+) 0
;;

val somme : int list -> int = <fun>

On met en place, facilement, l'algorithme décrit plus haut. Une approche très simple, en trois étapes :

compter le nombre de rues,
pour chaque place éclairée, compter le nombre de rues qui en partent (et qui sont donc éclairées),
s'il y a (au moins) une rue non éclairée, renvoyer false, sinon renvoyer true.

Il y a une finesse : en comptant une fois les rues dont les deux côtés sont éclairés, et deux fois les rues dont un seul côté est éclairé, on peut comparer au nombre de rues comptées doubles.

C'est légérement sous-optimal, comme on va devoir vérifier (en temps linéaire en taille la de l'éclairage) si chaque rue a un ou deux côté éclairés. Mais on gagne en mémoire puisqu'on n'a pas à construire une représentation de toutes les rues.

let compte_simple_ou_double_0 (ici : place) (voisines : rues) (proposition : eclairage) =
    somme
    (List.map (fun voisine -> 
        if List.mem voisine proposition
        then 1
        else 2
    ) voisines)
;;

File "[9]", line 1, characters 31-34:
Warning 27: unused variable ici.

val compte_simple_ou_double_0 : place -> rues -> eclairage -> int = <fun>

let verifie_eclairage_0 (graphe : ville) (proposition : eclairage) : bool =
    (* 1. compter le nombre de rues *)
    let nombre_rues =
        List.fold_left (fun a b -> a + (List.length b)) 0 (graphe)
        (* (List.length (List.flatten graphe)) *)
    in
    (* 2. pour chaque place *éclairée*, compter le nombre de rues qui en partent *)
    let nombre_rues_eclairees =
        somme
        (List.map (fun place_eclairee ->
            compte_simple_ou_double_0
            place_eclairee
            (List.nth graphe place_eclairee)
            proposition
        ) proposition)
    in
    (* 3. s'il y a (au moins) une rue non éclairée, renvoyer [false], sinon renvoyer [true] *)
    nombre_rues <= nombre_rues_eclairees
;;

val verifie_eclairage_0 : ville -> eclairage -> bool = <fun>

Notez qu'on peut même faire mieux, puisque cet appel à List.mem voisine proposition est inefficace (au pire il est en $\mathcal{O}(n)$, et on le fait au pire $n-1$ fois).

En effet, on peut précalculer, dans la fonction verifie_eclairage un tableau, de taille $n$ fixée (et connue à l'avance), qui contient en indice $i$ le résultat de List.mem i proposition : sauf qu'au lieu d'appeler plusieurs fois la fonction List.mem, on a qu'à parcourir la liste proposition une fois, et remplir les cases du tableau.

let compte_simple_ou_double (_ : place) (voisines : rues) (est_eclairee : bool array) =
    somme
    (List.map (fun voisine -> 
        if est_eclairee.(voisine)
        then 1
        else 2
    ) voisines)
;;

val compte_simple_ou_double : place -> rues -> bool array -> int = <fun>

Cette fonction précalcule, une seule fois, ce tableau.

let precalcule_places_eclairees (n : int) (proposition : eclairage) : bool array =
    let resultat = Array.make n false in
    List.iter (fun i -> 
        resultat.(i) <- true
    ) proposition;
    resultat
;;

val precalcule_places_eclairees : int -> eclairage -> bool array = <fun>

Et enfin, on s'en sert pour la fonction verifie_eclairage plus rapide.

let verifie_eclairage (graphe : ville) (proposition : eclairage) : bool =
    (* 0. précalcul *)
    let n = List.length graphe in
    let est_eclairee = precalcule_places_eclairees n proposition in
    (* 1. compter le nombre de rues *)
    let nombre_rues =
        List.fold_left (fun a b -> a + (List.length b)) 0 (graphe)
        (* (List.length (List.flatten graphe)) *)
    in
    (* 2. pour chaque place *éclairée*, compter le nombre de rues qui en partent *)
    let nombre_rues_eclairees =
        somme
        (List.map (fun place_eclairee ->
            compte_simple_ou_double
            place_eclairee
            (List.nth graphe place_eclairee)
            est_eclairee
        ) proposition)
    in
    (* 3. s'il y a (au moins) une rue non éclairée, renvoyer [false], sinon renvoyer [true] *)
    nombre_rues <= nombre_rues_eclairees
;;

val verifie_eclairage : ville -> eclairage -> bool = <fun>

Exemples¶

Avec le graphe définit plus haut, et les deux propositions d'éclairages :

graphe1;;

- : ville =
[[2]; [2; 3; 6]; [0; 1]; [1; 4]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
 [5; 7]]

Pour des éclairages valides.¶

Le premier est trivialement valide, on éclaire toutes les places donc toutes les rues sont bien éclairées.

eclairage1_sat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage1_sat;;

verifie_eclairage graphe1 eclairage1_sat;;    (* true *)

- : eclairage = [0; 1; 2; 3; 4; 5; 6; 7; 8]

- : rues list =
[[2]; [2; 3; 6]; [0; 1]; [1; 4]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
 [5; 7]]

- : bool = true

Le second est moins trivial, mais en vérifiant à la main sur le graphe on voit qu'il fonctionne.
- On a juste éteint la place $0$, mais l'arête $0-1$ reste éclairée par la place $1$,
- la place $4$ mais les arêtes $3-4$ et $4-5$ sont éclairées par les places $3$ et $5$,
- et la place $7$ mais les arêtes $6-7$ et $7-8$ sont éclairées par les places $6$ et $8$.

eclairage2_sat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage2_sat;;

verifie_eclairage graphe1 eclairage2_sat;;    (* true *)

- : eclairage = [1; 2; 3; 5; 6; 8]

- : rues list = [[2; 3; 6]; [0; 1]; [1; 4]; [1; 4; 6; 8]; [1; 5; 7]; [5; 7]]

- : bool = true

On peut essayer un éclairage de seulement 5 villes. Est-ce optimal ? (on répondra plus tard, mais oui)

let eclairage3_sat : eclairage = [
    2; 3; 5; 6; 7;
];;

List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage3_sat;;

verifie_eclairage graphe1 eclairage3_sat;;    (* true *)

val eclairage3_sat : eclairage = [2; 3; 5; 6; 7]

- : rues list = [[0; 1]; [1; 4]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8]]

- : bool = true

Pour des éclairages non valides :¶

Clairement, le premier est trop gourmand et on a éteint trop de place.

eclairage1_nonsat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage1_nonsat;;

verifie_eclairage graphe1 eclairage1_nonsat;;   (* false *)

- : eclairage = [2; 4; 8]

- : rues list = [[0; 1]; [3; 5]; [5; 7]]

- : bool = false

Le second semble bon, mais la rue $8-9$ par exemple est éteinte.

eclairage2_nonsat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage2_nonsat;;

verifie_eclairage graphe1 eclairage2_nonsat;;   (* false *)

- : eclairage = [1; 2; 3; 5; 6]

- : rues list = [[2; 3; 6]; [0; 1]; [1; 4]; [1; 4; 6; 8]; [1; 5; 7]]

- : bool = false

Bonus : vérifier que le graphe est valide¶

Bon... par acquis de conscience, on implémente l'étape de vérification évoquée plus haut.

D'abord, quelques fonctions utiles :

let max_liste (liste : int list) : int =
    List.fold_left max (-max_int) liste
;;

val max_liste : int list -> int = <fun>

max_liste [123; 12; 1];;

- : int = 123

let max_liste_liste (listeliste : int list list) : int =
    max_liste (List.map max_liste listeliste) 
;;

val max_liste_liste : int list list -> int = <fun>

max_liste_liste [[123; 12; 1]; [1234; 13]];;

- : int = 1234

List.for_all (fun x -> (0 <= x) && (x <= 1234)) (List.flatten [[123; 12; 1]; [1234; 13]])

- : bool = true

let compte_occurences (liste : int list) (x : int) =
    let rec aux xs x acc =
        match xs with
        | [] -> acc
        | y :: ys when y = x -> aux ys x (acc + 1)
        | _ :: ys -> aux ys x acc
    in
    aux liste x 0
;;

val compte_occurences : int list -> int -> int = <fun>

compte_occurences [1; 2; 3; 4; 5] 1;;
compte_occurences [1; 2; 3; 4; 5] 10;;
compte_occurences [1; 2; 3; 4; 5; 1; 6; 7] 1;;

- : int = 1

- : int = 0

- : int = 2

Puis, la vérification annoncée :

let graphe_valide (graphe : ville) : bool =
    let n = max_liste_liste graphe in
    (* D'abord, on vérifie qu'il y a exactement n + 1 listes de places voisines *)
    let test1 =
        (List.length graphe) = (n + 1)
    in
    (* Ensuite, on vérifie que toutes les places voisines sont bien dans des places valides *)
    let test2 =
        List.for_all (
            fun x -> (0 <= x) && (x <= n)
        ) (List.flatten graphe)
    in
    (* Enfin, on vérifie qu'une place voisine v n'est présente qu'une fois dans V[u] *)
    let test3 =
        List.for_all (
            fun voisines -> List.for_all (
                fun place ->
                    (compte_occurences voisines place) = 1
            ) voisines
        ) graphe
    in
    (* test1, test2, test3 *)
    test1 && test2 && test3
;;

val graphe_valide : ville -> bool = <fun>

graphe1;;

- : ville =
[[2]; [2; 3; 6]; [0; 1]; [1; 4]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
 [5; 7]]

graphe_valide graphe1;;

- : bool = true

On doit aussi tester trois cas de graphes qui contredisent un de chaque test :

S'il manque une place dans la liste d'adjacence :

let graphe2 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
                   (* place 8 absente ! *)
];;

val graphe2 : ville =
  [[2]; [2; 3; 6]; [0; 1]; [1; 3]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8]]

graphe_valide graphe2;;

- : bool = false

Si la liste d'adjacence est trop grande :

let graphe3 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [5; 7];        (* place 8 absente ! *)
    [5; 7]         (* place 9 ?! *)
];;

val graphe3 : ville =
  [[2]; [2; 3; 6]; [0; 1]; [1; 3]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
   [5; 7]; [5; 7]]

graphe_valide graphe3;;

- : bool = false

Si une des places voisines n'est pas valide :

let graphe4 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [50]           (* place 8 -> 50 ?! *)
];;

val graphe4 : ville =
  [[2]; [2; 3; 6]; [0; 1]; [1; 3]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
   [50]]

graphe_valide graphe4;;

- : bool = false

Et enfin, si une des listes d'adjacence contient deux fois la même place voisine :

let graphe5 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [5; 7; 5]      (* place 8 -> 5 deux fois ! *)
];;

val graphe5 : ville =
  [[2]; [2; 3; 6]; [0; 1]; [1; 3]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
   [5; 7; 5]]

graphe_valide graphe5;;

- : bool = false

Bonus : énumération de tous les éclairages possibles¶

Pour de tous petits graphes, on peut suivre l'approche naïve qui consiste à énumérer toutes les possibilités, et renvoyer celle de nombre de lampadaires minimal.

On pourra ensuite vérifier avec la fonction précédente que l'éclairage donné est bien valide.

Énumération des éclairages possibles¶

Un éclairage est un sous-ensemble, potentiellement vide, de $\{0,\dots,n-1\}$. Il y en a $2^n$ en tout.

Comment les générer efficacement ? En fait, on s'en fiche, le reste du code sera déjà exponentiel en $n$...

La fonction suivante prend une liste de liste, acc, et la dédouble en ajoutant x aux listes qui ne le contiennent pas encore, et en gardant une copie des listes d'avant. En travaillant avec des listes toutes distinctes, la liste acc est toujours dédoublée.

let ajoute_ou_pas (x : 'a) (acc : 'a list list) =
    (List.map (fun liste ->
        if (List.mem x liste)
        then liste
        else x :: liste
    ) acc
    )
    @
    (List.filter (fun liste ->
        not (List.mem x liste)
    ) acc
    )
;;

val ajoute_ou_pas : 'a -> 'a list list -> 'a list list = <fun>

ajoute_ou_pas 1 [[]];;
ajoute_ou_pas 2 [[1]; []];;

- : int list list = [[1]; []]

- : int list list = [[2; 1]; [2]; [1]; []]

Maintenant, il suffit d'itérer cette fonction, depuis la liste [[]] contenant juste la liste vide.

let tous_sous_ensembles (liste : 'a list) : 'a list list =
    let rec aux xs acc =
        match xs with
        | [] -> acc
        | y :: ys ->
            aux ys (ajoute_ou_pas y acc)
    in
    aux liste [ [] ]
;;

val tous_sous_ensembles : 'a list -> 'a list list = <fun>

tous_sous_ensembles [];;
tous_sous_ensembles [1];;
tous_sous_ensembles [1; 2];;
tous_sous_ensembles [1; 2; 3];; (* taille 2^3 = 8 *)

- : 'a list list = [[]]

- : int list list = [[1]; []]

- : int list list = [[2; 1]; [2]; [1]; []]

- : int list list = [[3; 2; 1]; [3; 2]; [3; 1]; [3]; [2; 1]; [2]; [1]; []]

tous_sous_ensembles [0; 1; 2; 3];; (* taille 2^4 = 16 *)
tous_sous_ensembles [0; 1; 2; 3; 4];; (* taille 2^5 = 32 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5];; (* taille 2^6 = 64 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6];; (* taille 2^7 = 128 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6; 7];; (* taille 2^8 = 256 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6; 7; 8];; (* taille 2^9 = 512 *)

assert ((List.length (tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6; 7; 8])) = 512);;

- : int list list =
[[3; 2; 1; 0]; [3; 2; 1]; [3; 2; 0]; [3; 2]; [3; 1; 0]; [3; 1]; [3; 0]; 
 [3]; [2; 1; 0]; [2; 1]; [2; 0]; [2]; [1; 0]; [1]; [0]; []]

- : int list list =
[[4; 3; 2; 1; 0]; [4; 3; 2; 1]; [4; 3; 2; 0]; [4; 3; 2]; [4; 3; 1; 0];
 [4; 3; 1]; [4; 3; 0]; [4; 3]; [4; 2; 1; 0]; [4; 2; 1]; [4; 2; 0]; [4; 2];
 [4; 1; 0]; [4; 1]; [4; 0]; [4]; [3; 2; 1; 0]; [3; 2; 1]; [3; 2; 0]; 
 [3; 2]; [3; 1; 0]; [3; 1]; [3; 0]; [3]; [2; 1; 0]; [2; 1]; [2; 0]; [2];
 [1; 0]; [1]; [0]; []]

- : int list list =
[[5; 4; 3; 2; 1; 0]; [5; 4; 3; 2; 1]; [5; 4; 3; 2; 0]; [5; 4; 3; 2];
 [5; 4; 3; 1; 0]; [5; 4; 3; 1]; [5; 4; 3; 0]; [5; 4; 3]; [5; 4; 2; 1; 0];
 [5; 4; 2; 1]; [5; 4; 2; 0]; [5; 4; 2]; [5; 4; 1; 0]; [5; 4; 1]; [5; 4; 0];
 [5; 4]; [5; 3; 2; 1; 0]; [5; 3; 2; 1]; [5; 3; 2; 0]; [5; 3; 2];
 [5; 3; 1; 0]; [5; 3; 1]; [5; 3; 0]; [5; 3]; [5; 2; 1; 0]; [5; 2; 1];
 [5; 2; 0]; [5; 2]; [5; 1; 0]; [5; 1]; [5; 0]; [5]; [4; 3; 2; 1; 0];
 [4; 3; 2; 1]; [4; 3; 2; 0]; [4; 3; 2]; [4; 3; 1; 0]; [4; 3; 1]; [4; 3; 0];
 [4; 3]; [4; 2; 1; 0]; [4; 2; 1]; [4; 2; 0]; [4; 2]; [4; 1; 0]; [4; 1];
 [4; 0]; [4]; [3; 2; 1; 0]; [3; 2; 1]; [3; 2; 0]; [3; 2]; [3; 1; 0]; 
 [3; 1]; [3; 0]; [3]; [2; 1; 0]; [2; 1]; [2; 0]; [2]; [1; 0]; [1]; [0]; 
 []]

- : int list list =
[[6; 5; 4; 3; 2; 1; 0]; [6; 5; 4; 3; 2; 1]; [6; 5; 4; 3; 2; 0];
 [6; 5; 4; 3; 2]; [6; 5; 4; 3; 1; 0]; [6; 5; 4; 3; 1]; [6; 5; 4; 3; 0];
 [6; 5; 4; 3]; [6; 5; 4; 2; 1; 0]; [6; 5; 4; 2; 1]; [6; 5; 4; 2; 0];
 [6; 5; 4; 2]; [6; 5; 4; 1; 0]; [6; 5; 4; 1]; [6; 5; 4; 0]; [6; 5; 4];
 [6; 5; 3; 2; 1; 0]; [6; 5; 3; 2; 1]; [6; 5; 3; 2; 0]; [6; 5; 3; 2];
 [6; 5; 3; 1; 0]; [6; 5; 3; 1]; [6; 5; 3; 0]; [6; 5; 3]; [6; 5; 2; 1; 0];
 [6; 5; 2; 1]; [6; 5; 2; 0]; [6; 5; 2]; [6; 5; 1; 0]; [6; 5; 1]; [6; 5; 0];
 [6; 5]; [6; 4; 3; 2; 1; 0]; [6; 4; 3; 2; 1]; [6; 4; 3; 2; 0]; [6; 4; 3; 2];
 [6; 4; 3; 1; 0]; [6; 4; 3; 1]; [6; 4; 3; 0]; [6; 4; 3]; [6; 4; 2; 1; 0];
 [6; 4; 2; 1]; [6; 4; 2; 0]; [6; 4; 2]; [6; 4; 1; 0]; [6; 4; 1]; [6; 4; 0];
 [6; 4]; [6; 3; 2; 1; 0]; [6; 3; 2; 1]; [6; 3; 2; 0]; [6; 3; 2];
 [6; 3; 1; 0]; [6; 3; 1]; [6; 3; 0]; [6; 3]; [6; 2; 1; 0]; [6; ...]; ...]

- : int list list =
[[7; 6; 5; 4; 3; 2; 1; 0]; [7; 6; 5; 4; 3; 2; 1]; [7; 6; 5; 4; 3; 2; 0];
 [7; 6; 5; 4; 3; 2]; [7; 6; 5; 4; 3; 1; 0]; [7; 6; 5; 4; 3; 1];
 [7; 6; 5; 4; 3; 0]; [7; 6; 5; 4; 3]; [7; 6; 5; 4; 2; 1; 0];
 [7; 6; 5; 4; 2; 1]; [7; 6; 5; 4; 2; 0]; [7; 6; 5; 4; 2]; [7; 6; 5; 4; 1; 0];
 [7; 6; 5; 4; 1]; [7; 6; 5; 4; 0]; [7; 6; 5; 4]; [7; 6; 5; 3; 2; 1; 0];
 [7; 6; 5; 3; 2; 1]; [7; 6; 5; 3; 2; 0]; [7; 6; 5; 3; 2]; [7; 6; 5; 3; 1; 0];
 [7; 6; 5; 3; 1]; [7; 6; 5; 3; 0]; [7; 6; 5; 3]; [7; 6; 5; 2; 1; 0];
 [7; 6; 5; 2; 1]; [7; 6; 5; 2; 0]; [7; 6; 5; 2]; [7; 6; 5; 1; 0];
 [7; 6; 5; 1]; [7; 6; 5; 0]; [7; 6; 5]; [7; 6; 4; 3; 2; 1; 0];
 [7; 6; 4; 3; 2; 1]; [7; 6; 4; 3; 2; 0]; [7; 6; 4; 3; 2]; [7; 6; 4; 3; 1; 0];
 [7; 6; 4; 3; 1]; [7; 6; 4; 3; 0]; [7; 6; 4; 3]; [7; 6; 4; 2; 1; 0];
 [7; 6; 4; 2; 1]; [7; 6; 4; 2; 0]; [7; 6; 4; 2]; [7; 6; 4; 1; 0];
 [7; 6; 4; 1]; [7; 6; 4; ...]; ...]

- : int list list =
[[8; 7; 6; 5; 4; 3; 2; 1; 0]; [8; 7; 6; 5; 4; 3; 2; 1];
 [8; 7; 6; 5; 4; 3; 2; 0]; [8; 7; 6; 5; 4; 3; 2]; [8; 7; 6; 5; 4; 3; 1; 0];
 [8; 7; 6; 5; 4; 3; 1]; [8; 7; 6; 5; 4; 3; 0]; [8; 7; 6; 5; 4; 3];
 [8; 7; 6; 5; 4; 2; 1; 0]; [8; 7; 6; 5; 4; 2; 1]; [8; 7; 6; 5; 4; 2; 0];
 [8; 7; 6; 5; 4; 2]; [8; 7; 6; 5; 4; 1; 0]; [8; 7; 6; 5; 4; 1];
 [8; 7; 6; 5; 4; 0]; [8; 7; 6; 5; 4]; [8; 7; 6; 5; 3; 2; 1; 0];
 [8; 7; 6; 5; 3; 2; 1]; [8; 7; 6; 5; 3; 2; 0]; [8; 7; 6; 5; 3; 2];
 [8; 7; 6; 5; 3; 1; 0]; [8; 7; 6; 5; 3; 1]; [8; 7; 6; 5; 3; 0];
 [8; 7; 6; 5; 3]; [8; 7; 6; 5; 2; 1; 0]; [8; 7; 6; 5; 2; 1];
 [8; 7; 6; 5; 2; 0]; [8; 7; 6; 5; 2]; [8; 7; 6; 5; 1; 0]; [8; 7; 6; 5; 1];
 [8; 7; 6; 5; 0]; [8; 7; 6; 5]; [8; 7; 6; 4; 3; 2; 1; 0];
 [8; 7; 6; 4; 3; 2; 1]; [8; 7; 6; 4; 3; 2; 0]; [8; 7; 6; 4; 3; 2];
 [8; 7; 6; 4; 3; 1; 0]; [8; 7; 6; 4; 3; 1]; [8; 7; 6; 4; 3; 0];
 [8; 7; 6; 4; ...]; ...]

- : unit = ()

C'est tellement plus simple en Python...

Une autre fonction utile :

let range (n : int) : (int list) =
    let rec range_x (n : int) : (int list) =
    match n with
    | n when n < 0 -> []
    | 0 -> [0]
    | n -> n :: (range_x (n - 1))
    in
    List.rev (range_x n)
;;

val range : int -> int list = <fun>

range 0;;
range 1;;
range 5;;
range 10;;

- : int list = [0]

- : int list = [0; 1]

- : int list = [0; 1; 2; 3; 4; 5]

- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

let tous_les_eclairages_possibles (graphe : ville) : (eclairage list) =
    assert (graphe_valide graphe);
    let n = (List.length graphe) - 1 in
    let sommets = range n in
    tous_sous_ensembles sommets    
;;

val tous_les_eclairages_possibles : ville -> eclairage list = <fun>

tous_les_eclairages_possibles graphe1;;

- : eclairage list =
[[8; 7; 6; 5; 4; 3; 2; 1; 0]; [8; 7; 6; 5; 4; 3; 2; 1];
 [8; 7; 6; 5; 4; 3; 2; 0]; [8; 7; 6; 5; 4; 3; 2]; [8; 7; 6; 5; 4; 3; 1; 0];
 [8; 7; 6; 5; 4; 3; 1]; [8; 7; 6; 5; 4; 3; 0]; [8; 7; 6; 5; 4; 3];
 [8; 7; 6; 5; 4; 2; 1; 0]; [8; 7; 6; 5; 4; 2; 1]; [8; 7; 6; 5; 4; 2; 0];
 [8; 7; 6; 5; 4; 2]; [8; 7; 6; 5; 4; 1; 0]; [8; 7; 6; 5; 4; 1];
 [8; 7; 6; 5; 4; 0]; [8; 7; 6; 5; 4]; [8; 7; 6; 5; 3; 2; 1; 0];
 [8; 7; 6; 5; 3; 2; 1]; [8; 7; 6; 5; 3; 2; 0]; [8; 7; 6; 5; 3; 2];
 [8; 7; 6; 5; 3; 1; 0]; [8; 7; 6; 5; 3; 1]; [8; 7; 6; 5; 3; 0];
 [8; 7; 6; 5; 3]; [8; 7; 6; 5; 2; 1; 0]; [8; 7; 6; 5; 2; 1];
 [8; 7; 6; 5; 2; 0]; [8; 7; 6; 5; 2]; [8; 7; 6; 5; 1; 0]; [8; 7; 6; 5; 1];
 [8; 7; 6; 5; 0]; [8; 7; 6; 5]; [8; 7; 6; 4; 3; 2; 1; 0];
 [8; 7; 6; 4; 3; 2; 1]; [8; 7; 6; 4; 3; 2; ...]; ...]

Liste de taille minimale parmi une liste de listes¶

let min_liste (liste : int list) : int =
    List.fold_left min (max_int) liste
;;

val min_liste : int list -> int = <fun>

min_liste [123; 12; 1];;

- : int = 1

let taille_min (listes : int list list) : int =
    min_liste (List.map List.length listes)
;;

val taille_min : int list list -> int = <fun>

Trouver un éclairage optimal¶

Ca va être assez naïf :

on calcule tous les éclairages possibles,
on filtre les éclairages pour ne garder que ceux qui sont valides,
on calcule la longueur minimale,
tant qu'on y est, on filtre pour ne garder que ceux qui sont de longueur minimale (plutôt que d'en renvoyer un seul).

let eclairages_optimaux (graphe : ville) : (eclairage list) =
    let propositions =
        tous_les_eclairages_possibles graphe
    in
    let propositions_valides =
        List.filter (verifie_eclairage graphe) propositions
    in
    let taille_minimale = 
        taille_min propositions_valides
    in
    let propositions_minimales =
        List.filter (fun li ->
            (List.length li) = taille_minimale
        ) propositions_valides
    in
    propositions_minimales
;;

val eclairages_optimaux : ville -> eclairage list = <fun>

Exemples¶

On commence avec un tout petit graphe, pour vérifier rapidement avant de passer sur un plus gros graphe :

let graphe2 : ville = [
    [1; 2];  (* place 0 -> 1 2 *)
    [0; 2];  (* place 1 -> 0 2 *)
    [0; 1]   (* place 2 -> 0 1 *)
] ;;

val graphe2 : ville = [[1; 2]; [0; 2]; [0; 1]]

tous_les_eclairages_possibles graphe2;;

List.length (tous_les_eclairages_possibles graphe2);;

- : eclairage list = [[2; 1; 0]; [2; 1]; [2; 0]; [2]; [1; 0]; [1]; [0]; []]

- : int = 8

Il y a $8$ éclairages possibles ($2^3$) et les $3$ de taille $2$ sont optimaux : en effet sur un graphe complet à $n$ sommets, il faut et il suffit d'éclairer n'importe quel ensenble de $n-1$ places pour éclairer toutes les $n(n-1)$ arêtes.

eclairages_optimaux graphe2;;

- : eclairage list = [[2; 1]; [2; 0]; [1; 0]]

Et sur le graphe avec lequel on travaille depuis le début :

graphe1;;

- : ville =
[[2]; [2; 3; 6]; [0; 1]; [1; 4]; [3; 5]; [1; 4; 6; 8]; [1; 5; 7]; [6; 8];
 [5; 7]]

tous_les_eclairages_possibles graphe1;;

List.length (tous_les_eclairages_possibles graphe1);;

- : eclairage list =
[[8; 7; 6; 5; 4; 3; 2; 1; 0]; [8; 7; 6; 5; 4; 3; 2; 1];
 [8; 7; 6; 5; 4; 3; 2; 0]; [8; 7; 6; 5; 4; 3; 2]; [8; 7; 6; 5; 4; 3; 1; 0];
 [8; 7; 6; 5; 4; 3; 1]; [8; 7; 6; 5; 4; 3; 0]; [8; 7; 6; 5; 4; 3];
 [8; 7; 6; 5; 4; 2; 1; 0]; [8; 7; 6; 5; 4; 2; 1]; [8; 7; 6; 5; 4; 2; 0];
 [8; 7; 6; 5; 4; 2]; [8; 7; 6; 5; 4; 1; 0]; [8; 7; 6; 5; 4; 1];
 [8; 7; 6; 5; 4; 0]; [8; 7; 6; 5; 4]; [8; 7; 6; 5; 3; 2; 1; 0];
 [8; 7; 6; 5; 3; 2; 1]; [8; 7; 6; 5; 3; 2; 0]; [8; 7; 6; 5; 3; 2];
 [8; 7; 6; 5; 3; 1; 0]; [8; 7; 6; 5; 3; 1]; [8; 7; 6; 5; 3; 0];
 [8; 7; 6; 5; 3]; [8; 7; 6; 5; 2; 1; 0]; [8; 7; 6; 5; 2; 1];
 [8; 7; 6; 5; 2; 0]; [8; 7; 6; 5; 2]; [8; 7; 6; 5; 1; 0]; [8; 7; 6; 5; 1];
 [8; 7; 6; 5; 0]; [8; 7; 6; 5]; [8; 7; 6; 4; 3; 2; 1; 0];
 [8; 7; 6; 4; 3; 2; 1]; [8; 7; 6; 4; 3; 2; ...]; ...]

- : int = 512

eclairages_optimaux graphe1;;

- : eclairage list =
[[8; 6; 5; 3; 2]; [7; 6; 5; 3; 2]; [7; 5; 4; 2; 1]; [7; 5; 4; 1; 0];
 [7; 5; 3; 2; 1]; [7; 5; 3; 1; 0]]

On vérifie ici que l'éclairage à $5$ places qu'on avait proposé plus haut est bien optimal.

Complexités en temps et espace (bonus)¶

Il est toujours utile de préciser, rapidement à l'oral et/ou dans le code (un commentaire suffit) les complexité (ou ordre de grandeur) des fonctions exigées par l'énoncé.

Les complexités ? Oui, il ne faut pas oublier l'espace (trop souvent négligé !).

Si vous n'êtes pas sûr ou ne savez pas comment le justifier, mieux vaut marquer :

« En $\mathcal{O}(n^2)$ en temps et en espace. »

que de marquer quelque chose de difficilement justifiable comme :

« Probablement en $\mathcal{O}(n)$ en temps et en espace. »

En temps¶

La première fonction de vérification proposée verifie_eclairage_0 est linéaire en temps, en $m$ le nombre de rues et $p$ le nombre de place éclairées, i.e., est en $\mathcal{O}(m p)$. C'est sous-optimal pour vérifier que toutes les rues sont bien éclairées, on devrait réussir à faire mieux en $\mathcal{O}(\max(n, m))$ !
La deuxième fonction de vérification proposée verifie_eclairage est elle bien linéaire en temps, seulement en $m$ le nombre de rues, i.e., est en $\mathcal{O}(\max(n, m))$ (s'il y a moins de rues que de places, il faut quand même créer le tableau est_eclairee en $\mathcal{O}(n)$). C'est optimal pour vérifier que toutes les rues sont bien éclairées ! Youpiiiiiii!!!!!!!!!!!
Les deux fonctions tous_les_eclairages_possibles et eclairages_optimaux sont en $\mathcal{O}(2^n)$ en temps, et c'est beaucoup !

En espace (ou en mémoire)¶

La première fonction de vérification proposée verifie_eclairage est aussi linéaire en espace en la taille du graphe.
La deuxième fonction de vérification proposée verifie_eclairage_0 est aussi linéaire en espace en la taille du graphe.
Les deux fonctions tous_les_eclairages_possibles et eclairages_optimaux sont aussi en $\mathcal{O}(2^n)$ en mémoire, et c'est beaucoup ! A noter par contre que le résultat renvoyé par eclairages_optimaux est, lui, de taille bien plus raisonnables, mais toujours possiblement exponentielle (si le nombre minimal de places éclairées est $k$, alors ${n \choose k}$).

Conclusion¶

Voilà pour la question obligatoire de programmation, et un gros bonus.

Qualités¶

On a décomposé le problème en 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 différents exemples.

Défauts¶

La première implémentation proposée de verifie_eclairage_0 n'est pas optimale,
La deuxième implémentation n'était pas immédiate,
et on a pas testé sur des exemples très ambitieux.

Ouverture ?¶

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