Txt

Bonjour,

J'ai le plaisir de vous annoncer ma soutenance d'habilitation à diriger les recherches intitulée

	  "Modèles Continus. Calculs. Algorithmique distribuée".

La soutenance aura lieu le

   	      jeudi 7 décembre 2006  à 15h00
	      au LORIA, à Nancy.
	      (salle A008)

Après avis de:

      Monsieur Eugène Asarin, Rapporteur
      Monsieur S. Barry Cooper, Rapporteur
      Monsieur Giuseppe Longo, Rapporteur

Devant la comission d'examen composée de:

       Monsieur Eugène Asarin
       Monsieur Vincent Blondel
       Monsieur José-Félix Costa
       Monsieur Giuseppe Longo
       Monsieur Jean-Yves Marion

Vous y êtes cordialement invités.

Bien cordialement,

Olivier Bournez Chargé de Recherche INRIA <Olivier.Bournez@loria.fr> http://www.loria.fr/~bournez Tel: 03 54 95 84 18

Le document d'habilitation se trouve sur ./HDR.

(an english translation is available)

La page http://www.loria.fr/access/acceder/fr contient des renseignements sur comment se rendre au Loria.

===

Résumé:

Les systèmes dynamiques continus permettent de modéliser de nombreux systèmes physiques, biologiques, ou issus de l'informatique distribuée. Nous nous intéressons à leur pouvoir de modélisation, et à leurs propriétés en tant que systèmes de calculs, et plus généralement aux propriétés calculatoires des modèles continus.

Les deux premiers chapitres ne visent pas à produire des résultats nouveaux, mais à motiver ce travail, et à le mettre en perspectives. Le chapitre 3 constitue un survol. Les chapitres 4, 5 et l'annexe A présentent un panorama de quelques-uns de nos résultats personnels en relations avec cette problématique.

Plus précisément, le chapitre 1 présente les systèmes dynamiques, avec un point de vue classique et mathématique. Il vise d'une part à souligner la richesse, et la subtilité des comportements possibles des systèmes dynamiques continus, et d'autre part à mettre en évidence que différents dispositifs sont intrinsèquement continus, et utilisables comme tels pour réaliser des calculs. En outre nous insistons sur la puissance de modélisation d'une classe de systèmes dynamiques, que nous nommons les problèmes de Cauchy polynomiaux.

Les exemples du chapitre 2, issus de la bioinformatique, des modèles de la biologie des populations, de la virologie biologique et de la virologie informatique, et de l'algorithmique distribuée, se distinguent de ceux du chapitre 1 par le fait qu'ils mettent explicitement en jeu une certaine notion de concurrence entre agents. Nous présentons la théorie des jeux, et ses modèles, en nous focalisant sur certains de ses modèles du dynamisme. Ces modèles continus deviennent naturels pour parler d'algorithmique distribuée, en particulier dès que l'on a affaire à des systèmes de grandes tailles, ou dont on ne contrôle pas les interactions. Nous pointons quelques modèles de l'algorithmique distribuée qui intègrent ces considérations, et le potentiel de l'utilisation des systèmes continus pour l'algorithmique distribuée.

Le chapitre 3 constitue un survol de la théorie des calculs pour les modèles à temps continu. La puissance des modèles de calculs à temps et espace discrets est relativement bien comprise grâce à la thèse de Church, qui postule que tous les modèles raisonnables et suffisamment puissants ont la même puissance, celle des machines de Turing. On peut aussi considérer des modèles où le temps est continu. Certaines grandes classes de modèles ont été considérées dans la littérature. Nous les reprenons dans ce chapitre, en présentant un panorama de ce qui est connu sur leurs propriétés calculatoires.

Le chapitre 4 présente un résumé de quelques-uns de nos résultats personnels à propos de la comparaison de la puissance de plusieurs modèles à temps continu, en relations avec la thèse de Emmanuel Hainry. Claude Shannon a introduit en 1941 le GPAC comme un modèle des dispositifs de calculs analogiques. Les résultats de Shannon ont longtemps été utilisés pour argumenter que ce modèle était plus faible que l'analyse récursive, et donc que les machines analogiques sont prouvablement plus faibles que les machines digitales. Avec Manuel Campagnolo, Daniel Graça, et Emmanuel Hainry, nous avons prouvé récemment que le GPAC et l'analyse récursive calculent en fait les mêmes fonctions. Ce résultat prend toute sa perspective si l'on comprend que les fonctions calculées par le GPAC correspondent aux problèmes de Cauchy polynomiaux, dont le pouvoir de modélisation est discuté dans le chapitre 1.

D'autre part, nous avons montré qu'il était possible de caractériser algébriquement les fonctions élémentairement calculables et calculables au sens de l'analyse récursive. Cela signifie d'une part qu'il est possible de les caractériser en termes d'une sous-classe des fonctions R-récursives à la Moore, ce qui étend les résultats de Campagnolo, Costa, Moore, de la calculabilité discrète à l'analyse récursive, mais aussi d'autre part, qu'il est possible de caractériser ces fonctions de façon purement continue, par l'analyse, sans référence à de la calculabilité.

Dans le chapitre 5, nous reprenons certains de nos résultats à propos de caractérisations logiques de classes de complexité dans le modèle de Blum Shub et Smale, en relations avec la thèse de Paulin Jacobé de Naurois. Le modèle de Blum Shub et Smale constitue un modèle de calcul à temps discret et à espace continu. Le modèle, défini initialement pour parler de complexité algébrique de problèmes sur le corps des réels, ou plus généralement sur un anneau, a été par la suite été étendu par Poizat en un modèle de calculs sur une structure logique arbitraire. Avec Paulin Jacobé de Naurois, Felipe Cucker et Jean-Yves Marion, nous avons caractérisé syntaxiquement les classes de complexité majeures dans ce modèle sur une structure arbitraire, à la Bellantoni et Cook 1992.

Le chapitre 6 est consacré à une conclusion, dans laquelle nous reprenons plusieurs questions et perspectives qui nous semblent intéressantes.

Dans l'annexe A, nous discutons un point de vue sur les hypercalculs. La question de l'existence de systèmes capables de réaliser des hypercalculs, c'est-à-dire d'effectuer des calculs exploitables qui ne seraient pas réalisables par aucune machine de Turing, fait encore couler de l'encre et des controverses. Nous avons été invité à exprimer notre point de vue dans un numéro spécial sur le sujet, que nous reprenons en annexe A. Nous y rappelons plusieurs mauvaises compréhensions fréquentes de la thèse de Church, et nous présentons un panorama de plusieurs classes de systèmes mathématiques, avec la caractérisation de leur puissance.