Les systèmes informatiques jouent un rôle essentiel dans la vie actuelle, et leurs erreurs peuvent avoir des conséquences dramatiques. Il existe des méthodes formelles permettant d'assurer qu'un système informatique est fiable. La méthode formelle utilisée dans cette thèse est appelée complétion d'automates d'arbres et permet d'analyser les systèmes à nombre d'états infini. Dans cette représentation, les états du système sont représentés par des termes et les ensembles d'états par des automates d'arbres. L'ensemble des comportements possibles d'un système est calculé grâce à l'application successive d'un système de réécriture modélisant le comportement du système vérifié. On garantit la fiabilité d'un système en vérifiant qu'un comportement interdit n'est pas présent dans l'ensemble des états accessibles. Mais cet ensemble n'est pas toujours calculable, et nous devons alors calculer une sur-approximation calculable de cet ensemble. Mais cette approximation peut s'avérer trop grossière et reconnaître de faux contre-exemples. La première contribution de cette thèse consiste alors à caractériser, par des formules logiques et de manière automatique, ce qu'est une "bonne" sur-approximation : une approximation représentant un sur-ensemble des configurations accessibles, et qui soit suffisamment précise pour ne pas reconnaître de faux contre-exemples. Résoudre ces formules conduit alors automatiquement à une sur-approximation concluante si elle existe, sans avoir recours à aucun paramétrage manuel. Le second problème de la complétion d'automates d'arbres est le passage à l'échelle, autrement dit le temps de calcul parfois élevé du calcul de complétion quand on s'attaque à des problèmes de la vie courante. Dans la vérification de programmes Java utilisant la complétion d'automates d'arbres, cette explosion peut être due à l'utilisation d'entiers de Peano. L'idée de notre seconde contribution est alors d'évaluer directement le résultat d'une opération arithmétique. D'une façon plus générale, il s'agit d'intégrer les éléments d'un domaine infini dans un automate d'arbres. En s'inspirant de méthodes issues de l'interprétation abstraite, cette thèse intègre des treillis abstraits dans les automates d'arbres, constituant alors un nouveau type d'automates. Les opérations sur le domaine infini représenté sont calculées en une seule étape d'évaluation plutôt que d'appliquer de nombreuses règles de réécriture. Nous avons alors adapté la complétion d'automates d'arbres à ce nouveau type d'automate, et la généricité du nouvel algorithme permet de brancher de nombreux treillis abstraits. Cette technique a été implémentée dans un outil appelé TimbukLTA, et cette implémentation permet de démontrer l'efficacité de cette technique.

