{ "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* : 3 avril 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: Annale 2006, \"Sudoku\"" ] }, { "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": 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": [ "----\n", "## Question de programmation\n", "La question de programmation pour ce texte était donnée au tout début, en page 2 :\n", "\n", "> « Écrire une fonction prenant pour paramètres un entier, $p \\geq 1$, et un tableau carré de côté $p$ (donc de taille $p^2$) d'entiers, $T$, et renvoyant un booléen disant si ce tableau est un carré latin, c'est-à-dire contenant dans chaque ligne et chaque colonne une et une seule fois chaque entier de $1$ à $p$.\n", "\n", "Mathématiquement, si $N_p := \\{1,\\dots,p\\}$, cela donne un prédicat $\\mathrm{estCarreLatin}_p(T)$ sur un tableau $T$ :\n", "$$\n", "\\mathrm{estCarreLatin}_p(T) \\Longleftrightarrow\n", "\\forall i \\in N_p, \\left\\{ T_{i,j} : j \\in N_p \\right\\} = N_p\n", "\\;\\text{and}\\;\n", "\\forall j \\in N_p, \\left\\{ T_{i,j} : i \\in N_p \\right\\} = N_p\n", "$$\n", "\n", "> « En prenant $p = n^2$ on obtient une partie des contraintes d'admissibilité d'une grille complète de Su Doku, mais il reste encore à vérifier la contrainte sur les petits carrés. »\n", "\n", "Pour l'annecdote historique, cette idée de carré latin date vraiment de l'époque romaine antique. On a trouvé à Pompeï des carrés latins de taille $4$ ou $5$ !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Réponse à l'exercice requis\n", "C'est assez rapide :\n", "\n", "1. On écrit une fonction qui permet d'extraire une ligne ou une colonne d'un tableau $T$,\n", "2. On écrit ensuite une fonction qui permet de vérifier si un tableau de $p$ entiers contient exactement $N_p = \\{1, \\dots, p\\}$,\n", "3. Enfin, on vérifie toutes les contraintes." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Remarque:* On suppose que tous les tableaux considérés sont :\n", "> - **non vides**\n", "> - et **carrés**\n", "> On ne vérifie pas ces deux points." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val ligne : int -> 'a array array -> int -> 'a array =