Résumé :
Nous définissons la notion de présentation rationnelle d'un espace métrique complet
comme moyen d'étude des espaces métriques et des
fonctions continues du point de vue de la complexité
algorithmique. Nous étudions dans ce cadre différentes
manières de présenter l'espace C[0,1]
des fonctions réelles uniformément continues
sur l'intervalle [0,1], muni de la norme
usuelle.
Ceci nous permet de faire une comparaison de nature globale
entre les notions de complexité attachées à
ces présentations.
En particulier, nous obtenons une
généralisation des résultats de Hoover
concernant le théorème d'approximation de
Weierstrass en temps polynomial.
Nous obtenons également une
généralisation des résultats de Ker-I Ko,
H. Friedman et N. Müller concernant
les fonctions analytiques calculables en temps polynomial.
Abstract : We define the notion of rational presentation of a complete metric space, in order to study metric spaces from the algorithmic complexity point of view. In this setting, we study some representations of the space C[0,1] of uniformly continuous real functions over [0,1] with the usual norm. This allows us to have a comparison of global kind between complexity notions attached to these presentations. In particular, we get a generalization of Hoover's results concerning the Weierstrass approximation theorem in polynomial time. We get also a generalization of previous results on analytic functions which are computable in polynomial time.