Dissertations / Theses on the topic 'Semi-algébrique'

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.
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}$.
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.

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.

L'objet de cette thèse est l'étude de l'espace de modules des G_2-fibrés principaux sur une courbe complexe projective connexe lisse, où G_2 désigne le groupe de Lie exceptionnel de plus petit rang. Le groupe G_2 est tout d'abord présenté comme le groupe des automorphismes de l'algèbre complexe des octaves de Cayley. D'autres définitions sont ensuite proposées. Les différentes réductions et extensions que peut admettre un G_2-fibré principal sont étudiées ainsi que la relation entre la stabilité d'un G_2-fibré principal et celle de son fibré vectoriel associé. L'espace de modules des G_2-fibrés principaux semistables est analysé. Nous obtenons notamment une caractérisation de son lieu lisse, une décomposition explicite de son lieu singulier en trois composantes connexes et une analyse de l'espace de Verlinde de niveau 1 pour le groupe G_2
This thesis studies the moduli space of principal G_2-bundles over a smooth connected projective curve, where G_2 is the exceptional Lie group of smallest rank. The group G_2 is first introduced as the group of automorphisms of the complex algebra of the Cayley numbers. Other equivalent definitions are also proposed. We study the reductions and extensions that a principal G_2_bundle can admit, as well as the link between a principal G_2-bundle and its associated vector bundle in relation to the notion of (semi)stability. The moduli space of semistable principal G_2-bundles is analysed. We notably obtain a characterisation of its smooth locus, with an explicit decomposition of its singular locus into three connected componants. We also give an analysis of the Verlinde space of G_2 at level 1

Par une approche algebrique de la limite semi-classique, nous etudions deux problemes de mecanique quantique moderne. Dans une premiere partie, nous nous interessons au comportement des electrons sur un reseau en champ magnetique. A deux dimensions et dans l'approximation des liaisons fortes, un tel systeme est decrit par le hamiltonien de harper. Les techniques algebriques permettent l'obtention d'un developpement systematique des niveaux de landau en fonction de la constante de planck effective, ici proportionnelle au champ magnetique. A l'aide d'une diagonalisation numerique exacte du hamiltonien, nous montrons la precision des developpements semi-classiques pour differents modeles de type harper. La deuxieme partie est consacree a l'etude de la localisation dynamique pour des systemes quantiques dependant du temps. Le modele de base est represente par une tige rigide tournant, sans frottements, autour d'un axe fixe. On applique, a intervalles reguliers, une force a ce rotateur. Un tel modele presente une transition vers le chaos pour certaines valeurs des parametres tandis que son analogue quantique conserve un mouvement stable. Par une analogie en termes de localisation d'anderson sur ce modele, constante de diffusion classique et longueur de localisation quantique sont liees par la formule de chirikov-izrailev-shepelyansky, faisant apparaitre la constante de planck effective du probleme, proportionnelle au rapport des frequences du rotateur quantique et de la force appliquee. Par les techniques algebriques, nous relions la longueur de localisation a la valeur moyenne dans le temps de l'energie cinetique du rotateur quantique

Un problème de géométrie algébrique réelle s'exprime sous forme d’un système d’équations et d’inéquations polynomiales, dont l’ensemble des solutions est un ensemble semi-algébrique. L'objectif de cette thèse est de montrer comment les algorithmes de ce domaine peuvent être décrits formellement dans le langage du système de preuve Coq.Un premier résultat est la définition formelle et la certification de l’algorithme de transformation de Newton présentée dans la thèse d'A. Bostan. Ce travail fait intervenir non seulement des polynômes, mais également des séries formelles tronquées. Un deuxième résultat est la description d'un type de donnée représentant les ensembles semi-algébriques. Un ensemble semialgébrique est représenté par une formule logique du premier ordre basée sur des comparaisons entre expressions polynomiales multivariées. Pour ce type de données, nous montrons comment obtenir les différentes opérations ensemblistes et allons jusqu'à décrire les fonctions semi-algébriques. Pour toutes ces étapes, nous fournissons des preuves formelles vérifiées à l'aide de Coq. Enfin, nous montrons également comment la continuité des fonctions semi-algébrique peut être décrite, mais sans en fournir une preuve formelle complète
A real algebraic geometry problem is expressed as a system of polynomial equations and inequalities, and the set of solutions are semi-algebraic sets. The objective of this thesis is to show how the algorithms of this domain can be formally described in the language of the Coq proof system. A first result is the formal definition and certification of the Newton transformation algorithm presented in A. Bostan's thesis. This work involves not only polynomials, but also truncated formal series. A second result is the description of a data type representing semi-algebraic sets. A semi-algebraic set is represented by a first-order logical formula based on comparisons between multivariate polynomial expressions. For this type of data, we show how to obtain the different set operations all the way to describing semialgebraic functions. For all these steps, we provide formal proofs verified with Coq. Finally, we also show how the continuity of semi-algebraic functions can be described, but without providing a fully formalized proof

