PROJET DE THÈSE : ALGORITHMIQUE DE BASE DES FONCTIONS ...

PROJET DE THÈSE :
ALGORITHMIQUE DE BASE DES FONCTIONS D-FINIES,
APPLICATIONS À L’ÉVALUATION GARANTIE
1. Présentation du domaine
Le calcul formel est l’étude des mathématiques effectives et de leur complexité. Cette discipline
à l’interface des mathématiques et de l’informatique touche plusieurs millions d’utilisateurs par le
biais de systèmes grand public comme Maple ou Mathematica. Le sujet de thèse développé ici est
à la confluence de trois grandes directions de recherche actuelles en calcul formel :
– considérer les équations différentielles et les récurrences non plus comme des objets à résoudre,
mais comme des structures de données représentant leur solutions (« D-finitude »);
– rechercher des algorithmes quasi-optimaux en utilisant l’analyse de complexité comme outil
de conception d’algorithmes;
– développer la complémentarité entre calcul numérique et calcul symbolique en exploitant les
capacités d’approximation en précision arbitraire de ce dernier (« symbolique-numérique »).
1.1. D-finitude. Historiquement, d’importants efforts de recherche en calcul formel on été
consacrés à donner des solutions en forme close de divers problèmes. Un exemple spectaculaire
est le calcul de primitives. Les premiers logiciels mimaient les méthodes de calcul employées à la
main. Puis l’algorithme de Risch, fondé sur des théorèmes de structure en algèbre différentielle,
a fourni une solution générale (un algorithme de décision) pour les fonctions élémentaires. Plus
largement, de nombreux ...