Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 24 Octobre 2006

Une mesure de l'aléatoire pour les générateurs linéaires congruentiels

par Eda Cesaratto (GREYC)

Les générateurs linéaires congruentiels de la forme xk+1 = a xk + b modulo n sont très utilisés pour produire des suites pseudo-aléatoires. La question essentielle est : '' De tels générateurs simulent-ils bien le hasard?'' . Arnold a défini une constante [qui dépend du triplet (a, b, n)] qu'il propose comme la mesure de l'aléatoire pour une telle suite. Dans le cas particulier des progressions arithmétiques (où a = 1), nous donnons une expression alternative de cette constante d'Arnold en fonction de la paire (b, n). Puis nous évaluons, la valeur moyenne de cette constante lorsque le couple (b, n) varie dans l'ensemble {(b, n) : 0 ≤ bn }. Le résultat est sans surprise: les progressions arithmétiques sont de très mauvais générateurs aléatoires (au sens d'Arnold), mais notre étude permet de quantifier précisément cette mauvaise qualité.

L'exposé est fondé sur un travail commun de Eda Cesaratto, Alain Plagne et Brigittte Vallée. Il sera donné en anglais.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr