(* 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

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,,n1}
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 ω
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
*) (* # Texte d'oral de modélisation - Agrégation Option Informatique *) (* ## Préparation à l'agrégation - ENS de Rennes, 2018-19 *) (* - *Date* : 21 mai 2019 - *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/) - *Texte*: [Jonglage (public2012-D2.pdf)](http://agreg.org/Textes/public2012-D2.pdf) *) (* ## À 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";; (* > 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. > J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers. *) (* 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. *) (* ---- *) (* ## Question de programmation *) (* La question de programmation pour ce texte était donnée en page 5, et était assez courte : > "Implanter dans l’un des langages de programmation autorisés l’algorithme de test de permutation." *) (* ---- *) (* ## Réponse à l'exercice requis Dans l'ordre, on va : 1. définir une structure de donnée (mot = tableau d'entier), 2. écrire une fonction qui vérifie qu'un tel tableau est bien une permutation de $\{0,\dots,n-1\}$, 3. transformer une chaîne comme `"5340"` en un mot `[|5;4;3;0|]`, 4. calculer le mot $\omega$ depuis un tel mot, `[|1;0;2;3|]`, 5. vérifier que ce mot $\omega$ est une permutation (c'est le **test de permutation**). 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. *) (* ### Structures de données On travaille avec des **mots** représentés comme des tableaux d'entiers. *) (* In[4]: *) type mot = int array ;; (* ### Vérifier qu'un mot est bien une permutation de $\{0,\dots,n-1\}$ 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|)$. 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|$). *) (* #### Fonction quadratique Pour chaque valeur $i\in\{0,\dots,n-1\}$, on parcourt le mot à la recherche d'une valeur $m[j]=i$. *) (* In[6]: *) let est_permut (m : mot) : bool = let p = Array.length m in let permut_bool = ref true in let i = ref 0 in while !i

x = !i) m ); incr i done; !permut_bool;; (* Complexité temporelle au pire en O(p^2) *) (* Complexité spatiale en O(p) *);; (* In[7]: *) est_permut [|3; 5; 1; 2; 4; 0|];; (* true ! *) est_permut [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *);; (* #### Fonction linéaire Au lieu de parcourir les valeurs à trouver et de les chercher, on peut parcourir les valeurs directement ! *) (* In[8]: *) let est_permut_lineaire (m : mot) : bool = let p = Array.length m in let tous_vus = Array.make p false in Array.iter (fun mi -> tous_vus.(mi) <- true ) m; Array.for_all (fun b -> b) tous_vus ;; (* Complexité temporelle au pire en O(p) *) (* Complexité spatiale en O(p) *);; (* In[9]: *) est_permut_lineaire [|3; 5; 1; 2; 4; 0|];; (* true ! *) est_permut_lineaire [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *);; (* #### Comparaison expérimentale On va faire quelques mesures empiriques du temps de calcul, entre la fonction linéaire et la fonction quadratique. Cela illustre aussi l'utilisation de `Sys.time()` pour obtenir le temps système. *) (* In[10]: *) let echange t i j = let tmp = t.(i) in t.(i) <- t.(j); t.(j) <- tmp; ;; (* In[11]: *) Random.self_init ();; (* On génère une permutation aléatoire facilement, en faisant plein d'échanges aléatoires (nombre et localisation aléatoires). **Attention, on essaie pas de generer selon la loi uniforme dans $\Sigma_p$**, c'est beaucoup plus difficile ! *) (* In[12]: *) let permutation_aleatoire p = let m = Array.init p (fun i -> i) in for _ = 1 to Random.int (10*p) do echange m (Random.int p) (Random.int p); done; m ;; (* In[13]: *) permutation_aleatoire 10;; (* In[13]: *) permutation_aleatoire 10;; (* In[13]: *) permutation_aleatoire 10;; (* Cette petite fonction permet de mesurer le temps machine mis pour calculer une fonction `f ()` : *) (* In[14]: *) let timeit f () = let debut = Sys.time () in let res = f () in let fin = Sys.time () in Printf.printf "\nTemps pour calculer f() = %f seconde(s)." (fin -. debut); res ;; (* 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`. *) (* In[17]: *) let test f_est_permut nombre_test taille () = Printf.printf "\nDébut de %i tests de taille %i..." nombre_test taille; flush_all (); for _ = 1 to nombre_test do let m = permutation_aleatoire taille in assert (f_est_permut m); done ;; (* - 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). *) (* In[26]: *) timeit (test est_permut_lineaire 100 1000) ();; timeit (test est_permut_lineaire 100 2000) ();; timeit (test est_permut_lineaire 100 4000) ();; Printf.printf "\n\n\n";; flush_all();; (* - 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). *) (* In[27]: *) timeit (test est_permut 100 1000) ();; timeit (test est_permut 100 2000) ();; timeit (test est_permut 100 4000) ();; Printf.printf "\n\n\n";; flush_all();; (* On peut afficher ces trois valeurs, juste pour mieux les visualiser : *) (* ![](images/Jonglage_mesure_temps_calcul.png) *) (* --- ### Construire le mot $\omega$ Cette fonction est toute simple, et est linéaire en temps et en mémoire. *) (* In[37]: *) let trouve_omega (m : mot) : mot = let p = Array.length m in let omega = Array.make p 0 in for i=0 to (p-1) do omega.(i) <- (i + m.(i)) mod p done; omega;; (* In[36]: *) trouve_omega [|4;4;1|];; trouve_omega [|5;3;4;0|];; (* Note : on peut être plus rapide avec une fonction `Array.init` au lieu de `Array.make` : *) (* In[32]: *) Array.make;; Array.init;; (* In[38]: *) let trouve_omega (m : mot) : mot = let p = Array.length m in Array.init p (fun i -> ((i + m.(i)) mod p)) ;; (* In[ ]: *) trouve_omega [|4;4;1|];; trouve_omega [|5;3;4;0|];; (* #### Transformer une chaîne de caractère "5241" en un `mot` *) (* On a d'abord besoin de convertir un caractère comme `'5'` en un entier `5`. Cela peut se faire manuellement comme ça : *) (* In[ ]: *) let entier (s : char) : int = match s with | '0'-> 0 | '1'-> 1 | '2'-> 2 | '3'-> 3 | '4'-> 4 | '5'-> 5 | '6'-> 6 | '7'-> 7 | '8'-> 8 | '9'-> 9 ;; (* In[ ]: *) let entier (s : char) : int = (int_of_char s) - (int_of_char '0') ;; (* Pour la transformation de la chaîne en un mot, on peut le faire manuellement comme ça : *) (* In[ ]: *) let transfo_mot (m : string) : mot = let p = String.length m in let mot_tableau = Array.make p 0 in for i = 0 to (p - 1) do mot_tableau.(i) <- entier (m.[i]) done; mot_tableau;; (* Complexité temporelle et spatiale en O(p) *);; (* In[ ]: *) transfo_mot "5241";; (* Mais on peut aussi accélérer un peu : *) (* In[ ]: *) Array.init;; (* In[ ]: *) let transfo_mot (m : string) : mot = Array.init (String.length m) (fun i -> (entier m.[i])) (* Complexité temporelle et spatiale en O(p) *);; (* In[47]: *) transfo_mot "5241";; (* ### Test de la permutation *) (* In[48]: *) let test_permut (m : string) : bool = est_permut (trouve_omega (transfo_mot m));; (* Complexité temporelle en O(p) *);; (* In[110]: *) let test_permut_mot (m : mot) : bool = est_permut (trouve_omega m);; (* Complexité temporelle en O(p) *);; (* Quelques exemples : *) (* In[49]: *) test_permut "433";; (* pas jonglable *);; (* In[52]: *) test_permut "432";; (* pas jonglable *);; (* In[53]: *) test_permut "441";; (* jonglable *);; (* In[50]: *) test_permut "5241";; (* jonglable *);; (* In[51]: *) test_permut "9340";; (* jonglable *);; (* ### Test de la moyenne Cet autre test n'est pas une condition nécessaire et suffisante, mais il est rapide à implémenter : *) (* In[67]: *) let test_moyenne_mot (m : mot) (b : int) : bool = let p = Array.length m in let s = ref 0 in for i = 0 to (p - 1) do s:= !s + m.(i) done; !s / p = b (* on teste l'égalité *) ;; (* In[68]: *) test_moyenne_mot [|5;4;3;0|] 3;; (* On va finir par quelques exemples : *) (* In[69]: *) let test_moyenne (m : string) (b : int) : bool = test_moyenne_mot (transfo_mot m) b;; (* In[70]: *) test_moyenne "433" 3;; (* In[71]: *) test_moyenne "443" 3;; (* In[72]: *) test_moyenne "432" 3;; (* In[73]: *) test_moyenne "5430" 3;; (* ---- ## Bonus ? *) (* ### Complexité - 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|)$. *) (* ### Autres idées *) (* 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)$. *) (* In[114]: *) let rec partition_aux balles p debut somme acc = let m = balles * p in let manque = Array.fold_left (fun c x -> if x = (-1) then c + 1 else c) 0 debut in if manque = 1 then let t = Array.copy debut in t.(p - 1) <- m - somme; t :: acc else let nacc = ref acc in for k = m - somme downto 0 do let ndebut = Array.copy debut in ndebut.(p - manque) <- k; nacc := partition_aux balles p ndebut (somme + k) !nacc done; !nacc ;; (* In[115]: *) let partition balles p = let debut = Array.make p (-1) in partition_aux balles p debut 0 [] ;; (* In[116]: *) let bp balles p = List.filter test_permut_mot (partition balles p);; (* Par exemples : *) (* In[117]: *) partition 3 3;; (* In[118]: *) bp 3 3;; (* On voit que l'on retrouve les mots donnés en exemples dans le texte, 441, 423, 333 par exemple : *) (* In[124]: *) List.mem [|4; 4; 1|] (bp 3 3);; List.mem [|4; 2; 3|] (bp 3 3);; List.mem [|3; 3; 3|] (bp 3 3);; (* Et le mot 433 n'est pas dans la liste calculée : *) (* In[125]: *) List.mem [|4; 3; 3|] (bp 3 3);; ;; (* Pour $m=4$, on commence à avoir beaucoup plus de réponses : *) (* In[121]: *) partition 4 4;; List.length (partition 4 4);; (* In[123]: *) bp 4 4;; List.length (bp 4 4);; (* ---- ## Conclusion *) (* Voilà pour les deux questions obligatoires de programmation : - on a décomposé le problème en sous-fonctions, - on a essayé d'être fainéant, en réutilisant les sous-fonctions, - on a fait des exemples et *on les garde* dans ce qu'on présente au jury, - on a testé la fonction exigée sur un exemple venant du texte, - et on a essayé d'en faire un peu plus (au début). > Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive. *)