Table of Contents¶
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
- Texte: Jonglage (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.
- Ce document est un notebook Jupyter, et est open-source sous Licence MIT sur GitHub, comme les autres solutions de textes de modélisation que j'ai écrite cette année.
- L'implémentation sera faite en OCaml, version 4+ :
Sys.command "ocaml -version";;
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 :
- définir une structure de donnée (mot = tableau d'entier),
- écrire une fonction qui vérifie qu'un tel tableau est bien une permutation de $\{0,\dots,n-1\}$,
- transformer une chaîne comme
"5340"en un mot[|5;4;3;0|], - calculer le mot $\omega$ depuis un tel mot,
[|1;0;2;3|], - 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.
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$.
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<p && !permut_bool do
permut_bool := !permut_bool && ( Array.exists (fun x -> x = !i) m );
incr i
done;
!permut_bool;;
(* Complexité temporelle au pire en O(p^2) *)
(* Complexité spatiale en O(p) *)
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 !
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) *)
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.
let echange t i j =
let tmp = t.(i) in
t.(i) <- t.(j);
t.(j) <- tmp;
;;
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 !
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
;;
permutation_aleatoire 10;;
permutation_aleatoire 10;;
permutation_aleatoire 10;;
Cette petite fonction permet de mesurer le temps machine mis pour calculer une fonction f () :
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.
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).
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).
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 :
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;;
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 :
Array.make;;
Array.init;;
let trouve_omega (m : mot) : mot =
let p = Array.length m in
Array.init p (fun i -> ((i + m.(i)) mod p))
;;
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 :
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
;;
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 :
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) *)
transfo_mot "5241";;
Mais on peut aussi accélérer un peu :
Array.init
let transfo_mot (m : string) : mot =
Array.init (String.length m) (fun i -> (entier m.[i]))
(* Complexité temporelle et spatiale en O(p) *)
transfo_mot "5241";;
Test de la permutation¶
let test_permut (m : string) : bool =
est_permut (trouve_omega (transfo_mot m));;
(* Complexité temporelle en O(p) *)
let test_permut_mot (m : mot) : bool =
est_permut (trouve_omega m);;
(* Complexité temporelle en O(p) *)
Quelques exemples :
test_permut "433";; (* pas jonglable *)
test_permut "432";; (* pas jonglable *)
test_permut "441";; (* jonglable *)
test_permut "5241";; (* jonglable *)
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 :
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é *)
;;
test_moyenne_mot [|5;4;3;0|] 3;;
On va finir par quelques exemples :
let test_moyenne (m : string) (b : int) : bool =
test_moyenne_mot (transfo_mot m) b;;
test_moyenne "433" 3;;
test_moyenne "443" 3;;
test_moyenne "432" 3;;
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)$.
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
;;
let partition balles p =
let debut = Array.make p (-1) in
partition_aux balles p debut 0 []
;;
let bp balles p = List.filter test_permut_mot (partition balles p);;
Par exemples :
partition 3 3;;
bp 3 3;;
On voit que l'on retrouve les mots donnés en exemples dans le texte, 441, 423, 333 par exemple :
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 :
List.mem [|4; 3; 3|] (bp 3 3);;
Pour $m=4$, on commence à avoir beaucoup plus de réponses :
partition 4 4;;
List.length (partition 4 4);;
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.