Mots et motifs : performances asymtotiques / Mireille Régnier = habilitation à diriger des recherches

Bibliogr.

Habilitation à diriger des recherches informatique 1991 université Paris XI

Nous étudions les performances d'algorithmes couramment utilisés en informatique, ma perspective étant celle de l'analyse en moyenne. Le premier chapitre est consacré à la structure arborescente de trie. Cette structure arborescente est associée à un processus de partitionnement récursif à la base de nombreux algorithmes: hachage, protocoles de communication... On montre en particulier que la transformation de Mellin est l'outil analytique approprié pour cette classe problèmes. Le deuxième chapitre traite des distributions limites de processus. Nous utilisons soit des méthodes analytiques basées sur le théorème de Lévy-pour les tries- soit des martingales -pour Quicksort-. Dans le troisième chapitre, nous étudions la recherche des motifs dans des textes. Nous proposons une approche algébrique basée notamment sur la combinatoire des mots et les séries génératrices. Elle se révèle puissante, et nous obtenons notamment les performances des deux algorithmes classiques : Knuth-Morris-Pratt et Boyer-Moore. Enfin, un algorithme de recherche multidimensionnelle est proposé.