Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur l'étude et les applications de trois ordres sur les permutations : les deux ordres faibles (gauche et droit) et l'ordre fort ou de Bruhat. Dans un premier temps, nous étudions l'action du groupe symétrique sur les polynômes multivariés. En particulier, les opérateurs de emph{différences divisées} permettent de définir des bases de l'anneau des polynômes qui généralisent les fonctions de Schur aussi bien du point de vue de leur construction que de leur interprétation géométrique. Nous étudions plus particulièrement la base des polynômes de Grothendieck introduite par Lascoux et Schützenberger. Lascoux a montré qu'un certain produit de polynômes peut s'interpréter comme un produit d'opérateurs de différences divisées. En développant ce produit, nous ré-obtenons un résultat de Lenart et Postnikov et prouvons de plus que le produit s'interprète comme une somme sur un intervalle de l'ordre de Bruhat. Nous présentons aussi l'implantation que nous avons réalisée sur Sage des polynômes multivariés. Cette implantation permet de travailler formellement dans différentes bases et d'effecteur des changements de bases. Elle utilise l'action des différences divisées sur les vecteurs d'exposants des polynômes multivariés. Les bases implantées contiennent en particulier les polynômes de Schubert, les polynômes de Grothendieck et les polynômes clés (ou caractères de Demazure).Dans un second temps, nous étudions le emph{treillis de Tamari} sur les arbres binaires. Celui-ci s'obtient comme un quotient de l'ordre faible sur les permutations : à chaque arbre est associé un intervalle de l'ordre faible formé par ses extensions linéaires. Nous montrons qu'un objet plus général, les intervalles-posets, permet de représenter l'ensemble des intervalles du treillis de Tamari. Grâce à ces objets, nous obtenons une formule récursive donnant pour chaque arbre binaire le nombre d'arbres plus petits ou égaux dans le treillis de Tamari. Nous donnons aussi une nouvelle preuve que la fonction génératrice des intervalles de Tamari vérifie une certaine équation fonctionnelle décrite par Chapoton. Enfin, nous généralisons ces résultats aux treillis de $m$-Tamari. Cette famille de treillis introduite par Bergeron et Préville-Ratelle était décrite uniquement sur les chemins. Nous en donnons une interprétation sur une famille d'arbres binaires en bijection avec les arbres $m+1$-aires. Nous utilisons cette description pour généraliser les résultats obtenus dans le cas du treillis de Tamari classique. Ainsi, nous obtenons une formule comptant le nombre d'éléments plus petits ou égaux qu'un élément donné ainsi qu'une nouvelle preuve de l'équation fonctionnelle des intervalles de $m$-Tamari. Pour finir, nous décrivons des structures algébriques $m$ qui généralisent les algèbres de Hopf $FQSym$ et $PBT$ sur les permutations et les arbres binaires

