La caractérisation des incertitudes est un enjeu essentiel qui permet une conception fiable des structures. Par ailleurs, la surveillance du phénomène de vieillissement est primordiale pour l'inspection et la prévention des risques. Ces deux enjeux peuvent être étudiés simultanément dans une analyse de fiabilité dépendante du temps. Toutefois, une telle analyse est souvent complexe et très couteuse en temps de calcul parce qu'elle demande plusieurs évaluations du modèle physique décrivant la performance de la structure. Dans ce contexte, on propose l'utilisation de la métamodélisation pour l'analyse de fiabilité dépendante du temps, concept largement exploré dans le cas de problèmes indépendants du temps. Ceci consiste à remplacer le modèle physique par un métamodèle analytique facile à évaluer de sorte que la méthode de simulation de Monte-Carlo peut être utilisée à coût de calcul réduit. D'autres problèmes sont liés aussi à ce type d'analyse, notamment la grande dimensionnalité du problème, la non Gaussianité et non stationnarité des processus stochastiques mis en jeu et la non linéarité de la fonction d'état limite. La thèse vise alors à proposer des méthodes précises mais aussi efficaces pour l'analyse de fiabilité dépendant du temps qui permettent de surmonter ces difficultés. Elle propose également une extension de ces méthodes au problème de conception fiabiliste dépendant du temps. / Uncertainty quantification is essential for designing reliable structures. Moreover, monitoring the aging process is of vital importance for the inspection and prevention of risks. These two aspects may be considered simultaneously throughout a time-variant reliability analysis. However, such analysis is in general complex and very time consuming because it requires numerous evaluations of the mechanical model describing the structural behavior. To overcome this issue, we propose to use the metamodeling approach that has been widely explored in the context of the probabilistic analysis, for time-variant reliability problems. This consists in replacing the mechanical model with a simple analytical function that is easy to evaluate and on which Monte-Carlo simulation can be performed at a low computational cost. Other challenges also encounter this analysis and are basically related to the high dimensionality of the problem, the non Gaussianity and non stationarity of the input stochastic processes and the non linearity of the limit state function. The thesis aims then to develop accurate and efficient approaches for time-variant reliability analysis that overcome the aforementioned difficulties. It also proposes to extend these methods to the field of time-variant reliability-based design optimization.

La sécurité de la cryptographie à clés publiques repose sur des problèmes mathématiques difficiles, notamment en théorie des nombres, tels que la factorisation pour RSA ou le logarithme discret pour ElGamal. Cependant les progrès des algorithmes rendent les protocoles basés sur des problèmes de théorie des nombres de moins en moins efficaces. De plus, l'arrivée de l'ordinateur quantique rendrait ces cryptosystèmes inutilisables. La cryptographie basée sur les codes en métrique rang est une alternative crédible pour concevoir des cryptosystèmes post-quantiques en raison de sa rapidité et de la faible taille de ses clés. Le but de cette thèse est d'étudier les problèmes difficiles en métrique rang et les algorithmes permettant de les résoudre, ainsi que de chercher de nouvelles attaques et de nouvelles primitives basées sur ces problèmes. / Security of public keys cryptography is based on difficult mathematic problems, especially in number field theory, such as the factorization for RSA or the discrete logarithm for ElGamal. However, algorithms are more and more efficient to solve these problems. Furthermore, quantum computers would be able to easily break these cryptosystems. Code-based cryptography in rank metric is a solid candidate to design new postquatum cryptosystems since it is fast and has low weight keysize. The goals of this thesis are to study hard problems in rank metric and algorithms which solve them, also to search for new attacks and new primitives based on these problems.

Die Kürzung einer Rang-k-Matrix ist ein wichtiger Bestandteil der Technik der Hierarchischen Matrizen. In dieser Arbeit untersuchen wir zwei verschiedene Kürzungsalgorithmen auf ihre Parallelisierbarkeit. Zuerst werden wir die sequentiellen Versionen der Algorithmen einführen, ihre Komplexitat untersuchen und diese Ergebnisse in numerischen Experimenten validieren. Danach parallelisieren wir beide Algorithmen und untersuchen ihr Laufzeitverhalten theoretisch und anhand von numerischen Experimenten auf Rechensystemen mit verteiltem und geteiltem Speicher. Es zeigt sich, dass beide Algorithmen gut parallelisierbar sind, wobei wir bei Rechensystemen mit verteiltem Speicher die Anzahl der verwendeten Prozessoren an die Groesse der zu kuerzenden Matrix anpassen sollten, damit wir einen linearen Speedup erreichen.

