Séries génératrices et analyse automatique d'algorithmes

this thesis studies systematic methods to determine automatically the average-case cost of an algorithm. Those methods apply generally to descent schemes in decomposable data structures, which enables one to model a large class of problems. More precisely, this thesis focuses on the first stage of the analysis of an algorithm, namely the algebraic analysis, which translates the program into mathematical objects, whereas the second stage extracts from those mathematical objects the desired information about the average-case cost. We define a language to describe decomposable data-structures and descent schemes on them. When one uses generating functions as mathematical objects (counting generating functions for data-structures, and cost generating functions for programs), we show that the algorithms described in this language directly translate into systems of equations for the corresponding generating functions, moreover using simple rules. From those equations, we can then determine in polynomial time the exact average-case cost for a given size of the input data-structures. We can also use those equations to compute using asymptotic analysis the average-case cost when the input data size tends to infinity, since we know that the asymptotic average cost is directly related to the behaviour of those generating functions around their singularities. Therefore, we show that to a given class of algorithms corresponds a well-defined class of generating functions, and in turn a given class of formulae for the asymptotic average cost. Those algebraic analysis rules were included in a software tool for the average-case analysis of algorithms, called Lambda-Upsilon-Omega, which proved useful for experiments and research.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