L'aléatoire en informatique

« Que ce soit en cryptographie, dans les jeux vidéo, pour les algorithmes de tri, les modèles scientifiques ou encore les réseaux de neurones : l'aléatoire est omniprésent en informatique. Générer des nombres aléatoires est donc un véritable défi. Pour commencer, imaginons un lancer de dé.

On l’imagine aléatoire car on ne peut rien en prévoir.

Si je lance un dé, je ne sais pas si je vais faire 2, 5 ou un autre nombre on définit donc ce lancer comme aléatoire . Imaginez maintenant que vous deveniez omniscient : vous connaissez la force du lancer, les frottements avec la table, la vitesse des dés, la position des dés dans la main, etc.

Deux lancers identiques donneraient forcément le même résultat.

C'est le fait que l’on ne maîtrise pas ces paramètres qui crée la notion de hasard. En informatique, tout les paramètres sont sous contrôle.

On se demande donc : Comment le hasard pourrait-il alors avoir une place ? Comment pourrait-on réellement générer un nombre complètement aléatoire avec un ordinateur ? … On ne peut pas, l’ordinateur ne peut pas créer de vrai hasard.

Mais même s’il ne peut pas produire de véritable hasard, il existe des méthodes pour s’en approcher très fortement.

On va alors fabriquer du pseudo-hasard, suffisamment compliqué pour sembler aléatoire.

C'est ce que font les générateurs de nombres pseudo-aléatoires, ou PRNG (PseudoRandom Number Generator). A) Pseudo-aléatoire — PRNG Pour démarrer un générateur pseudo-aléatoire, on fournit d’abord une graine .

Cette graine sert de point de départ au PRNG: deux exécutions avec la même graine produiront exactement la même suite de nombres.

Ensuite, le PRNG applique une série de formules mathématiques ou des listes précalculées pour générer chaque nombre ultérieur.Les PRNG sont efficaces : ils peuvent produire de nombreux nombres en un court laps de temps.

Mais ils sont aussi déterministes : une séquence donnée de nombres peut être reproduite si le la graine est connu. Un éxemple de PRNG très connu est l’algorithme de Mersenne-Twister il est notamment utilisé par la bibliothèque random de python. C’est un algorithme très complexe mais très performant mais parmi ses principaux atouts on retiendra : · · · Une période gigantesque : il peut produire 2^19937 − 1 nombres différents avant de retomber sur une séquence déjà produite a partir d’une graine. Les nombres générés sont bien répartis : toutes les valeurs possibles ont la même chance d’apparaître. Une rapidité supérieure à celle de la plupart des générateurs de bonne qualité. Imaginons qu’on utilise la suite de Fibonacci.

C’est une suite bien connue en maths, où chaque terme est la somme des deux précédents.

On commence souvent avec les deux premiers nombres : 1 et 1 qui dans le cadre des PRNG peuvent être deux graines. Donc on a : 1 + 1 = 2 → puis 1+2=3→ 2+3=5→ 3+5=8→ 5 + 8 = 13 → et ainsi de suite… La suite continue : 21, 34, 55, 89, 144, etc. Chaque nombre dépend uniquement des deux précédents.

Ce n’est pas du vrai hasard, mais la suite s’allonge rapidement et devient difficile à suivre sans tout connaître depuis le début. Maintenant, imaginons qu’on veuille utiliser cette suite pour créer des nombres entre 1 et 100 — comme si on voulait simuler un lancer de dé.... »