La présente étude cherche à identifier si le sexe de l'enfant, son rang de naissance et l'interaction entre ces deux variables amènent deux enfants d'une même famille à percevoir différents niveaux de soutien à l'autonomie, d'engagement et de structure offert par leurs parents à leur égard. L'échantillon est composé de 54 participants répartis en 27 dyades de frères et soeurs. Étant donné la présence de données nichées, des analyses par modélisation linéaire hiérarchique ont été réalisées afin de répondre à la question de recherche. Celles-ci montrent que les perceptions des enfants, au plan du soutien à l'autonomie et de la structure offerts par leurs parents, varient en fonction de l'interaction entre le sexe et le rang de naissance de l'enfant. Plus spécifiquement, les filles aînées perçoivent recevoir davantage de soutien de la part de leurs parents, suivi par les garçons cadets, les filles cadettes et les garçons aînés. De même, les garçons cadets perçoivent une plus grande structure familiale, suivi des filles aînées, des filles cadettes et finalement, des garçons aînés. Aucun résultat significatif ne fut observé en ce qui a trait aux perceptions des enfants à l'égard de l'engagement de leurs parents en fonction de leur sexe et de leur rang de naissance. Les résultats sont discutés à la lumière des écrits scientifiques sur la parentalité.

Quantitative aspects of systems, like the maximal consumption of resources, can be modeled by weighted automata. The usual approach is to weight transitions with elements of a semiring and to define the behavior of the weighted automaton by mul- tiplying the transition weights along a run. In this thesis, we define and investigate a new class of weighted automata over unranked trees which are defined over valuation monoids. By turning to valuation monoids we use a more general cost model: the weight of a run is now determined by a global valuation function. Besides the binary cost functions implementable via semirings, valuation functions enable us to cope with average and discounting. We first investigate the supports of weighted unranked tree automata over valuation monoids, i.e., the languages of all words which are evalu- ated to a non-zero value. We will furthermore consider the support of several other weighted automata models over different structures, like words and ranked trees. Next we prove a Nivat-like theorem for the new weighted unranked tree automata. More- over, we give a logical characterization for them. We show that weighted unranked tree automata are expressively equivalent to a weighted MSO logic for unranked trees. This solves an open problem posed by Droste and Vogler. Finally, we present a Kleene- type result for weighted ranked tree automata over valuation monoids.

Quantitative aspects of systems, like the maximal consumption of resources, can be modeled by weighted automata. The usual approach is to weight transitions with elements of a semiring and to define the behavior of the weighted automaton by mul- tiplying the transition weights along a run. In this thesis, we define and investigate a new class of weighted automata over unranked trees which are defined over valuation monoids. By turning to valuation monoids we use a more general cost model: the weight of a run is now determined by a global valuation function. Besides the binary cost functions implementable via semirings, valuation functions enable us to cope with average and discounting. We first investigate the supports of weighted unranked tree automata over valuation monoids, i.e., the languages of all words which are evalu- ated to a non-zero value. We will furthermore consider the support of several other weighted automata models over different structures, like words and ranked trees. Next we prove a Nivat-like theorem for the new weighted unranked tree automata. More- over, we give a logical characterization for them. We show that weighted unranked tree automata are expressively equivalent to a weighted MSO logic for unranked trees. This solves an open problem posed by Droste and Vogler. Finally, we present a Kleene- type result for weighted ranked tree automata over valuation monoids.

