Normal view MARC view ISBD view

Séries génératrices et analyse automatique d'algorithmes / Paul Zimmermann ; sous la direction de Philippe Flajolet

Auteur principal : Zimmermann, Paul, 1964-, AuteurAuteur secondaire : Flajolet, Philippe, 1948-2011, Directeur de thèseAuteur secondaire collectivité : École polytechnique, Palaiseau, Essonne, Etablissement de soutenanceType de document : ThèseLangue : français.Pays : France.Éditeur : [S.l.] : [s.n.], 1991Description : 1 vol. (186 p.) ; 30 cmISBN : 2726106757.Bibliographie : Bibliogr. p. 179-182.Sujet MSC : 68Q25, Computer science -- Theory of computing, Analysis of algorithms and problem complexity
68W30, Computer science -- Algorithms, Symbolic computation and algebraic computation
68N17, Computer science -- Software, Logic programming
97A70, Mathematics education - General, mathematics and education, Theses and postdoctoral theses
Note de thèse: Thèse de doctorat, informatique, 1991, Ecole Polytechnique PalaiseauEn-ligne : Tel
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 ZIM (Browse shelf) Available 10453-01

Bibliogr. p. 179-182

Thèse de doctorat informatique 1991 Ecole Polytechnique Palaiseau

l'objet de cette thèse est la mise en évidence de procédés systématiques pour déterminer automatiquement le coût moyen d'un algorithme. Ces procédés s'appliquent en général aux schémas de descente dans des structures de données décomposables, ce qui permet de modéliser une vaste classe de problèmes. Cette thèse s'intéresse plus précisément à la première phase de l'analyse d'un algorithme, l'analyse algébrique, qui traduit le programme en objets mathématiques, tandis que la seconde phase extrait de ces objets les informations désirées sur le coût moyen. Nous définissons un langage de spécification pour définir des structures de données décomposables et des procédures de descente sur celles-ci. Lorsque l'on utilise comme objets mathématiques des séries génératrices (de dénombrement pour les données, de coût pour les procédures), nous montrons que les algorithmes décrits dans ce langage se traduisent directement en systèmes d'équations pour les séries génératrices associées, et de surcroît par des règles simples. À partir de ces équations, nous pouvons ensuite déterminer en temps polynomial le coût moyen exact pour une valeur fixée de la taille des données. On pourra aussi utiliser ces équations pour calculer par analyse asymptotiquele coût moyen lorsque la taille des données tend vers l'infini, puisque l'on sait par ailleurs que le coût moyen asymptotique est directement lié au comportement des séries génératrices au voisinage de leurs singularités. Ainsi nous montrons qu'à une classe donnée d'algorithmes correspond une classe bien définie de séries génératrices, et par conséquent une certaine classe de formules pour le coût moyen asymptotique. Ces règles d'analyse algébrique ont été incorporées dans un système d'analyse automatique d'algorithmes, Lambda-Upsilon-Omega, qui s'est avéré être un outil très utile pour l'expérimentation et la recherche.

There are no comments for this item.

Log in to your account to post a comment.