Probabilistic algorithms for data streaming and random generation

Cette these examine deux types de problemes: l'analyse de grands flux de donnees reelles, et le probleme complementaire de la generation de grande quantites de donnees aleatoires. Pour cela, elle exploite un ensemble d'outils communs que sont la combinatoire analytique (et les fonctions generatrices), l'enumeration, les probabilites, les algorithmes probabilitistes, avec en particulier la methode Boltzmann pour la generation aleatoire. Tout d'abord, nous etudions des algorithmes de traitement de donnees: ces algorithmes sont capables d'extraire des informations de grands flux de donnees en utilisant des ressources tres limitees (notamment pour ce qui est de la memoire et du temps de traitement par element du flux). Une des nos contributions principales est de livrer l'analyse complete d'un algorithme optimal pour l'estimation du nombre d'elements distincts dans un flux, un probleme qui a suscite de nombreux travaux. Notre seconde contribution, un travail en commun avec des chercheurs de l'UPC a Barcelone, est d'introduire un estimateur novateur du nombre distinct d'elements sui se base sur des statistiques sur les permutations. La seconde partie se concentre sur la generation aleatoire de lois discretes, et d'objets combinatoires. Nous introduisons le premier algorithme optimal pour la generation de la loi uniforme discrete, un element central utilise pour les simulations par ordinateur. Nous introduisons aussi, dans un travail en commun avec Olivier Bodini, une extension du modele de Boltzmann pour permettre la generation aleatoire d'une nouvelle sorte d'objets appartenant a la combinatoire dite multiplicative, qui possede des liens etroits avec la theorie analytique des nombres. Enfin, toujours avec Olivier Bodini, nous presentons un travail en cours qui pourraient permettre d'ameliorer l'aspect pratique de la methode de Boltzmann.