{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Texte d'oral de modélisation - Agrégation Option Informatique
1.1  Préparation à l'agrégation - ENS de Rennes, 2016-17
1.2  À propos de ce document
1.3  Question de programmation
1.4  Réponse à l'exercice requis
1.4.1  Structures de données
1.4.2  Exemples de grilles
1.4.3  Permutations
1.4.4  Un déplacement
1.4.5  Test de la parité de σB
1.4.6  Fonctions demandées
1.4.7  Exemples
1.5  Bonus ?
1.5.1  Complexité
1.5.2  Autres idées
1.6  Conclusion
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Texte d'oral de modélisation - Agrégation Option Informatique" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Préparation à l'agrégation - ENS de Rennes, 2016-17" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- *Date* : 29 mai 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: [Taquin (pub2008-D2)](http://agreg.org/Textes/pub2008-D2.pdf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## À propos de ce document" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- 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": true }, "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": [ "> Notez que certaines fonctions des modules usuels [`List`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) et [`Array`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) ne sont pas disponibles en OCaml 3.12.\n", "> J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question de programmation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La question de programmation pour ce texte était donnée en page 5, et était assez courte :\n", "\n", "> \"Implanter l'algorithme qui, à partir d'une table $T$ du jeu de taquin, calcule les coordonnées du trou et la valeur de $\\pi_2(T)$.\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Réponse à l'exercice requis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Structures de données\n", "\n", "On doit pouvoir représenter $T$, une table du jeu de taquin.\n", "\n", "On utilisera la structure de données suggérée par l'énoncé :\n", "\n", "> \"Une table $T$ du jeu de taquin est codée par un tableau carré (encore noté $T$) où, pour $i, j \\in [| 0, n - 1 |]$, $T[i, j]$ désigne le numéro de la pièce située en ligne $i$ et colonne $j$, le trou étant codé par l’entier $0$.\"\n", "\n", "La figure 1 présente trois tables du jeu pour $n=4$; la première, notée $T_1$ , est aléatoire, la troisième est la table finale $T_f$ et la deuxième, notée $T_2$, peut être qualifiée d’intermédiaire : il est possible de passer en un certain nombre de coups de $T_1$ à $T_2$, puis de $T_2$ à $T_f$.\n", "\n", "![images/taquin.png](images/taquin.png)\n", "\n", "Par exemple, dans la table $T_1$ de la figure $1$, $T_1[2, 0] = 5$ et le trou est situé à la position $[3, 1]$." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type taquin = int array array\n" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type taquin = int array array;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exemples de grilles\n", "\n", "On reproduit les trois exemples ci-dessous :" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val t1 : taquin =\n", " [|[|10; 6; 4; 12|]; [|1; 14; 3; 7|]; [|5; 15; 11; 13|]; [|8; 0; 2; 9|]|]\n" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t1 : taquin = [|\n", " [| 10; 6; 4; 12 |];\n", " [| 1; 14; 3; 7 |];\n", " [| 5; 15; 11; 13 |];\n", " [| 8; 0; 2; 9 |]\n", "|];;" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val t2 : taquin =\n", " [|[|0; 1; 2; 4|]; [|3; 6; 10; 12|]; [|5; 7; 14; 11|]; [|8; 9; 15; 13|]|]\n" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t2 : taquin = [|\n", " [| 0; 1; 2; 4 |];\n", " [| 3; 6; 10; 12 |];\n", " [| 5; 7; 14; 11 |];\n", " [| 8; 9; 15; 13 |]\n", "|];;" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val tf : taquin =\n", " [|[|0; 1; 2; 3|]; [|4; 5; 6; 7|]; [|8; 9; 10; 11|]; [|12; 13; 14; 15|]|]\n" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let tf : taquin = [|\n", " [| 0; 1; 2; 3 |];\n", " [| 4; 5; 6; 7 |];\n", " [| 8; 9; 10; 11 |];\n", " [| 12; 13; 14; 15 |]\n", "|];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Permutations\n", "\n", "On peut essayer d'obtenir les deux permutations, $\\sigma(T)$ et $\\sigma^B(T)$, pour une table $T$ donnée.\n", "\n", "Une permutation sera un simple tableau, de tailles $n^2$ (pour $\\sigma$) et $n^2 - 1$ (pour $\\sigma^B$), qui stocke en case $i$ la valeur $\\sigma(T)[i]$." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type permutation = int array\n" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type permutation = int array ;;" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sigma : taquin -> permutation = \n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let sigma (t : taquin) : permutation =\n", " (* Initialisation *)\n", " let n = Array.length t in\n", " let sigm = Array.make (n * n) 0 in\n", " (* Remplissons sigm *)\n", " for i = 0 to n - 1 do\n", " for j = 0 to n - 1 do\n", " sigm.( i * n + j ) <- t.(i).(j)\n", " done;\n", " done;\n", " sigm\n", " (* On aurait aussi pu faire\n", " Array.init (n * n) (fun ij -> t.(ij mod n).(j / n))\n", " *)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Exemples :" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : permutation = [|10; 6; 4; 12; 1; 14; 3; 7; 5; 15; 11; 13; 8; 0; 2; 9|]\n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : permutation = [|0; 1; 2; 4; 3; 6; 10; 12; 5; 7; 14; 11; 8; 9; 15; 13|]\n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : permutation = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15|]\n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sigma t1;;\n", "sigma t2;;\n", "sigma tf;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C'était facile.\n", "Maintenant pour la permutation de Boustrophédon, $\\sigma^B(T)$.\n", "On va quand même stoquer le $0$, en position $0$." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val print : ('a, out_channel, unit) format -> 'a = \n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let print = Printf.printf;;" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sigmaB : taquin -> permutation = \n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let sigmaB (t : taquin) : permutation =\n", " (* Initialisation *)\n", " let n = Array.length t in\n", " let sigm = Array.make ((n * n) - 1) 0 in\n", " let nbzero = ref 0 in\n", " (* Remplissons sigm *)\n", " for i = 0 to n - 1 do\n", " for j = 0 to n - 1 do\n", " if i mod 2 = 0\n", " then (* gauche à droite *)\n", " if t.(i).(j) = 0 then\n", " incr nbzero\n", " else\n", " sigm.( i * n + j - !nbzero ) <- t.(i).(j)\n", " else (* droite à gauche *)\n", " if t.(i).(n - j - 1) = 0 then\n", " incr nbzero\n", " else\n", " sigm.( i * n + j - !nbzero ) <- t.(i).(n - j - 1)\n", " done;\n", " done;\n", " sigm\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Exemples :" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : permutation = [|10; 6; 4; 12; 7; 3; 14; 1; 5; 15; 11; 13; 9; 2; 8|]\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : permutation = [|1; 2; 4; 12; 10; 6; 3; 5; 7; 14; 11; 13; 15; 9; 8|]\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : permutation = [|1; 2; 3; 7; 6; 5; 4; 8; 9; 10; 11; 15; 14; 13; 12|]\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sigmaB t1;;\n", "sigmaB t2;;\n", "sigmaB tf;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un déplacement\n", "\n", "On a $4$ déplacements possibles, $\\{N, E, S, O\\}$." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type deplacement = Nord | Est | Sud | Ouest\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type deplacement = Nord | Est | Sud | Ouest ;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va avoir besoin d'une fonction qui trouve la position $(i,j)$ du trou :" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val ou_est : int -> taquin -> int * int = \n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val ou_est_trou : taquin -> int * int = \n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ou_est (x : int) (t : taquin) : (int * int) =\n", " let n = Array.length t in\n", " let ij = ref (0, 0) in\n", " for i = 0 to n - 1 do\n", " for j = 0 to n - 1 do\n", " if t.(i).(j) = x then\n", " ij := (i, j)\n", " done;\n", " done;\n", " !ij\n", ";;\n", "\n", "let ou_est_trou = ou_est 0 ;;" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val copie : taquin -> taquin = \n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let copie (t : taquin) : taquin =\n", " Array.map (Array.copy) t\n", ";;" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val unmouvement : taquin -> deplacement -> taquin = \n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let unmouvement (t : taquin) (dir : deplacement) : taquin =\n", " let n = Array.length t in\n", " let i, j = ou_est_trou t in\n", " let tsuivant = copie t in\n", " match dir with\n", " | Nord ->\n", " if i = 0\n", " then\n", " failwith \"Can't go north here\"\n", " else begin\n", " tsuivant.(i).(j) <- tsuivant.(i - 1).(j);\n", " tsuivant.(i - 1).(j) <- 0;\n", " tsuivant\n", " end;\n", " | Est ->\n", " if j = n - 1\n", " then failwith \"Can't go east here\"\n", " else begin\n", " tsuivant.(i).(j) <- tsuivant.(i).(j + 1);\n", " tsuivant.(i).(j + 1) <- 0;\n", " tsuivant\n", " end;\n", " | Sud ->\n", " if i = n - 1\n", " then failwith \"Can't go south here\"\n", " else begin\n", " tsuivant.(i).(j) <- tsuivant.(i + 1).(j);\n", " tsuivant.(i + 1).(j) <- 0;\n", " tsuivant\n", " end;\n", " | Ouest ->\n", " if j = 0\n", " then failwith \"Can't go west here\"\n", " else begin\n", " tsuivant.(i).(j) <- tsuivant.(i).(j - 1);\n", " tsuivant.(i).(j - 1) <- 0;\n", " tsuivant\n", " end;\n", ";;" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val t1' : taquin =\n", " [|[|10; 6; 4; 12|]; [|1; 14; 3; 7|]; [|5; 0; 11; 13|]; [|8; 15; 2; 9|]|]\n" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : permutation = [|10; 6; 4; 12; 1; 14; 3; 7; 5; 0; 11; 13; 8; 15; 2; 9|]\n" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let t1' = unmouvement t1 Nord ;;\n", "\n", "sigma t1';;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ça semble fonctionner comme dans l'exemple du texte." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Test de la parité de $\\sigma^B$\n", "\n", "Le critère suivant permet de savoir si une table de taquin est jouable, i.e, si on peut la résoudre :\n", "\n", "> $T$ est jouable si et seulement si $\\sigma^B(T)$ est paire." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val nb_inversions : permutation -> int = \n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let nb_inversions (sigm : permutation) : int =\n", " let nb = ref 0 in\n", " let m = Array.length sigm in\n", " for i = 0 to m - 1 do\n", " for j = i + 1 to m - 1 do\n", " if sigm.(i) > sigm.(j) then\n", " incr nb\n", " done;\n", " done;\n", " !nb\n", ";;" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_paire : permutation -> bool = \n" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_paire (sigm : permutation) : bool =\n", " ((nb_inversions sigm) mod 2) = 0\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut vérifier que les trois tables de l'énoncé ont bien une permutation de Boustrophédon paire :" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_paire (sigmaB t1);;\n", "est_paire (sigmaB t2);;\n", "est_paire (sigmaB tf);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et l'exemple de l'énonce qui n'est plus *jouable* :" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let tnof = copie tf in\n", "tnof.(0).(1) <- 2;\n", "tnof.(0).(2) <- 1;\n", "est_paire (sigmaB tnof);;" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_jouable : taquin -> bool = \n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_jouable (t : taquin) : bool =\n", " est_paire (sigmaB t)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Fonctions demandées\n", "\n", "- On a déjà écrit la fonction $\\pi_1(T)$, `nb_inversions`.\n", "- Pour $\\pi_2(T)$, on doit réfléchir un peu plus." ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val pi_1 : taquin -> int = \n" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let pi_1 (t : taquin) : int =\n", " nb_inversions (sigma t)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour $\\pi_2(T)$, on peut être inquiet de voir dans la définition de cette distance la table finale, qui est l'objectif de la résolution du problème, mais en fait les tables finales $T_f$ ont toutes la même forme : en case $(i,j)$ se trouve $i \\times n + j$ !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On commence par définir la norme $\\ell_1$, sur deux couples $(i,j)$ et $(x,y)$ :\n", "$$ \\ell_1 : (i,j), (x, y) \\mapsto |i-x| + |j-y| $$" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val norme_1 : int * int -> int * int -> int = \n" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let norme_1 (ij : int * int) (xy : int * int) : int =\n", " let i, j = ij and x, y = xy in\n", " abs(i - x) + abs(j - y)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Puis la distance définie $d(T[i,j])$ dans l'énoncé :" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val distance : taquin -> int -> int -> int = \n" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let distance (t : taquin) (i : int) (j : int) : int =\n", " let n = Array.length t in\n", " let valeur = t.(i).(j) in\n", " let ifin, jfin = valeur / n, valeur mod n in\n", " norme_1 (i, j) (ifin, jfin)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et enfin la fonction $\\pi_2(T)$ est facile à obtenir :" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val pi_2 : taquin -> int = \n" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let pi_2 (t : taquin) : int =\n", " let n = Array.length t in\n", " let d = ref 0 in\n", " for i = 0 to n - 1 do\n", " for j = 0 to n - 1 do\n", " if t.(i).(j) != 0\n", " then\n", " d := !d + (distance t i j)\n", " done;\n", " done;\n", " !d\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exemples\n", "\n", "On prend l'exemple du texte avec $T_1$.\n", "\n", "- $d(T_1[0,3]) = 6$ ?" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 6\n" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distance t1 0 3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- $\\pi_2(T) = 38$ ?" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 38\n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pi_2 t1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ça semble bon !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec $T_2$ :" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 4\n" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distance t2 0 3;;" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 26\n" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pi_2 t2;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec $T_f$, évidemment $\\pi_2(T) = 0$ puisque $T_f$ est résolue :" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distance tf 0 3;;" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pi_2 tf;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Bonus ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Complexité\n", "- La fonction $\\pi_1(T)$ est en $\\mathcal{O}(N)$ en temps et mémoire, si $N = n^2$ est le nombre d'éléments dans le tableau.\n", "- La fonction $\\pi_2(T)$ est aussi en $\\mathcal{O}(N)$ en temps et mémoire, si $N = n^2$ est le nombre d'éléments dans le tableau." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Autres idées\n", "\n", "- On pourrait faire deux versions améliorées des fonctions $\\pi_1$ et $\\pi_2$ pour calculer $\\pi(s_a(T))$ efficacement en fonction de $\\pi(t)$ et $a \\in \\{N, E, S, O\\}$. Sans écrire le code, elles seraient en temps constant, puisqu'il faut enlever et rajouter une (ou deux) valeurs dans une somme." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- On pourrait implémenter l'algorithme \"ligne à ligne\"." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- On pourrait implémenter d'autres algorithmes de résolution, et les vérifier sur un exemple non trivial." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Conclusion" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voilà pour les deux questions obligatoires de programmation :\n", "\n", "- on a décomposé le problème en sous-fonctions,\n", "- on a essayé d'être fainéant, en réutilisant les 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 un exemple venant du texte,\n", "- et on a essayé d'en faire un peu plus (au début).\n", "\n", "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive." ] } ], "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" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "289px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_position": { "height": "610px", "left": "0px", "right": "1223px", "top": "124px", "width": "249px" }, "toc_section_display": "block", "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 2 }