Ce travail porte sur la construction d'un modèle réduit en hydraulique fluviale avec une méthode de décomposition en polynôme du chaos. Ce modèle réduit remplace le modèle direct afin de réduire le coût de calcul lié aux méthodes ensemblistes en quantification d'incertitudes et assimilation de données. Le contexte de l'étude est la prévision des crues et la gestion de la ressource en eau. Ce manuscrit est composé de cinq parties, chacune divisée en chapitres. La première partie présente un état de l'art des travaux en quantification des incertitudes et en assimilation de données dans le domaine de l'hydraulique ainsi que les objectifs de la thèse. On présente le cadre de la prévision des crues, ses enjeux et les outils dont on dispose pour prévoir la dynamique des rivières. On présente notamment la future mission SWOT qui a pour but de mesurer les hauteurs d'eau dans les rivières avec un couverture globale à haute résolution. On précise notamment l'apport de ces mesures et leur complémentarité avec les mesures in-situ. La deuxième partie présente les équations de Saint-Venant, qui décrivent les écoulements dans les rivières, ainsi qu'une discrétisation numérique de ces équations, telle qu'implémentée dans le logiciel Mascaret-1D. Le dernier chapitre de cette partie propose des simplifications des équations de Saint-Venant. La troisième partie de ce manuscrit présente les méthodes de quantification et de réduction des incertitudes. On présente notamment le contexte probabiliste de la quantification d'incertitudes et d'analyse de sensibilité. On propose ensuite de réduire la dimension d'un problème stochastique quand on traite de champs aléatoires. Les méthodes de décomposition en polynômes du chaos sont ensuite présentées. Cette partie dédiée à la méthodologie s'achève par un chapitre consacré à l'assimilation de données ensemblistes et à l'utilisation des modèles réduits dans ce cadre. La quatrième partie de ce manuscrit est dédiée aux résultats. On commence par identifier les sources d'incertitudes en hydraulique que l'on s'attache à quantifier et réduire par la suite. Un article en cours de révision détaille la validation d'un modèle réduit pour les équations de Saint-Venant en régime stationnaire lorsque l'incertitude est majoritairement portée par les coefficients de frottement et le débit à l'amont. On montre que les moments statistiques, la densité de probabilité et la matrice de covariances spatiales pour la hauteur d'eau sont efficacement et précisément estimés à l'aide du modèle réduit dont la construction ne nécessite que quelques dizaines d'intégrations du modèle direct. On met à profit l'utilisation du modèle réduit pour réduire le coût de calcul du filtre de Kalman d'Ensemble dans le cadre d'un exercice d'assimilation de données synthétiques de type SWOT. On s'intéresse précisément à la représentation spatiale de la donnée telle que vue par SWOT: couverture globale du réseau, moyennage spatial entre les pixels observés. On montre notamment qu'à budget de calcul donné les résultats de l'analyse d'assimilation de données qui repose sur l'utilisation du modèle réduit sont meilleurs que ceux obtenus avec le filtre classique. On s'intéresse enfin à la construction du modèle réduit en régime instationnaire. On suppose ici que l'incertitude est liée aux coefficients de frottement. Il s'agit à présent de juger de la nécessité du recalcul des coefficients polynomiaux au fil du temps et des cycles d'assimilation de données. Pour ce travail seul des données in-situ ont été considérées. On suppose dans un deuxième temps que l'incertitude est portée par le débit en amont du réseau, qui est un vecteur temporel. On procède à une décomposition de type Karhunen-Loève pour réduire la taille de l'espace incertain aux trois premiers modes. Nous sommes ainsi en mesure de mener à bien un exercice d'assimilation de données. Pour finir, les conclusions et les perspectives de ce travail sont présentées en cinquième partie. / This work deals with the formulation of a surrogate model for the shallow water equations in fluvial hydraulics with a chaos polynomial expansion. This reduced model is used instead of the direct model to reduce the computational cost of the ensemble methods in uncertainty quantification and data assimilation. The context of the study is the flood forecasting and the management of water resources. This manuscript is composed of five parts, each divided into chapters. The first part presents a state of art of uncertainty quantification and data assimilation in the field of hydraulics as well as the objectives of this thesis. We present the framework of flood forecasting, its stakes and the tools available (numerical and observation) to predict the dynamics of rivers. In particular, we present the SWOT2 mission, which aims to measure the height of water in rivers with global coverage at high resolution. We highlight particularty their contribution and their complementarity with the in-situ measurements. The second part presents the shallow water equations, which describe the flows in the rivers. We are particularly interested in a 1D representation of the equations.We formulate a numerical discretization of these equations, as implemented in the Mascaret software. The last chapter of this part proposes some simplifications of the shallow-water equations. The third part of this manuscript presents the uncertainty quantification and reduced order methods. We present particularly the probabilistic context which makes it possible to define well-defined problem of uncertainty quantification and sensitivity analysis. It is then proposed to reduce the size of a stochastic problem when dealing with random fields in the context of geophysical models. The methods of chaos polynomial expansion are then presented ; we present in particular the different strategies for the computation of the polynomial coefficients. This section devoted to methodology concludes with a chapter devoted to Ensemble based data assimilation (specially the Ensemble Kalman filter) and the use of surrogate models in this framework. The fourth part of this manuscript is dedicated to the results. The first step is to identify the sources of uncertainty in hydraulics that should be quantified and subsequently reduced. An article, in the review state, details the method and the validation of a polynomial surrogate model for shallow water equations in steady state when the uncertainty is mainly carried by the friction coefficients and upstream inflow. The study is conducted on the river Garonne. It is shown that the statistical moments, the probability density and the spatial covariance matrice for the water height are efficiently and precisely estimated using the reduced model whose construction requires only a few tens of integrations of the direct model. The use of the surrogate model is used to reduce the computational cost of the Ensemble Kalman filter in the context of a synthetic SWOT like data assimilation exercise. The aim is to reconstruct the spatialized friction coefficients and the upstream inflow. We are interested precisely in the spatial representation of the data as seen by SWOT : global coverage of the network, spatial averaging between the observed pixels. We show in particular that at the given calculation budget (2500 simulations of the direct model) the results of the data assimilation analysis based on the use of the polynomial surrogate model are better than those obtained with the classical Ensemble Kalman filter. We are then interested in the construction of the reduced model in unsteady conditions. It is assumed initially that the uncertainty is carried with the friction coefficients. It is now necessary to judge the need for the recalculation of polynomial coefficients over time and data assimilation cycles. For this work only ponctual and in-situ data were considered. It is assumed in a second step that the uncertainty is carried by the upstr

