Rapporteur(e)s :

– Olivier Bournez, LIX, École Polytechnique

– Vasco Brattka, Universität der Bundeswehr München

– Elvira Mayordomo, Universidad de Zagaroza

Examinateurs :

– Julien Cervelle, LACL, Université Paris-Créteil Est

– Olivier Finkel, Institut de Mathématiques de Jussieu-Paris Rive Gauche

– Emmanuel Jeandel, LORIA, Université de Lorraine

Titre : Aspects Topologiques des Représentations en Analyse Calculable

Résumé : L’analyse calculable permet de formaliser le traitement algorithmique d’objets mathématiques infinis. La théorie repose sur une représentation symbolique des objets, dont le choix détermine les capacités de calcul de la machine, notamment sa difficulté à résoudre chaque problème donné. La friction entre le caractère discret du calcul et la nature continue des objets est capturée par la topologie, qui exprime l’idée d’approximation finie d’objets infinis.

Nous étudions en profondeur les multiples interactions entre calcul et topologie, cherchant à analyser l’information qui peut être extraite algorithmiquement d’une représentation. Je me penche plus particulièrement sur la comparaison entre deux représentations d’une même famille d’objets, sur les liens détaillés entre complexité algorithmique et topologique des problèmes, ainsi que sur les relations entre représentations finies et infinies.

Title : Topological Aspects of Representations in Computable Analysis

Abstract : Computable analysis provides a formalization of algorithmic computations over infinite mathematical objects. The central notion of this theory is the symbolic representation of objects, which determines the computation power of the machine, and has a direct impact on the difficulty to solve any given problem. The friction between the discrete nature of computations and the continuous nature of mathematical objects is captured by topology, which expresses the idea of finite approximations of infinite objects.

We thoroughly study the multiple interactions between computations and topology, analysing the information that can be algorithmically extracted from a representation. In particular, we focus on the comparison between two representations of a single family of objects, on the precise relationship between algorithmic and topological complexity of problems, and on the relationship between finite and infinite representations.