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

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.