Sur la résolution de systèmes polynomiaux paramétriques et l'élimination de quantificateurs sur les réels : algorithmes, complexité et implémentations

Solving polynomial systems is an active research area located betweencomputer sciences and mathematics. It finds many applications invarious fields of engineering and sciences (robotics, biology,cryptography, imaging, optimal control). In symbolic computation, onestudies and designs efficient algorithms that compute exact solutionsto those applications, which could be very delicate for numericalmethods because of the non-linearity of the given systems.Most applications in engineering are interested in the real solutionsto the system. The development of algorithms to deal with polynomialsystems over the reals is based on the concepts of effective realalgebraic geometry in which the class of semi-algebraic setsconstitute the main objects.This thesis focuses on three problems below, which appear in manyapplications and are widely studied in computer algebra and effectivereal algebraic geometry:- Classify the real solutions of a parametric polynomial system according to the values of the parameters;- One-block quantifier elimination, which is also the computation of the projection of a semi-algebraic set- Computation of the isolated points of a semi-algebraic set.We designed new symbolic algorithms with better complexity than thestate-of-the-art. In practice, our efficient implementations of thesealgorithms are capable of solving applications beyond the reach of thestate-of-the-art software.La résolution de systèmes polynomiaux est un domaine de rechercheactif situé entre informatique et mathématiques. Il trouve denombreuses applications dans divers domaines des sciences del'ingénieur (robotique, biologie) et du numérique (cryptographie,imagerie, contrôle optimal). Le calcul formel fournit des algorithmesqui permettent de calculer des solutions exactes à ces applications,ce qui pourraient être très délicat pour des algorithmes numériques enraison de la non-linéarité.La plupart des applications en ingénierie s'intéressent aux solutionsréelles. Le développement d'algorithmes permettant de les traiters'appuie sur les concepts de la géométrie réelle effective ; la classedes ensembles semi-algébriques en constituant les objets de base.Cette thèse se concentre sur trois problèmes ci-dessous, quiapparaissent dans de nombreuses applications et sont largement étudiéen calcul formel :- Classifier les racines réelles d'un système polynomialparamétrique selon les valeurs des paramètres;- Élimination d'un bloc de quantificateurs;- Calcul des points isolés d'un ensemble semi-algébrique.Nous concevons de nouveaux algorithmes symboliques avec une meilleurecomplexité que l'état de l'art. En pratique, nos implémentationsefficaces de ces algorithmes sont capables de résoudre des problèmeshors d'atteinte des logiciels de l'état de l'art