La mise au point de descripteurs locaux discriminants est aujourd'hui une priorité dans de nombreuses applications comme la reconnaissance d'objets, le suivi d'objets, la reconstruction 3D ou l'estimation de mouvement. La problématique réside dans le fait que ces descripteurs doivent être invariants aux conditions d'acquisition tout en conservant un pouvoir discriminant important. Dans ce contexte, nous nous sommes intéressés à l'invariance des descripteurs locaux de la littérature. Nous les avons notamment catégorisés en fonction des hypothèses sur lesquelles repose leur invariance. Ensuite, nous avons proposé des descripteurs locaux qui exploitent l'information de couleur dans les images. Nous avons montré que cette information peut être très pertinente lorsqu'elle est combinée à une information spatiale, à condition que son degré d'invariance soit contrôlé et adapté aux applications considérées. Ainsi, nous avons proposé un ensemble de descripteurs locaux couleur avec des degrés d'invariance différents. Ainsi, nous introduisons tout d'abord deux nouveaux descripteurs qui caractérisent les distributions spatiales des couleurs dans les régions analysées. L'idée originale consiste à appliquer des transformations affines entre les coordonnées spatiales des pixels et leurs coordonnées couleur. En effet, chaque pixel étant caractérisé par 5 valeurs, 2 coordonnées spatiales xy dans l'image et 3 composantes couleur RVB, nous proposons de rechercher une transformation affine qui permet de transformer les coordonnées xy de tous les pixels de la région concernée en coordonnées RVB de ces pixels. Nous montrons que l'application de cette transformation aux coordonnées xy fournit des coordonnées dans l'espace RVB qui a un double avantage. D'une part, les coordonnées d'un seul pixel dépendent à la fois de toutes les couleurs présentes dans la région mais aussi de leur répartition spatiale. Quelques coordonnées permettent donc de résumer efficacement le contenu de la région. D'autre part, ces coordonnées présente une invariance totale à toute transformation affine appliquée dans l'espace image 2D(invariance géométrique) et comme elles sont homogènes à des coordonnées couleur, nous pouvons leur procurer une invariance photométrique en leur appliquant des transformations affines particulières. Nous montrons que le degré d'invariance peut être contrôlé en fonction des besoins de l'application. Ces coordonnées nous permettent de définir le descripteur IVC (Image Vers Couleur). De manière similaire, nous évaluons une transformation affine de l'espace couleur à l'espace image et appliquons cette transformation aux coordonnées couleur. Les coordonnées obtenues par cette transformation sont invariantes à toute transformation affine appliquée dans l'espace couleur, elles présentent donc un degré d'invariance élevé aux variations photométriques. Ces coordonnées nous permettent de constituer le descripteur CVI (Couleur Vers Image). Nous montrons que ces deux descripteurs fournissent de très bons résultats dans le cadre de la reconnaissance d'objet et présentent une telle complémentarité que le descripteur obtenu par concaténation de IVC et CVI fournit de meilleurs résultats que la plupart des descripteurs couleur parus dans la littérature. Ensuite, nous proposons un descripteur qui présente un degré d'invariance plus élevé que les deux précédents puisqu'il n'est pas sensible aux transformations non-linéaires des couleurs modélisées par des fonctions croissantes appliquées indépendamment sur chaque composante couleur. Pour cela, nous exploitons les mesures de rang des pixels dans les images. De plus, nous utilisons les corrélations entre mesures de rang obtenues pour différentes composantes couleur. Ceci nous a permis de proposer un descripteur lui aussi très compact qui présente un degré d'invariance photométrique assez élevé. Enfin, nous abordons le problème de la caractérisation locale d'images par auto-similarités

