CODYS » Home

Bienvenue sur la page du projet ANR CODYS.

Orbites des systèmes dynamiques discrets en informatique.

Ce projet est financé par l'Agence Nationale de la Recherche, Appel à projets générique 2018.

Projet ANR-18-CE40-0007

Coordinatrice Valérie Berthé

Durée 48 mois, du 01-11-2018 au 01-11-2022

Partenaires

Financement disponible

  • Thèse de doctorat au LaBRI à commencer à l'automne 2019 (contactez-nous)
  • Postdoctorat à l'IRIF (contactez-nous)

Résumé

Les systèmes dynamiques ont largement prouvé leur utilité pour la modélisation des processus physiques. Mais ils modélisent également de nombreux phénomènes du monde numérique, en relation étroite avec l'algorithmique : les systèmes dynamiques peuvent modéliser l'exécution d'un algorithme, ainsi qu'une boucle dans un programme, comme l'action d'une application linéaire multidimensionnelle. Plus précisément, un système dynamique à temps discret est défini comme l'action d'une application T agissant sur un espace X (généralement considéré comme compact). On étudie ainsi l'évolution du système, sous l'action du temps discrétisé. L'évolution du système à partir d'un point x de X (condition initiale) est ensuite décrite par l'orbite (c'est-à-dire la trajectoire) du point x.

Ce projet se concentre sur les orbites (c'est-à-dire les trajectoires sous l'action du système) des systèmes dynamiques à temps discret qui sont pertinentes en informatique. Puisque, très grossièrement, les ordinateurs ne traitent que des données finies, ils ne voient que des orbites périodiques. Nous considérons donc deux principaux types d'orbites discrètes :

  • les orbites finies et périodiques (ces orbites ont généralement une signification arithmétique pour les systèmes que nous considérons et forment un ensemble dénombrable),
  • les orbites pour les discrétisations de systèmes dynamiques (la discrétisation étant généralement effectuée par rapport à un espace fini).

Nous aborderons deux types de questions sur les orbites discrètes dans le projet :

  • l'accessibilité et
  • le comportement à long terme.

Les problèmes d'accessibilité seront traités en se concentrant sur la construction d'invariants et d'orbites spéciales, et le comportement à long terme des orbites, en considérant le comportement ergodique et probabiliste des orbites tronquées.

Une des principales motivations de ce projet vient de la simulation. Nous voulons développer un formalisme commun pour l'étude de différents types de discrétisations naturelles, motivées par la simulation. On associe au système dynamique (X,T) une séquence de discrétisations qui dépendent d'un paramètre N (lié au nombre de points de l'espace de discrétisation). Le projet vise à décrire le comportement asymptotique de ces systèmes. Ce comportement asymptotique sera-t-il "proche" de celui du système initial? ou, est-ce qu'il oubliera complètement le système initial et se comportera comme un système dynamique fini aléatoire ? Plus précisément, nous nous concentrons sur l'étude et la comparaison d'orbites discrètes (orbites finies, périodiques et discrètes). Nous abordons la question de la pertinence des méthodes ergodiques et dynamiques pour leur étude et, plus généralement, pour la simulation. Nous prévoyons de développer une étude théorique et pratique de la discrétisation et de la simulation pour des systèmes simples comme des applications de l'intervalle ou des applications linéaires. Nous construisons de manière efficace des orbites spéciales et des invariants, et étudions le comportement statistique asymptotique d'un système dynamique, d'un point de vue calculabilité et effectif.

Ce projet de quatre ans est divisé en cinq tâches.

  • Nous abordons la question de la généricité selon divers points de vue dans la Tâche GEN.
  • La Tâche PER est consacrée à l'étude des orbites finies et périodiques, elle décrit leurs caractéristiques et les compare aux orbites du système initial.
  • La discrétisation est considérée dans la Tâche DIS, avec la simulation comme motivation.
  • La simulation est au cœur de la Tâche SIM, orientée vers le calcul numérique mais aussi vers l'étude des systèmes dynamiques comme modèles de calcul.
  • La Tâche SPE est dédiée à la construction d'orbites spéciales et d'invariants.