Le polynôme caractéristique d'une variété abélienne sur un corps fini est défini comme étant celui de son endomorphisme de Frobenius. La première partie de cette thèse est consacrée à l'étude des polynômes caractéristiques de variétés abéliennes de petite dimension. Nous décrivons l'ensemble des polynômes intervenant en dimension 3 et 4, le problème analogue pour les courbes elliptiques et surfaces abéliennes ayant été résolu par Deuring, Waterhouse et Rück.Dans la deuxième partie, nous établissons des bornes supérieures et inférieures sur le nombre de points rationnels des variétés abéliennes sur les corps finis. Nous donnons ensuite des bornes inférieures spécifiques aux variétés jacobiennes. Nous déterminons aussi des formules exactes pour les nombres maximum et minimum de points rationnels sur les surfaces jacobiennes. / The characteristic polynomial of an abelian variety over a finite field is defined to be the characteristic polynomial of its Frobenius endomorphism. The first part of this thesis is devoted to the study of the characteristic polynomials of abelian varieties of small dimension. We describe the set of polynomials which occur in dimension 3 and 4; the analogous problem for elliptic curves and abelian surfaces has been solved by Deuring, Waterhouse and Rück.In the second part, we give upper and lower bounds on the number of points on abelian varieties over finite fields. Next, we give lower bounds specific to Jacobian varieties. We also determine exact formulas for the maximum and minimum number of points on Jacobian surfaces.

Dans certains phénomènes physiques modélisés par des EDP, les coefficients intervenant dans les équations ne sont pas des fonctions déterministes fixées, et dépendent de paramètres qui peuvent varier. Ceci se produit par exemple dans le cadre de la modélisation des écoulements en milieu poreux lorsqu’on décrit le champ de perméabilité par un processus stochastique pour tenir compte de l’incertitude sur ce champs. Dans d’autres cadres, il peut s’agir de paramètres déterministes que l’on cherche à ajuster, par exemple pour optimiser un certain critère sur la solution. La solution u dépend donc non seulement de la variable x d’espace/temps mais aussi d’un vecteur y = (yj) de paramètres potentiellement nombreux, voire en nombre infinis. L’approximation numérique en y de l’application (x,y)-> u(x, y) est donc impossible par les méthodes classiques de type éléments finis, et il faut envisager des approches adaptées aux grandes dimensions. Cette thèse est consacrée à l’étude théorique et l’approximation numérique des EDP paramétriques en grandes dimensions. Pour une large classe d’EDP avec une certaine dépendance anisotrope en les paramètres yj, on étudie de la régularité en y de l’application u et on propose des méthodes d’approximation numérique dont les performances ne subissent pas les détériorations classiquement observées en grande dimension. On cherche en particulier à évaluer la complexité de la classe des solutions {u(y)}, par exemple au sens des épaisseurs de Kolmogorov, afin de comprendre les limites inhérentes des méthodes numériques. On analyse en pratique les propriétés de convergences de diverses méthodes d’approximation avec des polynômes creux. / For certain physical phenomenon that are modelled by PDE, the coefficients intervening in the equations are not fixed deterministic functions, but depend on parameters that may vary.

