print_endline Sys.ocaml_version;;
Sys.command "ocaml -version";;
4.04.2
- : unit = ()
The OCaml toplevel, version 4.04.2
- : int = 0
let print = Printf.printf;;
val print : ('a, out_channel, unit) format -> 'a = <fun>
La question de programmation pour ce texte était donnée au milieu, en page 3 :
« On suppose donnés les tableaux $T_i$. Un état du système est représenté par un vecteur $U$ de longueur $n$, dont la $i$-ème composante contient la position du robot $R_i$ (sous forme du numéro $j$ du lieu $L_j$ où il se trouve). »
« Écrire une fonction/procédure/méthode transition qui transforme $U$ en un état suivant du système (on admettra que les données sont telles qu’il existe un état suivant).
Simuler le système de robots pendant $n$ unités de temps. On prendra comme état initial du robot $R_i$ le premier élément du tableau $T_i$ . »
Vous remarquez que même avec une question bien précise comme celle-là, on dispose d'une relative liberté : la question n'impose pas le choix de modélisation !
Elle pourrait être traitée avec un automate ou graphe produit non simplifié, ou un graphe produit plus réduit (1ère solution), mais on aurait tout aussi pu utiliser une approche probabiliste, avec des chaînes de Markov par exemple (2ème solution).
Merci à Romain Dubourg (2017) pour son code. Cette deuxième solution est bien plus concise que l'approche avec un graphe produit non simplifié, en utilisant une approche plus directe.
En utilisant des tableaux, int array
, au lieu de listes, pour représenter les états $u$ on peut modifier l'état en place !
type etat = int array;;
type liste_rdv = (int array) array;;
type etat = int array
type liste_rdv = int array array
Avec l'exemple du texte.
let ex1_1 : etat = [| 1; 1; 2 |];;
let ex1 : liste_rdv = [|
[| 1; 3 |];
[| 1; 2 |];
[| 2; 3 |]
|];;
val ex1_1 : etat = [|1; 1; 2|]
val ex1 : liste_rdv = [|[|1; 3|]; [|1; 2|]; [|2; 3|]|]
On peut facilement trouver la première position de x
dans une liste et dans un tableau et -1
sinon.
let trouve (x:int) (a:int list) : int =
let rec aux (x:int) (a:int list) (i : int) : int =
match a with
| [] -> -1
| t :: _ when (t = x) -> i
| _ :: q -> aux x q (i+1)
in
aux x a 0
;;
val trouve : int -> int list -> int = <fun>
let trouve_array (x : int) (a : int array) : int =
trouve x (Array.to_list a)
;;
val trouve_array : int -> int array -> int = <fun>
let _ = trouve_array 2 ex1_1;; (* 2 *)
- : int = 2
On a besoin de pouvoir obtenir la liste des paires de robots pouvant réaliser un rendez-vous.
let rdv (u : etat) : ((int * int) list) =
let n = Array.length u in
let ls = ref [] in (* plus simple que d'imbriquer les List.filter et List.map... *)
for k = 0 to n - 1 do
let i = trouve_array u.(k)
(Array.sub u (k + 1) (n - (k + 1)))
in
if i >= 0 then
ls := (k, i + k + 1) :: !ls;
done;
!ls
;;
val rdv : etat -> (int * int) list = <fun>
Un rapide, pour visualiser le fonctionnement de la fonction rdv
.
let _ = rdv ex1_1 ;;
- : (int * int) list = [(0, 1)]
let ex3_1 = [| 1; 2; 1; 4; 4 |];;
let _ = rdv ex3_1 ;;
val ex3_1 : int array = [|1; 2; 1; 4; 4|]
- : (int * int) list = [(3, 4); (0, 2)]
Étant donné un état et une paire de robots pouvant réaliser un rendez-vous, la fonction suivante le réalise, en modifiant en place l'état $u$.
C'est bien plus simple que de traiter avec une approche fonctionnelle.
Pour une fonction comme ça, il faut absolument :
1
, i
, I
et l
qui se ressemblent beaucoup une fois projetés au tableau !).let realise_rdv (u : etat) (lr : liste_rdv) (xy : int * int) : etat =
let x, y = xy in
let ux = u.(x) and uy = u.(y) in
let rx, ry = lr.(x), lr.(y) in
u.(x) <- rx.(((trouve_array ux rx) + 1) mod (Array.length rx));
u.(y) <- ry.(((trouve_array uy ry) + 1) mod (Array.length ry));
u
;;
val realise_rdv : etat -> liste_rdv -> int * int -> etat = <fun>
Un rapide, pour visualiser le fonctionnement de la fonction realise_rdv
.
let u = [| 0; 0; 1 |];;
let l = [| [|0; 2|]; [|1; 2|]; [|2; 0|] |];;
let _ = realise_rdv u l (0, 1) ;;
val u : int array = [|0; 0; 1|]
val l : int array array = [|[|0; 2|]; [|1; 2|]; [|2; 0|]|]
- : etat = [|2; 1; 1|]
On vérifie que l'état u
a bien été modifié en place :
u;;
- : int array = [|2; 1; 1|]
transition
¶Et enfin, on calcule l'état suivant $u_1$ à partir de l'état $u_0$, en appliquant la fonction realise_rdv
à chaque état qui peut être modifié.
let transition (u0 : etat) (l0 : liste_rdv) : etat =
List.iter (fun u -> ignore (realise_rdv u0 l0 u)) (rdv u0);
u0
;;
val transition : etat -> liste_rdv -> etat = <fun>
On effectue n
transitions successives, non pas avec une approche récursive (qui ne serait pas récursive terminale, et donc avec une mémoire de pile d'appel linéaire en $\mathcal{O}(n)$), mais avec une simple boucle for
.
let rec n_transitions_trop_couteux (u : etat) (l : liste_rdv) (n : int) : etat =
if (n = 0) then
u
else
n_transitions_trop_couteux (transition u l) l (n-1)
;;
val n_transitions_trop_couteux : etat -> liste_rdv -> int -> etat = <fun>
let n_transitions (u : etat) (l : liste_rdv) (n : int) : etat =
for _ = 1 to n do
ignore (transition u l) (* u est changé en place *)
done;
u
;;
val n_transitions : etat -> liste_rdv -> int -> etat = <fun>
Avec l'exemple du texte :
let _ = ex1;;
let _ = ex1_1;;
- : liste_rdv = [|[|1; 3|]; [|1; 2|]; [|2; 3|]|]
- : etat = [|1; 1; 2|]
let _ = transition ex1_1 ex1;;
let _ = transition ex1_1 ex1;;
let _ = transition ex1_1 ex1;;
let _ = transition ex1_1 ex1;;
- : etat = [|3; 2; 2|]
- : etat = [|3; 1; 3|]
- : etat = [|1; 1; 2|]
- : etat = [|3; 2; 2|]
Avec l'autre exemple donné à l'oral, qui est un peu différent de celui du texte.
Quatre robots, $R_0$, $R_1$, $R_2$, $R_3$, ont comme liste de rendez-vous successifs, $T_0 = [0, 1, 2]$, $T_1 = [0]$, $T_2 = [1, 3]$ et $T_3 = [2, 3]$.
let ex2 = [| [|0; 1; 2|]; [|0|]; [|1; 3|]; [|2; 3|] |];;
let ex2_1 = [| 0; 0; 1; 2 |];;
let _ = n_transitions ex2_1 ex2 3;;
val ex2 : int array array = [|[|0; 1; 2|]; [|0|]; [|1; 3|]; [|2; 3|]|]
val ex2_1 : int array = [|0; 0; 1; 2|]
- : etat = [|0; 0; 3; 3|]
C'est trivial, mais il peut être utile de vérifier que n_transitions 3
fait pareil que trois appels à transition
:
let ex2_1 = [| 0; 0; 1; 2 |];; (* il faut l'écrire, il a été modifié *)
let _ = transition ex2_1 ex2;;
let _ = transition ex2_1 ex2;;
let _ = transition ex2_1 ex2;;
let _ = transition ex2_1 ex2;;
val ex2_1 : int array = [|0; 0; 1; 2|]
- : etat = [|1; 0; 1; 2|]
- : etat = [|2; 0; 3; 2|]
- : etat = [|0; 0; 3; 3|]
- : etat = [|1; 0; 1; 2|]
Avec un autre état initial :
let ex2_2 = [| 0; 0; 3; 2 |];;
let _ = transition ex2_2 ex2;;
let _ = transition ex2_2 ex2;; (* On bloque !*)
let _ = transition ex2_2 ex2;; (* On bloque !*)
val ex2_2 : int array = [|0; 0; 3; 2|]
- : etat = [|1; 0; 3; 2|]
- : etat = [|1; 0; 3; 2|]
- : etat = [|1; 0; 3; 2|]
Et avec encore un autre état initial :
let ex2_3 = [| 0; 0; 3; 3 |];;
let _ = transition ex2_3 ex2;;
let _ = transition ex2_3 ex2;;
let _ = transition ex2_3 ex2;; (* On a un cycle de taille 3 *)
let _ = transition ex2_3 ex2;;
val ex2_3 : int array = [|0; 0; 3; 3|]
- : etat = [|1; 0; 1; 2|]
- : etat = [|2; 0; 3; 2|]
- : etat = [|0; 0; 3; 3|]
- : etat = [|1; 0; 1; 2|]
Voici une troisième modélisation, avec des matrices et des chaînes de Markov.
L'idée de base vient de l'observation suivante : ajouter de l'aléa dans les déplacements des robots devraient permettre de s'assurer (avec une certaine probabilité) que tous les rendez-vous sont bien effectués.
Random.init 0;;
- : unit = ()
Etant donné une distribution discrète $\pi = (\pi_1,\dots,\pi_N)$ sur $\{1,\dots,N\}$, la fonction suivante permet de générer un indice $i$ tel que $$ \mathbb{P}(i = k) = \pi_k, \forall k \in \{1,\dots,N\}.$$
let weight_sampling (pi : float array) () =
let p = Random.float 1. in
let i = ref (-1) in
let acc = ref 0. in
while !acc < p do
incr i;
acc := (!acc) +. pi.(!i);
done;
!i
;;
val weight_sampling : float array -> unit -> int = <fun>
Par exemple, tirer 100 échantillons suivant la distribution $\pi = [0.5, 0.1, 0.4]$ devrait donner environ $50$ fois $0$, $10$ fois $1$ et $40$ fois $2$ :
let compte (a : 'a array) (x : 'a) : int =
Array.fold_left (fun i y -> if y = x then i + 1 else i) 0 a
;;
let echantillons = Array.init 100
(fun _ -> weight_sampling [| 0.5; 0.1; 0.4 |] ())
;;
compte echantillons 0;;
compte echantillons 1;;
compte echantillons 2;;
val compte : 'a array -> 'a -> int = <fun>
val echantillons : int array = [|0; 0; 2; 2; 0; 0; 0; 0; 0; 0; 0; 2; 1; 2; 0; 2; 1; 2; 1; 2; 2; 1; 2; 0; 1; 2; 2; 0; 2; 0; 2; 0; 0; 0; 2; 2; 2; 2; 2; 0; 2; 0; 2; 0; 0; 2; 2; 2; 1; 0; 1; 2; 0; 2; 2; 2; 0; 0; 2; 0; 2; 0; 0; 0; 0; 0; 1; 0; 1; 0; 0; 2; 2; 2; 2; 2; 2; 1; 0; 0; 2; 2; 2; 2; 0; 0; 0; 0; 1; 2; 0; 1; 0; 0; 0; 0; 1; 0; 0; 2|]
- : int = 46
- : int = 13
- : int = 41
$46/100$, $13/100$ et $41/100$, c'est pas trop loin de $0.5, 0.1, 0.4$.
On peut utiliser cette fonction pour suivre une transition, aléatoire, sur une chaîne de Markov.
let markov_1 (a : float array array) (i : int) : int =
let pi = a.(i) in
weight_sampling pi ()
;;
val markov_1 : float array array -> int -> int = <fun>
Avec un petit exemple définit, on peut voir le résultat de $100$ transitions différentes depuis l'état $0$ :
let a = [|
[| 0.4; 0.3; 0.3 |];
[| 0.3; 0.4; 0.3 |];
[| 0.3; 0.3; 0.4 |]
|]
;;
val a : float array array = [|[|0.4; 0.3; 0.3|]; [|0.3; 0.4; 0.3|]; [|0.3; 0.3; 0.4|]|]
print "\n";;
for _ = 0 to 100 do
print "%i" (markov_1 a 0);
done;;
flush_all ();;
- : unit = ()
- : unit = ()
- : unit = ()
On peut suivre plusieurs transitions :
let markov_n (a : float array array) (etat : int) (n : int) : int =
let u = ref etat in
for _ = 0 to n-1 do
u := markov_1 a !u;
done;
!u
;;
val markov_n : float array array -> int -> int -> int = <fun>
markov_n a 0 10;;
- : int = 2
Et pour plusieurs robots, c'est pareil : chaque robots a un état (robots.(i)
) et une matrice de transition (a.(i)
) :
let markovs_n (a : float array array array) (robots : int array) (n : int) : int array =
Array.mapi (fun i u -> markov_n a.(i) u n) robots
;;
val markovs_n : float array array array -> int array -> int -> int array = <fun>
Si par exemple chaque état a la même matrice de transition :
markovs_n [|a; a; a|] [|0; 1; 2|] 10;;
- : int array = [|1; 1; 0|]
Plutôt que d'imposer à chaque robot un ordre fixe de ses rendez-vous, on va leur donner une probabilité uniforme d'aller, après un rendez-vous, à n'importe lequel de leur rendez-vous.
(* Fonctions utiles *)
Array.init;;
Array.make_matrix;;
Array.iter;;
- : int -> (int -> 'a) -> 'a array = <fun>
- : int -> int -> 'a -> 'a array array = <fun>
- : ('a -> unit) -> 'a array -> unit = <fun>
let mat_proba_depuis_rdv (ts : int array array) : (float array array) array =
let n = Array.length ts in
let a = Array.init n (fun _ -> Array.make_matrix n n 0.) in
for i = 0 to n-1 do
(* Pour le robot R_i, ses rendez-vous T_i sont ts.(i) *)
let r = ts.(i) in
let m = Array.length r in
let p_i = 1. /. (float_of_int m) in
(* Pour chaque rendez-vous L_j dans T_i,
remplir a.(j).(k) par 1/m,
et aussi a.(k).(j) par 1/m
pour chaque autre k dans L_j
*)
for j = 0 to m-1 do
for k = 0 to m-1 do
a.(i).(r.(j)).(r.(k)) <- p_i;
a.(i).(r.(k)).(r.(j)) <- p_i;
done;
done;
done;
a
;;
val mat_proba_depuis_rdv : int array array -> float array array array = <fun>
Avec les fonctions précédentes, on peut faire évoluer le système.
let simule_markov_robots (ts : int array array)
(etats : int array) (n : int)
: int array =
let a = mat_proba_depuis_rdv ts in
markovs_n a etats n
;;
val simule_markov_robots : int array array -> int array -> int -> int array = <fun>
On commence avec le premier exemple du texte, avec trois robots $R_1, R_2, R_3$, qui ont comme tableaux de rendez-vous $T_1 = [1, 3]$, $T_2 = [2, 1]$ et $T_3 = [3, 2]$.
Ce système n'est pas bloqué, mais aucun rendez-vous n'est réalisé avec l'approche statique. L'approche probabiliste permettra, espérons, de résoudre ce problème.
let ex3 = [| [|0; 2|]; [|1; 0|]; [|2; 1|]|] ;;
val ex3 : int array array = [|[|0; 2|]; [|1; 0|]; [|2; 1|]|]
On peut écrire une fonction qui récupère l'état initial dans lequel se trouve chaque robot (le texte donnait comme convention d'utiliser le premier de chaque liste).
let premier_etat (rdvs : int array array) : int array =
Array.init (Array.length rdvs) (fun i -> rdvs.(i).(0))
;;
val premier_etat : int array array -> int array = <fun>
let ex3_1 = premier_etat ex3;;
val ex3_1 : int array = [|0; 1; 2|]
On vérifie la matrice de transition produite par mat_proba_depuis_rdv
:
mat_proba_depuis_rdv ex3;;
- : float array array array = [|[|[|0.5; 0.; 0.5|]; [|0.; 0.; 0.|]; [|0.5; 0.; 0.5|]|]; [|[|0.5; 0.5; 0.|]; [|0.5; 0.5; 0.|]; [|0.; 0.; 0.|]|]; [|[|0.; 0.; 0.|]; [|0.; 0.5; 0.5|]; [|0.; 0.5; 0.5|]|]|]
On peut vérifier que ces chaînes de Markov représentent bien le comportement des robots, par exemple le premier robot $R_1$ a $T_1 = [1, 3]$, donc il alterne entre l'état $0$ et $2$, avec la matrice de transition $$ \mathbf{A}_i := \begin{bmatrix} 1/2 & 0 & 1/2 \\ 0 & 0 & 0 \\ 1/2 & 0 & 1/2 \end{bmatrix}. $$
Et enfin on peut simuler le système, par exemple pour juste une étape, plusieurs fois (pour bien visualiser).
simule_markov_robots ex3 ex3_1 0;; (* rien à faire ! *)
- : int array = [|0; 1; 2|]
simule_markov_robots ex3 ex3_1 1;;
- : int array = [|0; 0; 1|]
Pour mieux comprendre le fonctionnement, on va afficher les états intermédiaires.
let print = Printf.printf;;
val print : ('a, out_channel, unit) format -> 'a = <fun>
let affiche_etat (etat : int array) =
Array.iter (fun u -> print "%i " u) etat;
print "\n";
flush_all ();
;;
val affiche_etat : int array -> unit = <fun>
affiche_etat ex3_1;;
- : unit = ()
212211100011001111122012001220121202021210112221021002120120002102200202210112002021002012110120102010 1 2
let u = ref ex3_1 in
for _ = 0 to 10 do
affiche_etat !u;
u := simule_markov_robots ex3 !u 1;
done;;
0 1 2 2 1 2 0 1 1 0 0 2 0 1 1 0 0 1 0 1 1 0 1 1 2 1 1 2 0 1 0 1 1
- : unit = ()
On constate que des rendez-vous ont bien été effectués ! Pas à chaque fois, mais presque.
En tout cas, ça fonctionne mieux que l'approche naïve, peu importe l'état initial.
let u = ref [| 0; 1; 1 |] in
for _ = 0 to 10 do
affiche_etat !u;
u := simule_markov_robots ex3 !u 1;
done;;
0 1 1 0 1 2 0 0 1 0 0 2 2 1 2 0 0 1 2 1 2 2 0 1 2 1 1 0 1 1 0 0 1
- : unit = ()
Sur 11 états, le rendez-vous 0 a été fait 1 fois, le 1 a été fait 4 fois, et le 2 a été fait 4 fois aussi. Soit 9 sur 11 étapes utiles ! Pas mal !
(ce texte n'est pas valide à chaque exécution à cause de l'aléa...)
Puis le second exemple :
let ex4 = [| [|0; 3|]; [|0; 1|]; [|1; 2|]; [|2; 3|] |];;
val ex4 : int array array = [|[|0; 3|]; [|0; 1|]; [|1; 2|]; [|2; 3|]|]
let ex4_1 = premier_etat ex4;;
val ex4_1 : int array = [|0; 0; 1; 2|]
On vérifie la matrice de transition produite par mat_proba_depuis_rdv
:
mat_proba_depuis_rdv ex4;;
- : float array array array = [|[|[|0.5; 0.; 0.; 0.5|]; [|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]; [|0.5; 0.; 0.; 0.5|]|]; [|[|0.5; 0.5; 0.; 0.|]; [|0.5; 0.5; 0.; 0.|]; [|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]|]; [|[|0.; 0.; 0.; 0.|]; [|0.; 0.5; 0.5; 0.|]; [|0.; 0.5; 0.5; 0.|]; [|0.; 0.; 0.; 0.|]|]; [|[|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.5; 0.5|]; [|0.; 0.; 0.5; 0.5|]|]|]
Et enfin on peut simuler le système, par exemple pour juste une étape, plusieurs fois (pour bien visualiser).
simule_markov_robots ex4 ex4_1 0;; (* rien à faire ! *)
- : int array = [|0; 0; 1; 2|]
simule_markov_robots ex4 ex4_1 1;;
- : int array = [|3; 1; 1; 2|]
let u = ref ex4_1 in
for _ = 0 to 10 do
affiche_etat !u;
u := simule_markov_robots ex4 !u 1;
done;;
0 0 1 2 0 0 1 2 0 0 1 3 3 0 1 3 0 0 1 3 0 1 1 2 0 1 2 3 3 0 2 3 0 1 2 3 0 0 2 2 3 0 1 2
- : unit = ()
Sur 11 états, le rendez-vous 0 a été fait 5 fois, le 1 a été fait 2 fois, le 2 a été fait 3 fois, et le 3 a été fait 3 fois aussi. Soit plus d'un rendez-vous par étape réussi en moyenne, et tous les rendez-vous ont été vus.
(ce texte n'est pas valide à chaque exécution à cause de l'aléa...)
On ne va pas en faire plus, mais cela suffit de montrer la pertinence de cette autre approche.
Merci d'avoir lu jusque là !
Voilà pour la question obligatoire de programmation :
Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.
N'hésitez pas à aller voir ce dépôt GitHub pour d'autres notebooks, notamment cette page pour d'autres notebooks corrigeant des textes de modélisation (option D, informatique théorique) pour l'agrégation de mathématiques.