Résumé
Le séminaire donné par Philippe Flajolet, directeur de recherches à l’INRIA, a été consacré aux algorithmes probabilistes sur de grandes masses de données. Il a illustré un autre grand principe algorithmique, l’exploitation positive de l’aléa, reposant ici sur l’utilisation de fonctions de hachage pseudo-aléatoires. Une telle fonction va associer une information de taille fixe (par exemple 32 ou 64 bits) à n’importe quelle information d’entrée (mot, texte, image, son, etc.). Étant pseudo-aléatoire, elle va répartir équitablement les informations d’entrée dans les valeurs hachées, en cassant leurs régularités potentielles. P. Flajolet a montré l’efficacité de ces algorithmes dans un grand nombre de problèmes apparemment dissociés : le comptage approché de mots dans un livre avec très peu de mémoire et sans dictionnaire, le classement d’un grand nombre de documents selon leur similarité, la détection d’intrusions et de virus dans un réseau, etc. Bien que ces algorithmes soient très simples, leur analyse fait appel à des mathématiques particulièrement sophistiquées.