Cette thèse comporte trois volets indépendants en cryptographie, en théorie de Hodge p-adique et en analyse numérique.La première partie consiste en l'étude d'algorithmes performants de résolution du logarithme discret. La résolution du logarithme discret consiste à déterminer les exposants d'une famille fixée de générateurs dans la décomposition des éléments du groupe. Dans le cas des groupes multiplicatifs d'un corps fini, la complexité des calculs dépendent de la taille - dite de petite, moyenne ou grande caractéristique- de la caractéristique du corps dans lesquels on effectue les calculs.Nous présentons différents algorithmes dans chacune des caractéristiques (petite, moyenne ou grande) en précisant quel est l'algorithme le plus performant dans chacun des cas.La seconde partie s'inscrit dans le contexte du programme de Langlands p-adique. Nous présentons une généralisation de l'un des outils centraux de la théorie, les modules de Breuil-Kisin, en plusieurs variables La troisième partie est un travail effectué en collaboration avec Victor Vilaça Da Rocha, Roberta Tittarelli, Richard Sambilason Rafefimanana, Victor Michel-Dansac et Benjamin Couéraud. Il a été initié lors de la treizième SEME, Semaine d'Etudes Maths Entreprises organisée par l'Agence pour les Mathématiques en Interaction avec l'Entreprise et la Société (AMIES).L'Institut Français du Pétrole et des Energies Nouvelles nous a soumis un problème de résolution numérique d'un système d'équations modélisant la désorption d'un gaz de schiste en une dimension.Nous proposons plusieurs schémas du premier ordre recourant à un traitement implicite de l'équation de relaxation. Enfin nous présentons un schéma numérique d'ordre deux en temps. / In this thesis, we present three independent works in cryptography, p-adic Hodge theory and Numerical analysis.First we present several algorithms to solve the discrete logarithm in several characteristic finite fields. We are particularly interested with the determination of classes of polynomial functions with small coefficients.The second part of the thesis deals with one of the major object of p-adic Hodge theory. We present a multi-variable version of Breuil-Kisin modules where the Lubin-Tate tower replaces the classical cyclotomic tower. He third proposes two numerical schemes for the modelisation of desorption of shale gaz.

L'objet principal de cette thèse est l'étude de plusieurs modèles de polynômes aléatoires. Il s'agit de comprendre le comportement macroscopique des racines de polynômes aléatoires dont le degré tend vers l'infini. Nous explorerons la connexion existant entre les racines de polynômes aléatoires et les gaz de Coulomb afin d'obtenir des principes de grandes déviations pour la mesure empiriques des racines. Nous revisitons l'article de Zeitouni et Zelditch qui établit un principe de grandes déviations pour un modèle général de polynômes aléatoires à coefficients gaussiens complexes. Nous étendons ce résultat au cas des coefficients gaussiens réels. Ensuite, nous démontrons que ces résultats restent valides pour une large classe de lois sur les coefficients, faisant des grandes déviations un phénomène universel pour ces modèles. De plus, nous démontrons tous les résultats précédents pour le modèle des polynômes de Weyl renormalisés. Nous nous intéressons aussi au comportement de la racine de plus grand module des polynômes de Kac. Celle-ci a un comportement non-universel et est en général une variable aléatoire à queues lourdes. Enfin, nous démontrons un principe de grandes déviations pour la mesure empirique des ensembles biorthogonaux. / The main topic of this thesis is the study of the roots of random polynomials from several models. We seek to understand the behavior of the roots as the degree of the polynomial tends to infinity. We explore the connexion between the roots of random polynomials and Coulomb gases to obtain large deviations principles for the empirical measures of the roots of random polynomials. We revisit the article of Zeitouni and Zelditch which establishes the large deviations for a rather general model of random polynomials with independent complex Gaussian coefficients. We extend this result to the case of real Gaussian coefficients. Then, we prove that those results are also valid for a wide class of distributions on the coefficients, which means that those large deviations principles are a universal property. We also prove all of those results for renormalized Weyl polynomials. study the largest root in modulus of Kac polynomials. We show that this random variable has a non-universal behavior and has heavy tails. Finally, we establish a large deviations principle for the empirical measures of biorthogonal ensembles.

