Résumé de la conférence de D. Xiao - Journée Annuelle 2011

Le pseudo-aléa : objets et  génération
par David Xiao} (LIAFA, Université Paris Diderot)

En mathématiques,  l'utilisation de l'aléa  permet de simplifier certaines preuves,  ou même d'obtenir des preuves de  certains résultats dont on ne connait pas de preuves constructives. En informatique,  l'utilisation de l'aléa  mène à  la construction  d'algorithmes probabilistes, souvent très élégants et  efficaces.  Là aussi, il existe  des problèmes  résolus de manière très satisfaisante par un algorithme probabiliste, pour lesquels on ne connait aucun algorithme déterministe efficace.  Pourtant, l'utilisation de l'aléa n'est pas toujours satisfaisante: elle  conduit à  des preuves mathématiques non-constructives, et, en algorithmique, elle nécessite d'avoir accès à un aléa "informatique''. 

Il est  donc  souhaitable d'essayer  de supprimer l'aléa ou du moins de restreindre son utilisation  autant que possible.  Les objets pseudo-aléatoires  sont là pour "remplacer'' l'aléa. Ce sont des objets qui "ressemblent''  à des objets aléatoires, mais  qui  sont produits   plus efficacement, à partir d'une faible quantité d' aléa,  et quelquefois sans aucun aléa du tout.


Dans cet exposé, nous  décrirons  quelques exemples  importants d'objets pseudo-aléatoires :  les graphes expandeurs, les extracteurs d'aléa, les codes correcteurs d'erreurs, et les générateurs pseudo-aléatoires.  Nous montrerons quelques unes de leurs applications.  En comprenant mieux les objets pseudo-aléatoires, nous   pouvons  réduire la part de l'aléa dans beaucoup d'applications, et nous pouvons parfois la supprimer totalement. Nous pouvons aussi  mieux comprendre l'aléa lui-même.