.

Le concept de radio logicielle (SDR) est une solution pertinente pour concevoir des équipements multi-standards. Une façon de réaliser de tels équipements est d'identifier les fonctions et opérateurs communs entre les standards. Cette approche s’appelle la paramétrisation et est divisée en deux catégories : l'approche pragmatique qui est une version pratique pour créer et développer des opérateurs communs à partir d’opérateurs existants, et l'approche théorique dont l’objectif est de réaliser une exploration graphique d’un équipement multi-standards selon différents niveaux de granularité, accompagnée d’un problème d'optimisation. C’est cette dernière approche qui a constitué le sujet de base de cette thèse. Ainsi, une fonction de coût doit être optimisée afin de sélectionner les opérateurs communs entre les différentes normes, ce qui permet de proposer une configuration optimale à partir de laquelle sont déduits les opérateurs communs. Dans notre travail, nous avons dans un premier temps modélisé théoriquement la structure graphique d’un système multi-standards par un hypergraphe orienté. En outre, nous avons fourni une expression mathématique alternative de la fonction de coût suggérée, en utilisant des définitions propres à la théorie des graphes. Ensuite, nous avons montré que le problème d'optimisation associé était un problème NP sous une certaine contrainte, ce qui a entraîné une preuve d'exclusion de certaines configurations dont les coûts ne peuvent être minimaux. Ceci a constitué la deuxième contribution de cette thèse. Enfin, nous avons proposé un nouvel algorithme permettant de résoudre le problème d'optimisation donné, et dont l'intérêt est de donner une solution optimale du problème au lieu d’une solution approchée fournie par les méthodes heuristiques classiques. Un programme associé à cet algorithme a été développé en langage C, puis appliqué à plusieurs exemples de cas génériques afin d’en étudier les performances. / The Software-Defined Radio (SDR) concept is emerging as a potential and efficient solution for designing flexible future-proof multi-standard systems. A way of realizing a multi-standard terminal is to identify the appropriate common functions and operators inside and between the standards. This is what's called the parametrization approach, which can be divided into two categories: the pragmatic approach which is a practical version to create and develop common operators, and the theoretical approach which represents a graphical exploration of the SDR multi-standard system at different levels of granularity accompanied with an optimization problem. It’s in this last approach where our thesis subject dwells. In this context, a suggested cost function (in previous work) has to be optimized in order to select the convenient common operators between the different standards, enabling to construct an optimal design. In our work, we theoretically model a previously proposed graph structure of an SDR multi-standard system as a directed hypergraph as well as provide an alternative mathematical formal expression of the suggested cost function, using various graph theoretical definitions and notations. Afterwards, we prove that the associated optimization problem is an NP-problem under a certain constraint, which entails a proof of exclusion of some particular design options when searching for a minimum cost design. This was the second contribution in this thesis before we finally present a new algorithm (which exploits various modelization aspects of directed hypergraphs) that can solve the optimization problem, whose interest is in it giving an exact-optimal solution to our problem instead of a near-optimal one provided by heuristics. A program code for this algorithm was developed in C-language, and then it was applied on several generic case examples in order to explore its performance skills.

Cette étude a pour sujet les hypergraphes. / This study has for subject the hypergraphs.

