De l'algorithmique à l'arithmétique via le calcul formel

This document presents my research contributions from 1988 to 2001, performed first at INRIA Rocquencourt within the Algo project (1988 to 1992), then at INRIA Lorraine and LORIA within the projects Euréca (1993-1997), PolKA (1998-2000), and Spaces (2001). Three main periods can be roughly distinguished: from 1988 to 1992 where my research focused on analysis of algorithms and random generation, from 1993 to 1997 where I worked on computer algebra and related algorithms, finally from 1998 to 2001 where I was interested in arbitrary precision floating-point arithmetic with well-defined semantics.Ce mémoire présente mes travaux de recherche de 1988 à 2001, travaux effectués d'abord à l'INRIA Rocquencourt au sein du projet Algo (1988 à 1992), puis à l'INRIA Lorraine et au LORIA dans les projets Euréca (1993 à 1997), PolKA (1998 à 2000), et Spaces (2001). Au niveau thématique, on peut distinguer grosso modo trois phases : une première période allant de 1988 à 1992 où j'ai surtout travaillé sur l'analyse d'algorithmes et la génération aléatoire, une seconde période de 1993 à 1997 où je me suis investi dans le calcul formel et les algorithmes sous-jacents, enfin une troisième période depuis 1998 où je me suis intéressé aux problèmes d'arithmétique exacte en précision arbitraire