Automatic average-case analysis of algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1990

Automatic average-case analysis of algorithms

Philippe Flajolet
  • Fonction : Auteur
  • PersonId : 829512
Paul Zimmermann
Bruno Salvy

Résumé

Many probabilistic properties of elementary discrete combinatorial structures of interest for the average-case analysis of algorithms prove to be decidable. This paper presents a general framework in which such decision procedures can be developed : it is based on a combination of generating function techniques for counting and complex analysis techniques for asymptotic estimations. We expose here the theory of exact analysis in terms of generating functions for four different domains the iterative/recursive and unlabelled/labelled data type domains. We then present some major components of the associated asymptotic theory and exhibit a class of naturally arising functions that can be automatically analyzed. A fair fragment of this theory is also incorporated into a system called Lambda-Upsilon-Omega. In this way, using computer algebra, one can procedure automatically non-trivial average-case analysis of algorithms operating over a variety of "decomposable" combinatorial structures. At a fundamental level, this paper is part of a global attempt at understanding why so many elementary combinatorial problems tend to have elementary asymptotic solutions. In several cases, it proves possible to relate entire classes of elementary combinatorial problems whose structure is well-defined with classes of elementary "special" functions and classes of asymptotic forms relative to counting, probabilities or average-case complexity.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1233.pdf (188.63 Ko) Télécharger le fichier

Dates et versions

inria-00077102 , version 1 (29-05-2006)

Identifiants

  • HAL Id : inria-00077102 , version 1

Citer

Philippe Flajolet, Paul Zimmermann, Bruno Salvy. Automatic average-case analysis of algorithms. [Research Report] RR-1233, INRIA. 1990. ⟨inria-00077102⟩
147 Consultations
438 Téléchargements

Partager

Gmail Facebook X LinkedIn More