Le théorème de h-cobordisme est bien connu en topologie différentielle et PL. Il a été démontré par Stephen Smale et avec comme conséquence la preuve de la conjecture de Poincaré en dimension supérieure à 4. Une généralisation pour les h-cobordismes possiblement non simplement connexe est appelée théorème de s-cobordisme. Dans cette thèse, nous démontrons les versions semi-algébrique et Nash de ces théorèmes. C'est à dire, avec des données semi-algébriques ou Nash, nous obtenons un homéomorphisme semi-algébrique (respectivement un difféomorphisme Nash). Les principaux outils intervenant sont la triangulation semi-algébrique et les approximations Nash. Un aspect de la nature algébrique des objets semi-algébriques et Nash est qu'on peut mesurer leurs complexités. Nous montrons les théorèmes de h et s-cobordisme avec borne uniforme sur la complexité de l'homéomorphisme semi-algébrique (difféomorphisme Nash) voulu, en fonction de complexité des données du cobordisme. Pour finir, nous déduisons la validité de ces théorèmes version semi-algébrique et Nash sur tout corps réel clos.

Dans ce travail nous nous intéressons aux systèmes dynamiques du point de vue de l'entropie. Nous rappellons tout d'abord le formalisme des structures d'entropie introduit par T.Downarowicz. Dans ce cadre on donne en particulier une preuve élémentaire du principe variationnel pour l'entropie de queue et on généralise certaines structures d'entropie aux endomorphismes.<br>Dans un deuxième temps, nous reprenons l'approche semi-algébrique de Y. Yomdin et M. Gromov pour contrôler la dynamique locale des applications de classe $C^r$. On présente une preuve complète du lemme algébrique de Gromov, qui est un point clé de la théorie de Yomdin. Aussi nous déduisons de nouvelles applications dynamiques de cette théorie : d'une part nous bornons l'entropie de queue mesurée en fonction de l'exposant de Lyapounov ; d'autre part nous généralisons une formule due à J.Buzzi pour l'entropie k-dimensionnelle d'un produit d'applications de classe $C^{\infty}$.<br>On s'intéresse enfin à la théorie des extensions symboliques due à M.Boyle et T.Downarowicz pour les applications $C^r$ et affines par morceaux du plan. On exhibe en particulier des exemples de dynamique $C^r$ de l'intervalle ayant une grande entropie d'extension symbolique. Nous donnerons aussi une borne de l'entropie d'extensions symboliques pour les applications affines par morceaux du plan.

L'objet de ce travail est l'étude des courbes intégrales du champ de gradient de fonctions définissables dans une structure o-minimale. On s'intéresse au comportement des courbes intégrales au voisinage d'une fibre atypique. <br /><br /><br /><br />Le premier chapitre rappelle certaines propriétés géométriques des<br />ensembles définissables dans une structure o-minimale.<br /><br /><br />Le deuxième chapitre s'attache à l'étude d'une famille définissable de fonctions définies sur des ouverts contenus dans un même compact. On montre grâce à la formule de Cauchy-Crofton que la longueur des courbes intégrales du champ de gradient de chaque fonction est majorée par une constante ne dépendant que de la dimension et du compact. On en déduit ensuite une borne explicite dans le cas d'un polynôme générique de degré fixé. <br /><br /><br />Le troisième chapitre est consacré aux fonctions $C^1$ définies sur<br />des ouvert non bornés. On montre que l'ensemble des valeurs ne vérifiant pas la condition de Malgrange (valeurs critiques asymptotiques) est fini et contient les valeurs atypiques qui ne sont pas valeurs critiques. <br /><br /><br />On établit dans le quatrième chapitre un théorème de plongement d'une composante connexe arbitraire d'une fibre correspondant à la valeur critique asymptotique dans une composante connexe d'une fibre typique voisine. Ce résultat, obtenu par une inégalité du type Lojasiewicz à l'infini, permet de comprendre les changements de type topologiques des fibres d'une fonction définissable au voisinage d'une valeur atypique. En dimension deux, on décrit l'ensemble des points d'une fibre typique par lesquels passe une courbe intégrale du champ de gradient qui n'atteint pas le niveau atypique. <br /><br /><br />Enfin, le dernier chapitre étudie certaines courbes intégrales<br />remarquables du champ de gradient. Une courbe réalisant le minimum de la norme du gradient sur les niveaux est une courbe intégrale du champ de gradient si et seulement si c'est une droite. Ce résultat conduit à s'interroger sur la finitude de séparatrices du champ de gradient d'une fonction polynomiale.