Nous donnons une description globale des caracteres des representations unitaires irreductibles des groupes de lie resolubles presque algebriques sur un corps p-adique. Pour ce faire, nous etablissons une formule du caractere au voisinage des elements semi-simples. On commence par demontrer la formule du caractere au voisinage de l'element neutre. Notre demonstration se fait par recurrence sur la dimension du groupe g. On se ramene a faire des calculs explicites dans le cas ou le radical unipotent de g est un groupe de heisenberg. De fait, nous sommes capables de demontrer la formule du caractere dans le cadre plus general que voici : on suppose que le radical unipotent de g est de heisenberg, tel que son centre soit le centre du groupe g. Pour demontrer, dans cette situation, la formule du caractere au voisinage de l'element neutre, nous sommes amenes a demontrer un resultat, qui est la version p-adique d'un resultat bien connu de kirillov. Pour obtenir la formule du caractere au voisinage d'un element semi-simple quelconque, nous avons utilise la methode de descente de harish-chandra. Pour ce faire, nous avons du etendre au cas des groupes presque algebriques sur un corps p-adique, les resultats concernant les restrictions des fonctions generalisees invariantes dus a harish-chandra dans le cas algebrique reductif et a m. Duflo et m. Vergne dans le cas presque algebrique reel. Comme application de notre formule pour l'extension de la representation de schrodinger du groupe de heisenberg au produit semi-direct avec le groupe metaplectique, nous donnons une formule explicite pour le caractere de la representation metaplectique (ou de weil) et de ses composantes irreductibles.

L'objet de cette thèse est l'étude de l'espace de modules des G2-fibrés principaux sur une courbe complexe projective connexe lisse, où G2 désigne le groupe de Lie exceptionnel de plus petit rang. Le groupe G2 est caractérisé via trois approches différentes, la première étant celle où G2 est défini comme le groupe des automorphismes de l'algèbre complexe des octaves de Cayley. Les différentes réductions et extensions que peut admettre un G2-fibré principal sont étudiées ainsi que la relation entre la stabilité d'un G2-fibré principal et celle du fibré vectoriel qui lui est associé. L'espace de modules des G2-fibrés principaux semi-stables est analysé. Nous obtenons notamment une caractérisation de son lieu lisse, une décomposition explicite de son lieu singulier en trois composantes connexes et une analyse de l'espace de Verlinde de niveau 1 pour le groupe G2.

Dans la présente thèse, on établit des bornes supérieures sur les nombres de Betti des ensembles définis à l'aide de fonctions pfaffiennes, en fonction de la complexité pfaffienne (ou format) de ces ensembles. Les fonctions pfaffiennes ont été définies par Khovanskii, comme solutions au comportement quasi-polynomial de certains systèmes polynomiaux d'équations différentielles. Les ensembles semi-pfaffiens satisfont une condition de signe booléene sur des fonctions pfaffiennes, et les ensembles sous-pfaffiens sont projections de semi-pfaffiens. Wilkie a démontré que les fonctions pfaffiennes engendrent une structure o-minimale, et Gabrielov a montré que cette structure pouvait etre efficacement décrite par des ensembles pfaffiens limites. A l'aide de la théorie de Morse, de déformations, de recurrences sur le niveau combinatoire et de suites spectrales, on donne dans cette thèse des bornes effectives pourtoutes les catégories d'ensembles pré-citées.

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