Ces dernières années, les systèmes de communication sans fil utilisant plusieurs antennes en émission et en réception, couramment appelés systèmes MIMO, sont apparus comme une solution très prometteuse pour améliorer le débit et la fiabilité des transmissions de données. Dans le but de répartir l'information sur les différentes antennes d'émission, une multitude de codes temps-espace a été proposée dans la littérature. Parmi ces schémas de codage, les codes temps-espace en treillis (STTCs), basés sur des modulations codées en treillis dans un contexte multi-antennaire, se sont distingués comme offrant un très bon gain de codage. Des critères ont été élaborés pour analyser les performances des STTCs. Cependant, pour identifier les codes offrant les meilleures performances, il est nécessaire d'appliquer ces critères sur la totalité des codes. Cette recherche exhaustive nécessite un temps important de calcul, en particulier lorsque le nombre d'antennes d'émission, le nombre d'états du codeur ou encore la complexité de la modulation augmentent. Le but de cette thèse est de proposer des solutions rapides et efficaces pour construire les meilleurs STTCs sans avoir recours à une recherche exhaustive. Dans un premier temps, une nouvelle méthode de construction des STTCs $2^n$-PSK équilibrés est présentée. L'avantage de cette classe de codes est de contenir l'ensemble des STTCS offrant les meilleures performances. Il suffit alors d'analyser seulement les STTCs $2^n$-PSK équilibrés pour trouver les meilleurs STTCs. Une deuxième méthode appelée 'coset partitioning' est ensuite présentée. Exploitant une approche en cosets du set partitioning proposé par Ungerboeck, elle permet de générer de manière optimale les STTCs $2^n$2n-PSK les plus performants. Ainsi, les meilleurs STTCs 4-PSK de 2 à 8 antennes d'émission et les meilleurs STTCs 8-PSK de 2 à 6 antennes d'émission sont proposés. Par la suite, nous nous intéressons à la génération des STTCs $2^{2n}$-QAM. Basée sur la décomposition de la distance euclidienne entre deux mots de code, une méthode permettant la génération des meilleurs STTCs $2^{2n}$-QAM est décrite. Ainsi, grâce à l'efficacité de cette méthode, pour la première fois, des STTCs 16-QAM avec 3 et 4 antennes et des STTCs 64-QAM avec 2 et 3 antennes d'émission sont construits. Par ailleurs, les performances de tous les nouveaux codes proposés durant ces travaux de thèse sont évaluées par simulation en présence de canaux lents ou rapides de Rayleigh et en prenant en référence les meilleurs codes correspondants jusqu'alors publiés (lorsqu'ils existent).

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

Grâce à la fabrication additive, il est aujourd'hui possible de fabriquer de nouvelles géométries. Les perspectives offertes par les moyens de fabrications conventionnelles et additives sont très différentes. Des propositions de design très contraintes peuvent devenir beaucoup plus libres avec la fabrication additive. Cette liberté qu'elle offre fait émerger une multitude de possibilités. Dans ce manuscrit, nous nous sommes focalisés sur un type particulier de structures (les octetruss) ainsi que sur les moyens de fabrication EBM (Electron Beam Melting) de la société ARCAM. Les travaux présentés dans cette thèse ont été réalisés au sein des laboratoires G-SCOP et SIMAP ainsi qu'en partenariat avec l'entreprise POLY-SHAPE. Ce manuscrit est articulé autour de trois principaux points.Il s'agit tout d'abord de faire émerger des structures treillis lors du processus de conception. Pour cela, deux approches existantes sont détaillées. La première met en œuvre l'optimisation topologique et la seconde s'appuie sur le concept de matériau équivalent. Ensuite deux méthodologies permettent de faire émerger des zones dans lesquelles l'intégration de structures treillis est adaptée. La première consiste à réaliser les différentes zones en s'appuyant sur un champ de contraintes issu d'un calcul Eléments Finis, la seconde se base sur un résultat d'optimisation topologique pour établir les différentes zones. Cette seconde méthodologie est appliquée à un cas d'étude industriel.Ensuite nous étudions comment remplir les différentes zones avec des structures treillis adaptées en nous focalisant tout d'abord sur leur génération. Un accent particulier est porté sur l'intersection des différents barreaux par la mise en place de sphères. Une méthodologie permettant de générer des arrondis est également proposée. Une étude est menée sur l'ensemble des paramètres et informations à considérer pour intégrer une structure treillis à une zone donnée. Cette étude conduit à une proposition de méthodologie qui est appliquée à un cas d'étude industriel.Enfin, les aspects liés à la fabrication sont pris en compte. Pour cela, nous considérons différentes limites du moyen de fabrication EBM pour des structures treillis comme les dimensions maximales réalisables ou les problématiques thermiques. Une étude consistant à prédire la dépoudrabilité des pièces est réalisée. Enfin, des essais mécaniques sont effectués. Nos résultats sont comparés à ceux obtenus dans d'autres travaux. L'impact des arrondis sur le comportement mécanique d'une pièce est discuté. / Thanks to additive manufacturing, it is now possible to manufacture new geometric shapes. The prospects offered by the methods of conventional and additive manufacturing are very different. Highly constrained design proposals can become much freer with additive manufacturing. The freedom it offers brings forward a multitude of possibilities. In this manuscript, we focused on a particular type of structures (the octetruss) as well as the use of EBM (Electron Beam Melting) of ARCAM as a means of manufacturing. The work presented in this thesis was carried out in the laboratories G-SCOP and SIMAP as well as in partnership with the company POLY-SHAPE. This manuscript focuses on three main points.The first of which is the action of emergence of lattice structures during the design process. For this, two existing approaches are detailed. The first uses topological optimization and the second is based on the concept of equivalent material. Following these, there are two methodologies used to identify areas in which the integration of lattice structures is possible and appropriate. The first consists of creating the different zones by relying on a stress field resulting from a finite element calculation, the second establishes the different zones using a topological optimization result. This second methodology is applied to an industrial case study.Secondly, we study how to fill the different areas with appropriate lattice structures by focusing first on their generation. Particular emphasis is placed on the intersection of the various bars by the establishment of spheres. A methodology for generating rounded-shape is also proposed. A study is carried out on all the parameters and information in order to integrate a lattice structure to a given area. This study leads to a proposed methodology that is applied to an industrial case study.Finally, aspects related to manufacturing are taken into account. For this, we consider different limits of the EBM manufacturing and what they mean for lattice structures; such as maximum achievable dimensions or thermal problems. A study to predict powder removal in order to extract the fabricated structure is performed. Mechanical tests are carried out. Our results are compared to those obtained in other works. The impact of curve on the mechanical behavior of a product is discussed.

Cette thèse a pour objectif l"établissement de méthodes numériques pour l'optimisation multi-objectif de structures soumises à des facteurs incertains. Au cœur de ce travail, nous nous sommes focalisés sur l'adaptation du chaos polynomial pour l'évaluation non intrusive de la part de l'incertain. Pour atteindre l'objectif fixé, nous sommes confrontés à deux verrous : l'un concerne les coûts élevés de calcul d'une simulation unitaire par éléments finis, l'autre sa précision limitée. Afin de limiter la charge de calcul pour la construction du chaos polynomial, nous nous sommes concentrés sur la construction d'un chaos polynomial creux. Nous avons également développé un programme d’échantillonnage basé sur l’hypercube latin personnalisé prenant en compte la précision limitée de la simulation. Du point de vue de la modélisation nous avons proposé une approche multi-fidèle impliquant une hiérarchie de modèles allant des simulations par éléments finis complètes jusqu'aux surfaces de réponses en passant par la réduction de modèles basés sur la physique. Enfin, nous avons étudié l'optimisation multi-objectif de structures sous incertitudes. Nous avons étendu le modèle PCE des fonctions objectif à la prise en compte des variables déterministes de conception. Nous avons illustré notre travail sur des exemples d'emboutissage et sur la conception optimale des structures en treillis. / This thesis aims at Multi-Objective Optimization under Uncertainty in structural design. We investigate Polynomial Chaos Expansion (PCE) surrogates which require extensive training sets. We then face two issues: high computational costs of an individual Finite Element simulation and its limited precision. From numerical point of view and in order to limit the computational expense of the PCE construction we particularly focus on sparse PCE schemes. We also develop a custom Latin Hypercube Sampling scheme taking into account the finite precision of the simulation. From the modeling point of view,we propose a multifidelity approach involving a hierarchy of models ranging from full scale simulations through reduced order physics up to response surfaces. Finally, we investigate multiobjective optimization of structures under uncertainty. We extend the PCE model of design objectives by taking into account the design variables. We illustrate our work with examples in sheet metal forming and optimal design of truss structures.

.

.

On souhaite reconstruire en ligne des signaux à échantillons manquants en utilisant une approche paramétrique. On propose alors des algorithmes adaptatifs d'identification et de reconstruction de processus AR à échantillons manquants. On s'intéresse premièrement à l'extension des algorithmes de gradient au cas des signaux à échantillons manquants. On propose alors deux alternatives à un algorithme existant fondées sur deux autres prédicteurs. Les algorithmes proposés convergent vers une estimation non biaisée des paramètres. Or les algorithmes de gradient souffrent d'une faible vitesse de convergence. Pour cela, on s'intéresse à l'extension de l'algorithme MCR au cas des signaux à échantillons manquants. On utilise alors l'algorithme MCR pseudo-linéaire pour l'identification conjointement avec un filtre de Kalman pour une prédiction optimale du signal au sens des moindres carrés. L'algorithme résultant permet une identification non biaisée des paramètres. De plus, il est rapide et bien adapté à l'identification de processus non stationnaires. Néanmoins, souhaitant contrôler la stabilité du filtre identifié, on s'intéresse ensuite à une identification fondée sur une structure en treillis du filtre. Ainsi, on propose une extension de l'algorithme de Burg adaptatif au cas des signaux à échantillons manquants, en utilisant pour la prédiction un filtre de Kalman. La stabilité du modèle ainsi identifié est garantie. De plus, l'algorithme s'adapte rapidement aux variations des paramètres. Finalement, on propose d'utiliser les algorithmes proposés dans un système à transmission non uniforme. On obtient ainsi l'amélioration simultanée du RSB et du débit de transmission moyen.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

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 / This thesis comes within the scope of algebraic combinatorics and studies problems related to three orders on permutations: the two said weak orders (right and left) and the strong order or Bruhat order.We first look at the action of the symmetric group on multivariate polynomials. By using the emph{divided differences} operators, one can obtain some generalisations of the Schur function and form bases of non symmetric multivariate polynomials. This construction is similar to the one of Schur functions and also allows for geometric interpretations. We study more specifically the Grothendieck polynomials which were introduced by Lascoux and Schützenberger. Lascoux proved that a product of these polynomials can be interpreted in terms of a product of divided differences. By developing this product, we reobtain a result of Lenart and Postnikov and also prove that it can be interpreted as a sum over an interval of the Bruhat order. We also present our implementation of multivariate polynomials in Sage. This program allows for formal computation on different bases and also implements many changes of bases. It is based on the action of the divided differences operators. The bases include Schubert polynomials, Grothendieck polynomials and Key polynomials. In a second part, we study the emph{Tamari lattice} on binary trees. This lattice can be obtained as a quotient of the weak order. Each tree is associated with the interval of its linear extensions. We introduce a new object called, emph{interval-posets} of Tamari and show that they are in bijection with the intervals of the Tamari lattice. Using these objects, we give the recursive formula counting the number of elements smaller than or equal to a given tree. We also give a new proof that the generating function of the intervals of the Tamari lattice satisfies some functional equation given by Chapoton. Our final contributions deals with the $m$-Tamari lattices. This family of lattices is a generalization of the classical Tamari lattice. It was introduced by Bergeron and Préville-Ratelle and was only known in terms of paths. We give the description of this order in terms of some family of binary trees, in bijection with $m+1$-ary trees. Thus, we generalize our previous results and obtain a recursive formula counting the number of elements smaller than or equal to a given one and a new proof of the functional equation. We finish with the description of some new $"m"$ Hopf algebras which are generalizations of the known $FQSym$ on permutations and $PBT$ on binary trees