Les systèmes dynamiques continus permettent de modéliser de nombreux<br />systèmes physiques, biologiques, ou issus de l'informatique<br />distribuée. Nous nous intéressons à leur pouvoir de modélisation, et à<br />leurs propriétés en tant que systèmes de calculs, et plus généralement<br />aux propriétés calculatoires des modèles continus.<br /><br />Les deux premiers chapitres ne visent pas à produire des résultats<br />nouveaux, mais à motiver ce travail, et à le mettre en<br />perspectives. Le chapitre 3 constitue un survol. Les chapitres 4, 5 et<br />l'annexe A présentent un panorama de quelques-uns de nos résultats<br />personnels en relations avec cette problématique.<br /><br />Plus précisément, le chapitre 1 présente les systèmes dynamiques, avec<br />un point de vue classique et mathématique. Il vise d'une part à<br />souligner la richesse, et la subtilité des comportements possibles des<br />systèmes dynamiques continus, et d'autre part à mettre en évidence que<br />différents dispositifs sont intrinsèquement continus, et utilisables<br />comme tels pour réaliser des calculs. En outre nous insistons sur la<br />puissance de modélisation d'une classe de systèmes dynamiques, que<br />nous nommons les problèmes de Cauchy polynomiaux.<br /><br />Les exemples du chapitre 2, issus de la bioinformatique, des modèles<br />de la biologie des populations, de la virologie biologique et de la<br />virologie informatique, et de l'algorithmique distribuée, se<br />distinguent de ceux du chapitre 1 par le fait qu'ils mettent<br />explicitement en jeu une certaine notion de concurrence entre agents.<br />Nous présentons la théorie des jeux, et ses modèles, en nous<br />focalisant sur certains de ses modèles du dynamisme. Ces modèles<br />continus deviennent naturels pour parler d'algorithmique distribuée,<br />en particulier dès que l'on a affaire à des systèmes de grandes<br />tailles, ou dont on ne contrôle pas les interactions. Nous pointons<br />quelques modèles de l'algorithmique distribuée qui intègrent ces<br />considérations, et le potentiel de l'utilisation des systèmes continus<br />pour l'algorithmique distribuée.<br /><br />Le chapitre 3 constitue un survol de la théorie des calculs pour les<br />modèles à temps continu. La puissance des modèles de calculs à temps<br />et espace discrets est relativement bien comprise grâce à la thèse de<br />Church, qui postule que tous les modèles raisonnables et suffisamment<br />puissants ont la même puissance, celle des machines de Turing. On peut<br />aussi considérer des modèles où le temps est continu. Certaines<br />grandes classes de modèles ont été considérées dans la<br />littérature. Nous les reprenons dans ce chapitre, en présentant un<br />panorama de ce qui est connu sur leurs propriétés calculatoires.<br /><br />Le chapitre 4 présente un résumé de quelques-uns de nos résultats<br />personnels à propos de la comparaison de la puissance de plusieurs<br />modèles à temps continu, en relations avec la thèse de Emmanuel<br />Hainry. Claude Shannon a introduit en 1941 le GPAC comme un modèle des<br />dispositifs de calculs analogiques. Les résultats de Shannon ont<br />longtemps été utilisés pour argumenter que ce modèle était plus faible<br />que l'analyse récursive, et donc que les machines analogiques sont<br />prouvablement plus faibles que les machines digitales. Avec Manuel<br />Campagnolo, Daniel Graça, et Emmanuel Hainry, nous avons prouvé<br />récemment que le GPAC et l'analyse récursive calculent en fait les<br />mêmes fonctions. Ce résultat prend toute sa perspective si l'on<br />comprend que les fonctions calculées par le GPAC correspondent aux<br />problèmes de Cauchy polynomiaux, dont le pouvoir de modélisation est<br />discuté dans le chapitre 1.<br /><br />D'autre part, nous avons montré qu'il était possible de caractériser<br />algébriquement les fonctions élémentairement calculables et<br />calculables au sens de l'analyse récursive. Cela signifie d'une part<br />qu'il est possible de les caractériser en termes d'une sous-classe des<br />fonctions R-récursives à la Moore, ce qui étend les résultats de<br />Campagnolo, Costa, Moore, de la calculabilité discrète à l'analyse<br />récursive, mais aussi d'autre part, qu'il est possible de caractériser<br />ces fonctions de façon purement continue, par l'analyse, sans<br />référence à de la calculabilité.<br /><br />Dans le chapitre 5, nous reprenons certains de nos résultats à propos<br />de caractérisations logiques de classes de complexité dans le modèle<br />de Blum Shub et Smale, en relations avec la thèse de Paulin Jacobé de<br />Naurois. Le modèle de Blum Shub et Smale constitue un modèle de calcul<br />à temps discret et à espace continu. Le modèle, défini initialement<br />pour parler de complexité algébrique de problèmes sur le corps des<br />réels, ou plus généralement sur un anneau, a été par la suite été<br />étendu par Poizat en un modèle de calculs sur une structure logique<br />arbitraire. Avec Paulin Jacobé de Naurois, Felipe Cucker et Jean-Yves<br />Marion, nous avons caractérisé syntaxiquement les classes de<br />complexité majeures dans ce modèle sur une structure arbitraire, à la<br />Bellantoni et Cook 1992.<br /><br />Le chapitre 6 est consacré à une conclusion, dans laquelle nous<br />reprenons plusieurs questions et perspectives qui nous semblent<br />intéressantes.<br /><br />Dans l'annexe A, nous discutons un point de vue sur les<br />hypercalculs. La question de l'existence de systèmes capables de<br />réaliser des hypercalculs, c'est-à-dire d'effectuer des calculs<br />exploitables qui ne seraient pas réalisables par aucune machine de<br />Turing, fait encore couler de l'encre et des controverses. Nous avons<br />été invité à exprimer notre point de vue dans un numéro spécial sur le<br />sujet, que nous reprenons en annexe A. Nous y rappelons plusieurs<br />mauvaises compréhensions fréquentes de la thèse de Church, et nous<br />présentons un panorama de plusieurs classes de systèmes mathématiques,<br />avec la caractérisation de leur puissance.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00123104 |
| Date | 07 December 2006 |
| Creators | Bournez, Olivier |
| Publisher | Institut National Polytechnique de Lorraine - INPL |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | habilitation ࠤiriger des recherches |
Page generated in 0.0026 seconds