Identifiant pérenne de la notice : 207037612
Notice de type
Notice de regroupement
Note publique d'information : Cette these est consacree au developpement d'une methode d'analyse d'algorithmes,
c'est-a-dire de determination du cout moyen d'execution des algorithmes. Pour une
large classe d'algorithmes recursifs descendants dans des structures arborescentes,
nous montrons comment l'analyse peut se faire de facon systematique au moyen d'un
calcul de complexite; le formalisme developpe permet de traduire l'algorithme en un
systeme d'equations que satisfont les fonctions generatrices associees au cout d'execution.
On utilise pour ce faire, le concept de serie formelle d'arbres et on montre comment
les primitives de programmation peuvent etre traduites en operateurs sur les series.
L'estimation du cout moyen se fait en etudiant les singularites des solutions analytiques
des systemes: la methode de darboux est ici l'un des outils fondamentaux. On analyse
ainsi divers algorithmes operant sur des familles d'expressions algebriques (recherche
de motif, derivation, simplification, etc...) et sur des structures de donnees liees
a la recherche: arbres tournois a cles repetees
paprika.idref.fr
data.idref.fr
Documentation