Cette thèse est dédiée à l'étude de la hiérarchie moments-sommes-de-carrés, une famille de problèmes de programmation semi-définie en optimisation polynomiale, couramment appelée hiérarchie de Lasserre. Nous examinons différents aspects de ses propriétés et applications. Comme application de la hiérarchie, nous approchons certains objets potentiellement compliqués, comme l'abscisse polynomiale et les plans d'expérience optimaux sur des domaines semi-algébriques. L'application de la hiérarchie de Lasserre produit des approximations par des polynômes de degré fixé et donc de complexité bornée. En ce qui concerne la complexité de la hiérarchie elle-même, nous en construisons une modification pour laquelle un taux de convergence amélioré peut être prouvé. Un concept essentiel de la hiérarchie est l'utilisation des modules quadratiques et de leurs duaux pour appréhender de manière flexible le cône des polynômes positifs et le cône des moments. Nous poursuivons cette idée pour construire des approximations étroites d'ensembles semi-algébriques à l'aide de séparateurs polynomiaux. / This thesis is dedicated to investigations of the moment-sums-of-squares hierarchy, a family of semidefinite programming problems in polynomial optimization, commonly called the Lasserre hierarchy. We examine different aspects of its properties and purposes. As applications of the hierarchy, we approximate some potentially complicated objects, namely the polynomial abscissa and optimal designs on semialgebraic domains. Applying the Lasserre hierarchy results in approximations by polynomials of fixed degree and hence bounded complexity. With regard to the complexity of the hierarchy itself, we construct a modification of it for which an improved convergence rate can be proved. An essential concept of the hierarchy is to use quadratic modules and their duals as a tractable characterization of the cone of positive polynomials and the moment cone, respectively. We exploit further this idea to construct tight approximations of semialgebraic sets with polynomial separators.

Le calcul géométrique en modélisation et en CAO nécessite la résolution approchée, et néanmoins certifiée, de systèmes polynomiaux. Nous introduisons de nouveaux algorithmes de sous-division afin de résoudre ce problème fondamental, calculant des développements en fractions continues des coordonnées des solutions. Au delà des exemples concrets, nous fournissons des estimations de la complexité en bits et des bornes dans le modèle de RAM réelle. La difficulté principale de toute méthode de résolution consiste en les points singuliers isolés. Nous utilisons les systèmes locaux inverses et des calculs numériques certifiés afin d'obtenir un critère de certification pour traiter les solutions singulières. Ce faisant, nous sommes en mesure de vérifier l'existence et l'unicité des singularités d'une structure de multiplicité donnée. Nous traitons deux principales applications géométriques. La première: l'approximation des ensembles semi-algébriques plans, apparaît fréquemment dans la résolution de contraintes géométriques. Nous présentons un algorithme efficace pour identifier les composants connexes et pour calculer des approximations polygonales et isotopiques à l'ensemble exact. Dans un deuxième temps, nous présentons un cadre algébrique afin de calculer des diagrammes de Voronoi. Celui-ci sera applicable à tout type de diagramme dans lequel la distance à partir d'un site peut être exprimé par une fonction polynomiale à deux variables (anisotrope, diagramme de puissance etc). Si cela n'est pas possible (par exemple diagramme de Apollonius, VD des ellipses etc), nous étendons la théorie aux distances implicitement données.

