Nous considérons plusieurs problèmes autour des matrices à signes alternants (MSA). Dans un premier chapitre nous donnons une formule de comptage des MSAs selon le nombre k de -1 qu'elles contiennent et leur taille n. Cette formule permet d'obtenir une évaluation asymptotique pour un k donné lorsque n tend vers l'infini et une expression simple pour les valeurs de k inférieures ou égales à 7.Une deuxième partie est consacrée à une famille de MSAs dont les triangles Gogs (ou triangles monotones) associés sont en bijection avec une famille de triangles Magogs (ou des partition planes auto complémentaires symétriques). Nous présentons une méthode de minoration du nombre d'éléments de taille n dans cette famille d'objets.Enfin, nous évaluons la probabilité d'apparition de motifs (sous-diagrammes) dans des diagrammes de cordes tirés selon la distribution limite introduite par la conjecture de Razumov et Stroganov. / Abstract

Cette thèse se situe dans le domaine de la combinatoire algébrique. Autrement dit, l'idée est d'utiliser des structures algébriques, en l'occurence des algèbres de Hopf combinatoires, pour mieux étudier et comprendre les objets combinatoires ainsi que des algorithmes de composition et de décomposition agissant sur ces objets. Ce travail de recherche repose sur la construction et l'étude de structure algébrique sur des objets combinatoires généralisant les permutations. Après avoir rappelé le contexte et les notations des différents objets intervenant dans cette recherche, nous proposons dans la seconde partie l'étude de l'algèbre de Hopf introduite par Aguiar et Orellana indexée par les permutations de blocs uniformes. En se focalisant sur une description de ces objets via d'autres bien connus, les permutations et les partitions d'ensembles, nous proposons une réalisation polynomiale et une étude plus simple de cette algèbre. La troisième partie étudie une deuxième généralisation en interprétant les permutations comme des matrices. Nous définissons et étudions alors des familles de matrices carrées sur lesquelles nous définissons des algorithmes de composition et de décomposition. La quatrième partie traite des matrices à signes alternants. Après avoir définie l'algèbre de Hopf sur ces matrices, nous étudions des statistiques et le comportement de la structure algébrique vis-à-vis de ces statistiques. Tous ces chapitres s'appuient fortement sur l'exploration informatique, et fait l'objet d'une implémentation utilisant le logiciel Sage. Ce dernier chapitre est consacré à la découverte et la manipulation de structures algébriques sur Sage. Nous terminons en expliquant les améliorations apportées pour l'étude de structure algébrique au travers du logiciel Sage / This thesis is in the field of algebraic combinatorics. In other words, the idea is to use algebraic structures, in this case of combinatorial Hopf algebras, to better study and understand the combinatorial objects and algorithms for composition and decomposition about these objects. This research is based on the construction and study of algebraic structure of combinatorial objects generalizing permutations. After recalling the background and notations of various objects involved in this research, we propose, in the second part, the study of the Hopf algebra introduced by Aguiar and Orellana based on uniform block permutations. By focusing on a description of these objects via well-known objects, permutations and set partitions, we propose a polynomial realization and an easier study of this algebra. The third section considers a second generalization interpreting permutations as matrices. We define and then study the families of square matrices on which we define algorithms for composition and decomposition. The fourth part deals with alternating sign matrices. Having defined the Hopf algebra of these matrices, we study the statistics and the behavior of the algebraic structure with these statistics. All these chapters rely heavily on computer exploration, and is the subject of an implementation using Sage software. This last chapter is dedicated to the discovery and manipulation of algebraic structures on Sage. We conclude by explaining the improvements to the study of algebraic structure through the Sage software

Cette HDR présente mes travaux récents en combinatoire (énumérative et algébrique) autour du groupe symétrique, et répartis sur trois axes principaux : les co-quasi-invariants polynomiaux, les matrices à signes alternants et les tableaux boisés.

La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'art. / Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.