Introduite par B. Totaro, la filtration par le poids sur l'homologie des variétés algébriques réelles, analogue réel de la filtration par le poids de P. Deligne sur les variétés algébriques complexes, a été réalisée via un complexe de chaînes filtré par C. McCrory et A. Parusinski, qui en ont enrichi la compréhension, notamment à travers l'étude de la suite spectrale induite. Au milieu des nombreuses informations recelées par cette suite spectrale de poids, on retrouve les nombres de Betti virtuels. Dans cette thèse, on montre l'existence d'une filtration par le poids équivariante sur l'homologie équivariante des variétés algébriques réelles munies d'une action d'un groupe fini. On la réalise par un complexe filtré et, via la construction de plusieurs suites spectrales, on effectue des avancées significatives pour extraire des invariants additifs. Lors de notre étude, on définit fonctoriellement un complexe de poids avec action et on montre qu'un résultat de découpage d'une variété Nash munie d'une involution algébrique entraîne un analogue de la suite exacte de Smith, tenant compte de la filtration Nash-constructible. A travers la construction d'un complexe de poids invariant dans le cadre d'involutions algébriques, on retrouve également les nombres de Betti virtuels équivariants de G. Fichou. Enfin, en appliquant les bons foncteurs aux résultats sur les produits de filtrations par le poids réelles de T. Limoges, on donne des résultats sur les produits de filtrations par le poids équivariantes.

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

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.



Le premier chapitre rappelle certaines propriétés géométriques des
ensembles définissables dans une structure o-minimale.


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é.


Le troisième chapitre est consacré aux fonctions $C^1$ définies sur
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.


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.


Enfin, le dernier chapitre étudie certaines courbes intégrales
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.

La notion de données semi-structureées est liée au monde du web. On appelle donnée semi-structurée une donnée dont le schéma n'est pas défini a priori. Par exemple, il peut s'agir d'une page HTML, d'un site Web tout entier ou encore d'un document XML. Cette thèse étudie les requêtes sur les données modélisées par des graphes. Plus précisément, on s'intéresse à différents langages de requêtes associés. Dans le cas des graphes orientés, on utilise des techniques de réécriture et d'automates pour étudier - à des fins d'optimisation de requêtes - les contraintes d'inclusions. Elles portent sur les chemins qui permettent de naviguer dans la donnée. Par ailleurs, on génère un index d'une donnée qui préserve toutes les contraintes d'inclusions. Ensuite, on étend cette étude pour obtenir le concept de requête graphe. Appliqué au cas des documents "XML coloré", elles permettent d'étudier formellement l'expressivité et la complexité de langages de requêtes inspirés de XPath et de XQuery. Enfin, les résultats théoriques sont validés par des expérimentations.

Ce travail comporte deux parties, l'une théorique et l'autre pratique, et porte sur l'utilisation combinée d'outils combinatoires et algébriques pour la construction et l'analyse de plans d'expérience. Nous nous intéressons en particulier à des caractérisations polynomiales des propriétés d'invariance faible d'un plan expérimental et proposons une définition ainsi qu'un cadre de résolution d'un problème de construction de type polynomial à l'aide de la géométrie algébrique réelle et du lien entre l'optimisation semi-définie positive et le théorème des zéros réels. Nous nous intéresserons ici également à la méthodologie des surfaces de réponse et plus particulièrement à la propriété d'isovariance statistique, ce qui nous amène à étudier plus particulièrement des plans dont le support est inclus dans une sphère. Les principaux avantages de l'approche développée dans ce travail sont sa grande généralité, son automatisation et l'obtention des coordonnées exactes des points support du plan ce qui permet une détermination complète des confusions d'effets contrairement à la construction numérique de plans d'expérience euclidiens qui ne permet pas l'analyse exacte des confusions d'effets qui apparaissent nécessairement lorsque nous nous intéressons à des plans euclidiens de petite taille. Or une connaissance précise des confusions d'effets est nécessaire pour rendre possible l'utilisation de modèles polynomiaux qui ne seront plus limités au degré 2 comme c'est trop souvent le cas dans la théorie et dans la pratique. De nombreux exemples de construction de plans isovariants, l'étude de leurs caractéristiques ainsi que les programmes ayant permis d'obtenir ces résultats sont également présentés.

