Algorithmie et aléatoire
Un ordinateur et encore plus un algorithme est forcément déterministe : répéter un algorithme avec les mêmes entrées doit rendre la même sortie. Alors comment expliquer que python fournisse le module random qui génère des nombres aléatoires (random.random) ou mélange des tableaux (random.shuffle) ?
Il y a deux techniques qu'utilise un ordinateur peut proposer de l'aléatoire :
- il demande de l'aide extérieur,
- il fait semblant.
On va montrer le principe des deux techniques dans ce qui suit. Ce ne sera cependant qu'une introduction le sujet est vaste et peut devenir vite (très) compliqué et contre intuitif. Donc dans le doute :
Ne recodez pas vos propres algorithmes pour gérer l'aléatoire : utilisez des bibliothèques ou modules développés par des professionnels.
Nombres aléatoire et pseudo-aléatoires
En informatique, un générateur aléatoire Il n'est pas nécessaire de pouvoir générer des réels en informatique, seul 1 bit suffit.
Entropie et nombres aléatoires
TBD il suffit de générer soit 0 soit 1 de façon équiprobable puis on généralise aux nombres puis modulo (preuve homogène si génération homogène)
exemple de la colline et bille au dessus au milieu
figure fonctionnement porte : 2 états stables mais continue (car physique), donc il existe un autre état instable La moindre perturbation le fait aller d'un côté ou de l'autre.
Schema avec interrupteur pour bloquer.
adaptation au réel : exemple de la colline. et idem pour les interrupteur (dépasse le cadre de ce cours)
TBD coûteux en temps.
Et ces méthodes sont implémentées directement sur le processeur
Nombres pseudo-aléatoires
"Random numbers should not be generated with a method chosen at random. Some theory should be used.” (Donald Knuth, 1969)
TBD qu'en faire ? Prédire le monde physique (uniforme) ou la crypto (non prévisible) ?
TBD pseudo-aléatoire (modulo et le démontrer) et aléatoire. On suppose qu'on a un truc aléatoire, genre /dev/random sous unix qui prend des paramètre extérieur pour générer de l'entropie.
fonctionne avec un seed puis une suite
Nombres pseudo-aléatoires cryptographiques
TBD permutations. Pas du tout uniforme.
Permutation et Tableaux aléatoires
Tableau aléatoire parler de fisher-yates et du moyen de trouver des choses aléatoires en informatique. Notion de pseudo-aléatoire et de process physique pour l'aléatoire trouver des ref.
TBD Fisher-Yates
La complexité en moyenne est également un moyen rapide et simple d'estimer la complexité d'un code. Pour estimer la complexité en moyenne d'un algorithme codé, on mesure le temps pris par l'algorithme pour s'exécuter avec des données aléatoires et on en fait la moyenne (c'est un estimateur sans biais de la moyenne théorique).