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

Abstract : 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.
Document type :
Theses
Complete list of metadatas

https://pastel.archives-ouvertes.fr/tel-00526670
Contributor : Paul Zimmermann <>
Submitted on : Friday, October 15, 2010 - 2:15:13 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on : Sunday, January 16, 2011 - 2:26:16 AM

File

Identifiers

  • HAL Id : tel-00526670, version 1

Collections

Citation

Paul Zimmermann. Séries génératrices et analyse automatique d'algorithmes. Informatique [cs]. Ecole Polytechnique X, 1991. Français. ⟨tel-00526670⟩

Share

Metrics

Record views

606

Files downloads

1717