Les travaux exposés dans cette thèse se situent à l’interface des mathématiques discrètes, des corps finis et de la cryptographie symétrique.Les 'boîtes-S’ sont des fonctions non-linéaires de petites tailles qui constituent souvent la partie de confusion, indispensable, des chiffrements par blocs ou des fonctions de hachages.Dans la première partie de cette thèse, nous nous intéressons à la construction de boîtes-S bijectives résistantes aux attaques différentielle. Nous étudions l’inverse pour la composition des monômes de permutations optimaux vis-à-vis du critère différentiel. Nous explorons ensuite des classes spécifiques de polynômes creux. Enfin, nous construisons des boîtes-S à partir de leurs dérivées discrètes.Dans la deuxième partie, nous portons notre attention sur la cryptanalyse différentielle impossible. Cette cryptanalyse à clairs choisis très performante pour attaquer des chiffrements par blocs itératifs, exploite la connaissance d’une différentielle de probabilité zéro pour écarter les clés candidates. Elle est très technique, et de nombreuses erreurs ont été repérées dans des travaux passés, invalidant certaines attaques. Le but de ces travaux est de formaliser et d’automatiser l’évaluation des complexités d’une telle attaque afin d’unifier et d’optimiser les résultats obtenus. Nous proposons aussi de nouvelles techniques réduisant les complexités cette cryptanalyse. Nous démontrons enfin l’efficacité de notre approche en fournissant les meilleures cryptanalyses différentielles impossibles contre les chiffrements CLEFIA, Camellia, LBlock et Simon. / The work I have carried out in this thesis lie between discrete mathematics, finite fields theory and symmetric cryptography. In block ciphers, as well as in hash functions, SBoxes are small non-linear and necessary functions working as confusion layer.In the first part of this document, we are interesting in the design of bijective SBoxes that have the best resistance to differential attacks. We study the compositional inverse of the so-called Almost Perfect Nonlinear power functions. Then, we extensively study a class of sparse permutation polynomials with low differential uniformity. Finally, we build functions, over finite fields, from their discrete derivatives.In the second part, we realize an automatic study of a certain class of differential attacks: impossible differential cryptanalysis. This known plaintexts attack has been shown to be very efficient against iterative block ciphers. It exploits the knowledge of a differential with probability zero to occur. However this cryptanalysis is very technical and many flaws have been discovered, thus invalidating many attacks realized in the past. Our goal is to formalize, to improve and to automatize the complexity evaluation in order to optimize the results one can obtain. We also propose new techniques that aims at reducing necessary data and time complexities. We finally prove the efficiency of our method by providing some of the best impossible differential cryptanalysis against Feistel oriented block ciphers CLEFIA, Camellia, LBlock and Simon.

Les défaut de la vision sont analysés et classés à partir des caractéristiques mathématiques du front d’onde de l’oeil considéré. Après avoir présenté la méthode actuelle basée sur la décomposition du front d’onde dans la base orthonormale de Zernike ainsi que certaines de ses limitations, on propose ici une nouvelle base de décomposition. Celle-ci repose sur l’utilisation del’espace des fronts d’onde polynomiaux de valuation supérieure ou égale à L + 1 (où L est un entier naturel) et permet de décomposer de manière unique un front d’onde polynomial en la somme d’un front d’onde polynomial de bas degré (inférieur ou égal à L) et un front d’onde polynomial de haute valuation (supérieure ou égal à L + 1). En choisissant L = 2, une nouvelle décomposition est obtenue, appelée D2V3, où le front d’onde polynomial de haut degré ne comporte pas de termes de degré radial inférieur ou égal à deux. Cette approche permet de dissocier parfaitement les aberrations optiques corrigibles ou non par le port de lunettes. Différents cas cliniques présentés dans la dernière section permettent de mettre en évidence l’intérêt de cette nouvelle base de décomposition. / The eye vision defaults are analyzed and classified by studyingthe corresponding eye wavefront. After presenting the orthogonal basis, called the Zernike basis, that is currently used for the medical diagnosis, a new decomposition basis is built. It is based on the use of the space of polynomials of valuation greater or equal to L+1 (for L a natural integer). It allows to uniquely decompose a polynomial wavefront into the sum of a polynomial of low degree (lesser or equal to L) and a polynomial of high valuation (greater or equal to L +1). By choosing L = 2, a new decomposition, called D2V3, is obtained where the polynomial wavefront of high degree does not include terms of radial degree lesser or equal to 2. In particular, it allows to quantify perfectly the aberrations that can be corrected by eyeglasses or not. Various clinical examples clearly show the interest of this new basis compared to a diagnosis based on the Zernike decomposition.

