{ "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, 2018-19
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  Vérifier qu'un mot est bien une permutation de {0,…,n−1}\" role=\"presentation\">{0,…,𝑛−1}{0,…,n−1}
1.4.2.1  Fonction quadratique
1.4.2.2  Fonction linéaire
1.4.2.3  Comparaison expérimentale
1.4.3  Construire le mot ω\" role=\"presentation\">𝜔ω
1.4.3.1  Transformer une chaîne de caractère \"5241\" en un mot
1.4.4  Test de la permutation
1.4.5  Test de la moyenne
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, 2018-19" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- *Date* : 21 mai 2019\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: [Jonglage (public2012-D2.pdf)](http://agreg.org/Textes/public2012-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": [ "Merci à Pierre et Clarence, élèves de la préparation à l'agrégation en 2018/2019, de m'avoir autorisé à utiliser une partie de leur implémentation pour cette (proposition de) correction." ] }, { "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 dans l’un des langages de programmation autorisés l’algorithme de test de permutation.\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Réponse à l'exercice requis\n", "\n", "Dans l'ordre, on va :\n", "\n", "1. définir une structure de donnée (mot = tableau d'entier),\n", "2. écrire une fonction qui vérifie qu'un tel tableau est bien une permutation de $\\{0,\\dots,n-1\\}$,\n", "3. transformer une chaîne comme `\"5340\"` en un mot `[|5;4;3;0|]`,\n", "4. calculer le mot $\\omega$ depuis un tel mot, `[|1;0;2;3|]`,\n", "5. vérifier que ce mot $\\omega$ est une permutation (c'est le **test de permutation**).\n", "\n", "En bonus, on implémente aussi le **test de moyenne**, et on illustre le bon fonctionnement de notre implémentation sur les exemples du texte." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Structures de données\n", "\n", "On travaille avec des **mots** représentés comme des tableaux d'entiers." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type mot = int array\n" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type mot = int array ;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Vérifier qu'un mot est bien une permutation de $\\{0,\\dots,n-1\\}$\n", "\n", "On présente deux implémentations, la première n'est pas très réfléchie et se trouve être avoir une complexité temporelle en $\\mathcal{O}(|mot|^2)$, tandis que la seconde est plus réfléchie et fonctionne en temps linéaire $\\mathcal{O}(|mot|)$.\n", "\n", "On va supposer que chaque valeur du mot d'entrée est bien dans $\\{0,\\dots,n-1\\}$, et on vérifie simplement que chaque valeur est présente une et une seule fois (si $n=|mot|$)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Fonction quadratique\n", "\n", "Pour chaque valeur $i\\in\\{0,\\dots,n-1\\}$, on parcourt le mot à la recherche d'une valeur $m[j]=i$." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_permut : mot -> bool = \n" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_permut (m : mot) : bool =\n", " let p = Array.length m in\n", " let permut_bool = ref true in\n", " let i = ref 0 in\n", " while !i

x = !i) m );\n", " incr i\n", " done;\n", " !permut_bool;;\n", "(* Complexité temporelle au pire en O(p^2) *)\n", "(* Complexité spatiale en O(p) *)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_permut [|3; 5; 1; 2; 4; 0|];; (* true ! *)\n", "est_permut [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Fonction linéaire\n", "\n", "Au lieu de parcourir les valeurs à trouver et de les chercher, on peut parcourir les valeurs directement !" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_permut_lineaire : mot -> bool = \n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let est_permut_lineaire (m : mot) : bool =\n", " let p = Array.length m in\n", " let tous_vus = Array.make p false in\n", " Array.iter (fun mi ->\n", " tous_vus.(mi) <- true\n", " ) m;\n", " Array.for_all (fun b -> b) tous_vus\n", ";;\n", "(* Complexité temporelle au pire en O(p) *)\n", "(* Complexité spatiale en O(p) *)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_permut_lineaire [|3; 5; 1; 2; 4; 0|];; (* true ! *)\n", "est_permut_lineaire [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Comparaison expérimentale\n", "\n", "On va faire quelques mesures empiriques du temps de calcul, entre la fonction linéaire et la fonction quadratique.\n", "Cela illustre aussi l'utilisation de `Sys.time()` pour obtenir le temps système." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val echange : 'a array -> int -> int -> unit = \n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let echange t i j =\n", " let tmp = t.(i) in\n", " t.(i) <- t.(j);\n", " t.(j) <- tmp;\n", ";;" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Random.self_init ();;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On génère une permutation aléatoire facilement, en faisant plein d'échanges aléatoires (nombre et localisation aléatoires).\n", "**Attention, on essaie pas de generer selon la loi uniforme dans $\\Sigma_p$**, c'est beaucoup plus difficile !" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val permutation_aleatoire : int -> int array = \n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let permutation_aleatoire p =\n", " let m = Array.init p (fun i -> i) in\n", " for _ = 1 to Random.int (10*p) do\n", " echange m (Random.int p) (Random.int p);\n", " done;\n", " m\n", ";;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int array = [|1; 3; 7; 9; 8; 4; 5; 0; 2; 6|]\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "permutation_aleatoire 10;;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int array = [|1; 3; 7; 9; 8; 4; 5; 0; 2; 6|]\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "permutation_aleatoire 10;;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int array = [|1; 3; 7; 9; 8; 4; 5; 0; 2; 6|]\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "permutation_aleatoire 10;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Cette petite fonction permet de mesurer le temps machine mis pour calculer une fonction `f ()` :" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val timeit : (unit -> 'a) -> unit -> 'a = \n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let timeit f () =\n", " let debut = Sys.time () in\n", " let res = f () in\n", " let fin = Sys.time () in\n", " Printf.printf \"\\nTemps pour calculer f() = %f seconde(s).\" (fin -. debut);\n", " res\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va s'en servir avec cette fonction, qui test `nombre_test` fois la vérification `f_est_permut` sur une permutation aléatoire de taille `taille`." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val test : (int array -> bool) -> int -> int -> unit -> unit = \n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let test f_est_permut nombre_test taille () =\n", " Printf.printf \"\\nDébut de %i tests de taille %i...\" nombre_test taille;\n", " flush_all ();\n", " for _ = 1 to nombre_test do\n", " let m = permutation_aleatoire taille in\n", " assert (f_est_permut m);\n", " done\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Pour la fonction qui devrait être linéaire, on observe bien un temps de calcul qui croît linéairement avec la taille de l'entrée ($p=1000,2000,4000$ ici)." ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "Début de 100 tests de taille 1000...\n", "Temps pour calculer f() = 0.211866 seconde(s).\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "Début de 100 tests de taille 2000...\n", "Temps pour calculer f() = 0.316790 seconde(s).\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "Début de 100 tests de taille 4000...\n", "Temps pour calculer f() = 0.574821 seconde(s).\n", "\n", "\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit (test est_permut_lineaire 100 1000) ();;\n", "timeit (test est_permut_lineaire 100 2000) ();;\n", "timeit (test est_permut_lineaire 100 4000) ();;\n", "\n", "Printf.printf \"\\n\\n\\n\";;\n", "flush_all();;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Pour la fonction qui devrait être quadratique, on observe bien un temps de calcul qui croît quadratiquement avec la taille de l'entrée ($p=1000,2000,4000$ ici)." ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "Début de 100 tests de taille 1000...\n", "Temps pour calculer f() = 1.389953 seconde(s).\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "Début de 100 tests de taille 2000...\n", "Temps pour calculer f() = 5.122529 seconde(s).\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "Début de 100 tests de taille 4000...\n", "Temps pour calculer f() = 20.058526 seconde(s).\n", "\n", "\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit (test est_permut 100 1000) ();;\n", "timeit (test est_permut 100 2000) ();;\n", "timeit (test est_permut 100 4000) ();;\n", "\n", "Printf.printf \"\\n\\n\\n\";;\n", "flush_all();;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut afficher ces trois valeurs, juste pour mieux les visualiser :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](images/Jonglage_mesure_temps_calcul.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "### Construire le mot $\\omega$\n", "Cette fonction est toute simple, et est linéaire en temps et en mémoire." ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val trouve_omega : mot -> mot = \n" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let trouve_omega (m : mot) : mot =\n", " let p = Array.length m in\n", " let omega = Array.make p 0 in\n", " for i=0 to (p-1) do\n", " omega.(i) <- (i + m.(i)) mod p\n", " done;\n", " omega;;" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot = [|1; 2; 0|]\n" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : mot = [|1; 0; 2; 3|]\n" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "trouve_omega [|4;4;1|];;\n", "trouve_omega [|5;3;4;0|];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note : on peut être plus rapide avec une fonction `Array.init` au lieu de `Array.make` :" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int -> 'a -> 'a array = \n" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int -> (int -> 'a) -> 'a array = \n" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Array.make;;\n", "Array.init;;" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val trouve_omega : mot -> mot = \n" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let trouve_omega (m : mot) : mot =\n", " let p = Array.length m in\n", " Array.init p (fun i -> ((i + m.(i)) mod p))\n", ";;" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot = [|1; 2; 0|]\n" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : mot = [|1; 0; 2; 3|]\n" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "trouve_omega [|4;4;1|];;\n", "trouve_omega [|5;3;4;0|];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Transformer une chaîne de caractère \"5241\" en un `mot`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On a d'abord besoin de convertir un caractère comme `'5'` en un entier `5`.\n", "Cela peut se faire manuellement comme ça :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "File \"[41]\", line 1, characters 30-162:\n", "Warning 8: this pattern-matching is not exhaustive.\n", "Here is an example of a case that is not matched:\n", "'a'\n" ] }, { "data": { "text/plain": [ "val entier : char -> int = \n" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let entier (s : char) : int = match s with\n", " | '0'-> 0\n", " | '1'-> 1\n", " | '2'-> 2\n", " | '3'-> 3\n", " | '4'-> 4\n", " | '5'-> 5\n", " | '6'-> 6\n", " | '7'-> 7\n", " | '8'-> 8\n", " | '9'-> 9\n", ";;" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val entier : char -> int = \n" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let entier (s : char) : int =\n", " (int_of_char s) - (int_of_char '0')\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour la transformation de la chaîne en un mot, on peut le faire manuellement comme ça :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val transfo_mot : string -> mot = \n" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let transfo_mot (m : string) : mot =\n", " let p = String.length m in\n", " let mot_tableau = Array.make p 0 in\n", " for i = 0 to (p - 1) do\n", " mot_tableau.(i) <- entier (m.[i])\n", " done;\n", " mot_tableau;;\n", "(* Complexité temporelle et spatiale en O(p) *)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot = [|5; 2; 4; 1|]\n" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "transfo_mot \"5241\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Mais on peut aussi accélérer un peu :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int -> (int -> 'a) -> 'a array = \n" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Array.init" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val transfo_mot : string -> mot = \n" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let transfo_mot (m : string) : mot =\n", " Array.init (String.length m) (fun i -> (entier m.[i]))\n", "(* Complexité temporelle et spatiale en O(p) *)" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot = [|5; 2; 4; 1|]\n" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "transfo_mot \"5241\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Test de la permutation" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val test_permut : string -> bool = \n" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let test_permut (m : string) : bool =\n", " est_permut (trouve_omega (transfo_mot m));;\n", "(* Complexité temporelle en O(p) *)" ] }, { "cell_type": "code", "execution_count": 110, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val test_permut_mot : mot -> bool = \n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let test_permut_mot (m : mot) : bool =\n", " est_permut (trouve_omega m);;\n", "(* Complexité temporelle en O(p) *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quelques exemples :" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_permut \"433\";; (* pas jonglable *)" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_permut \"432\";; (* pas jonglable *)" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_permut \"441\";; (* jonglable *)" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_permut \"5241\";; (* jonglable *)" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_permut \"9340\";; (* jonglable *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Test de la moyenne\n", "\n", "Cet autre test n'est pas une condition nécessaire et suffisante, mais il est rapide à implémenter :" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val test_moyenne_mot : mot -> int -> bool = \n" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let test_moyenne_mot (m : mot) (b : int) : bool =\n", " let p = Array.length m in\n", " let s = ref 0 in\n", " for i = 0 to (p - 1) do\n", " s:= !s + m.(i)\n", " done;\n", " !s / p = b (* on teste l'égalité *)\n", ";;" ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_moyenne_mot [|5;4;3;0|] 3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va finir par quelques exemples :" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val test_moyenne : string -> int -> bool = \n" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let test_moyenne (m : string) (b : int) : bool =\n", " test_moyenne_mot (transfo_mot m) b;;" ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_moyenne \"433\" 3;;" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_moyenne \"443\" 3;;" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_moyenne \"432\" 3;;" ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "test_moyenne \"5430\" 3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Bonus ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Complexité\n", "- Sauf la fonction volontairement écrite pour être quadratique, toutes les fonctions suivantes sont linéaires, c'est à dire qu'elles ont une complexité en temps *et en mémoire* bornée par $\\mathcal{O}(|mot|)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Autres idées" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction suivante donne la liste des mots de taille `p` commençant par `debut` (dont la somme des coefficients vaut `somme`) concaténée avec `acc`, en temps $\\mathcal{O}(m^p)$." ] }, { "cell_type": "code", "execution_count": 114, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val partition_aux :\n", " int -> int -> int array -> int -> int array list -> int array list = \n" ] }, "execution_count": 114, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec partition_aux balles p debut somme acc =\n", " let m = balles * p in\n", " let manque = Array.fold_left (fun c x -> if x = (-1) then c + 1 else c) 0 debut in\n", " if manque = 1 then\n", " let t = Array.copy debut in\n", " t.(p - 1) <- m - somme;\n", " t :: acc\n", " else\n", " let nacc = ref acc in\n", " for k = m - somme downto 0 do\n", " let ndebut = Array.copy debut in\n", " ndebut.(p - manque) <- k;\n", " nacc := partition_aux balles p ndebut (somme + k) !nacc\n", " done;\n", " !nacc\n", ";;" ] }, { "cell_type": "code", "execution_count": 115, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val partition : int -> int -> int array list = \n" ] }, "execution_count": 115, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let partition balles p =\n", " let debut = Array.make p (-1) in\n", " partition_aux balles p debut 0 []\n", ";;" ] }, { "cell_type": "code", "execution_count": 116, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val bp : int -> int -> mot list = \n" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let bp balles p = List.filter test_permut_mot (partition balles p);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemples :" ] }, { "cell_type": "code", "execution_count": 117, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "- : int array list =\n", "[[|0; 0; 9|]; [|0; 1; 8|]; [|0; 2; 7|]; [|0; 3; 6|]; [|0; 4; 5|];\n", " [|0; 5; 4|]; [|0; 6; 3|]; [|0; 7; 2|]; [|0; 8; 1|]; [|0; 9; 0|];\n", " [|1; 0; 8|]; [|1; 1; 7|]; [|1; 2; 6|]; [|1; 3; 5|]; [|1; 4; 4|];\n", " [|1; 5; 3|]; [|1; 6; 2|]; [|1; 7; 1|]; [|1; 8; 0|]; [|2; 0; 7|];\n", " [|2; 1; 6|]; [|2; 2; 5|]; [|2; 3; 4|]; [|2; 4; 3|]; [|2; 5; 2|];\n", " [|2; 6; 1|]; [|2; 7; 0|]; [|3; 0; 6|]; [|3; 1; 5|]; [|3; 2; 4|];\n", " [|3; 3; 3|]; [|3; 4; 2|]; [|3; 5; 1|]; [|3; 6; 0|]; [|4; 0; 5|];\n", " [|4; 1; 4|]; [|4; 2; 3|]; [|4; 3; 2|]; [|4; 4; 1|]; [|4; 5; 0|];\n", " [|5; 0; 4|]; [|5; 1; 3|]; [|5; 2; 2|]; [|5; 3; 1|]; [|5; 4; 0|];\n", " [|6; 0; 3|]; [|6; 1; 2|]; [|6; 2; 1|]; [|6; 3; 0|]; [|7; 0; 2|];\n", " [|7; 1; 1|]; [|7; 2; 0|]; [|8; 0; 1|]; [|8; 1; 0|]; [|9; 0; 0|]]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" } ], "source": [ "partition 3 3;;" ] }, { "cell_type": "code", "execution_count": 118, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot list =\n", "[[|0; 0; 9|]; [|0; 1; 8|]; [|0; 3; 6|]; [|0; 4; 5|]; [|0; 6; 3|];\n", " [|0; 7; 2|]; [|0; 9; 0|]; [|1; 1; 7|]; [|1; 2; 6|]; [|1; 4; 4|];\n", " [|1; 5; 3|]; [|1; 7; 1|]; [|1; 8; 0|]; [|2; 0; 7|]; [|2; 2; 5|];\n", " [|2; 3; 4|]; [|2; 5; 2|]; [|2; 6; 1|]; [|3; 0; 6|]; [|3; 1; 5|];\n", " [|3; 3; 3|]; [|3; 4; 2|]; [|3; 6; 0|]; [|4; 1; 4|]; [|4; 2; 3|];\n", " [|4; 4; 1|]; [|4; 5; 0|]; [|5; 0; 4|]; [|5; 2; 2|]; [|5; 3; 1|];\n", " [|6; 0; 3|]; [|6; 1; 2|]; [|6; 3; 0|]; [|7; 1; 1|]; [|7; 2; 0|];\n", " [|8; 0; 1|]; [|9; 0; 0|]]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bp 3 3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On voit que l'on retrouve les mots donnés en exemples dans le texte, 441, 423, 333 par exemple :" ] }, { "cell_type": "code", "execution_count": 124, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.mem [|4; 4; 1|] (bp 3 3);;\n", "List.mem [|4; 2; 3|] (bp 3 3);;\n", "List.mem [|3; 3; 3|] (bp 3 3);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et le mot 433 n'est pas dans la liste calculée :" ] }, { "cell_type": "code", "execution_count": 125, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 125, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.mem [|4; 3; 3|] (bp 3 3);;\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour $m=4$, on commence à avoir beaucoup plus de réponses :" ] }, { "cell_type": "code", "execution_count": 121, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "- : int array list =\n", "[[|0; 0; 0; 16|]; [|0; 0; 1; 15|]; [|0; 0; 2; 14|]; [|0; 0; 3; 13|];\n", " [|0; 0; 4; 12|]; [|0; 0; 5; 11|]; [|0; 0; 6; 10|]; [|0; 0; 7; 9|];\n", " [|0; 0; 8; 8|]; [|0; 0; 9; 7|]; [|0; 0; 10; 6|]; [|0; 0; 11; 5|];\n", " [|0; 0; 12; 4|]; [|0; 0; 13; 3|]; [|0; 0; 14; 2|]; [|0; 0; 15; 1|];\n", " [|0; 0; 16; 0|]; [|0; 1; 0; 15|]; [|0; 1; 1; 14|]; [|0; 1; 2; 13|];\n", " [|0; 1; 3; 12|]; [|0; 1; 4; 11|]; [|0; 1; 5; 10|]; [|0; 1; 6; 9|];\n", " [|0; 1; 7; 8|]; [|0; 1; 8; 7|]; [|0; 1; 9; 6|]; [|0; 1; 10; 5|];\n", " [|0; 1; 11; 4|]; [|0; 1; 12; 3|]; [|0; 1; 13; 2|]; [|0; 1; 14; 1|];\n", " [|0; 1; 15; 0|]; [|0; 2; 0; 14|]; [|0; 2; 1; 13|]; [|0; 2; 2; 12|];\n", " [|0; 2; 3; 11|]; [|0; 2; 4; 10|]; [|0; 2; 5; 9|]; [|0; 2; 6; 8|];\n", " [|0; 2; 7; 7|]; [|0; 2; 8; 6|]; [|0; 2; 9; 5|]; [|0; 2; 10; 4|];\n", " [|0; 2; 11; 3|]; [|0; 2; 12; 2|]; [|0; 2; 13; 1|]; [|0; 2; 14; 0|];\n", " [|0; 3; 0; 13|]; [|0; 3; 1; 12|]; [|0; 3; 2; 11|]; [|0; 3; 3; 10|];\n", " [|0; 3; 4; 9|]; [|0; 3; 5; 8|]; [|0; 3; 6; 7|]; [|0; 3; 7; 6|];\n", " [|0; 3; 8; 5|]; [|0; 3; 9; 4|]; [|0; 3; 10; 3|]; [|0; 3; 11; ...|]; ...]\n" ] }, "execution_count": 121, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 969\n" ] }, "execution_count": 121, "metadata": {}, "output_type": "execute_result" } ], "source": [ "partition 4 4;;\n", "\n", "List.length (partition 4 4);;" ] }, { "cell_type": "code", "execution_count": 123, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot list =\n", "[[|0; 0; 0; 16|]; [|0; 0; 1; 15|]; [|0; 0; 4; 12|]; [|0; 0; 5; 11|];\n", " [|0; 0; 8; 8|]; [|0; 0; 9; 7|]; [|0; 0; 12; 4|]; [|0; 0; 13; 3|];\n", " [|0; 0; 16; 0|]; [|0; 1; 1; 14|]; [|0; 1; 3; 12|]; [|0; 1; 5; 10|];\n", " [|0; 1; 7; 8|]; [|0; 1; 9; 6|]; [|0; 1; 11; 4|]; [|0; 1; 13; 2|];\n", " [|0; 1; 15; 0|]; [|0; 2; 0; 14|]; [|0; 2; 3; 11|]; [|0; 2; 4; 10|];\n", " [|0; 2; 7; 7|]; [|0; 2; 8; 6|]; [|0; 2; 11; 3|]; [|0; 2; 12; 2|];\n", " [|0; 4; 0; 12|]; [|0; 4; 1; 11|]; [|0; 4; 4; 8|]; [|0; 4; 5; 7|];\n", " [|0; 4; 8; 4|]; [|0; 4; 9; 3|]; [|0; 4; 12; 0|]; [|0; 5; 1; 10|];\n", " [|0; 5; 3; 8|]; [|0; 5; 5; 6|]; [|0; 5; 7; 4|]; [|0; 5; 9; 2|];\n", " [|0; 5; 11; 0|]; [|0; 6; 0; 10|]; [|0; 6; 3; 7|]; [|0; 6; 4; 6|];\n", " [|0; 6; 7; 3|]; [|0; 6; 8; 2|]; [|0; 8; 0; 8|]; [|0; 8; 1; 7|];\n", " [|0; 8; 4; 4|]; [|0; 8; 5; 3|]; [|0; 8; 8; 0|]; [|0; 9; 1; 6|];\n", " [|0; 9; 3; 4|]; [|0; 9; 5; ...|]; ...]\n" ] }, "execution_count": 123, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : int = 369\n" ] }, "execution_count": 123, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bp 4 4;;\n", "\n", "List.length (bp 4 4);;" ] }, { "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 }