From Dyna3S

Main: Accueil

Bienvenue sur la page du projet Dyna3S :

Dynamique des algorithmes du pgcd : une approche Algorithmique, Analytique, Arithmétique et Symbolique.

Ce projet est financé par l'Agence Nationale de la Recherche, ANR Programme Blanc SIMI 2.

Projet ANR-13-BS02-0003

Coordinatrice : Valérie Berthé

Durée : 60 mois, du 15-10-2013 au 15-10-2018

Partenaires

Résumé

Le but de ce projet est d'étudier des algorithmes de calcul de pgcd (plus grand commun diviseur) du point de vue des systèmes dynamiques. On considère un algorithme de pgcd comme un système dynamique discret en se concentrant sur les entrées entières. Nous sommes en premier lieu intéressés par le problème du calcul du pgcd de plusieurs entiers. Mais une motivation supplémentaire provient également de la géométrie discrète, cadre dans lequel la compréhension des primitives basiques, les droites et les plans discrets, repose sur des algorithmes de type Euclide.

Nous avons deux objectifs principaux.

Nous allons considérer tout particulièrement deux types d'algorithmes de pgcd, tous deux étant associés à des homographies par morceaux. La première famille est produite par des algorithmes de réduction dans les réseaux qui calculent des vecteurs courts, alors que la second famille rassemble des algorithmes de fractions continues multidimensionnels qui calculent de bonnes approximations rationnelles (comme l'algorithme de Jacobi-Perron).

Nous allons comparer de façon systématique ces algorithmes et décrire leur paramètres principaux quand les entrées sont soit réelles (trajectoires génériques) ou entières (trajectoires tronquées). Nous menons cette étude simultanément selon deux points de vue, un point de vue discret, correspondant aux entrées rationnelles, et un point de vue continu, correspondant aux entrées réelles. Cela produit deux cadres dynamiques considérés pour eux-mêmes, mais aussi en interaction, selon la méthodologie de l'analyse dynamique.
Cette méthodologie combine des outils qui proviennent de la théorie ergodique et de la dynamique symbolique avec des outils de la combinatoire analytique et des outils algorithmiques. Elle se décompose en 3 étapes principales.

Un des buts de ce projet est d'établir des relations fortes entre les chercheurs qui travaillent dans les domaines impliqués et qui n'ont pas encore collaboré; au sein de ce projet, ils vont travailler sur le même objet, à savoir les algorithmes de type Euclide, selon des approches complémentaires et différentes :

Projets apparentés

Comparaisons Une page autour de la comparaison des algorithmes de fractions continues.

Retrieved from https://www.irif.fr/~dyna3s/Accueil
Page last modified on October 08, 2018, at 11:56 AM