Table des Matières¶
- 1. Agrégation externe de mathématiques, texte d’exercice diffusé en 2012
1. Agrégation externe de mathématiques, texte d’exercice diffusé en 2012¶
1.1 Épreuve de modélisation, option informatique¶
- Ce notebook Jupyter, utilisant OCaml (via le kernel IOcaml), est une correction non officielle d'un texte de modélisation pour l'option informatique de l'agrégation externe de mathématiques.
- Il s'agit du texte public2012-D3.
- Cette tentative de correction partielle a été rédigée par Lilian Besson (sur GitHub ?, sur Bitbucket ?), et est open-source.
- Une autre version, en Python 3, est disponible (aussi sur GitHub).
Feedbacks?¶
- Vous avez trouvé un bug ? → Signalez-le moi svp !, merci d'avance.
- Vous avez une question ? → Posez la svp !
1.2.1 Pour l'option informatique (D) de l'agrégation de mathématiques (en France).¶
Attention : ce document ne prétend pas être LA correction du texte, mais un exemple de solution.
Initialisation du générateur de nombres aléatoires et d'une fonction généralisée d'affichage.
Random.self_init ();;
let print = Format.printf;;
C'est un très bon réflexe d'utiliser print = Format.printf ainsi défini, elle permet d'afficher facilement du texte contenant des paramètres. Pour plus de détails, voir la documentation de Printf.printf et des explications sur Format.
Il suffit de retenir que printf s'utilise comme ça :
print "Chaine de caractere\n";;
print "Chaine avec variables : il faut retenir %%i, %%f, %%s et %%c...\n" ;;
print "\n - %%i pour un entier : %i, " 1 ;;
print "\n - %%f pour un flottant : %f, " 3.1415 ;;
print "\n - %%s pour une string : %s, " "OK?" ;;
print "\n - %%c pour un caractère : %c\n" 'c' ;;
1.3 Jeux de Nim¶
1.3.1 Représentation des configurations¶
Pas besoin d'un type de données trop complexe :
type nim = int array;;
On va d'abord écrire une fonction toute simple qui affiche une configuration, en mode texte.
let print_nim =
Array.iteri (fun case total -> begin
print "\n%i: " case;
for j = 1 to total do
print "! ";
done;
end);;
On peut définir et afficher deux exemples de configuration d'un jeu de Nim, venant de la figure 1.
let a = [| 1; 3; 5 |] ;;
print "\n Configuration (a) de la Figure 1 :";
print_nim a;;
let b = [| 1; 3; 2 |] ;;
print "\n Configuration (b) de la Figure 1 :";
print_nim b;;
1.3.2 Fonction de Sprague-Grundy pour le jeu de Nim¶
Elle est donnée par le corollaire 1. en page 6/7 du texte.
On a besoin du xor ("ou exclusif", cf cette page) bit à bit, obtenu en OCaml avec l'opérateur lxor) :
$$ \gamma(\mathrm{Nim}(x_1, \dots, x_k)) := \bigoplus_{i=1}^{k} x_i = x_1 \oplus \dots \oplus x_k. $$
Petit rappel sur cette fonction xor :
| Entrée | Entrée | Sortie | |
|---|---|---|---|
| False | $\oplus$ | False | = False |
| False | $\oplus$ | True | = True |
| True | $\oplus$ | False | = True |
| True | $\oplus$ | True | = False |
On peut la définir avec l'opérateur infixe :
let somme_nim = ( lxor ) ;;
Ou bien plus simplement :
let somme_nim x y = x lxor y ;;
Quelques exemples, juste pour vérifier.
- D'abord, les valeurs pour les deux entiers
0et1:
somme_nim 0 0;; (** = 0 *)
somme_nim 0 1;; (** = 1 *)
somme_nim 1 0;; (** = 1 *)
somme_nim 1 1;; (** = 0 *)
- Ensuite, d'autres valeurs, juste pour tester :
somme_nim 3 5;; (** 3 xor 5 = 011_2 xor 101_2 = 111_2 = 6 *)
somme_nim 5 9;; (** 5 xor 9 = 0101_2 xor 1001_2 = 1100_2 = 12 *)
somme_nim 12 1;; (** 12 xor 1 = 1100_2 xor 0001_2 = 1101_2 = 13 *)
somme_nim 12 2;; (** 12 xor 2 = 1100_2 xor 0010_2 = 1110_2 = 14 *)
D'après le corollaire 1., il suffit d'appliquer un xor bit à bit à chaque valeur du tableau pour calculer $\gamma$.
En OCaml, on peut faire ça avec une boucle, une fonction récursive, ou plus concisement avec Array.fold_left.
Array.fold_left ;;
Rappel : fold_left prend une fonction f(x,y) et x0 calcule
f( ... f( f( x0, a[0] ), a[1] ), a[n-1] ).
Ici, pour f = somme_nim, il faut donner x0 = 0 pour que le premier calcul f(0, a[0]) = a[0].
let gamma = Array.fold_left somme_nim 0;;
print "\nGamma(a) = %i" (gamma(a));;
print "\nGamma(b) = %i" (gamma(b));;
1.3.3 Déterminer un coup à jouer selon une stratégie gagnante (s'il y en a une)¶
On suit l'algorithme proposé par le texte, qui utilise la fonction $\gamma$ sur la configuration pour savoir s'il y a une stratégie ou non (d'après la proposition 5.), et ensuite si elle existe on doit trouver un coup qui ammene $\gamma$ à 0.
On a d'abord besoin d'une exception pour signaler s'il n'y a pas de stratégie gagnante.
exception Pas_de_Strat_Gagnante;;
1.3.3.1 Stratégie optimale¶
L'algorithme va être assez naïf, depuis une configuration actuelle $c$ :
- si $\gamma(c)$ est $0$, on échoue (
Pas_de_Strat_Gagnante), - sinon, on explore toutes les configurations $c'$ atteignables en un coup depuis $c$, et on choisis la première qui amène à $\gamma(c') = 0$.
let next ?(id=0) config =
let g = gamma config in
(** La prop. 5 donne directement : si g(s_0) = 0 alors échec. *)
if g = 0 then raise Pas_de_Strat_Gagnante;
(** Sinon, on calcul les gamma des fils, et on pointe vers le fils avec un gamma nul. *)
print "\n\nIl y a une stratégie gagnante :\n";
(** En pratique, on aurait pas besoin de calculer chaque fils,
comme on sait que g != 0, et on doit obtenir g' = 0,
on peut s'arreter au premier coup qui donne g' = 0.
*)
let config' = Array.copy config in
let colonne = ref 0 and
nb = ref 1 in
(** Il suffit d'explorer toutes les configurations accessibles depuis l'état actuel : *)
for j = 0 to (Array.length config') - 1 do
for i = 1 to config'.(j) do
config'.(j) <- config'.(j) - i; (** On essaie d'appliquer ce coup. *)
if (gamma config') = 0 then begin
(** On a trouvé un coup gagnant, on le stocke. *)
colonne := j;
nb := i;
end;
config'.(j) <- config'.(j) + i; (** On annule ce coup. *)
done;
done;
(** On applique le coup retenu, dernier coup à donner gamma(c') = 0. *)
print "\nLe joueur courant (numéro %i) doit enlever %i allumette à la %i-ième rangée." id !nb !colonne;
config'.(!colonne) <- config.(!colonne) - !nb; (** On retire nb allumette sur cette colonne. *)
(* assert ((gamma config') = 0); (** Si on veut vérifier *) *)
config'
;;
Note : cette fonction utilise la notation
?(id=0)dans sa définition pour définir un argument optionnel avec valeur par défaut. La fonctionnextpeut être appelée de deux façons :
next a: sans spécifierid, qui vaudra donc0,next ~id:1 a: en spécifiantid=1, qui vaut ici1.Cette astuce n'est pas requise, et c'est un peu de la "frime", inutile de la retenir et de se forcer à s'en servir. Néanmoins, ça peut être utile dans certaines situations.
On peut tester cette fonction sur nos deux configuration a et b :
try
print_nim (next ~id:0 a);
with _ -> print "\n\nBlocage durant la simulation 1 (sur a).";;
try
print_nim (next ~id:1 b);
with _ -> print "\n\nBlocage durant la simulation 2 (sur b).";;
1.3.4. Une stratégie "stupide" : complètement aléatoire¶
On a d'abord besoin de deux fonctions utilitaires :
array_filter, pour filtrer un tableau (commeList.filtermais pour unarray). On fait ça simplement en transformant le tableau en liste, on filtre la liste, puis la liste en tableau. Attention, la taille du tableau n'est pas préservée.- et
choosepour choisir un élément aléatoire (uniforme) dans un tableau. En Python, on auraitrandom.choice. On fait ça simplement en tirant un entierialéatoire uniformément parmi0, ..., n-1pourn = Array.length a, puis en renvoyanta.(i).
(Et oui, la libraire standard de OCaml est assez limitée)...
let array_filter pred a =
Array.of_list (List.filter pred (Array.to_list a));;
let choose a
= a.(Random.int (Array.length a));;
Dans le but de comparer cette fonction next, qui implémente une stratégie optimale, on implémente aussi une stratégie complétement aléatoire ("Dummy player").
La stratégie aléatoire fonctionne en trois étapes :
- trouve les rangées qui ont encore des allumettes (en calculant leurs indices, via
array_filter, dans le tableauindices), - choisi une rangée aléatoirement
i(uniformément), - enlève un nombre aléatoire (uniforme) d'allumette entre
1etxi, pourxile nombre d'allumette dans la rangéei(i.e.,xi = config.(i)).
(** Un adversaire stupide qui joue aléatoirement. *)
let random ?(id=1) config =
print "\nLe joueur courant (numéro %i) joue aléatoirement.\n" id;
let indices = array_filter ( fun i -> (config.(i) > 0) ) (Array.init (Array.length config) (fun i -> i)) in
let i = choose indices in
print "Le joueur (%i) choisi de regarder la %i-ième rangée.\n" id i;
let nbAEnlever = 1 + Random.int config.(i) in
print "Le joueur (%i) choisi d'enlever %i allumettes parmi les %i disponibles.\n" id nbAEnlever config.(i);
let config' = Array.copy config in
config'.(i) <- config.(i) - nbAEnlever;
config';
;;
1.4 Deux exemples, manuellement¶
1.4.1 Premier exemple¶
On peut ainsi faire un exemple de début de partie entre deux joueurs "stupides" :
let a0 = a ;; (* Debut du jeu *)
print_nim a0 ;;
let a1 = random ~id:0 a0 ;;
print_nim a1 ;;
let a2 = random ~id:1 a1 ;;
print_nim a2 ;;
let a3 = random ~id:0 a2 ;;
print_nim a3 ;;
(* ... etc *)
1.4.2 Second exemple¶
On peut aussi faire le même exemple de début de partie entre un joueur "optimal" et un joueur "stupide" :
let c = [| 2; 3; 2 |] ;;
let a0 = c ;; (* Debut du jeu *)
print_nim a0 ;;
let a1 = next ~id:0 a0 ;;
print_nim a1 ;;
let a2 = random ~id:1 a1 ;;
print_nim a2 ;;
let a3 = next ~id:0 a2 ;;
print_nim a3 ;;
(* ... etc *)
1.5 Un bonus : simulation du jeu¶
Maintenant qu'on dispose d'un joueur stupide et d'un joueur optimal, on peut rapidement coder une petite fonction qui les fera s'affronter (même si c'est un peu cruel envers le pauvre joueur "stupide" purement aléatoire !).
exception Perdu of int;;
1.5.1 Simulation de plusieurs étapes¶
La fonction kpas va jouer la partie, en partant de la configuration donnée, en commençant par le joueur id et pour un certain nombre de coups joués (nbPas).
Si on ne donne pas ce nombre de coups, le nombre total d'allumette est utilisé (sachant qu'une partie se termine souvent par une exception Pas_de_Strat_Gagnante lorsque le joueur optimal ne peut plus gagner).
let kpas config id nbPas =
let id = ref id in
let config' = ref (Array.copy config) in
for i = 1 to nbPas do
print "\nTour numéro %i." i;
print_nim !config';
print "\n";
if (Array.fold_left ( + ) 0 !config') = 0 then raise (Perdu !id);
begin
if !id = 0 then (** Le joueur 0 joue bien. *)
config' := next ~id:(!id) !config'
else (** Mais le joueur 1 joue aléatoirement. *)
config' := random ~id:(!id) !config'
end;
id := 1 - !id; (** Juste pour alterner entre 0 et 1 : 0 -> 1, 1 -> 0 *)
done;
!config';
;;
On peut finalement implementer une jolie fonction qui simule en partant du joueur 0 (comme le vrai jeu de Nim) et interprète l'exception renvoyée pour afficher l'issue du jeu :
let simulation config =
(** On compte le nombre total d'allumettes. *)
let n = Array.fold_left (fun i j -> i + j + 1) 0 config in
(** Puis on lance le joueur 0 avec au plus [n] pas. *)
kpas config 0 n;
;;
(** Dernière fonction, [nim], qui lance [simulation] et rattrape les exceptions. *)
let nim a =
let resultat =
(* try ignore (simulation a) with *)
try ignore(simulation a); None with
| Perdu i -> (Some i)
| Pas_de_Strat_Gagnante -> None
in
begin
match resultat with
| None -> print "Blocage à cause de la stratégie optimisée.\n\n"
| Some i -> print "\n ==> Le joueur %i a perdu !\n\n" i
end;
resultat
;;
1.5.2 Exemple :¶
nim a;;
nim b;;
Pas très utile jusqu'ici...
nim c;;
1.5.3 Générer des configurations aléatoires¶
On peut écrire une fonction qui génére une configuration aléatoire, et ensuite lancer notre simulation nim() dessus, pour voir ce que ça donne sur une configuration plus grande.
La fonction randomstart(k, p) va générer une configuration aléatoire :
- avec un nombre de lignes uniforme dans
{1, ..., k}, - et un nombre d'allumettes uniforme dans
{1, ..., p}pour chaque ligne.
let randomstart k p () = Array.init (1 + Random.int k) (fun i -> 1 + Random.int p);;
Par exemple :
let c = randomstart 5 8 ();;
print_nim c;;
Le joueur optimal (d'indice 0) gagne toujours¶
let c = randomstart 5 8 () ;;
print "Configuration random c :" ;;
print_nim c;;
nim c;;
Le joueur stupide peut-il quand-même gagner ?¶
c = randomstart 5 8 () ;;
print "Configuration random c :" ;;
print_nim c ;;
nim c ;;
C'est effectivement possible que le joueur 0 (celui qui commence) perde, même en suivant sa stratégie gagnante.
Si le joueur aléatoire 1 a de la chance...
1.5 Conclusion¶
C'est tout ce que j'avais eu le temps d'implémenter durant les 4h de préparation (c'est un des textes que j'avais préparé en juin 2014, dans les "vraies" conditions en oraux blanc, à l'ENS Cachan, et le code initial était en OCaml mais je n'ai rien changé à part l'écriture du notebook Jupyter).
Quelques remarques :
- durant l'épreuve de modélisation, vous êtes libres de faire ce que vous voulez, la seule partie requise est dans le paragraphe Exercice de programmation (ici, il s'agissait d'implémenter une fonction similaire à
optimal()(cf. plus haut). - les quelques développements supplémentaires traites ci-dessus (stratégie stupide, configuration aléatoire, simulation de jeu), ne sont qu'une suggestion de ce qui pouvait être fait sur ce texte,
- d'autres suggestions sont possibles, si vous avez des idées, envoyez-moi vos notebooks !.
Edit : j'avais une erreur dans mon calcul de
next, corrigée le 11/01/17.
1.6 Attention :¶
Les 35/40 minutes de passage au tableau ne doivent PAS être uniquement consacrée à la présentation de vos expériences sur l'ordinateur !
Il faut aussi :
- faire une introduction générale (citer des mots clés),
- présenter le plan de votre présentation,
- introduire les notations, les objectifs et les résultats donnés par le texte,
- prouver ou exposer des développements theoriques personnels (à choisir parmi la liste proposée, mais pas seulement),
- etc.
C'est tout pour aujourd'hui les amis ! Allez voir d'autres notebooks si vous voulez.