Dans cette thèse, nous nous intéressons à l'étude des structures déterminantielles apparaissent dans l'optimisation semi-définie (SDP), le prolongement naturel de la programmation linéaire au cône des matrices symétrique semi-définie positives. Si l'approximation d'une solution d'un programme semi-défini peut être calculé efficacement à l'aide des algorithmes de points intérieurs, ni des algorithmes exacts efficaces pour la SDP sont disponibles, ni une compréhension complète de sa complexité théorique a été atteinte. Afin de contribuer à cette question centrale en optimisation convexe, nous concevons un algorithme exact pour décider la faisabilité d'une inégalité matricielle linéaire (LMI) $A(x)\succeq 0$. Quand le spectraèdre associé (le lieu $\spec$ des $x \in \RR^n$ ou $A(x)\succeq 0$) n'est pas vide, la sortie de cet algorithme est une représentation algébrique d'un ensemble fini qui contient au moins un point $x \in \spec$: dans ce cas, le point $x$ minimise le rang de $A(x)$ sur $\spec$. La complexité est essentiellement quadratique en le degré de la représentation en sortie, qui coïncide, expérimentalement, avec le degré algébrique de l'optimisation semi-définie. C'est un garantie d'optimalité de cette approche dans le contexte des algorithmes exacts pour les LMI et la SDP. Remarquablement, l'algorithme ne suppose pas la présence d'un point intérieur dans $\spec$, et il profite de l'existence de solutions de rang faible de l'LMI $A(x)\succeq 0$. Afin d'atteindre cet objectif principal, nous développons une approche systématique pour les variétés déterminantielles associées aux matrices linéaires. Nous prouvons que décider la faisabilité d'une LMI $A(x)\succeq 0$ se réduit à calculer des points témoins dans les variétés déterminantielles définies sur $A(x)$. Nous résolvons ce problème en concevant un algorithme exact pour calculer au moins un point dans chaque composante connexe réelle du lieu des chutes de rang de $A(x)$. Cet algorithme prend aussi avantage des structures supplémentaires, et sa complexité améliore l'état de l'art en géométrie algébrique réelle. Enfin, les algorithmes développés dans cette thèse sont implantés dans une nouvelle bibliothèque Maple appelé Spectra, et les résultats des expériences mettant en évidence la meilleure complexité sont fournis. / In this thesis we focus on the study of determinantal structures arising in semidefinite programming (SDP), the natural extension of linear programming to the cone of symetric positive semidefinite matrices. While the approximation of a solution of a semidefinite program can be computed efficiently by interior-point algorithms, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. In order to contribute to this central question in convex optimization, we design an exact algorithm for deciding the feasibility of a linear matrix inequality (LMI) $A(x) \succeq 0$. When the spectrahedron $\spec = \{x \in \RR^n \mymid A(x) \succeq 0\}$ is not empty, the output of this algorithm is an algebraic representation of a finite set meeting $\spec$ in at least one point $x^*$: in this case, the point $x^*$ minimizes the rank of the pencil on the spectrahedron. The complexity is essentially quadratic in the degree of the output representation, which meets, experimentally, the algebraic degree of semidefinite programs associated to $A(x)$. This is a guarantee of optimality of this approach in the context of exact algorithms for LMI and SDP. Remarkably, the algorithm does not assume the presence of an interior point in the spectrahedron, and it takes advantage of the existence of low rank solutions of the LMI. In order to reach this main goal, we develop a systematic approach to determinantal varieties associated to linear matrices. Indeed, we prove that deciding the feasibility of a LMI can be performed by computing a sample set of real solutions of determinantal polynomial systems. We solve this problem by designing an exact algorithm for computing at least one point in each real connected component of the locus of rank defects of a pencil $A(x)$. This algorithm admits as input generic linear matrices but takes also advantage of additional structures, and its complexity improves the state of the art in computational real algebraic geometry. Finally, the algorithms developed in this thesis are implemented in a new Maple library called {Spectra}, and results of experiments highlighting the complexity gain are provided.