En apprentissage automatique on a pour but d'apprendre un modèle, à partir de données, qui soit capable de faire des prédictions sur des nouvelles données (pas explorées auparavant). Pour obtenir un modèle qui puisse se généraliser sur les nouvelles données, et éviter le sur-apprentissage, nous devons restreindre le modèle. Ces restrictions sont généralement une connaissance a priori de la structure du modèle. Les premières approches considérées dans la littérature sont la régularisation de Tikhonov et plus tard le Lasso pour induire de la parcimonie dans la solution. La parcimonie fait partie d'un concept fondamental en apprentissage automatique. Les modèles parcimonieux sont attrayants car ils offrent plus d'interprétabilité et une meilleure généralisation (en évitant le sur-apprentissage) en induisant un nombre réduit de paramètres dans le modèle. Au-delà de la parcimonie générale et dans de nombreux cas, les modèles sont structurellement contraints et ont une représentation simple de certains éléments fondamentaux, comme par exemple une collection de vecteurs, matrices ou tenseurs spécifiques. Ces éléments fondamentaux sont appelés atomes. Dans ce contexte, les normes atomiques fournissent un cadre général pour estimer ce type de modèles. périodes de modèles. Le but de cette thèse est d'utiliser le cadre de parcimonie convexe fourni par les normes atomiques pour étudier une forme de parcimonie matricielle. Tout d'abord, nous développons un algorithme efficace basé sur les méthodes de Frank-Wolfe et qui est particulièrement adapté pour résoudre des problèmes convexes régularisés par une norme atomique. Nous nous concentrons ensuite sur l'estimation de la structure des modèles graphiques gaussiens, où la structure du modèle est encodée dans la matrice de précision et nous étudions le cas avec des variables manquantes. Nous proposons une formulation convexe avec une approche algorithmique et fournissons un résultat théorique qui énonce les conditions nécessaires pour récupérer la structure souhaitée. Enfin, nous considérons le problème de démixage d'un signal en deux composantes ou plus via la minimisation d’une somme de normes ou de jauges, encodant chacune la structure a priori des composants à récupérer. En particulier, nous fournissons une garantie de récupération exacte dans le cadre sans bruit, basée sur des mesures d'incohérence / The goal of machine learning is to learn a model from some data that will make accurate predictions on data that it has not seen before. In order to obtain a model that will generalize on new data, and avoid overfitting, we need to restrain the model. These restrictions are usually some a priori knowledge of the structure of the model. First considered approaches included a regularization, first ridge regression and later Lasso regularization for inducing sparsity in the solution. Sparsity, also known as parsimony, has emerged as a fundamental concept in machine learning. Parsimonious models are appealing since they provide more interpretability and better generalization (avoid overfitting) through the reduced number of parameters. Beyond general sparsity and in many cases, models are constrained structurally so they have a simple representation in terms of some fundamental elements, consisting for example of a collection of specific vectors, matrices or tensors. These fundamental elements are called atoms. In this context, atomic norms provide a general framework for estimating these sorts of models. The goal of this thesis is to use the framework of convex sparsity provided by atomic norms to study a form of matrix sparsity. First, we develop an efficient algorithm based on Frank-Wolfe methods that is particularly adapted to solve problems with an atomic norm regularization. Then, we focus on the structure estimation of Gaussian graphical models, where the structure of the graph is encoded in the precision matrix and study the case with unobserved variables. We propose a convex formulation with an algorithmic approach and provide a theoretical result that states necessary conditions for recovering the desired structure. Finally, we consider the problem of signal demixing into two or more components via the minimization of a sum of norms or gauges, encoding each a structural prior on the corresponding components to recover. In particular, we provide general exact recovery guarantees in the noiseless setting based on incoherence measures

Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n}) / Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})

L'analyse pertinente de l'information contenue dans les mesures instrumentales modernes nécessite le développement de méthodes algorithmiques performantes. La spectroscopie n'échappant pas à cette règle, nombre d'outils chimiométriques d'analyse multivariée ont été mis au point en conséquence. L'objectif de cette thèse est de participer à ces développements pour caractériser les spectres et les profils de concentration des composés intervenant lors de réactions photoinduites suivies en spectroscopique résolue en temps. Un premier travail concerne l'analyse du rang de données de différence. Une déficience de rang systématique de ces données a été mise en évidence. Une approche basée sur un algorithme de modélisation hybride est proposée en réponse à ce problème. En effet l'introduction d'un modèle cinétique compense cette déficience de rang des données. Le deuxième travail se rapporte à la caractérisation de l'influence du bruit (d'une part sur la mesure et d'autre part sur la résolution multivariée). Une analyse de la structure de corrélation du bruit permet d'expliquer les phénomènes de surajustement des méthodes de modélisation souple. Un second algorithme résout ce problème en pondérant les données en fonction d'une estimation de l'erreur de mesure. Ces points sont illustrés par deux applications ; premièrement une contribution à l'analyse du centre réactionnel de la bactérie <i>Rhodobacter sphaeroides</i> par spectroscopie IRTF et ensuite l'étude de la photorelaxation de la benzophénone par spectroscopie d'absorption transitoire.