{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Texte d'oral de modélisation - Agrégation Option Informatique\n",
"## Préparation à l'agrégation - ENS de Rennes, 2016-17\n",
"- *Date* : 22 mai 2017\n",
"- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n",
"- *Texte*: Annale 2010, [\"Tissus cellulaires\" (public2010-D2)](http://agreg.org/Textes/public2010-D2.pdf)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## À propos de ce document\n",
"- 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/).\n",
"- 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.\n",
"- L'implémentation sera faite en OCaml, version 4+ :"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The OCaml toplevel, version 4.04.2\n"
]
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Sys.command \"ocaml -version\";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Question de programmation\n",
"La question de programmation pour ce texte était donnée au tout début, et occupe toute la page 2 :\n",
"\n",
"### Modélisation\n",
"> \n",
"> On veut simuler un phénomène de contamination. L’état d’une cellule est représenté par un\n",
"> entier compris entre $0$ et $K$ ($K \\geq 1$ est un paramètre fixé).\n",
"> \n",
"> 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.\n",
"> Tous les autres états représentent différents stades d’infection.\n",
"> Une cellule infectée commence dans l’état $1$ et à chaque itération passe dans l’état suivant (c.-à-d. $2$ puis $3$ puis...).\n",
"> 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.\n",
"> \n",
"> Une cellule infectée n’est pas tout de suite contagieuse (c.-à-d. capable d’infecter ses voisines).\n",
"> 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$).\n",
"> Durant cette période, elle peut contaminer chacune de ses deux voisines (les plus proches à droite et à gauche).\n",
"> 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.\n",
"> \n",
"> Les cellules ne bougent pas et on les suppose rangées les unes à côté des autres sur une ligne.\n",
"> Elles sont toutes mises à jour en même temps, de manière synchrone.\n",
"> Pour simplifier, on suppose que les première et dernière cellules restent toujours dans le même état $0$.\n",
"> \n",
"> \n",
"> \n",
"> Tout ceci est schématisé sur la Fig. 1 où l’on voit en haut une configuration et en bas la configuration suivante.\n",
"> 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.\n",
"> 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$.\n",
"> Dans cette illustration, l’état de la troisième cellule (3) est en gras pour\n",
"> indiquer pour quelles cellules il intervient durant la mise à jour.\n",
"\n",
"### Exercice\n",
"> É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.\n",
"\n",
"> Préciser la complexité en temps et en espace de la simulation."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Solution\n",
"\n",
"On va essayer d'être rapide et de faire simple, aussi $K=5$ et $I=2$ seront **fixés** et constants dans tout le code suivant."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Les constantes $K$ et $I$ de la simulation sont fixées :\n",
"\n",
"- $K = 5$ fixe le nombre d'états différents dans lequel peut être une cellule,\n",
"- $I = 2$ fixe le seuil à partir duquel une cellule devient contagieuse"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val k : int = 5\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val i : int = 2\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let k = 5;;\n",
"\n",
"let i = 2;;\n",
"\n",
"assert (i <= k);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pour une cellule"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"L'état d'une cellule est un entier :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type etatcellule = int\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type etatcellule = int;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Voici quelques fonctions \"triviales\" pour traduire les propriétés décrites par le texte :"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val est_saine : etatcellule -> bool = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** Une cellule est saine si son état est [0], infectée sinon. *)\n",
"let est_saine (etat : etatcellule) : bool = \n",
" etat = 0\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val grossir : etatcellule -> etatcellule = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let grossir (etat : etatcellule) : etatcellule =\n",
" if etat >= k then 0 else (etat + 1)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val est_contagieuse : etatcellule -> bool = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let est_contagieuse (etat : etatcellule) : bool = \n",
" etat >= i\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val infecte : etatcellule -> etatcellule = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let infecte (etat : etatcellule) : etatcellule =\n",
" if etat = 0 then 1 else etat\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pour une ligne de cellule (*un tissu*)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Si on voulait représenter des tissus en plusieurs dimensions (2, 3),\n",
"ici on devrait utiliser `etatcellule array array` (ou `etatcellule array array array`),\n",
"mais en 1D, `etatcellule array` suffit."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type tissu = etatcellule array\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type tissu = etatcellule array;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour créer un nouvel organse, constitué uniquement de cellules saines :"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val nouveau_tissu : int -> tissu = \n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nouveau_tissu (length : int) : tissu =\n",
" Array.make length (0 : etatcellule)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Par exemple, un \"muscle\", long de 20 cellules, toutes saines :"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val muscle1 : tissu =\n",
" [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]\n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let muscle1 : tissu = nouveau_tissu 20;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cette fonction sera un raccourci utile pour infecter une cellule choisie :"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val infecte_cible : tissu -> int -> unit = \n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let infecte_cible (org : tissu) (indice : int) : unit =\n",
" org.(indice) <- (infecte org.(indice))\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Un second muscle, long de 21 cellules, avec une seule cellule malade en indice 11 :"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val muscle2 : tissu =\n",
" [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0; 0|]\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let muscle2 : tissu =\n",
" let m = nouveau_tissu 21 in begin\n",
" infecte_cible m 11;\n",
" m\n",
" end\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Toutes ces fonctions s'exécutent en temps constant $\\mathcal{O}(1)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Évolution d'une cellule qui n'est pas au bord en fonction de l'état précédent de ces deux voisins et de son état."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On représente une cellule avec ses deux voisins :"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type lcor = { l : etatcellule; co : etatcellule; r : etatcellule; }\n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type lcor = { l : etatcellule; co : etatcellule; r : etatcellule; };;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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` :"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val nouvel_etat_cellule : lcor -> unit -> etatcellule = \n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nouvel_etat_cellule ({l; co; r} : lcor) () : etatcellule =\n",
" if co = k then\n",
" (* La cellule guérit, ce qu'on autoriserait plus dans le second modèle. *)\n",
" 0\n",
" else begin\n",
" if (est_saine co) then\n",
" (* Si elle est saine, elle peut devenir infectée : *)\n",
" if ( (est_contagieuse l) || (est_contagieuse r) )\n",
" then\n",
" (* Devient infectée. *)\n",
" 1\n",
" else\n",
" co \n",
" else\n",
" (* Si elle est déjà infectée, elle grandit toute seule. *)\n",
" grossir co\n",
" end\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Cette fonction s'exécute en temps constant $\\mathcal{O}(1)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Construction du sous-tableau des triplets `lcor`, en ignorant la première et dernière cellule :"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val cree_lcor : tissu -> lcor array = \n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let cree_lcor (org : tissu) : lcor array =\n",
" let n = Array.length org in\n",
" assert (n >= 2);\n",
" Array.init (n - 2) (fun i -> \n",
" { l = org.(i); co = org.(i + 1); r = org.(i + 2) }\n",
" )\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Cette fonction s'exécute en temps linéaire $\\mathcal{O}(n)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Testons sur les deux exemples précédents :"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val lcor1 : lcor array =\n",
" [|{l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}|]\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val lcor2 : lcor array =\n",
" [|{l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 1}; {l = 0; co = 1; r = 0}; {l = 1; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0}; {l = 0; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 0}|]\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let lcor1 = cree_lcor muscle1;;\n",
"let lcor2 = cree_lcor muscle2;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Un troisième exemple plus intéressant sera le tissu de la Figure 1, qu'on supposera de petite taille.\n",
""
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val muscle3 : int array = [|0; 0; 3; 0; 0; 1; 5; 0; 0|]\n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val lcor3 : lcor array =\n",
" [|{l = 0; co = 0; r = 3}; {l = 0; co = 3; r = 0}; {l = 3; co = 0; r = 0};\n",
" {l = 0; co = 0; r = 1}; {l = 0; co = 1; r = 5}; {l = 1; co = 5; r = 0};\n",
" {l = 5; co = 0; r = 0}|]\n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let muscle3 = [| 0; 0; 3; 0; 0; 1; 5; 0; 0 |];;\n",
"\n",
"let lcor3 = cree_lcor muscle3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Une fonction concise pour afficher un tissu (ie. une ligne de cellules)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, Format.formatter, unit) format -> 'a = \n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Format.printf;;"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print_tissu_x : etatcellule list -> unit = \n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print_tissu_x (etats : etatcellule list) : unit =\n",
" match etats with\n",
" | [] -> print \"\";\n",
" | s0 :: [] -> print \"[ %i ]\" s0;\n",
" | s0 :: l -> begin\n",
" print \"[ %i\" s0;\n",
" List.iter (fun (s : etatcellule) -> print \"-%i\" s) l;\n",
" print \" ]\";\n",
" end\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Cette fonction s'exécute en temps linéaire $\\mathcal{O}(n)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Simple fonction pour *afficher* un `tissu` (revient à afficher un tableau) :"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print_tissu : tissu -> unit = \n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print_tissu (o : tissu) : unit =\n",
" print_tissu_x (Array.to_list o)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" : muscle 1.\n",
"\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"[ 0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0 ][ 0-0-0-0-0-0-0-0-0-0-0-1-0-0-0-0-0-0-0-0-0 ] : muscle 2.\n",
"\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"[ 0-0-3-0-0-1-5-0-0 ] : muscle 3.\n",
"\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print_tissu muscle1;;\n",
"print_endline \" : muscle 1.\\n\";;\n",
"flush_all ();;\n",
"\n",
"print_tissu muscle2;;\n",
"print_endline \" : muscle 2.\\n\";;\n",
"flush_all ();;\n",
"\n",
"print_tissu muscle3;;\n",
"print_endline \" : muscle 3.\\n\";;\n",
"flush_all ();;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### La fonction demandée pour faire évoluer un tissu, étape par étape."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**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).\n",
"\n",
"Cette fonction renvoie la valeur du tissu, pour éventuellement faire des sauvegardes ou l'afficher, mais le tissu est bien modifié en place !"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val une_etape_infection : tissu -> tissu = \n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let une_etape_infection (ti : tissu) : tissu =\n",
" let n = Array.length ti in\n",
" let lcor_ti = cree_lcor ti in\n",
" for j = 1 to n - 2 do\n",
" ti.(j) <- nouvel_etat_cellule lcor_ti.(j-1) ()\n",
" done;\n",
" ti\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Cette fonction s'exécute en temps linéaire $\\mathcal{O}(n)$, puisque `cree_lcor` l'est, et `nouvel_etat_cellule` est en temps constant."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Un exemple sur le tissu sain, le tissu infecté au milieu et le tissu de la Figure 1."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : tissu = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"une_etape_infection muscle1;;"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : tissu = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 2; 0; 0; 0; 0; 0; 0; 0; 0; 0|]\n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"une_etape_infection muscle2;;"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : tissu = [|0; 1; 4; 1; 0; 2; 0; 1; 0|]\n"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"une_etape_infection muscle3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Faire évoluer sur plusieurs étapes, en affichant les étapes intermédiaires"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val m_etapes_infection : tissu -> int -> tissu = \n"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let m_etapes_infection (ti : tissu) (m : int) : tissu =\n",
" print \"\\n\\nSTART : %i étapes de propagation de l'infection.\" m;\n",
" print \"\\nÉtape 0 : \";\n",
" print_tissu ti;\n",
" for j = 1 to m do\n",
" print \"\\nÉtape %.2i : \" j;\n",
" print_tissu (une_etape_infection ti);\n",
" done;\n",
" flush_all ();\n",
" ti\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Cette fonction s'exécute en temps $\\mathcal{O}(n \\times m)$, puisqu'elle appelle $m$ fois `une_etape_infection` qui est en temps linéaire $\\mathcal{O}(n)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On relance les exemples depuis le début :"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val muscle1 : tissu =\n",
" [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]\n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"\n",
"START : 3 étapes de propagation de l'infection.\n",
"Étape 0 : [ 0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0 ]\n",
"Étape 01 : [ 0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0 ]\n",
"Étape 02 : [ 0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0 ]\n"
]
},
{
"data": {
"text/plain": [
"- : tissu = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]\n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let muscle1 = nouveau_tissu 20;;\n",
"m_etapes_infection muscle1 3;;\n",
"(* Il n'évolue pas *)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val muscle2 : tissu =\n",
" [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0; 0|]\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Étape 03 : [ 0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0 ]\n",
"\n",
"START : 40 étapes de propagation de l'infection.\n",
"Étape 0 : [ 0-0-0-0-0-0-0-0-0-0-0-1-0-0-0-0-0-0-0-0-0 ]\n",
"Étape 01 : [ 0-0-0-0-0-0-0-0-0-0-0-2-0-0-0-0-0-0-0-0-0 ]\n",
"Étape 02 : [ 0-0-0-0-0-0-0-0-0-0-1-3-1-0-0-0-0-0-0-0-0 ]\n",
"Étape 03 : [ 0-0-0-0-0-0-0-0-0-0-2-4-2-0-0-0-0-0-0-0-0 ]\n",
"Étape 04 : [ 0-0-0-0-0-0-0-0-0-1-3-5-3-1-0-0-0-0-0-0-0 ]\n",
"Étape 05 : [ 0-0-0-0-0-0-0-0-0-2-4-0-4-2-0-0-0-0-0-0-0 ]\n",
"Étape 06 : [ 0-0-0-0-0-0-0-0-1-3-5-1-5-3-1-0-0-0-0-0-0 ]\n",
"Étape 07 : [ 0-0-0-0-0-0-0-0-2-4-0-2-0-4-2-0-0-0-0-0-0 ]\n",
"Étape 08 : [ 0-0-0-0-0-0-0-1-3-5-1-3-1-5-3-1-0-0-0-0-0 ]\n",
"Étape 09 : [ 0-0-0-0-0-0-0-2-4-0-2-4-2-0-4-2-0-0-0-0-0 ]\n",
"Étape 10 : [ 0-0-0-0-0-0-1-3-5-1-3-5-3-1-5-3-1-0-0-0-0 ]\n",
"Étape 11 : [ 0-0-0-0-0-0-2-4-0-2-4-0-4-2-0-4-2-0-0-0-0 ]\n",
"Étape 12 : [ 0-0-0-0-0-1-3-5-1-3-5-1-5-3-1-5-3-1-0-0-0 ]\n",
"Étape 13 : [ 0-0-0-0-0-2-4-0-2-4-0-2-0-4-2-0-4-2-0-0-0 ]\n",
"Étape 14 : [ 0-0-0-0-1-3-5-1-3-5-1-3-1-5-3-1-5-3-1-0-0 ]\n",
"Étape 15 : [ 0-0-0-0-2-4-0-2-4-0-2-4-2-0-4-2-0-4-2-0-0 ]\n",
"Étape 16 : [ 0-0-0-1-3-5-1-3-5-1-3-5-3-1-5-3-1-5-3-1-0 ]\n",
"Étape 17 : [ 0-0-0-2-4-0-2-4-0-2-4-0-4-2-0-4-2-0-4-2-0 ]\n",
"Étape 18 : [ 0-0-1-3-5-1-3-5-1-3-5-1-5-3-1-5-3-1-5-3-0 ]\n",
"Étape 19 : [ 0-0-2-4-0-2-4-0-2-4-0-2-0-4-2-0-4-2-0-4-0 ]\n",
"Étape 20 : [ 0-1-3-5-1-3-5-1-3-5-1-3-1-5-3-1-5-3-1-5-0 ]\n",
"Étape 21 : [ 0-2-4-0-2-4-0-2-4-0-2-4-2-0-4-2-0-4-2-0-0 ]\n",
"Étape 22 : [ 0-3-5-1-3-5-1-3-5-1-3-5-3-1-5-3-1-5-3-1-0 ]\n",
"Étape 23 : [ 0-4-0-2-4-0-2-4-0-2-4-0-4-2-0-4-2-0-4-2-0 ]\n",
"Étape 24 : [ 0-5-1-3-5-1-3-5-1-3-5-1-5-3-1-5-3-1-5-3-0 ]\n",
"Étape 25 : [ 0-0-2-4-0-2-4-0-2-4-0-2-0-4-2-0-4-2-0-4-0 ]\n",
"Étape 26 : [ 0-1-3-5-1-3-5-1-3-5-1-3-1-5-3-1-5-3-1-5-0 ]\n",
"Étape 27 : [ 0-2-4-0-2-4-0-2-4-0-2-4-2-0-4-2-0-4-2-0-0 ]\n",
"Étape 28 : [ 0-3-5-1-3-5-1-3-5-1-3-5-3-1-5-3-1-5-3-1-0 ]\n",
"Étape 29 : [ 0-4-0-2-4-0-2-4-0-2-4-0-4-2-0-4-2-0-4-2-0 ]\n",
"Étape 30 : [ 0-5-1-3-5-1-3-5-1-3-5-1-5-3-1-5-3-1-5-3-0 ]\n",
"Étape 31 : [ 0-0-2-4-0-2-4-0-2-4-0-2-0-4-2-0-4-2-0-4-0 ]\n",
"Étape 32 : [ 0-1-3-5-1-3-5-1-3-5-1-3-1-5-3-1-5-3-1-5-0 ]\n",
"Étape 33 : [ 0-2-4-0-2-4-0-2-4-0-2-4-2-0-4-2-0-4-2-0-0 ]\n",
"Étape 34 : [ 0-3-5-1-3-5-1-3-5-1-3-5-3-1-5-3-1-5-3-1-0 ]\n",
"Étape 35 : [ 0-4-0-2-4-0-2-4-0-2-4-0-4-2-0-4-2-0-4-2-0 ]\n",
"Étape 36 : [ 0-5-1-3-5-1-3-5-1-3-5-1-5-3-1-5-3-1-5-3-0 ]\n",
"Étape 37 : [ 0-0-2-4-0-2-4-0-2-4-0-2-0-4-2-0-4-2-0-4-0 ]\n",
"Étape 38 : [ 0-1-3-5-1-3-5-1-3-5-1-3-1-5-3-1-5-3-1-5-0 ]\n",
"Étape 39 : [ 0-2-4-0-2-4-0-2-4-0-2-4-2-0-4-2-0-4-2-0-0 ]\n"
]
},
{
"data": {
"text/plain": [
"- : tissu = [|0; 3; 5; 1; 3; 5; 1; 3; 5; 1; 3; 5; 3; 1; 5; 3; 1; 5; 3; 1; 0|]\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let muscle2 = let m = nouveau_tissu 21 in begin infecte_cible m 11; m end;;\n",
"m_etapes_infection muscle2 40;;\n",
"(* tout le tissu est infecté ! Dès la 20ème étape *)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val muscle3 : int array = [|0; 0; 3; 0; 0; 1; 5; 0; 0|]\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : tissu = [|0; 2; 5; 2; 1; 3; 1; 2; 0|]\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Étape 40 : [ 0-3-5-1-3-5-1-3-5-1-3-5-3-1-5-3-1-5-3-1-0 ]\n",
"\n",
"START : 8 étapes de propagation de l'infection.\n",
"Étape 0 : [ 0-0-3-0-0-1-5-0-0 ]\n",
"Étape 01 : [ 0-1-4-1-0-2-0-1-0 ]\n",
"Étape 02 : [ 0-2-5-2-1-3-1-2-0 ]\n",
"Étape 03 : [ 0-3-0-3-2-4-2-3-0 ]\n",
"Étape 04 : [ 0-4-1-4-3-5-3-4-0 ]\n",
"Étape 05 : [ 0-5-2-5-4-0-4-5-0 ]\n",
"Étape 06 : [ 0-0-3-0-5-1-5-0-0 ]\n",
"Étape 07 : [ 0-1-4-1-0-2-0-1-0 ]\n"
]
}
],
"source": [
"let muscle3 = [| 0; 0; 3; 0; 0; 1; 5; 0; 0 |];;\n",
"m_etapes_infection muscle3 8;;\n",
"(* 3 étapes suffisent à tout infecter *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> Voilà, ce sera tout pour cette solution."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Complexités en temps et espace (bonus)\n",
"\n",
"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é."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### En temps\n",
"- Une étape d'infection, i.e., `une_etape_infection`, est en temps linéaire $\\mathcal{O}(n)$ (et c'est optimal),\n",
"- Donc $m$ étapes, i.e., `m_etapes_infection`, est en temps $\\mathcal{O}(n \\times m)$ (et c'est optimal)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### En espace\n",
"Tout est bien évidemment linéaire en $n$ la taille du tissu."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Conclusion\n",
"\n",
"Voilà pour la question obligatoire de programmation.\n",
"\n",
"### Qualités\n",
"- On a décomposé le problème en sous-fonctions,\n",
"- on a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n",
"- on a testé la fonction exigée sur de petits exemples et sur un exemple de taille réelle (venant du texte).\n",
"\n",
"### Défauts\n",
"- Par contre, on a testé avec uniquement une valeur pour $I$ et $K$ (resp., $2$ et $5$), et les fonctions écrites ne sont pas paramétriques en $I$ et $K$. (notez que ce serait assez trivial de les rendre des paramètres)\n",
"\n",
"\n",
"> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.\n",
"\n",
"> 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)."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "OCaml 4.04.2",
"language": "OCaml",
"name": "ocaml-jupyter"
},
"language_info": {
"codemirror_mode": "text/x-ocaml",
"file_extension": ".ml",
"mimetype": "text/x-ocaml",
"name": "OCaml",
"nbconverter_exporter": null,
"pygments_lexer": "OCaml",
"version": "4.04.2"
},
"notify_time": "10",
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "429px",
"width": "251px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_section_display": "block",
"toc_window_display": true
}
},
"nbformat": 4,
"nbformat_minor": 2
}