| dbo:abstract
|
- Un générateur de nombres pseudo-aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être suffisamment indépendants les uns des autres, et il est potentiellement difficile de repérer des groupes de nombres qui suivent une certaine règle (comportements de groupe). Un algorithme, par nature déterministe, génère des suites de nombres qui ne peuvent pas satisfaire complètement les critères mathématiques qualifiant les suites aléatoires. On les appelle suites pseudo-aléatoires, car leurs propriétés s'approchent seulement des propriétés idéales des suites aléatoires parfaites. Comme le faisait remarquer ironiquement John von Neumann : « Quiconque considère des méthodes arithmétiques pour produire des nombres aléatoires » disait-il « est, bien sûr, en train de commettre un péché ». De vrais nombres aléatoires peuvent être produits avec du matériel qui tire parti de certaines propriétés physiques stochastiques (bruit électronique d'une résistance par exemple). Les méthodes pseudo-aléatoires sont souvent employées sur des ordinateurs, dans diverses tâches comme la méthode de Monte-Carlo, la simulation ou les applications cryptographiques, les algorithmes probabilistes. Différentes raisons justifient de se satisfaire d’un rendu pseudo-aléatoire, parmi lesquelles :
* il est difficile d’obtenir des nombres véritablement aléatoires et, dans certaines situations, l'utilisation de nombre pseudo-aléatoires suffit en lieu et place de nombres réellement aléatoires, c'est le cas des algorithmes de Las Vegas ;
* les programmes générateurs de nombres aléatoires sont particulièrement adaptés à une implémentation informatique, donc plus facilement et plus efficacement utilisables ;
* dans certaines circonstances (par exemple en modélisation Monte Carlo), on doit effectuer plusieurs fois des calculs avec la même suite de nombres aléatoires : régénérer cette suite à partir de l'algorithme est plus efficace que de la stocker en mémoire. Une analyse mathématique rigoureuse est nécessaire pour déterminer le degré d'aléa d'un générateur pseudo-aléatoire. Robert R. Coveyou, de l'Oak Ridge National Laboratory, écrivit, dans un article, que « la génération de nombres aléatoires est trop importante pour être confiée au hasard ». La plupart des algorithmes pseudo-aléatoires essaient de produire des sorties qui sont uniformément distribuées ; à partir d'une suite uniforme, il existe des méthodes pour générer des suites de nombres selon les principales lois de probabilité (par exemple la méthode de la transformée inverse). Une classe très répandue de générateurs utilise une congruence linéaire. D'autres s'inspirent de la suite de Fibonacci en additionnant deux valeurs précédentes ou font appel à des registres à décalage à rétroaction linéaire, dans lesquels le résultat précédent est injecté après une transformation intermédiaire. Certains générateurs pseudo-aléatoires sont dits cryptographiques quand certaines contraintes sont satisfaites. Citons entre autres Fortuna, Yarrow ou Blum Blum Shub. (fr)
- Un générateur de nombres pseudo-aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être suffisamment indépendants les uns des autres, et il est potentiellement difficile de repérer des groupes de nombres qui suivent une certaine règle (comportements de groupe). Un algorithme, par nature déterministe, génère des suites de nombres qui ne peuvent pas satisfaire complètement les critères mathématiques qualifiant les suites aléatoires. On les appelle suites pseudo-aléatoires, car leurs propriétés s'approchent seulement des propriétés idéales des suites aléatoires parfaites. Comme le faisait remarquer ironiquement John von Neumann : « Quiconque considère des méthodes arithmétiques pour produire des nombres aléatoires » disait-il « est, bien sûr, en train de commettre un péché ». De vrais nombres aléatoires peuvent être produits avec du matériel qui tire parti de certaines propriétés physiques stochastiques (bruit électronique d'une résistance par exemple). Les méthodes pseudo-aléatoires sont souvent employées sur des ordinateurs, dans diverses tâches comme la méthode de Monte-Carlo, la simulation ou les applications cryptographiques, les algorithmes probabilistes. Différentes raisons justifient de se satisfaire d’un rendu pseudo-aléatoire, parmi lesquelles :
* il est difficile d’obtenir des nombres véritablement aléatoires et, dans certaines situations, l'utilisation de nombre pseudo-aléatoires suffit en lieu et place de nombres réellement aléatoires, c'est le cas des algorithmes de Las Vegas ;
* les programmes générateurs de nombres aléatoires sont particulièrement adaptés à une implémentation informatique, donc plus facilement et plus efficacement utilisables ;
* dans certaines circonstances (par exemple en modélisation Monte Carlo), on doit effectuer plusieurs fois des calculs avec la même suite de nombres aléatoires : régénérer cette suite à partir de l'algorithme est plus efficace que de la stocker en mémoire. Une analyse mathématique rigoureuse est nécessaire pour déterminer le degré d'aléa d'un générateur pseudo-aléatoire. Robert R. Coveyou, de l'Oak Ridge National Laboratory, écrivit, dans un article, que « la génération de nombres aléatoires est trop importante pour être confiée au hasard ». La plupart des algorithmes pseudo-aléatoires essaient de produire des sorties qui sont uniformément distribuées ; à partir d'une suite uniforme, il existe des méthodes pour générer des suites de nombres selon les principales lois de probabilité (par exemple la méthode de la transformée inverse). Une classe très répandue de générateurs utilise une congruence linéaire. D'autres s'inspirent de la suite de Fibonacci en additionnant deux valeurs précédentes ou font appel à des registres à décalage à rétroaction linéaire, dans lesquels le résultat précédent est injecté après une transformation intermédiaire. Certains générateurs pseudo-aléatoires sont dits cryptographiques quand certaines contraintes sont satisfaites. Citons entre autres Fortuna, Yarrow ou Blum Blum Shub. (fr)
|
| rdfs:comment
|
- Un générateur de nombres pseudo-aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être suffisamment indépendants les uns des autres, et il est potentiellement difficile de repérer des groupes de nombres qui suivent une certaine règle (comportements de groupe). (fr)
- Un générateur de nombres pseudo-aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être suffisamment indépendants les uns des autres, et il est potentiellement difficile de repérer des groupes de nombres qui suivent une certaine règle (comportements de groupe). (fr)
|