On se propose de montrer par une variante méromorphe du tubage que : PF(lambda = 0; som::(V)|F|**(2)lambda omega 'lambda omega ) = trace::(V) ((N) union (omega )) = tomega ',omega ou V est une variété analytique complexe compacte de dimension N + 1, F: V->C une application meromorphe telle que div(F) = PD::(O) - QD::(1) ou P,Q appartient à N*, D::(O) et D::(1) sont des hypersurfaces lisses transverses. Omega,omega ' des 1-formes sur V, holomorphe et meromorphe respectivement, telles que les poles de omega ' soient dans D::(O) et RES::(DO)omega ' = O dans H**(N)(D::(O),C). Trace::(V) : H**(2N+2)(V,C)->C est l'intégration sur V. (N=) est une classe de H**(N+1)(V,C) qui prolonge celle de omega ' sur V-D::(O); tomega ' est un courant de degré N+1 sur V D-ferme dont la classe induit celle de omega ' sur V-D::(O) construit suivant herrara-lieberman

Le but de cette thèse est de calculer l'optimum d'un polynôme sur un ensemble semi-algébrique et les points où cet optimum est atteint. Pour atteindre cet objectif, nous combinons des méthodes de base de bord avec la hiérarchie de relaxation convexe de Lasserre afin de réduire la taille des matrices de moments dans les problèmes de programmation semi-définie positive (SDP). Afin de vérifier si le minimum est atteint, nous apportons un nouveau critère pour vérifier l'extension plate de Curto Fialkow utilisant des bases orthogonales. En combinant ces nouveaux résultats, nous fournissons un nouvel algorithme qui calcule l'optimum et les points minimiseurs. Nous décrivons plusieurs expérimentations et des applications dans différents domaines qui prouvent la performance de l'algorithme. Au niveau théorique nous prouvons aussi la convergence finie d'une hiérarchie SDP construite à partir d'un idéal de Karush-Kuhn-Tucker et ses conséquences dans des cas particuliers. Nous étudions aussi le cas particulier où les minimiseurs ne sont pas des points de KKT en utilisant la variété de Fritz-John
The objective of this thesis is to compute the optimum of a polynomial on a closed basic semialgebraic set and the points where this optimum is reached. To achieve this goal we combine border basis method with Lasserre's hierarchy in order to reduce the size of the moment matrices in the SemiDefinite Programming (SDP) problems. In order to verify if the minimum is reached we describe a new criterion to verify the flat extension condition using border basis. Combining these new results we provide a new algorithm which computes the optimum and the minimizers points. We show several experimentations and some applications in different domains which prove the perfomance of the algorithm. Theorethically we also prove the finite convergence of a SDP hierarchie contructed from a Karush-Kuhn-Tucker ideal and its consequences in particular cases. We also solve the particular case where the minimizers are not KKT points using Fritz-John Variety

Considérons les systèmes à évènements discrets qui sont modélisables par des réseaux de Pétri du type "graphes d'évènements temporisés", Ils ont un comportement optimal (fonctionnement au plus tôt) qui peut-être calculé sans simulation par un système dynamique qui est linéaire dans l'algèbre des dïodes (max,+) ou (min,+). Le comportement asymptotique d'un tel système à évènements discrets est cyclique et les caractéristiques de ce cycle (période, délai, motif) sont analysables par un calcul de valeur propre sur la matrice de dynamique. À partir de cette formulation linéaire, une représentation externe (fonction de transfert) peut-être obtenue grâce à un calcul formel sur des séries à coefficients dans les dïodes, la fonction de transfert d'un tel système est rationnelle au sens des dïoides et est factorisable en une expression finie de polynômes.

Les algèbres de Lie ont été introduites vers la fin du XIXème siècle afin d'étudier certains problèmes de nature géométrique. Dans un soucis de classification de ces objets, les algèbres de Lie semi-simples se sont vues conférer un rôle important. Les algèbres de Lie symétriques sont, elles, une généralisation des algèbres de Lie. De plus, il existe une correspondance bijective entre les algèbres de Lie réelles et les algèbres de Lie symétriques complexes, ce qui renforce l'intérêt porté à ces dernières. Un second niveau de structure des algèbre de Lie (semi-simples complexe) joue un rôle important. Il s'agit de considérer l'algèbre de Lie g comme une G-variété où G est le groupe algébrique adjoint de g opérant via l'action adjointe sur g. Il s'avère alors utile d'étudier ceci dans le cadre de la géométrie algébrique. Les propriétés géométriques de certaines variétés issues des algèbres de Lie ont alors pu être étudiées. D'un point de vue général, ce travail consiste à généraliser et comprendre les propriétés de variétés analogues dans les algèbres de Lie symétriques.

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.

Le calcul de l'infimum global $f^*$ d'un polynôme à $n$ variables sous contraintes est une question centrale qui apparaît dans de nombreux domaines des sciences de l'ingénieur. Pour certaines applications, il est important d'obtenir des résultats fiables. De nombreuses techniques ont été développées dans le cas où les contraintes sont données par des inéquations polynomiales. Dans cette thèse, on se concentre sur le problème d'optimisation d'un polynôme à $n$ variables sous des contraintes définies par des équations polynomiales à $n$ variables. Notre but est d'obtenir des outils, algorithmes et implémentations efficaces et fiables pour résoudre ces problèmes d'optimisation. Notre stratégie est de ramener le problème d'optimisation sous des contraintes qui définissent des ensembles algébriques de dimension quelconque à un problème équivalent, sous des nouvelles contraintes dont on maîtrise la dimension. La variété algébrique définie par ces nouvelles contraintes est l'union du lieu critique du polynôme objectif et d'un ensemble algébrique de dimension au plus 1. Pour cela, on utilise des objets géométriques définis comme lieux critiques de projections linéaires. Grâce au bon contrôle de la dimension, on prouve l'existence de certificats pour des bornes inférieures sur $f^*$ sur nos nouvelles variétés. Ces certificats sont donnés par des sommes de carrés et on ne suppose pas que $f^*$ est atteint. De même, on utilise les propriétés de nos objets géométriques pour concevoir un algorithme exact pour le calcul de $f^*$. S'il existe, l'algorithme renvoie aussi un minimiseur. Pour un problème avec $s$ contraintes et des polynômes de degrés au plus $D$, la complexité est essentiellement cubique en $(sD)^n$ et linéaire en la complexité d'évaluation des entrées. L'implantation, disponible sous forme de bibliothèque Maple, reflète cette complexité. Elle a permis de résoudre des problèmes inatteignables par les autres algorithmes exacts.

Les algèbres de Lie ont été introduites vers la fin du XlXème siècle afin d’étudier certains problèmes de nature géométrique. Dans un soucis de classification de ces objets, les algèbres de Lie réductives se sont vues conférer un rôle important. Les algèbres de Lie symétriques sont, elles, une généralisation des algèbres de Lie. De plus, il existe une correspondance bijective entre les algèbres de Lie réelles et les algèbres de Lie symétriques complexes, ce qui renforce l’intérêt porté à ces dernières, Un second niveau de structure des algèbre de Lie (semi-simples complexe) joue un rôle important. Il s’agit de considérer l’algèbre de Lie g comme une G-variété où G est le groupe algébrique adjoint de g opérant via l’action adjointe sur g. Il s’avère alors utile d’étudier ceci dans le cadre de la géométrie algébrique. Les propriétés géométriques de certaines variétés issues des algèbres de Lie ont alors pu être étudiées. D’un point de vue général, ce travail consiste à généraliser et comprendre les propriétés de variétés analogues dans les algèbres de Lie symétriques
Lie algebras were introduced toward the end of nineteenth century in order to study some problems arising from geometry. In the interest of classifying these objects, the subcategory of semisimple Lie algebras has been studied. Symmetric Lie algebras are a generalisation of Lie algebras and there are connections between complex symmetric Lie algebras and real Lie algebras. There is an another level structure on (semisimple complex) Lie algebras. Denoting by G the algebraic adjoint group of g, we can conside g as a G-variety under the adjoint action M. We can then study some properties in the framework of algebraic geometry. One can then study various G-varieties arising from this setting. From a global perspective, I try to generalize or understand some properties of analogue varieties in symmetric Lie algebras

Ce manuscrit est consacré à l'étude de la combinatoire de deux algèbres de Hopf d'extraction-contraction. La première est l'algèbre de Hopf de mots tassés WMat introduite par Duchamp, Hoang-Nghia et Tanasa dont l'objectif était la construction d'un modèle de coproduit d'extraction-contraction pour les mots tassés. Nous expliquons certains sous-objets ou objets quotients ainsi que des applications vers d'autres algèbres de Hopf. Ainsi, nous considérons une algèbre de permutations dont le dual gradué possède un coproduit de déconcaténation par blocs et un produit de double battage décalé. Le double battage engendre la commutativité de l'algèbre qui est donc distincte de celle de Malvenuto et Reutenauer. Nous introduisons également une algèbre de Hopf engendrée par les mots tassés de la forme x₁...x₁. Elle est isomorphe à l'algèbre de Hopf des fonctions symétriques non commutatives. Son dual gradé est donc isomorphe à l'algèbre de Hopf des fonctions quasi-symétriques. Nous considérons également une algèbre de Hopf de compositions et donnons son interprétation en termes de coproduit semi-direct d'algèbres de Hopf. Le deuxième objet d'étude est l'algèbre de Hopf de diagrammes de dissection HD introduite par Dupont en théorie des nombres. Nous cherchons des éléments de réponse concernant la nature de sa cogèbre sous-jacente. Est-elle colibre ? La dimension des éléments primitifs de degré 3 ne permet pas de conclure. Le cas du degré 5 permet d'établir la non-coliberté dans le cas où le paramètre de HD vaut - 1. Nous étudions également la structure pré-Lie du dual gradué HD. Nous réduisons le champ de recherche à la sous-algèbre pré-Lie non triviale engendrée par le diagramme de dissection de degré 1. Cette algèbre pré-Lie n'est pas libre
This thesis deals with the study of combinatorics of two Hopf algebras. The first one is the packed words Hopf algebra WMAT introduced by Duchamp, Hoang-Nghia, and Tanasa who wanted to build a coalgebra model for packed words by using a selection-quotient process. We describe certain sub-objects or quotient objects as well as maps to other Hopf algebras. We consider first a Hopf algebra of permutations. Its graded dual has a block deconcatenation coproduct and double shuffle product. The double shuffle product is commutative so the Hopf algebra is different from the Malvenuto and Reutenauer one. We analyze then the Hopf algebra generated by packed words looking like x₁...x₁. This Hopf algebra and non commutative symmetric functions are isomorphic. So its graded dual and quasi-symmetric functions are isomorphic too. Finally we consider a Hopf algebra of compositions an give its interpretation in terms of a semi-direct coproduct structure. The second objet we study is the Hopf algebra of dissection diagrams HD introduced by Dupont in number theory. We study the cofreedom problem. We can't conclude with homogeneous primitive elements of degree 3. With the degree 5 case, we can say that is not cofree with the parameter -1. We study the pre-Lie algebra structure of HD's graded dual too. We consider in particular the sup-pre-Lie algebra generated by the dissection diagram of degree 1. It is not a free pre-Lie algebra

La quantité de données disponibles n'a jamais été aussi grande. Se poser les bonnes questions, c'est-à-dire des questions qui soient à la fois pertinentes et dont la réponse est accessible est difficile. L'analyse topologique de données tente de contourner le problème en ne posant pas une question trop précise mais en recherchant une structure sous-jacente aux données. Une telle structure est intéressante en soi mais elle peut également guider le questionnement de l'analyste et le diriger vers des questions pertinentes. Un des outils les plus utilisés dans ce domaine est l'homologie persistante. Analysant les données à toutes les échelles simultanément, la persistance permet d'éviter le choix d'une échelle particulière. De plus, ses propriétés de stabilité fournissent une manière naturelle pour passer de données discrètes à des objets continus. Cependant, l'homologie persistante se heurte à deux obstacles. Sa construction se heurte généralement à une trop large taille des structures de données pour le travail en grandes dimensions et sa robustesse ne s'étend pas au bruit aberrant, c'est-à-dire à la présence de points non corrélés avec la structure sous-jacente.Dans cette thèse, je pars de ces deux constatations et m'applique tout d'abord à rendre le calcul de l'homologie persistante robuste au bruit aberrant par l'utilisation de la distance à la mesure. Utilisant une approximation du calcul de l'homologie persistante pour la distance à la mesure, je fournis un algorithme complet permettant d'utiliser l'homologie persistante pour l'analyse topologique de données de petite dimension intrinsèque mais pouvant être plongées dans des espaces de grande dimension. Précédemment, l'homologie persistante a également été utilisée pour analyser des champs scalaires. Ici encore, le problème du bruit aberrant limitait son utilisation et je propose une méthode dérivée de l'utilisation de la distance à la mesure afin d'obtenir une robustesse au bruit aberrant. Cela passe par l'introduction de nouvelles conditions de bruit et l'utilisation d'un nouvel opérateur de régression. Ces deux objets font l'objet d'une étude spécifique. Le travail réalisé au cours de cette thèse permet maintenant d'utiliser l'homologie persistante dans des cas d'applications réelles en grandes dimensions, que ce soit pour l'inférence topologique ou l'analyse de champs scalaires
Massive amounts of data are now available for study. Asking questions that are both relevant and possible to answer is a difficult task. One can look for something different than the answer to a precise question. Topological data analysis looks for structure in point cloud data, which can be informative by itself but can also provide directions for further questioning. A common challenge faced in this area is the choice of the right scale at which to process the data.One widely used tool in this domain is persistent homology. By processing the data at all scales, it does not rely on a particular choice of scale. Moreover, its stability properties provide a natural way to go from discrete data to an underlying continuous structure. Finally, it can be combined with other tools, like the distance to a measure, which allows to handle noise that are unbounded. The main caveat of this approach is its high complexity.In this thesis, we will introduce topological data analysis and persistent homology, then show how to use approximation to reduce the computational complexity. We provide an approximation scheme to the distance to a measure and a sparsifying method of weighted Vietoris-Rips complexes in order to approximate persistence diagrams with practical complexity. We detail the specific properties of these constructions.Persistent homology was previously shown to be of use for scalar field analysis. We provide a way to combine it with the distance to a measure in order to handle a wider class of noise, especially data with unbounded errors. Finally, we discuss interesting opportunities opened by these results to study data where parts are missing or erroneous

Cette thèse est divisée en deux parties. Dans la première partie, nous introduisons une nouvelle condition, appelée additivité torique, sur une famille de variétés abéliennes qui dégénèrent en un schéma semi-abelien au-dessus d’un diviseur à croisements normaux. La condition ne dépend que du module de Tate T l A(K sep ) de la fibre générique. Nous montrons que l’additivité torique est une condition suffisante pour l’existence d’un modèle de Néron, si la base est un schéma de caractéristique nulle. Dans le cas de la jacobienne d’une courbe lisse à réduction semi-stable, on obtient le même résultat sans aucune hypothèse sur la caractéristique de base; et nous montrons que l’additivité torique est aussi nécessaire pour l’existence d’un modèle de Néron, si la base est un schéma de caractéristique nulle. Dans la deuxième partie, on considère le cas d’une famille de courbes nodales sur un anneau de valuation discrète. On donne une condition combinatoire sur le graphe dual de la fibre spéciale, appelée semi-factorialité, qui équivaut au fait que tous les faisceaux inversibles sur la fibre générique s’étendent en des faisceaux inversibles sur l’espace total de la courbe. Il est démontré par la suite que cette condition est automatiquement satisfaite après un éclatement centré aux points fermés non-réguliers de la famille de courbes. On applique le résultat ci-dessus pour généraliser un théorème de Raynaud sur le modèle de Néron des jacobiennes de courbes lisses, au cas des courbes nodales
This thesis is subdivided in two parts. In the first part, we introduce a new condition, called toric-additivity, on a family of abelian varieties degenerating to a semi-abelian scheme over a normal crossing divisor. The condition depends only on the Tate module TlA(Ksep) of the generic fibre, for a prime l invertible on the base. We show that toric-additivity is a sufficient condition for the existence of a Néron model if the base is a Q-scheme. In the case of the jacobian of a smooth curve with semi-stable reduction, we obtain the same result without assumptions on the base characteristic; and we show that toric-additivity is also necessary for the existence of a Néron model, when the base is a Q-scheme. In the second part, we consider the case of a family of nodal curves over a discrete valuation ring, having split singularities. We say that such a family is semi factorial if every line bundle on the generic fibre extends to a line bundle on the total space. We give a necessary and sufficient condition for semi- factoriality, in terms of combinatorics of the dual graph of the special fibre. In particular, we show that performing one blow-up with center the non regular closed points yields a semi-factorial model of the generic fibre. As an application, we extend the result of Raynaud relating Néron models of smooth curves and Picard functors of their regular models to the case of nodal curves having a semi-factorial model

La majorité des courbes et surfaces rencontrées dans la modélisation géométrique sont définies comme l'ensemble des solutions d'un système d'équations et d'inéquations algébriques (ensemble semi-algébrique). De nombreux problèmes dans différentes disciplines scientifiques font appel à des requètes de proximité telles que la recherche du ou des voisins les plus proches ou la quantification du voisinage de deux objets.

Le diagramme de Voronoï d'un ensemble d'objets est une décomposition de l'espace en zones de proximité. La zone de proximité d'un objet est l'ensemble des points plus proches de cet objet que de tout autre objet. Les diagrammes de Voronoï permettent de répondre aux requètes de proximité après avoir identifié la zone de proximité à laquelle le point objet de la requète appartient. Le graphe dual du diagramme de Voronoï est appelé le graphe de Delaunay. Seules les approximations par des coniques peuvent garantir un ordre de continuité approprié au niveau des points de contact, ce qui est nécessaire pour garantir l'exactitude du graphe de Delaunay.

L'objectif théorique de cette thèse est la mise en évidence des propriétés algébriques et géométriques élémentaires de la courbe déplacée d'une courbe algébrique et de réduire le calcul semi-algébrique du graphe de Delaunay à des calculs de valeurs propres. L'objectif pratique de cette thèse est le calcul certifié du graphe de Delaunay pour des ensembles semi-algébriques de faible degré dans le plan euclidien.

La méthodologie associe l'analyse par intervalles et la géométrie algébrique algorithmique. L'idée centrale de cette thèse est qu'un pré-traitement symbolique unique peut accélérer l'évaluation numérique certifiée du détecteur de conflits dans le graphe de Delaunay. Le pré-traitement symbolique est le calcul de l'équation implicite de la courbe déplacée généralisée d'une conique. La réduction du problème semi-algébrique de la détection de conflits dans le graphe de Delaunay à un problème d'algèbre linéaire a été possible grâce à la considération du sommet de Voronoï généralisé (un concept introduit dans cette thèse).

Le calcul numérique certifié du graphe de Delaunay a été éffectué avec une librairie de résolution de systèmes zéro-dimensionnels d'équations et d'inéquations algébriques basée sur l'analyse d'intervalles (ALIAS). Le calcul certifié du graphe de Delaunay repose sur des théorèmes sur l'unicité de racines dans des intervalles donnés (Kantorovitch et Moore-Krawczyk). Pour les coniques, les calculs sont accélérés lorsque l'on ne considère que les équations implicites des courbes déplacées.