Dans cette thèse, nous étudions les aspects structurels et algorithmiques de différents problèmes de théorie des graphes. Rappelons qu’un graphe est un ensemble de sommets éventuellement reliés par des arêtes. Deux sommets sont adjacents s’ils sont reliés par une arête.<p>Tout d’abord, nous considérons les deux problèmes suivants :le problème de vertex cover et celui de dominating set, deux cas particuliers du problème de hitting set. Un vertex cover est un ensemble de sommets qui rencontrent toutes les arêtes alors qu’un dominating set est un ensemble X de sommets tel que chaque sommet n’appartenant pas à X est adjacent à un sommet de X. La version connexe de ces problèmes demande que les sommets choisis forment un sous-graphe connexe. Pour les deux problèmes précédents, nous examinons le prix de la connexité, défini comme étant le rapport entre la taille minimum d’un ensemble répondant à la version connexe du problème et celle d’un ensemble du problème originel. Nous prouvons la difficulté du calcul du prix de la connexité d’un graphe. Cependant, lorsqu’on exige que le prix de la connexité d’un graphe ainsi que de tous ses sous-graphes induits soit borné par une constante fixée, la situation change complètement. En effet, pour les problèmes de vertex cover et de dominating set, nous avons pu caractériser ces classes de graphes pour de petites constantes.<p>Ensuite, nous caractérisons en termes de dominating sets connexes les graphes Pk- free, graphes n’ayant pas de sous-graphes induits isomorphes à un chemin sur k sommets. Beaucoup de problèmes sur les graphes sont étudiés lorsqu’ils sont restreints à cette classe de graphes. De plus, nous appliquons cette caractérisation à la 2-coloration dans les hypergraphes. Pour certains hypergraphes, nous prouvons que ce problème peut être résolu en temps polynomial.<p>Finalement, nous travaillons sur le problème de Pk-hitting set. Un Pk-hitting set est un ensemble de sommets qui rencontrent tous les chemins sur k sommets. Nous développons un algorithme d’approximation avec un facteur de performance de 3. Notre algorithme, basé sur la méthode primal-dual, fournit un Pk-hitting set dont la taille est au plus 3 fois la taille minimum d’un Pk-hitting set. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille sur des machines parallèles. Dans ce contexte, la mémoire est un facteur qui limite voire empêche souvent l’utilisation de solveurs directs, notamment ceux basés sur la méthode multifrontale. Cette étude se concentre sur les problèmes de mémoire et de performance des deux phases des méthodes directes les plus coûteuses en mémoire et en temps : la factorisation numérique et la résolution triangulaire. Dans une première partie nous nous intéressons à la phase de résolution à seconds membres creux, puis, dans une seconde partie, nous nous intéressons à la scalabilité mémoire de la factorisation multifrontale. La première partie de cette étude se concentre sur la résolution triangulaire à seconds membres creux, qui apparaissent dans de nombreuses applications. En particulier, nous nous intéressons au calcul d’entrées de l’inverse d’une matrice creuse, où les seconds membres et les vecteurs solutions sont tous deux creux. Nous présentons d’abord plusieurs schémas de stockage qui permettent de réduire significativement l’espace mémoire utilisé lors de la résolution, dans le cadre d’exécutions séquentielles et parallèles. Nous montrons ensuite que la façon dont les seconds membres sont regroupés peut fortement influencer la performance et nous considérons deux cadres différents : le cas "hors-mémoire" (out-of-core) où le but est de réduire le nombre d’accès aux facteurs, qui sont stockés sur disque, et le cas "en mémoire" (in-core) où le but est de réduire le nombre d’opérations. Finalement, nous montrons comment améliorer le parallélisme. Dans la seconde partie, nous nous intéressons à la factorisation multifrontale parallèle. Nous montrons tout d’abord que contrôler la mémoire active spécifique à la méthode multifrontale est crucial, et que les technique de "répartition" (mapping) classiques ne peuvent fournir une bonne scalabilité mémoire : le coût mémoire de la factorisation augmente fortement avec le nombre de processeurs. Nous proposons une classe d’algorithmes de répartition et d’ordonnancement "conscients de la mémoire" (memory-aware) qui cherchent à maximiser la performance tout en respectant une contrainte mémoire fournie par l’utilisateur. Ces techniques ont révélé des problèmes de performances dans certains des noyaux parallèles denses utilisés à chaque étape de la factorisation, et nous avons proposé plusieurs améliorations algorithmiques. Les idées présentées tout au long de cette étude ont été implantées dans le solveur MUMPS (Solveur MUltifrontal Massivement Parallèle) et expérimentées sur des matrices de grande taille (plusieurs dizaines de millions d’inconnues) et sur des machines massivement parallèles (jusqu’à quelques milliers de coeurs). Elles ont permis d’améliorer les performances et la robustesse du code et seront disponibles dans une prochaine version. Certaines des idées présentées dans la première partie ont également été implantées dans le solveur PDSLin (solveur linéaire hybride basé sur une méthode de complément de Schur). / We consider the solution of very large sparse systems of linear equations on parallel architectures. In this context, memory is often a bottleneck that prevents or limits the use of direct solvers, especially those based on the multifrontal method. This work focuses on memory and performance issues of the two memory and computationally intensive phases of direct methods, that is, the numerical factorization and the solution phase. In the first part we consider the solution phase with sparse right-hand sides, and in the second part we consider the memory scalability of the multifrontal factorization. In the first part, we focus on the triangular solution phase with multiple sparse right-hand sides, that appear in numerous applications. We especially emphasize the computation of entries of the inverse, where both the right-hand sides and the solution are sparse. We first present several storage schemes that enable a significant compression of the solution space, both in a sequential and a parallel context. We then show that the way the right-hand sides are partitioned into blocks strongly influences the performance and we consider two different settings: the out-of-core case, where the aim is to reduce the number of accesses to the factors, that are stored on disk, and the in-core case, where the aim is to reduce the computational cost. Finally, we show how to enhance the parallel efficiency. In the second part, we consider the parallel multifrontal factorization. We show that controlling the active memory specific to the multifrontal method is critical, and that commonly used mapping techniques usually fail to do so: they cannot achieve a high memory scalability, i.e. they dramatically increase the amount of memory needed by the factorization when the number of processors increases. We propose a class of "memory-aware" mapping and scheduling algorithms that aim at maximizing performance while enforcing a user-given memory constraint and provide robust memory estimates before the factorization. These techniques have raised performance issues in the parallel dense kernels used at each step of the factorization, and we have proposed some algorithmic improvements. The ideas presented throughout this study have been implemented within the MUMPS (MUltifrontal Massively Parallel Solver) solver and experimented on large matrices (up to a few tens of millions unknowns) and massively parallel architectures (up to a few thousand cores). They have demonstrated to improve the performance and the robustness of the code, and will be available in a future release. Some of the ideas presented in the first part have also been implemented within the PDSLin (Parallel Domain decomposition Schur complement based Linear solver) solver.

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille sur des machines parallèles. Dans ce contexte, la mémoire est un facteur qui limite voire empêche souvent l'utilisation de solveurs directs, notamment ceux basés sur la méthode multifrontale. Cette étude se concentre sur les problèmes de mémoire et de performance des deux phases des méthodes directes les plus coûteuses en mémoire et en temps : la factorisation numérique et la résolution triangulaire. Dans une première partie nous nous intéressons à la phase de résolution à seconds membres creux, puis, dans une seconde partie, nous nous intéressons à la scalabilité mémoire de la factorisation multifrontale. La première partie de cette étude se concentre sur la résolution triangulaire à seconds membres creux, qui apparaissent dans de nombreuses applications. En particulier, nous nous intéressons au calcul d'entrées de l'inverse d'une matrice creuse, où les seconds membres et les vecteurs solutions sont tous deux creux. Nous présentons d'abord plusieurs schémas de stockage qui permettent de réduire significativement l'espace mémoire utilisé lors de la résolution, dans le cadre d'exécutions séquentielles et parallèles. Nous montrons ensuite que la façon dont les seconds membres sont regroupés peut fortement influencer la performance et nous considérons deux cadres différents : le cas "hors-mémoire" (out-of-core) où le but est de réduire le nombre d'accès aux facteurs stockés sur disque, et le cas "en mémoire" (in-core) où le but est de réduire le nombre d'opérations. Finalement, nous montrons comment améliorer le parallélisme. Dans la seconde partie, nous nous intéressons à la factorisation multifrontale parallèle. Nous montrons tout d'abord que contrôler la mémoire active spécifique à la méthode multifrontale est crucial, et que les techniques de "répartition" (mapping) classiques ne peuvent fournir une bonne scalabilité mémoire : le coût mémoire de la factorisation augmente fortement avec le nombre de processeurs. Nous proposons une classe d'algorithmes de répartition et d'ordonnancement "conscients de la mémoire" (memory-aware) qui cherchent à maximiser la performance tout en respectant une contrainte mémoire fournie par l'utilisateur. Ces techniques ont révélé des problèmes de performances dans certains des noyaux parallèles denses utilisés à chaque étape de la factorisation, et nous avons proposé plusieurs améliorations algorithmiques. Les idées présentées tout au long de cette étude ont été implantées dans le solveur MUMPS (Solveur MUltifrontal Massivement Parallèle) et expérimentées sur des matrices de grande taille (plusieurs dizaines de millions d'inconnues) et sur des machines massivement parallèles (jusqu'à quelques milliers de coeurs). Elles ont permis d'améliorer les performances et la robustesse du code et seront disponibles dans une prochaine version. Certaines des idées présentées dans la première partie ont également été implantées dans le solveur PDSLin (solveur linéaire hybride basé sur une méthode de complément de Schur).

Dans un cycle ou chaque document scientifique, s'inspirant lui même d'autres productions, sera lu et commenté par des chercheurs qui le citeront, l'écrit sera une production tour à tour finie, réactualisée et toujours une source d'appropriation et de citation. Après une introduction à la recherche d'information, nous examinerons la typologie des documents scientifiques, les modalités de stockage et de diffusion, ainsi que les normes et protocoles associés. Nous décrivons plusieurs méthodes de recherche documentaire et différents outils d'interrogation des bases de connaissances. Nous postulons qu'aujourd'hui la recherche documentaire peut être techniquement automatisée, de la première étape d'établissement du périmètre de recherche jusqu'à l'écriture de la bibliographie. Les étapes de sélection et de gestion documentaire peuvent aussi être facilitées par des outils et normes dédiés. Nous proposons une étude centrée sur l'usager pour faire émerger des profils utilisateurs et les usages associés, puis nous soumettons une démarche conceptuelle et expérimentale d'accompagnement visuel à la recherche de documentation scientifique. Nous nous intéressons tant aux méthodologies d'évaluation et de recommandation de ce type de littérature qu'aux formats et normes documentaires. Nous synthétisons l'ensemble des procédures d'automatisation bibliographiques pour modéliser un outil de recherche alliant respect des normes, souplesse d'usage et considération des besoins cognitifs et documentaires de l'usager. Cette interface servira de support à une recherche naviguée dans les corpus documentaires avec l'intégration de services d'exposition de métadonnées.

L'extraction de connaissances à partir de données incomplètes constitue un axe de recherche en plein essor. Dans cette thèse, nous y contribuons par la proposition d'une méthode de complétion des valeurs manquantes. Nous commençons par aborder cette problématique par la définition de modèles d'apparition des valeurs manquantes. Nous en proposons une nouvelle typologie en fonction des données connues et nous les caractérisons de façon non redondante grâce à la base d'implications propres. Un algorithme de calcul de cette base de règles, formalisé à partir de la théorie des hypergraphes, est également proposé dans cette thèse. Ensuite, nous exploitons les informations fournies lors de l'étape de caractérisation afin de proposer une méthode de complétion contextualisée, qui complète les valeurs manquantes selon le type aléatoire/non-aléatoire et selon le contexte. La complétion des valeurs manquantes non aléatoires est effectuée par des valeurs spéciales, renfermant intrinsèquement les origines des valeurs manquantes et déterminées grâce à des schémas de caractérisation. Finalement, nous nous intéressons aux techniques d'évaluation des méthodes de complétion et nous proposons une nouvelle technique fondée sur la stabilité d'un clustering entre les données de référence et les données complétées.

Lors de cette thèse, je me suis intéressée à la modélisation du métabolisme des micro-organismes. Nous nous sommes focalisé sur le métabolisme des petites molécules qui ne prend pas en compte les réactions associées aux macromolécules, telle que la synthèse des protéines.Nous avons ainsi utilisé différents formalismes de modélisation.Tout d'abord, nous avons développé TOTORO où les réseaux métaboliques sont représentés par des hypergraphes dirigés et qui permet d'identifier les réactions ayant participé à une transition métabolique. TOTORO a été utilisé sur un jeu de données sur la levure en présence de cadmium. Nous avons pu montrer que nous retrouvons les mécanismes connus de désintoxication.Ensuite, en utilisant une méthode de modélisation par contraintes, nous discutons d'un développement en cours, KOTOURA, qui propose d'utiliser les connaissances actuelles de concentrations de métabolites entre différentes conditions pour inférer de manière quantitative les possibles asynchronies des réactions lors du passage d'un état stable à un autre. Nous avons testé son implémentation sur des données simulées.Enfin, nous proposons MULTIPUS, une méthode d'extraction d'(hyper)-arbres de Steiner dirigés qui permet de sélectionner les voies métaboliques pour la production de composés au sein d'une communauté bactérienne. Les réseaux métaboliques sont modélisés en utilisant des hypergraphes dirigés et pondérés. Nous proposons un algorithme de programmation dynamique paramétré ainsi qu'une formulation utilisant la programmation par ensemble réponse. Ces deux propositions sont ensuite comparées dans deux cas d'applications / In this PhD work, we proposed to model metabolism. Our focus was to develop generic models, that are not specific to one organism or condition, but are instead based on general assumptions that we tried to validate using data from the literature.We first present TOTORO that uses a qualitative measurement of concentrations in two steady-states to infer the reaction changes that lead to differences in metabolite pools in both conditions.TOTORO enumerates all sub-(hyper)graphs that represent a sufficient explanation for the observed differences in concentrations. We exploit a dataset of Yeast (Saccharomyces cerevisiae) exposed to cadmium and show that we manage to retrieve the known pathways used by the organisms. We then address the same issue, but using a constraint-based programming framework, called KOTOURA, that allows to infer more quantitatively the reaction changes during the perturbed state. We use in this case exact concentration measurements and the stoichiometric matrix, and show on simulated datasets that the overall variations of reaction fluxes can be captured by our formulation.Finally, we propose MULTIPUS, a method to infer microbial communities and metabolic roads to produce specific target compounds from a set of defined substrates. We use in this case a weighted directed hypergraph. We apply MULTIPUS to the production of antibiotics using a consortium composed of an archae and an actinobacteria and show hat their metabolic capacities are complementary. We then infer for another community the excretion of an inhibitory product (acetate) by a 1,3-propanediol (PDO) producer and its consumption by a methanogene archae

Les jeux stochastiques à somme nulle possèdent une structure récursive qui s'exprime dans leur opérateur de programmation dynamique, appelé opérateur de Shapley. Ce dernier permet d'étudier le comportement asymptotique de la moyenne des paiements par unité de temps. En particulier, le paiement moyen existe et ne dépend pas de l'état initial si l'équation ergodique - une équation non-linéaire aux valeurs propres faisant intervenir l'opérateur de Shapley - admet une solution. Comprendre sous quelles conditions cette équation admet une solution est un problème central de la théorie de Perron-Frobenius non-linéaire, et constitue le principal thème d'étude de cette thèse. Diverses classes connues d'opérateur de Shapley peuvent être caractérisées par des propriétés basées entièrement sur la relation d'ordre ou la structure métrique de l'espace. Nous étendons tout d'abord cette caractérisation aux opérateurs de Shapley "sans paiements", qui proviennent de jeux sans paiements instantanés. Pour cela, nous établissons une expression sous forme minimax des fonctions homogènes de degré un et non-expansives par rapport à une norme faible de Minkowski. Nous nous intéressons ensuite au problème de savoir si l'équation ergodique a une solution pour toute perturbation additive des paiements, problème qui étend la notion d'ergodicité des chaînes de Markov. Quand les paiements sont bornés, cette propriété d'"ergodicité" est caractérisée par l'unicité, à une constante additive près, du point fixe d'un opérateur de Shapley sans paiement. Nous donnons une solution combinatoire s'exprimant au moyen d'hypergraphes à ce problème, ainsi qu'à des problèmes voisins d'existence de points fixes. Puis, nous en déduisons des résultats de complexité. En utilisant la théorie des opérateurs accrétifs, nous généralisons ensuite la condition d'hypergraphes à tous types d'opérateurs de Shapley, y compris ceux provenant de jeux dont les paiements ne sont pas bornés. Dans un troisième temps, nous considérons le problème de l'unicité, à une constante additive près, du vecteur propre. Nous montrons d'abord que l'unicité a lieu pour une perturbation générique des paiements. Puis, dans le cadre des jeux à information parfaite avec un nombre fini d'actions, nous précisons la nature géométrique de l'ensemble des perturbations où se produit l'unicité. Nous en déduisons un schéma de perturbations qui permet de résoudre les instances dégénérées pour l'itération sur les politiques. / Zero-sum stochastic games have a recursive structure encompassed in their dynamic programming operator, so-called Shapley operator. The latter is a useful tool to study the asymptotic behavior of the average payoff per time unit. Particularly, the mean payoff exists and is independent of the initial state as soon as the ergodic equation - a nonlinear eigenvalue equation involving the Shapley operator - has a solution. The solvability of the latter equation in finite dimension is a central question in nonlinear Perron-Frobenius theory, and the main focus of the present thesis. Several known classes of Shapley operators can be characterized by properties based entirely on the order structure or the metric structure of the space. We first extend this characterization to "payment-free" Shapley operators, that is, operators arising from games without stage payments. This is derived from a general minimax formula for functions homogeneous of degree one and nonexpansive with respect to a given weak Minkowski norm. Next, we address the problem of the solvability of the ergodic equation for all additive perturbations of the payment function. This problem extends the notion of ergodicity for finite Markov chains. With bounded payment function, this "ergodicity" property is characterized by the uniqueness, up to the addition by a constant, of the fixed point of a payment-free Shapley operator. We give a combinatorial solution in terms of hypergraphs to this problem, as well as other related problems of fixed-point existence, and we infer complexity results. Then, we use the theory of accretive operators to generalize the hypergraph condition to all Shapley operators, including ones for which the payment function is not bounded. Finally, we consider the problem of uniqueness, up to the addition by a constant, of the nonlinear eigenvector. We first show that uniqueness holds for a generic additive perturbation of the payments. Then, in the framework of perfect information and finite action spaces, we provide an additional geometric description of the perturbations for which uniqueness occurs. As an application, we obtain a perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration.