Forum de mathématiques - Bibm@th.net

capesman

Modérateur

Inscription : 15-08-2016

Messages : 152

[Info 26] - Exemples d'algorithmes utilisant un générateur...

Bonjour,

  Cette discussion est ouverte pour parler de la leçon du capes de mathématiques : Exemples d'algorithmes utilisant un générateur de nombres aléatoires.

Capesman.

Dernière modification par capesman (27-11-2018 22:01:32)

capesman

Modérateur

Inscription : 15-08-2016

Messages : 152

Re : [Info 26] - Exemples d'algorithmes utilisant un générateur...

Bonjour,

  Le rapport du jury 2018 donne des pistes pour cette leçon :

"Il  s’agit  dans  cette  leçon  de  présenter  l’utilisation  de  générateurs  pseudo-aléatoires  dans  les algorithmes.  Toute  discussion lancée  sur  le  degré  d’aléatoire  de  ces  générateurs  est explicitement hors sujet. On pourra supposer dans toute la leçon qu’on dispose d’une fonction random() qui fournit un réel aléatoire de l’intervalle [0,1] selon une loi uniforme.

On pourra d’abord présenter des algorithmes qui permettent à partir de cette fonction de fournir un entier aléatoire entre 0 et $N-1$ selon une loi uniforme, puis s’intéresser à la construction d’objets mathématiques classiques, comme un tableau de taille $M$ de nombres entiers aléatoires entre 0 et $N-1$. On pourra aussi s’intéresser à des exemples plus complexes, par exemple utiliser Python pour  créer  une  permutation  aléatoire  des  entiers  de  l’intervalle $[0,N-1]$,  etc.  On  peut  aussi envisager le lien avec la géométrie et utiliser Scratch pour dessiner des figures aléatoires dans le plan.

On  pourra  ensuite  utiliser  le  générateur  aléatoire  dans  le  cadre  d’algorithmes  classiques.  Par exemple,  certains  tris  sont  plus  efficaces  si  on  mélange  aléatoirement  les  données  avant  de  les trier.

Une autre utilisation consiste à tester l’efficacité d’algorithmes classiques sur des jeux de données aléatoires pour évaluer leur complexité en moyenne. La difficulté est ici de bien contrôler la loi de génération des données. Toute discussion avancée sur cette question est explicitement hors sujet, mais il est demandé au candidat d’être conscient du problème.

On peut aussi utiliser l’aléatoire pour des méthodes de résolution de type Monte-Carlo. Un exemple classique est le calcul de $\pi$. L’algorithme peut être facilement programmé en Python ou en Scratch. (Malheureusement, la convergence de la méthode simple est très lente.)

Une autre utilisation réside dans la simulation d’expériences probabilistes."

Capesman