l'objet de cette thèse est la mise en évidence de procédés <em>systématiques</em> pour déterminer <em>automatiquement</em> le coût moyen d'un algorithme. Ces procédés s'appliquent en général aux schémas de <em>descente</em> dans des structures de données <em>décomposables</em>, 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'<em>analyse algébrique</em>, 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 <em>directement</em> en systèmes d'équations pour les séries génératrices associées, et de surcroît par des règles <em>simples</em>. À 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 <em>analyse asymptotique</em>le 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.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00526670 |
| Date | 06 March 1991 |
| Creators | Zimmermann, Paul |
| Publisher | Ecole Polytechnique X |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0022 seconds