Outils d'utilisateurs
nombres_aleatoires
Différences
Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
|
nombres_aleatoires [2015/07/21 13:31] brozer |
nombres_aleatoires [2018/08/30 20:35] (Version actuelle) gbdivers |
||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| - | ^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^ | + | ^ [[definir_ses_types|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[collection|Chapitre suivant]] ^ |
| - | ====== Les nombres pseudo-aléatoires ====== | + | ====== [Aller plus loin] Les nombres pseudo-aléatoires ====== |
| - | Un nombre aléatoire est un nombre dont la valeur est choisie au hasard. Ils sont utilisé dans de nombreux contextes, par exemple dans un jeu vidéo (pour avoir un comportement non prédictible), en cryptographie (pour encoder des informations), dans les tests automatisés du code (pour vérifier le comportement d'un programme avec des valeurs indéterminées). Vous verrez dans différents projets de ce cours des cas d'utilisation des nombres aléatoires. | + | Un nombre aléatoire est un nombre dont la valeur est choisie au hasard. Ils sont utilisés dans de nombreux contextes, par exemple dans les jeux vidéo (pour avoir un comportement non prédictible), en cryptographie (pour encoder des informations), ou dans les tests automatisés de code (pour vérifier le comportement d'un programme avec des valeurs indéterminées). Vous verrez dans différents projets de ce cours des cas d'utilisation des nombres aléatoires. |
| ===== Qualité des nombres aléatoires ===== | ===== Qualité des nombres aléatoires ===== | ||
| - | Tirer des nombres aléatoires peut sembler être une tâche facile. On peut par exemple prendre un dé de jeux (non pipé) à six faces et le lancer plusieurs fois pour obtenir une série de nombres aléatoires compris entre un et six. On peut également lancer une pièce de monnaie pour obtenir des nombres aléatoires valant zéro (Pile) ou un (Face). | + | Tirer des nombres aléatoires peut sembler être une tâche facile. On peut par exemple prendre un dé (non pipé) à six faces et le lancer plusieurs fois pour obtenir une série de nombres aléatoires compris entre un et six. On peut également lancer une pièce de monnaie pour obtenir des nombres aléatoires valant zéro (pile) ou un (face). |
| - | La difficulté vient du fait qu'il est facile d'obtenir des suites de nombres dont on n'arrive pas à prédire la prochaine valeur, mais qui présente quand même des propriétés mathématiques prédictibles. Si on additionne par exemple la valeur de deux dés, on aura un nombre aléatoire compris entre 2 et 12. Mais la probabilité d'obtenir un 12 est bien inférieure (1 chance sur 36) à la probabilité d'obtenir un 7 (12 chances sur 36). | + | La difficulté vient du fait qu'il est facile d'obtenir des suites de nombres dont on n'arrive pas à prédire la prochaine valeur mais qui présentent quand même des propriétés mathématiques prédictibles. Si on additionne par exemple la valeur de deux dés, on aura un nombre aléatoire compris entre 2 et 12. Mais la probabilité d'obtenir un 12 est bien inférieure (1 chance sur 36) à la probabilité d'obtenir un 7 (12 chances sur 36). |
| - | Quand vous jouez à un jeu de société, ce n'est pas très important que les nombres obtenus ne soient pas parfaitement aléatoire (et c'est de toute façon intégré comme composante du jeu). Mais lorsque les nombres aléatoires permettent de crypter des données importantes ou sécuriser une numéro de carte bancaire, la moindre propriété mathématique prédictible sur une série de nombres aléatoires peut permettre de contourner ces sécurités. | + | Quand vous jouez à un jeu de société, ce n'est pas très important que les nombres obtenus ne soient pas parfaitement aléatoires (et c'est même intégré comme composante du jeu). Mais lorsque les nombres aléatoires permettent de crypter des données importantes ou de sécuriser un numéro de carte bancaire, la moindre propriété mathématique prédictible sur une série de nombres aléatoires peut permettre de contourner ces sécurités. |
| - | Il ne faut donc pas simplement que les nombres semblent aléatoires. Il faut le prouver mathématiquement. (Et bien sûr, cela sort complètement du domaine de ce livre, ces sont des travaux de recherches très pointus). | + | Il ne faut donc pas simplement que les nombres semblent aléatoires. Il faut le prouver mathématiquement. Et bien sûr, cela sort complètement du cadre de ce cours, ce sont des travaux de recherches mathématique très pointus. |
| Pour en revenir à la programmation, on peut se poser une question : comment générer des nombres parfaitement aléatoires sur un ordinateur ? Ce n'est pas si simple, puisqu'un ordinateur est prévu pour être parfaitement prédictible (la même suite d'instructions avec les mêmes données produira le même résultat). | Pour en revenir à la programmation, on peut se poser une question : comment générer des nombres parfaitement aléatoires sur un ordinateur ? Ce n'est pas si simple, puisqu'un ordinateur est prévu pour être parfaitement prédictible (la même suite d'instructions avec les mêmes données produira le même résultat). | ||
| Ligne 145: | Ligne 145: | ||
| #include <iostream> | #include <iostream> | ||
| #include <random> | #include <random> | ||
| - | #include <chrono> | + | #include <ctime> |
| int main() { | int main() { | ||
| - | const auto seed = std::time(nullptr); | + | auto const seed = std::time(nullptr); |
| std::cout << seed << std::endl; | std::cout << seed << std::endl; | ||
| std::default_random_engine engin { seed }; | std::default_random_engine engin { seed }; | ||
| Ligne 154: | Ligne 154: | ||
| </code> | </code> | ||
| - | La fonction ''std::time'' retourne le temps passé depuis une date fixée (généralement 1970), en secondes. | + | La fonction ''std::time'' retourne le temps passé depuis une date fixée (généralement le 1er janvier 1970), en secondes. |
| <note> | <note> | ||
| Ligne 170: | Ligne 170: | ||
| ==== Les différents générateurs ==== | ==== Les différents générateurs ==== | ||
| - | Plusieurs générateurs déterministes sont proposés dans la bibliothèque standard du C++. Ces générateurs sont définis par l’algorithme utilisé et par les valeurs utilisées pour le configurer. Pour comprendre cela, regardons un peu plus en détail la documentation : [[http://en.cppreference.com/w/cpp/numeric/random|Pseudo-random number generation]]. | + | Plusieurs générateurs déterministes sont proposés dans la bibliothèque standard du C++. Ces générateurs sont définies par l’algorithme utilisé et par les valeurs utilisées pour le configurer. Pour comprendre cela, regardons un peu plus en détail la documentation : [[http://en.cppreference.com/w/cpp/numeric/random|Pseudo-random number generation]]. |
| - | Trois algorithmes de génération sont utilisés. La documentation donne des liens vers les pages de Wikipédia décrivant ces algorithmes. | + | Trois algorithmes de génération sont utilisé. La documentation donne des liens vers les pages de Wikipédia décrivant ces algorithmes. |
| * ''std::linear_congruential_engine'' : algorithme congruentiel linéaire ; | * ''std::linear_congruential_engine'' : algorithme congruentiel linéaire ; | ||
| Ligne 236: | Ligne 236: | ||
| Par exemple, si vous avez un jeu de 32 cartes et que vous souhaitez en tirer une au hasard, il faudra générer un nombre compris en 1 et 32. Si vous avez un personnage dans un jeu vidéo contrôlé aléatoirement, qui ne peut se déplacer que dans quatre directions, vous devrez générer un nombre aléatoire qui ne peut prendre par exemple que les valeurs 0 (monter), 1 (descendre), 2 (aller à droite) ou 3 (aller à gauche). Ce type de distribution est uniforme, chaque valeur à la même probabilité d'apparaître. | Par exemple, si vous avez un jeu de 32 cartes et que vous souhaitez en tirer une au hasard, il faudra générer un nombre compris en 1 et 32. Si vous avez un personnage dans un jeu vidéo contrôlé aléatoirement, qui ne peut se déplacer que dans quatre directions, vous devrez générer un nombre aléatoire qui ne peut prendre par exemple que les valeurs 0 (monter), 1 (descendre), 2 (aller à droite) ou 3 (aller à gauche). Ce type de distribution est uniforme, chaque valeur à la même probabilité d'apparaître. | ||
| - | D'autres exemples. Si vous créez un jeu de simulation de courses de voiture et que le joueur tourne de 10°, dans le monde réel, ça ne sera pas exactement 10°, mais 10° plus ou moins une erreur (due à l’imprécision du volant, des imperfections de la route, etc). Dans le jeu, pour avoir plus de réalisme, on peut modifier l'angle avec une erreur, pour obtenir par exemple 10.2° ou 9.9°. On pourra avoir des valeurs très différentes de 10°, par exemple 12° ou 8.5°, mais cela sera beaucoup plus rare. Pour simuler cela, on va utiliser une distribution normale. | + | D'autres exemples. Si vous créer un jeu de simulation de courses de voiture et que le joueur tourne de 10°, dans le monde réel, ça ne sera pas exactement 10°, mais 10° plus ou moins une erreur (due à l’imprécision du volant, des imperfections de la route, etc). Dans le jeu, pour avoir plus de réalisme, on peut modifier l'angle avec une erreur, pour obtenir par exemple 10.2° ou 9.9°. On pourra avoir des valeurs très différentes de 10°, par exemple 12° ou 8.5°, mais cela sera beaucoup plus rare. Pour simuler cela, on va utiliser une distribution normale. |
| ==== Les générateurs standard de distribution ==== | ==== Les générateurs standard de distribution ==== | ||
| - | La bibliothèque standard du C++ contient d'autres distributions que les distributions uniformes et normale. Vous pouvez avoir le détail dans la [[http://en.cppreference.com/w/cpp/numeric/random|documentation]] pour les fonctions à utiliser et sur [[https://fr.wikipedia.org/wiki/Liste_de_lois_de_probabilit%C3%A9|Wikipédia]] pour les explications sur les propriétés des distributions. Dans la majorité des cas, les deux distributions citées seront suffisantes, nous verrons que cela là dans la suite du cours. | + | La bibliothèque standard du C++ contient d'autres distributions que les distributions uniformes et normale. Vous pouvez avoir le détail dans la [[http://en.cppreference.com/w/cpp/numeric/random|documentation]] pour les fonctions à utiliser et sur [[https://fr.wikipedia.org/wiki/Liste_de_lois_de_probabilit%C3%A9|Wikipédia]] pour les explications sur les propriétés des distributions. Dans la majorité des cas, les deux distributions citées seront suffisantes, nous verrons cela dans la suite du cours. |
| Il existe deux distributions uniformes et une normale : | Il existe deux distributions uniformes et une normale : | ||
| Ligne 248: | Ligne 248: | ||
| * ''std::normal_distribution'' pour générer des nombres réels selon une loi normale. | * ''std::normal_distribution'' pour générer des nombres réels selon une loi normale. | ||
| - | Ces générateurs ne sont pas à proprement parler des générateurs de nombres aléatoires. Ils prennent en fait l'un des générateurs aléatoires vu précédemment pour générer un nombre respectant une loi donnée. Ce ne sont pas non plus des adaptateurs, comme ceux vu précédemment, puisqu'ils ne modifient pas le comportement des générateurs aléatoires. Ces générateurs de distribution prennent simplement un générateur en paramètre et l'utilise en interne pour générer des nombres. | + | Ces générateurs ne sont pas à proprement parlé des générateurs de nombres aléatoires. Ils prennent en fait l'un des générateurs aléatoires vu précédemment pour générer un nombre respectant une loi donnée. Ce ne sont pas non plus des adaptateurs, comme ceux vu précédemment, puisqu'ils ne modifient pas le comportement des générateurs aléatoires. Ces générateurs de distribution prennent simplement un générateur en paramètre et l'utilise en interne pour générer des nombres. |
| ==== Initialisation ==== | ==== Initialisation ==== | ||
| Ligne 257: | Ligne 257: | ||
| * la génération, en utilisant un générateur aléatoire. | * la génération, en utilisant un générateur aléatoire. | ||
| - | Pour initialiser une générateur de distribution, il faut créer une variable en utilisant le type de générateur que vous souhaitez, et en donnant les paramètres de la distribution. Ces paramètres varient selon le type de générateur : | + | Pour initialiser un générateur de distribution, il faut créer une variable en utilisant le type de générateur que vous souhaitez, et en donnant les paramètres de la distribution. Ces paramètres varient selon le type de générateur : |
| * valeurs minimale et maximale pour les générateurs de loi uniforme ; | * valeurs minimale et maximale pour les générateurs de loi uniforme ; | ||
| * moyenne et déviation standard pour le générateur de loi normale. | * moyenne et déviation standard pour le générateur de loi normale. | ||
| - | |||
| - | __ ajouter une figure __ | ||
| Le code C++ correspond est relativement similaire à ce que vous avez déjà vu. | Le code C++ correspond est relativement similaire à ce que vous avez déjà vu. | ||
| Ligne 277: | Ligne 275: | ||
| </code> | </code> | ||
| - | Vous avez déjà rencontré la notation avec chevrons ''<'' et ''>'' dans ce cours. Dans les codes précédents, un paramètre été placé entre ces chevrons, mais ce n'est pas une obligation ici. Si les chevrons ne contiennent rien, cela signifie que le paramètre par défaut est utilisé (voir la documentation pour connaître les paramètres par défaut. Ici, les paramètres par défaut sont ''int'' pour la loi uniforme sur les entiers et ''double'' pour les deux autres lois). Vous pouvez utiliser un autre paramètre : | + | Vous avez déjà rencontré la notation avec chevrons ''<'' et ''>'' dans ce cours. Dans les codes précédents, un paramètre était placé entre ces chevrons, mais ce n'est pas une obligation ici. Si les chevrons ne contiennent rien, cela signifie que le paramètre par défaut est utilisé (voir la documentation pour connaître les paramètres par défaut. Ici, les paramètres par défaut sont ''int'' pour la loi uniforme sur les entiers et ''double'' pour les deux autres lois). Vous pouvez utiliser un autre paramètre : |
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| Ligne 284: | Ligne 282: | ||
| int main() { | int main() { | ||
| - | std::normal_distribution<double> double_normal(5, 1); // loi normale utilisant des double | + | std::normal_distribution<> double_normal(5, 1); // loi normale utilisant des double |
| std::normal_distribution<float> float_normal(5, 1); // loi normale utilisant des float | std::normal_distribution<float> float_normal(5, 1); // loi normale utilisant des float | ||
| } | } | ||
| Ligne 306: | Ligne 304: | ||
| </code> | </code> | ||
| - | Le type passé en paramètre fait partie intégrante du type final. Le type de ''normal'' n'est pas ''std::normal_distribution'', mais bien ''std::normal_distribution<float>''. Cela signifie par exemple que les types ''std::normal_distribution<double>'' et ''std::normal_distribution<float>'' ne sont pas compatibles entre eux : | + | Le type passé en paramètre fait partie intégrante du type final. Le type de ''normal'' n'est pas ''std::normal_distribution'', mais bien ''std::normal_distribution<float>''. Cela signifie par exemple que les types ''std::normal_distribution<>'' (dont le type par défaut est ''double'') et ''std::normal_distribution<float>'' ne sont pas compatibles entre eux : |
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| Ligne 316: | Ligne 314: | ||
| Les valeurs 5 et 1 correspondent aux paramètres de la distribution. Elles ne sont pas utilisées lors de la compilation, mais uniquement lors de l'exécution. | Les valeurs 5 et 1 correspondent aux paramètres de la distribution. Elles ne sont pas utilisées lors de la compilation, mais uniquement lors de l'exécution. | ||
| - | <note>La séparation de la phase de compilation (//compile-time//) et lors de la phase d'exécution (//runtime//) est une notion importante en C++. Il est nécessaire de bien comprendre ce qui est fait à chaque étape. Vous verrez cette notion régulièrement.</note> | + | <note>La séparation de la phase de compilation (//compile-time//) et de la phase d'exécution (//runtime//) est une notion importante en C++. Il est nécessaire de bien comprendre ce qui est fait à chaque étape. Vous verrez cette notion régulièrement.</note> |
| ==== Génération ==== | ==== Génération ==== | ||
| Ligne 324: | Ligne 322: | ||
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| std::normal_distribution<float> normal(0, 1); // initialisation | std::normal_distribution<float> normal(0, 1); // initialisation | ||
| - | const auto value = normal(engin); // génération | + | auto const value = normal(engin); // génération |
| </code> | </code> | ||
| - | Contrairement aux générateurs aléatoires qui ne prennent pas d'argument, les générateurs de distribution prennent en argument le générateur aléatoire à utiliser. A chaque fois que le générateur de distribution est appelé, il appelle en interne le générateur aléatoire pour générer un nombre aléatoire, puis l'adapte en fonction de la distribution. | + | Contrairement aux générateurs aléatoires qui ne prennent pas d'argument, les générateurs de distribution prennent en argument le générateur aléatoire à utiliser. À chaque fois que le générateur de distribution est appelé, il appelle en interne le générateur aléatoire pour générer un nombre aléatoire, puis l'adapte en fonction de la distribution. |
| Pour résumer l'utilisation des générateurs de distributions, ceux-ci utilisent trois sources d'information pour générer un nombre : | Pour résumer l'utilisation des générateurs de distributions, ceux-ci utilisent trois sources d'information pour générer un nombre : | ||
| * le type de valeur générée (le type passé en argument entre chevrons, qui sera le même type que la variable ''value'' avec ''auto'') ; | * le type de valeur générée (le type passé en argument entre chevrons, qui sera le même type que la variable ''value'' avec ''auto'') ; | ||
| - | * le type de distribution et ses paramètres (définies lors de l'initialisation du générateur de distribution) ; | + | * le type de distribution et ses paramètres (définis lors de l'initialisation du générateur de distribution) ; |
| - | * le générateur aléatoire utilisé (définie lors de la génération des nombres). | + | * le générateur aléatoire utilisé (défini lors de la génération des nombres). |
| ===== Pour résumer ===== | ===== Pour résumer ===== | ||
| - | Au final, vous devriez avoir un code similaire à cela pour générer un nombre aléatoire (adapter selon le type de distribution) : | + | Au final, vous devriez avoir un code similaire à cela pour générer un nombre aléatoire (à adapter selon le type de distribution) : |
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| #include <iostream> | #include <iostream> | ||
| #include <random> | #include <random> | ||
| - | #include <chrono> | + | #include <ctime> |
| int main() { | int main() { | ||
| - | const auto seed = std::time(nullptr); // génération de la graine | + | auto const seed = std::time(nullptr); // génération de la graine |
| std::default_random_engine engin { seed }; // générateur aléatoire | std::default_random_engine engin { seed }; // générateur aléatoire | ||
| std::normal_distribution<float> normal(0, 1); // générateur de distribution | std::normal_distribution<float> normal(0, 1); // générateur de distribution | ||
| Ligne 354: | Ligne 352: | ||
| ===== Travaux pratiques ===== | ===== Travaux pratiques ===== | ||
| - | 1. Donner une série de nombres aléatoires, produit avec un algo (donné ou non), une graine comprise entre 0 et 100. Essayer de retrouver la graine/algo __ probablement à faire plus tard, après les boucles et tests__ | + | 1. Donner une série de nombres aléatoires, produit avec un algo/graine (donné ou non), une graine comprise entre 0 et 100. Essayer de retrouver la graine/algo __ probablement à faire plus tard, après les boucles et tests__ |
| 2. __exos : proposer des exos avec fonctions de calculs et affiche déjà écrit__ | 2. __exos : proposer des exos avec fonctions de calculs et affiche déjà écrit__ | ||
| - | ^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^ | + | |
| + | ^ [[definir_ses_types|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[collection|Chapitre suivant]] ^ | ||
nombres_aleatoires.1437478300.txt.gz · Dernière modification: 2015/07/21 13:31 par brozer
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported
