CE40 - Mathématiques, informatique théorique, automatique et traitement du signal

Orbites des systèmes dynamiques discrets en informatique – CODYS

Orbites des systèmes dynamiques discrets en informatique

Ce projet se concentre sur les orbites (c'est-a`-dire les trajectoires sous l'action du syste`me) des syste`mes dynamiques a` temps discret qui sont pertinentes en informatique. Puisque, tre`s grossie`rement, les ordinateurs ne traitent que des donne´es finies, ils ne voient que des orbites pe´riodiques.

Orbites discrètes

Nous conside´rons deux principaux types d'orbites discre`tes :<br /><br /> les orbites finies et pe´riodiques (ces orbites ont ge´ne´ralement une signification arithme´tique pour les syste`mes que nous conside´rons et forment un ensemble de´nombrable),<br /> les orbites pour les discre´tisations de syste`mes dynamiques (la discre´tisation e´tant ge´ne´ralement effectue´e par rapport a` un espace fini).

Nous aborderons deux types de questions sur les orbites discre`tes dans le projet :

-l'accessibilite´ et
-le comportement a` long terme.

Les proble`mes d'accessibilite´ seront traite´s en se concentrant sur la construction d'invariants et d'orbites spe´ciales, et le comportement a` long terme des orbites, en conside´rant le comportement ergodique et probabiliste des orbites tronque´es.
Ce projet de quatre ans est divise´ en cinq ta^ches.

Nous abordons la question de la ge´ne´ricite´ selon divers points de vue dans la Ta^che GEN.
La Ta^che PER est consacre´e a` l'e´tude des orbites finies et pe´riodiques, elle de´crit leurs caracte´ristiques et les compare aux orbites du syste`me initial.
La discre´tisation est conside´re´e dans la Ta^che DIS, avec la simulation comme motivation.
La simulation est au cœur de la Ta^che SIM, oriente´e vers le calcul nume´rique mais aussi vers l'e´tude des syste`mes dynamiques comme mode`les de calcul.
La Ta^che SPE est de´die´e a` la construction d'orbites spe´ciales et d'invariants.

Nous construisons de manie`re efficace des orbites spe´ciales et des invariants, et e´tudions le comportement statistique asymptotique d'un syste`me dynamique, d'un point de vue calculabilite´ et effectif.

Une des principales motivations de ce projet vient de la simulation. Nous voulons de´velopper un formalisme commun pour l'e´tude de diffe´rents types de discre´tisations naturelles, motive´es par la simulation. On associe au syste`me dynamique (X,T) une se´quence de discre´tisations qui de´pendent d'un parame`tre N (lie´ au nombre de points de l'espace de discre´tisation). Le projet vise a` de´crire le comportement asymptotique de ces syste`mes. Ce comportement asymptotique sera-t-il «proche« de celui du syste`me initial? ou, est-ce qu'il oubliera comple`tement le syste`me initial et se comportera comme un syste`me dynamique fini ale´atoire ? Plus pre´cise´ment, nous nous concentrons sur l'e´tude et la comparaison d'orbites discre`tes (orbites finies, pe´riodiques et discre`tes). Nous abordons la question de la pertinence des me´thodes ergodiques et dynamiques pour leur e´tude et, plus ge´ne´ralement, pour la simulation. Nous pre´voyons de de´velopper une e´tude the´orique et pratique de la discre´tisation et de la simulation pour des syste`mes simples comme des applications de l'intervalle ou des applications line´aires.

Les systèmes dynamiques ont largement prouvé leur utilité pour la modélisation des processus physiques. En effet, les systèmes dynamiques modélisent l'évolution de systèmes dont les composantes interagissent de manière simple, permettant de passer d'une propriété locale à une propriété globale. 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), et 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.

Pour atteindre cet objectif, 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, qui 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 invariantes.

Coordination du projet

Valerie BERTHE (Institut de Recherche en Informatique Fondamentale)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LaBRI Laboratoire Bordelais de Recherche en Informatique
IRIF Institut de Recherche en Informatique Fondamentale

Aide de l'ANR 369 754 euros
Début et durée du projet scientifique : octobre 2018 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter