In [1]:
Sys.command "ocaml -version";;
Out[1]:
La question de programmation pour ce texte était donnée au tout début, et occupe toute la page 2 :
On veut simuler un phénomène de contamination. L’état d’une cellule est représenté par un entier compris entre $0$ et $K$ ($K \geq 1$ est un paramètre fixé).
Une cellule est normalement saine, non contaminée, dans l’état $0$ et reste dans cet état tant qu’elle n’est pas infectée. Tous les autres états représentent différents stades d’infection. Une cellule infectée commence dans l’état $1$ et à chaque itération passe dans l’état suivant (c.-à-d. $2$ puis $3$ puis...). Quand elle atteint l’état $K$, elle a remporté sa lutte contre l’infection et retourne à l’état $0$, saine et non infectée à l’itération suivante.
Une cellule infectée n’est pas tout de suite contagieuse (c.-à-d. capable d’infecter ses voisines). Une cellule devient infectieuse à partir du stade $I$ ($I \leq K$, $I$ est un autre paramètre fixé) et le reste jusqu’à sa guérison (retour à l’état $0$). Durant cette période, elle peut contaminer chacune de ses deux voisines (les plus proches à droite et à gauche). Si celles-ci ne sont pas déjà infectées, elles le deviennent automatiquement, au stade $1$; si elles sont déjà infectées, elles le restent.
Les cellules ne bougent pas et on les suppose rangées les unes à côté des autres sur une ligne. Elles sont toutes mises à jour en même temps, de manière synchrone. Pour simplifier, on suppose que les première et dernière cellules restent toujours dans le même état $0$.
Tout ceci est schématisé sur la Fig. 1 où l’on voit en haut une configuration et en bas la configuration suivante. Chaque cellule est mise à jour en fonction de ses deux plus proches voisines, sauf pour les cellules des deux extrémités dont l’état ne change pas. Après la configuration $(0, 0, 3, 0, 0, 1, 5 ,\dots, 0 )$, le système passe donc à la configuration $(0, 1, 4, 1, 0, 2, 0 ,\dots, 0 )$ pour $K = 5$ et $I = 2$. Dans cette illustration, l’état de la troisième cellule (3) est en gras pour indiquer pour quelles cellules il intervient durant la mise à jour.
Écrire un programme permettant d’afficher la progression de la contamination sur une vingtaine d’itérations, par exemple pour les valeurs ($K = 5$ et $I = 2$) en partant d’une seule cellule infectée sur une ligne d’une vingtaine de cellules saines.
Préciser la complexité en temps et en espace de la simulation.
Les constantes $K$ et $I$ de la simulation sont fixées :
In [2]:
let k = 5;;
let i = 2;;
assert (i <= k);;
Out[2]:
Out[2]:
Out[2]:
L'état d'une cellule est un entier :
In [3]:
type etatcellule = int;;
Out[3]:
Voici quelques fonctions "triviales" pour traduire les propriétés décrites par le texte :
In [4]:
(** Une cellule est saine si son état est [0], infectée sinon. *)
let est_saine (etat : etatcellule) : bool =
etat = 0
;;
Out[4]:
In [5]:
let grossir (etat : etatcellule) : etatcellule =
if etat >= k then 0 else (etat + 1)
;;
Out[5]:
In [6]:
let est_contagieuse (etat : etatcellule) : bool =
etat >= i
;;
Out[6]:
In [7]:
let infecte (etat : etatcellule) : etatcellule =
if etat = 0 then 1 else etat
;;
Out[7]:
Si on voulait représenter des tissus en plusieurs dimensions (2, 3),
ici on devrait utiliser etatcellule array array (ou etatcellule array array array),
mais en 1D, etatcellule array suffit.
In [8]:
type tissu = etatcellule array;;
Out[8]:
Pour créer un nouvel organse, constitué uniquement de cellules saines :
In [9]:
let nouveau_tissu (length : int) : tissu =
Array.make length (0 : etatcellule)
;;
Out[9]:
Par exemple, un "muscle", long de 20 cellules, toutes saines :
In [10]:
let muscle1 : tissu = nouveau_tissu 20;;
Out[10]:
Cette fonction sera un raccourci utile pour infecter une cellule choisie :
In [11]:
let infecte_cible (org : tissu) (indice : int) : unit =
org.(indice) <- (infecte org.(indice))
;;
Out[11]:
Un second muscle, long de 21 cellules, avec une seule cellule malade en indice 11 :
In [12]:
let muscle2 : tissu =
let m = nouveau_tissu 21 in begin
infecte_cible m 11;
m
end
;;
Out[12]:
On représente une cellule avec ses deux voisins :
In [13]:
type lcor = { l : etatcellule; co : etatcellule; r : etatcellule; };;
Out[13]:
On peut ensuite donner l'état de la cellule courante (précédemment dans l'état co) en fonction de l'état de sa voisine de gauche l et de droite r :
In [14]:
let nouvel_etat_cellule ({l; co; r} : lcor) () : etatcellule =
if co = k then
(* La cellule guérit, ce qu'on autoriserait plus dans le second modèle. *)
0
else begin
if (est_saine co) then
(* Si elle est saine, elle peut devenir infectée : *)
if ( (est_contagieuse l) || (est_contagieuse r) )
then
(* Devient infectée. *)
1
else
co
else
(* Si elle est déjà infectée, elle grandit toute seule. *)
grossir co
end
;;
Out[14]:
Construction du sous-tableau des triplets lcor, en ignorant la première et dernière cellule :
In [15]:
let cree_lcor (org : tissu) : lcor array =
let n = Array.length org in
assert (n >= 2);
Array.init (n - 2) (fun i ->
{ l = org.(i); co = org.(i + 1); r = org.(i + 2) }
)
;;
Out[15]:
Testons sur les deux exemples précédents :
In [16]:
let lcor1 = cree_lcor muscle1;;
let lcor2 = cree_lcor muscle2;;
Out[16]:
Out[16]:
Un troisième exemple plus intéressant sera le tissu de la Figure 1, qu'on supposera de petite taille.
In [17]:
let muscle3 = [| 0; 0; 3; 0; 0; 1; 5; 0; 0 |];;
let lcor3 = cree_lcor muscle3;;
Out[17]:
Out[17]:
In [18]:
let print = Format.printf;;
Out[18]:
In [19]:
let print_tissu_x (etats : etatcellule list) : unit =
match etats with
| [] -> print "";
| s0 :: [] -> print "[ %i ]" s0;
| s0 :: l -> begin
print "[ %i" s0;
List.iter (fun (s : etatcellule) -> print "-%i" s) l;
print " ]";
end
;;
Out[19]:
Simple fonction pour afficher un tissu (revient à afficher un tableau) :
In [20]:
let print_tissu (o : tissu) : unit =
print_tissu_x (Array.to_list o)
;;
Out[20]:
In [21]:
print_tissu muscle1;;
print_endline " : muscle 1.\n";;
flush_all ();;
print_tissu muscle2;;
print_endline " : muscle 2.\n";;
flush_all ();;
print_tissu muscle3;;
print_endline " : muscle 3.\n";;
flush_all ();;
Out[21]:
Out[21]:
Out[21]:
Out[21]:
Out[21]:
Out[21]:
Out[21]:
Out[21]:
Out[21]:
Attention, elle agit par effet de bords ! (i.e., en modifiant en place le tissu donné, c'est pour ça qu'on utilise des tableaux et non des listes).
Cette fonction renvoie la valeur du tissu, pour éventuellement faire des sauvegardes ou l'afficher, mais le tissu est bien modifié en place !
In [22]:
let une_etape_infection (ti : tissu) : tissu =
let n = Array.length ti in
let lcor_ti = cree_lcor ti in
for j = 1 to n - 2 do
ti.(j) <- nouvel_etat_cellule lcor_ti.(j-1) ()
done;
ti
;;
Out[22]:
cree_lcor l'est, et nouvel_etat_cellule est en temps constant.Un exemple sur le tissu sain, le tissu infecté au milieu et le tissu de la Figure 1.
In [23]:
une_etape_infection muscle1;;
Out[23]:
In [24]:
une_etape_infection muscle2;;
Out[24]:
In [25]:
une_etape_infection muscle3;;
Out[25]:
In [26]:
let m_etapes_infection (ti : tissu) (m : int) : tissu =
print "\n\nSTART : %i étapes de propagation de l'infection." m;
print "\nÉtape 0 : ";
print_tissu ti;
for j = 1 to m do
print "\nÉtape %.2i : " j;
print_tissu (une_etape_infection ti);
done;
flush_all ();
ti
;;
Out[26]:
une_etape_infection qui est en temps linéaire $\mathcal{O}(n)$.On relance les exemples depuis le début :
In [27]:
let muscle1 = nouveau_tissu 20;;
m_etapes_infection muscle1 3;;
(* Il n'évolue pas *)
Out[27]:
Out[27]:
In [28]:
let muscle2 = let m = nouveau_tissu 21 in begin infecte_cible m 11; m end;;
m_etapes_infection muscle2 40;;
(* tout le tissu est infecté ! Dès la 20ème étape *)
Out[28]:
Out[28]:
In [29]:
let muscle3 = [| 0; 0; 3; 0; 0; 1; 5; 0; 0 |];;
m_etapes_infection muscle3 8;;
(* 3 étapes suffisent à tout infecter *)
Out[29]:
Out[29]:
Voilà, ce sera tout pour cette solution.
Voilà pour la question obligatoire de programmation.
Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.
Vous auriez pu choisir de modéliser le problème avec une autre approche, ou vous auriez pu expérimenter des extensions de cette approche (e.g., des tissus en 2D ou 3D).