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 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.