{ "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" ] }, { "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 =