Le problème généralisé des moments (PGM) est un problème d'optimisation linéaire sur des espaces de mesures. Il permet de modéliser simplement un grand nombre d'applications. En toute généralité il est impossible à résoudre mais si ses données sont des polynômes et des ensembles semi-algébriques alors on peut définir une hiérarchie de relaxations semidéfinies (SDP) - la hiérarchie moments-sommes-de-carrés (moments-SOS) - qui permet en principe d'approcher la valeur optimale avec une précision arbitraire. Le travail contenu dans cette thèse adresse deux facettes concernants le PGM et la hiérarchie moments-SOS: Une première facette concerne l'évolution des relaxations SDP pour le PGM. Le degré des poids SOS dans la hiérarchie moments-SOS augmente avec l'ordre de relaxation. Lorsque le nombre de variables n'est pas modeste, on obtient rapidement des programmes SDP de taille trop grande pour les logiciels de programmation SDP actuels, sauf si l'on peut utiliser des symétries ou une parcimonie structurée souvent présente dans beaucoup d'applications de grande taille. On présente donc un nouveau certificat de positivité sur un compact semi-algébrique qui (i) exploite la parcimonie présente dans sa description, et (ii) dont les polynômes SOS ont un degré borné à l'avance. Grâce à ce nouveau certificat on peut définir une nouvelle hiérarchie de relaxations SDP pour le PGM qui exploite la parcimonie et évite l'explosion de la taille des matrices semidéfinies positives liée au degré des poids SOS dans la hiérarchie standard. Une deuxième facette concerne (i) la modélisation de nouvelles applications comme une instance particulière du PGM, et (ii) l'application de la méthodologie moments-SOS pour leur résolution. En particulier on propose des approximations déterministes de contraintes probabilistes, un problème difficile car le domaine des solutions admissibles associées est souvent non-convexe et même parfois non connecté. Dans notre approche moments-SOS le domaine admissible est remplacé par un ensemble plus petit qui est le sous-niveau d'un polynôme dont le vecteur des coefficients est une solution optimale d'un certain SDP. La qualité de l'approximation (interne) croît avec le degré du polynôme et la taille du SDP. On illustre cette approche dans le problème du calcul du flux de puissance optimal dans les réseaux d'énergie, une application stratégique où la prise en compte des contraintes probabilistes devient de plus en plus cruciale (e.g., pour modéliser l'incertitude liée á l'énergie éolienne et solaire). En outre on propose une extension des cette procedure qui est robuste à l'incertitude sur la distribution sous-jacente. Des garanties de convergence sont fournies. Une deuxième contribution concerne l'application de la méthodologie moments-SOS pour l'approximation de solutions généralisés en commande optimale. Elle permet de capturer le comportement limite d'une suite minimisante de commandes et de la suite de trajectoires associée. On peut traiter ainsi le cas de phénomènes simultanés de concentrations de la commande et de discontinuités de la trajectoire. Une troisième contribution concerne le calcul de solutions mesures pour les lois de conservation hyperboliques scalaires dont l'exemple typique est l'équation de Burgers. Cette classe d'EDP non linéaire peut avoir des solutions discontinues difficiles à approximer numériquement avec précision. Sous certaines hypothèses, la solution mesurepeut être identifiée avec la solution classique (faible) à la loi de conservation. Notre approche moment-SOS fournit alors une méthode alternative pour approcher des solutions qui contrairement aux méthodes existantes évite une discrétisation du domaine. / The generalized moment problem (GMP) is a linear optimization problem over spaces of measures. It allows to model many challenging mathematical problems. While in general it is impossible to solve the GMP, in the case where all data are polynomial and semialgebraic sets, one can define a hierarchy of semidefinite relaxations - the moment-sums-of-squares (moment-SOS) hierachy - which in principle allows to approximate the optimal value of the GMP to arbitrary precision. The work presented in this thesis addresses two facets concerning the GMP and the moment-SOS hierarchy: One facet is concerned with the scalability of relaxations for the GMP. The degree of the SOS weights in the moment-SOS hierarchy grows when augmenting the relaxation order. When the number of variables is not small, this leads quickly to semidefinite programs (SDPs) that are out of range for state of the art SDP solvers, unless one can use symmetries or some structured sparsity which is typically present in large scale applications. We provide a new certificate of positivity which (i) is able to exploit the structured sparsity and (ii) only involves SOS polynomials of fixed degree. From this, one can define a new hierarchy of SDP relaxations for the GMP which can take into account sparsity and at the same time prevents from explosion of the size of SDP variables related to the increasing degree of the SOS weights in the standard hierarchy. The second facet focusses on (i) modelling challenging problems as a particular instance of the GMP and (ii) solving these problems by applying the moment-SOS hierarchy. In particular we propose deterministic approximations of chance constraints a difficult problem as the associated set of feasible solutions is typically non-convex and sometimes not even connected. In our approach we replace this set by a (smaller) sub-level-set of a polynomial whose vector of coefficients is a by-product of the moment-SOS hierarchy when modeling the problem as an instance of the GMP. The quality of this inner approximation improves when increasing the degree of the SDP relaxation and asymptotic convergence is guaranteed. The procedure is illustrated by approximating the feasible set of an instance of the chance-constrained AC Optimal Power Flow problem (a nonlinear problem in the management of energy networks) which nowadays becomes more and more important as we rely increasingly on uncertain energy sources such as wind and solar power. Furthermore, we propose an extension of this framework to the case where the underlying distribution itself is uncertain and provide guarantees of convergence. Another application of the moment-SOS methodology discussed in this thesis consider measure valued solutions to optimal control problems. We show how this procedure can capture the limit behavior of an optimizing sequence of control and its corresponding sequence of trajectories. In particular we address the case of concentrations of control and discontinuities of the trajectory may occur simultaneously. In a final contribution, we compute measure valued solutions to scalar hyperbolic conservation laws, such as Burgers equation. It is known that this class of nonlinear partial differential equations has potentially discontinuous solutions which are difficult to approximate numerically with accuracy. Under some conditions the measure valued solution can be identified with the classical (weak) solution to the conservation law. In this case our moment-SOS approach provides an alternative numerical scheme to compute solutions which in contrast to existing methods, does not rely on discretization of the domain.

