(* This OCaml script was exported from a Jupyter notebook using an open-source software (under the MIT License) written by @Naereen from https://github.com/Naereen/Jupyter-Notebook-OCaml This software is still in development, please notify me of a bug at https://github.com/Naereen/Jupyter-Notebook-OCaml/issues/new if you find one *) (* # Table of Contents
*) (* # Texte d'oral de modélisation - Agrégation Option Informatique ## Préparation à l'agrégation - ENS de Rennes, 2016-17 - *Date* : 3 avril 2017 - *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/) - *Texte*: Annale 2006, "Sudoku" *) (* ## À propos de ce document - 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/). - 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. - L'implémentation sera faite en OCaml, version 4+ : *) (* In[1]: *) Sys.command "ocaml -version";; (* ---- ## Question de programmation La question de programmation pour ce texte était donnée au tout début, en page 2 : > « É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$. Mathématiquement, si $N_p := \{1,\dots,p\}$, cela donne un prédicat $\mathrm{estCarreLatin}_p(T)$ sur un tableau $T$ : $$ \mathrm{estCarreLatin}_p(T) \Longleftrightarrow \forall i \in N_p, \left\{ T_{i,j} : j \in N_p \right\} = N_p \;\text{and}\; \forall j \in N_p, \left\{ T_{i,j} : i \in N_p \right\} = N_p $$ > « 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. » 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$ ! *) (* ---- ## Réponse à l'exercice requis C'est assez rapide : 1. On écrit une fonction qui permet d'extraire une ligne ou une colonne d'un tableau $T$, 2. On écrit ensuite une fonction qui permet de vérifier si un tableau de $p$ entiers contient exactement $N_p = \{1, \dots, p\}$, 3. Enfin, on vérifie toutes les contraintes. *) (* > *Remarque:* On suppose que tous les tableaux considérés sont : > - **non vides** > - et **carrés** > On ne vérifie pas ces deux points. *) (* In[2]: *) let ligne p t i = Array.init p (fun j -> t.(i).(j)) ;; (* t.(i) marche aussi bien ! *) let colonne p t j = Array.init p (fun i -> t.(i).(j)) ;; (* On a besoin de savoir si un tableau de booléens sont tous vrais ou pas. On peut utiliser la fonction déjà existante, `Array.for_all`, ou bien un `Array.fold_left`, ou une implémentation manuelle. *) (* In[3]: *) let tousVrai tab = let res = ref true in for i = 0 to (Array.length tab) - 1 do res := !res && tab.(i) done; !res ;; (* In[4]: *) let tousVrai = Array.fold_left (&&) true;; (* Array.for_all marche aussi bien ! *);; (* Ca permet de facilement vérifier si un tableau `tab` de taille $p$ est exactement $N_p = \{1,\dots,p\}$, en temps linéaire (c'est optimal) en $p$. 1. On ajoute un test que tous les entiers soient bien entre $1$ et $p$, 2. puis on fait ce test en $\mathcal{O}(\# tab)$, en créant est un tableau `estLa` de taille $p$, remplis de `false`. En bouclant sur $t$, on remplit $\texttt{tab}[i]$ à `true` dans `estLa` (en fait, `tab(i) - 1` car les indices sont entre $0$ et $p-1$). A la fin, si le tableau `estLa` est rempli de `true`, alors on a vu tous les entiers de $N_p$ une et une seule fois. *) (* In[5]: *) let estNp p tab = if tousVrai (Array.map (fun x -> (1 <= x) && (x <= p)) tab) then begin let estLa = Array.make p false in for i = 0 to p - 1 do estLa.(tab.(i) - 1) <- true done; tousVrai estLa end else false ;; (* On va adopter une méthode naïve mais simple à écrire : - on construit deux tableaux de $p$ booléens, - on les remplit des contraintes pour les $p$ lignes et les $p$ colonnes, - et on les vérifie avec `tousVrai`. *) (* In[6]: *) let contraintes_lignes p t = tousVrai (Array.init p (fun i -> estNp p (ligne p t i) )) ;; (* In[7]: *) let contraintes_colonnes p t = tousVrai (Array.init p (fun j -> estNp p (colonne p t j) )) ;; (* In[8]: *) let carre_latin p t = (contraintes_lignes p t) && (contraintes_colonnes p t) ;; (* ### Une autre approche Plutôt que d'écrire une fonction pour extraire une colonne, et deux fonction qui vérifies les contraintes sur les lignes et les colonnes, on remarque le fait suivant : > « Les colonnes de $t$ sont les lignes de $t^T$, la matrice transposée de $t$ ». Donc pas besoin de savoir extraire les colonnes, dès qu'on a écrit `contraintes_lignes`, on peut avoir les contraintes sur les colonnes facilement. Pour calculer la transposée, une approche simple utilise deux boucles `for` : *) (* In[9]: *) let transpose_for p tab = let tab2 = Array.make_matrix p p 0 in for i = 0 to p - 1 do for j = 0 to p - 1 do tab2.(i).(j) <- tab.(j).(i); done; done; tab2 ;; (* On peut rapidement vérifier sur un exemple, $$ \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}^{T} = \begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix}. $$ *) (* In[10]: *) transpose_for 2 [| [|1; 2|]; [|3; 4|] |];; (* Notez qu'on peut faire mieux, sans boucles `for`, avec deux `Array.init` imbriqués : *) (* In[11]: *) let transpose p tab = Array.init p (fun i -> (Array.init p (fun j -> tab.(j).(i))));; (* In[12]: *) transpose 2 [| [|1; 2|]; [|3; 4|] |];; (* Et donc : *) (* In[13]: *) let carre_latin2 p t = (contraintes_lignes p t) && (contraintes_lignes p (transpose p t)) ;; (* ### Un mauvais exemple On va prendre le premier carré de taille $p = 3$ dans le problème de Su Doku donné en figure 1 de l'énoncé.