Alors que la complexité des fonctions d'ordre 1 est bien définie et étudiée, il n'existe pas de notion satisfaisante à tout ordre. Une telle théorie existe déjà à l'ordre 2 et permet de définir une classe analogue aux fonctions calculables en temps polynomial usuelles. Cela est tout particulièrement intéressant dans le domaine de l'analyse récursive où l'on peut représenter, entre autres, les nombres et les fonctions réelles par des fonctions d'ordre 1. On peut alors remarquer un lien fort entre calculabilité et continuité, et aussi rapprocher la complexité avec certaines propriétés analytiques, ce que nous illustrons dans le cas des opérateurs réels. Nous prouvons cependant que, du point de vue de la complexité, les fonctions d'ordre 1 ne permettent pas de représenter fidèlement certains espaces mathématiques. Ce résultat appuie tout particulièrement la nécessité d'une théorie de la complexité d'ordre supérieur. Nous développons alors un modèle de calcul basé sur la sémantique des jeux, où l'application de deux fonctions est représentée par la confrontation de deux stratégies dans un jeu. En définissant la taille de telles stratégies, nous pouvons déduire une notion robuste et pertinente de complexité pour ces stratégies et donc pour les fonctions d'ordre supérieur. Nous définissons aussi une classe de fonctions calculables en temps polynomial qui paraît être un bon candidat pour définir une classe de complexité raisonnable à tout ordre / While first order complexity is well defined and studied, higher order lacks a satisfactory notion of complexity. Such a theory already exists at order 2 and provides a complexity class analogue to usual polynomial time computable functions. This is already especially interesting in the domain of computable analysis, where real numbers or real functions for example can be represented by first order functions. In particular, there is a clear link between computability and continuity, and we also illustrate in the case of real operators that complexity can be related to some analytical properties. However, we prove that, from a complexity point of view, some mathematical spaces can not be faithfully represented by order 1 functions and require higher order ones. This result underlines that there is a need to develop a notion of complexity at higher types which will be, in particular but not only, useful to computable analysis. We have developed a computational model for higher type sequential computations based on a game semantics approach, where the application of two functions is represented by the game opposing two strategies. By defining the size of such strategies, we are able to define a robust and meaningful notion of complexity at all types, together with a class of polynomial time computable higher order functionals which seems to be a good candidate for a class of feasible functionals at higher types

Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles<br />calculent diverses fonctions, certains sont plus puissants que d'autres,<br />certains sont deux à deux incomparables. Le calcul sur les réels est donc de<br />ce point de vue bien différent du calcul sur les entiers qui est unifié par la<br />thèse de Church-Turing qui affirme que tous les modèles raisonnables calculent<br />les mêmes fonctions.<br /><br />Les résultats de cette thèse sont de deux sortes. Premièrement, nous<br />montrons des équivalences entre les fonctions récursivement calculables et une<br />certaine classe de fonctions R-récursives et entre les fonctions<br />GPAC-calculables et les fonctions récursivement calculables. Ces deux<br />résultats ne sont cependant valables que si les fonctions présentent quelques<br />caractéristiques : elles doivent être définies sur un compact et dans le<br />premier cas être de classe C^2. Deuxièmement, nous montrons également une<br />hiérarchie de classes de fonctions R-récursives qui caractérisent les<br />fonctions élémentairement calculables, les fonctions<br />En-calculables pour n?3 (où les En sont les<br />fonctions de la hiérarchie de Grzegorczyk), et des fonctions récursivement<br />calculables. Ce résultat utilise un opérateur de limite dont nous avons prouvé<br />la généralité en montrant qu'il transfère une inclusion sur la partie discrète<br />des fonctions en une inclusion sur les fonctions sur les réels elles-mêmes.<br /><br />Ces résultats constituent donc une avancée vers une éventuelle<br />unification des modèles de calcul sur les réels.

Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles calculent diverses fonctions, certains sont plus puissants que d'autres, certains sont deux à deux incomparables. Le calcul sur les réels est donc de ce point de vue bien différent du calcul sur les entiers qui est unifié par la thèse de Church-Turing affirmant que tous les modèles raisonnables calculent les mêmes fonctions. Nous montrons des équivalences entre les fonctions récursivement calculables et une certaine classe de fonctions R-récursives et entre les fonctions GPAC-calculables et les fonctions récursivement calculables. Nous montrons également une hiérarchie de classes de fonctions R-récursives qui caractérisent les fonctions élémentairement calculables, les fonctions de la hiérarchie de Grzegorczyk et les fonctions récursivement calculables à l'aide d'un opérateur de limite. Ces résultats constituent donc une avancée vers une éventuelle unification des modèles de calcul sur les réels / Computation on the real numbers can be modelised in several different ways. There indeed exist a lot of different computation models on the reals. However, there are few results for comparing those models, and most of these results are incomparability results. The case of computation over the reals hence is quite different from the classical case where Church thesis claims that all reasonable models compute exactly the same functions. We show that recursively computable functions (in the sense of computable analysis) can be shown equivalent to some adequately defined class of R-recursive functions, and also to GPAC-computable functions. More than an analog characterization of recursively enumerable functions, we show that the limit operator we defined can be used to provide an analog characterization of elementarily computable functions and functions from Grzegorczyk's hierarchy. Those results can be seen as a first step toward a unification of computable functions over the reals