Un circuit arithmétique dont les entrées sont des entiers ou une variable x et dont les portes calculent la somme ou le produit représente un polynôme univarié. On assimile la complexité de représentation d'un polynôme par un circuit arithmétique au nombre de portes multiplicatives minimal requis pour cette modélisation. Et l'on cherche à obtenir une borne inférieure à cette complexité, et cela en fonction du degré d du polynôme. A une chaîne additive pour d, correspond un circuit arithmétique pour le monôme de degré d. La conjecture de Strassen prétend que le nombre minimal de portes multiplicatives requis pour représenter un polynôme de degré d est au moins la longueur minimale d'une chaîne additive pour d. La conjecture de Strassen généralisée correspondrait à la même proposition lorsque les portes du circuit arithmétique ont degré entrant g au lieu de 2. Le mémoire consiste d'une part en une généralisation du concept de chaînes additives, et une étude approfondie de leur construction. On s'y intéresse d'autre part aux polynômes qui peuvent être représentés avec très peu de portes multiplicatives (les d-gems). On combine enfin les deux études en lien avec la conjecture de Strassen. On obtient en particulier de nouveaux cas de circuits vérifiant la conjecture. / An arithmetic circuit with inputs among x and the integers which has product gates and addition gates represents a univariate polynomial. We define the complexity of the representation of a polynomial by an arithmetic circuit as the minimal number of product gates required for this modelization. And we seek a lower bound to this complexity, with respect to the degree d of the polynomial. An addition chain for d corresponds to an arithmetic circuit computing the monomial of degree d. Strassen's conjecture states that the minimal number of product gates required to represent a polynomial of degree d is at least the minimal length of an addition chain for d. The generalized Strassen conjecture corresponds to the same statement where the indegree of the gates of the arithmetic circuit is g instead of 2. The thesis consists, on the one hand, of the generalization of the concept of addition chains, and a study of the subject. On the other hand, it is concerned with polynomials which can be represented with very few product gates (d-gems). Both studies related to Strassen's conjecture are combined. In particular, we get new classes of circuits verifying the conjecture.