Normal view MARC view ISBD view

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

Auteur principal : Regnier, Mireille, AuteurAuteur secondaire collectivité : Université Paris-Dauphine, Etablissement de soutenanceType de document : ThèseLangue : français.Pays : France.Éditeur : [S.l.] : [s.n.], 1991Description : 1 vol. (50 p.) ; 30 cmISBN : 2726107036.Bibliographie : Bibliogr. .Sujet MSC : 68Q30, Theory of computing, Algorithmic information theory (Kolmogorov complexity, etc.)
34K25, Ordinary differential equations, Asymptotic theory of functional-differential equations
68W15, Algorithms in computer science, Distributed algorithms
97-02, Research exposition (monographs, survey articles) pertaining to mathematics education
Note de thèse: Habilitation à diriger des recherches, informatique, 1991, université Paris XI
Tags from this library: No tags from this library for this title. Log in to add tags.
Current location Call number Status Date due Barcode
CMI
Salle S
Thèses REG (Browse shelf) Available 10523-01

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é.

There are no comments for this item.

Log in to your account to post a comment.