Comptages probabilistes, de l'analyse aux programmes

Diverses applications, des réseaux à la fouille de données en passant par le traitement de données textuelles, necessitent l'extraction automatique de caractéristiques quantitatives de grands ensembles de données. Par exemple, le calcul de la cardinalité (le nombre d'éléments différents vérifiant divers critères), l'entropie empirique, ou encore les moments de fréquence, selon une terminologie due à Alon, Matias, et Szegedy. Au cours des deux dernières décennies, plusieurs algorithmes ont été proposés qui permettent de traiter des flux de données massifs avec une mémoire très petite (souvent de quelques kilo-octets), tout en fournissant des estimation de bonne qualité (quelques pourcents, typiquement). On montera quelques uns des principaux algorithmes dont l'analyse, voire même souvent la conception, repose sur diverses méthodes de combinatoire analytique. L'accent sera mis en particulier dans cet exposé sur l'articulation entre problèmes algorithmiques spécifiques et méthodes générales d'analyse d'algorithmes.