Mots manquants dans les textes aléatoires

Parmi l'ensemble des mots d'une longueur donnée sur un alphabet fixe, ceux qui n'apparaissent pas dans un texte sont appelés ``mots manquants''. Nous présenterons des méthodes de calcul, une exacte et une approchée, de l'espérance du nombre de mots manquants dans un texte aléatoire. Nous comparerons les résultats des deux approches et parlerons de leurs applications à l'analyse d'algorithmes de recherche de motifs et à la génération de nombre pseudo--aléatoires.

Travail en commun avec S. Rahmann, DKFZ, Heidelberg en Allemagne.