On introduit une nouvelle structure algébrique qui formalise bien les problèmes de reconstruction, assortie d’une conjecture qui permettrait de traiter directement des symétries. Le cadre fournit par cette étude permet de plus d’engendrer des relations qui ont lieu entre les nombres de sous-structures, et d’une certaine façon, la conjecture formulée affirme qu’on les obtient toutes. De plus, la généralisation des résultats précédemment obtenus pour la reconstruction permet de chercher `a en apprécier les limites en recherchant des cas où ces relations sont optimales. Ainsi, on montre que les théorèmes de V.Müller et de L.Lovasz sont les meilleurs possibles en exhibant des cas limites. Cette généralisation aux algèbres d’invariants, déjà effectuée par P.J.Cameron et V.B.Mnukhin, permet de placer les problèmes de reconstruction en tenaille entre d’une part des relations (fournies) que l’on veut exploiter, et des exemples qui établissent l’optimalité du résultat. Ainsi, sans aucune donnée sur le groupe, le résultat de L.Lovasz est le meilleur possible, et si l’on considère l’ordre du groupe, le résultat de V.Müller est le meilleur possible. / A new algebraic structure is described, that is a useful framework in whichreconstruction problems and results can be expressed. A conjecture is madewhich would, provided it is true, help to address the problem of symmetries.A consequence of the abstract language in which the theory is formulated isthe expression of relations between the numbers of substructures of a structure(for example, the number of subgraphs of a given type in a graph).Moreover, a generalisation similar to the one achieved by P.J.Cameron andV.B.Mnukhin of the results of edge reconstruction to invariant algebras isstated. Examples are then provided to show that the result of L.Lovasz isbest possible if one knows nothing about the underlying group, and that theresult of V.Müller is best possible if one knows only the order of the group.Thus, reconstruction problems are set in a theory that generates relationsto address them, and at the same time, provides examples establishing thesharpness of the theorems.

La présente thèse porte sur le développement d'une théorie d'algèbre linéaire, de géométrie et d'analyse basée sur les algèbres (Z2)n-commutatives, c'est-à-dire des algèbres (Z2)n-graduées associatives unitaires satisfaisant ab = (-1)<deg(a),deg(b)>ba, pour tout couple d'éléments homogènes a, b de degrés deg(a), deg(b) où <.,.> est le produit scalaire usuel). Cette généralisation de la supergéométrie a de nombreuses applications : en mathématiques (l'algèbre de Deligne des superformes différentielles, l'algèbre des quaternions et les algèbres de Clifford en sont des exemples) et même en physique (paraparticules). Dans ce travail, les notions de trace et de (super)déterminant pour des matrices à coefficients dans une algèbre gradué-commutative sont définies et étudiés. Une attention particulière est portée au cas des algèbres de Clifford : ce point de vue gradué fournit une nouvelle approche au problème classique du « bon » déterminant pour des matrices à coefficient non-commutatifs (quaternioniques). En outre, nous entreprenons l'étude de la géométrie différentielle (Z2)n-graduée. Privilégiant l'approche par les espaces annelés, les (Z2)n-supervariétés sont définies en choisissant l'algèbre (Z2)n-commutative des séries formelles en variables graduées comme modèle pour le faisceau de fonctions. Les résultats les plus marquants ainsi obtenus sont : le Berezinien gradué et son interprétation cohomologique (essentielle pour établir une théorie de l'intégration) ; le théorème des morphismes, attestant qu'on peut rétablir un morphisme entre (Z2)n-supervariétés à partir de sa seule expression sur les coordonnées ; le théorème de Batchelor-Gawedzki pour les (Z2)n-supervariétés lisses / The present thesis deals with a development of linear algebra, geometry and analysis based on (Z2)n-superalgebras ; associative unital algebras which are (Z2)n-graded and graded-commutative, i.e. statisfying ab=(-1)<deg(a),deg(b)>ba, for all homogeneous elements a, b of respective degrees deg(a), deg(b) in (Z2)n (<.,.> denoting the usual scalar product). This generalization widens the range of applications of supergeometry to many mathematical structures (quaternions and more generally Clifford algebras, Deligne algebra of superdifferential forms, higher vector bundles) and appears also in physics (for describing paraparticles) proving its worth and relevance. In this dissertation, we first focus on (Z2)n-superalgebra theory ; we define and characterize the notions of trace and (super)determinant of matrices over graded-commutative algebras. Special attention is given to the case of Clifford algebras, where our study gives a new approach to treat the classical problem of finding a “good” determinant for matrices with noncommuting (quaternionic) entries. Further, we undertake the study of (Z2)n-graded differential geometry. Privileging the ringed space approach, we define (smooth) (Z2)n-supermanifolds modeling their algebras of functions on the (Z2)n-commutative algebra of formal power series in graded variables, and develop the theory along the lines of supergeometry. Notable results are : the graded Berezinian and its cohomological interpretation (essential to establish integration theory) ; the theorem of morphism, which states that a morphism of (Z2)n-supermanifolds can be recovered from its coordinate expression ; Batchelor-Gawedzki theorem for (Z2)n-supermanifolds

Cette thèse se concentre sur la résolution de systèmes linéaires creux dans le contexte d’applications massivement parallèles. Ce type de problèmes s’exprime sous la forme AX=B, où A est une matrice creuse d’ordre n x n, i.e. qui possède un nombre d’entrées nulles suffisamment élevé pour pouvoir être exploité, et B et X sont respectivement la matrice de seconds membres et la matrice de solution de taille n x nrhs. Cette résolution par des méthodes dites directes est effectuée grâce à une étape de factorisation qui réduit A en deux matrices triangulaires inférieure et supérieure L et U, suivie de deux résolutions triangulaires pour calculer la solution.Nous nous intéressons à ces résolutions avec une attention particulière apportée à la première, LY=B. Dans beaucoup d’applications, B possède un grand nombre de colonnes (nrhs >> 1) transformant la phase de résolution en un goulot d’étranglement. Elle possède souvent aussi une structure creuse, donnant l’opportunité de réduire la complexité de cette étape.Cette étude aborde sous des angles complémentaires la résolution triangulaire de systèmes linéaires avec seconds membres multiples et creux. Nous étudions dans un premier temps la complexité asymptotique de cette étape dans différents contextes (2D, 3D, facteurs compressés ou non). Nous considérons ensuite l’exploitation de cette structure et présentons de nouvelles approches s’appuyant sur une modélisation du problème par des graphes qui permettent d’atteindre efficacement le nombre minimal d’opérations. Enfin, nous donnons une interprétation concrète de son exploitation sur une application d’électromagnétisme pour la géophysique. Nous adaptons aussi des algorithmes parallèles aux spécificités de la phase de résolution.Nous concluons en combinant l'ensemble des résultats précédents et en discutant des perspectives de ce travail. / We consider direct methods to solve sparse linear systems AX = B, where A is a sparse matrix of size n x n with a symmetric structure and X and B are respectively the solution and right-hand side matrices of size n x nrhs. A is usually factorized and decomposed in the form LU, where L and U are respectively a lower and an upper triangular matrix. Then, the solve phase is applied through two triangular resolutions, named respectively the forward and backward substitutions.For some applications, the very large number of right-hand sides (RHS) in B, nrhs >> 1, makes the solve phase the computational bottleneck. However, B is often sparse and its structure exhibits specific characteristics that may be efficiently exploited to reduce this cost. We propose in this thesis to study the impact of the exploitation of this structural sparsity during the solve phase going through its theoretical aspects down to its actual implications on real-life applications.First, we investigate the asymptotic complexity, in the big-O sense, of the forward substitution when exploiting the RHS sparsity in order to assess its efficiency when increasing the problem size. In particular, we study on 2D and 3D regular problems the asymptotic complexity both for traditional full-rank unstructured solvers and for the case when low-rank approximation is exploited. Next, we extend state-of-the-art algorithms on the exploitation of RHS sparsity, and also propose an original approach converging toward the optimal number of operations while preserving performance. Finally, we show the impact of the exploitation of sparsity in a real-life electromagnetism application in geophysics that requires the solution of sparse systems of linear equations with a large number of sparse right-hand sides. We also adapt the parallel algorithms that were designed for the factorization to solve-oriented algorithms.We validate and combine the previous improvements using the parallel solver MUMPS, conclude on the contributions of this thesis and give some perspectives.

La disponibilité et la persistance à l'échelle locale des métaux lourds pourraient être critiques notamment pour l'usage futur des zones agricoles ou urbaines, au droit desquelles de nombreux sites industriels se sont installés dans le passé. La gestion de ces situations environnementales complexes nécessitent le développement de nouvelles méthodes d'analyse peu invasives (capteurs environnementaux), comme celles utilisant des biosenseurs bactériens, afin d'identifier et d'évaluer directement l'effet biologique et la disponibilité chimique des métaux. Ainsi dans ce travail de thèse, nous avons cherché à identifier, à l'aide d'outils mathématiques de l'algèbre multilinéaire, les réponses de senseurs bactériens fluorescents dans des conditions environnementales variées, qu'il s'agisse d'un stress engendré par la présence à forte dose d'un métal ou d'une carence nutritive engendrée par son absence. Cette identification est fondée sur l'analyse quantitative à l'échelle d'une population bactérienne de signaux multidimensionnels. Elle repose en particulier sur (i) l'acquisition de données spectrales (fluorescence) multi-variées sur des suspensions de biosenseurs multicolores interagissant avec des métaux et sur (ii) le développement d'algorithme de décomposition tensoriels. Les méthodes proposées, développées et utilisées dans ce travail s'efforcent d'identifier « sans a priori» a minima, la réponse fonctionnelle de biosenseurs sous différentes conditions environnementales, par des méthodes de décomposition de tenseurs sous contraintes des signaux spectraux observables. Elles tirent parti de la variabilité des réponses systémiques et permettent de déterminer les sources élémentaires identifiant le système et leur comportement en fonction des paramètres extérieurs. Elles sont inspirées des méthodes CP et PARALIND . L'avantage de ce type d'approche, par rapport aux approches classiques, est l'identification unique des réponses des biosenseurs sous de faibles contraintes. Le travail a consisté à développer des algorithmes efficaces de séparations de sources pour les signaux fluorescents émis par des senseurs bactériens, garantissant la séparabilité des sources fluorescentes et l'unicité de la décomposition. Le point original de la thèse est la prise en compte des contraintes liées à la physique des phénomènes analysés telles que (i) la parcimonie des coefficients de mélange ou la positivité des signaux source, afin de réduire au maximum l'usage d'a priori ou (ii) la détermination non empirique de l'ordre de la décomposition (nombre de sources). Cette posture a permis aussi d'améliorer l'identification en optimisant les mesures physiques par l'utilisation de spectres synchrones ou en apportant une diversité suffisante aux plans d'expériences. L'usage des spectres synchrones s'est avéré déterminant à la fois pour améliorer la séparation des sources de fluorescence, mais aussi pour augmenter le rapport signal sur bruit des biosenseurs les plus faibles. Cette méthode d'analyse spectrale originale permet d'élargir fortement la gamme chromatique des biosenseurs fluorescents multicolores utilisables simultanément. Enfin, une nouvelle méthode d'estimation de la concentration de polluants métalliques présents dans un échantillon à partir de la réponse spectrale d'un mélange de biosenseurs non-spécifiques a été développée / Availability and persistence of heavy metals could be critical for future use of agricultural or urban areas, on which many industrial sites have installed in the past. The management of these complex environmental situations requiring the development of new analytical methods minimally invasive, such as bacterial biosensors, to identify and directly assess the biological effects and the chemical availability of metals. The aims of this thesis was to identify the responses of fluorescent bacterial sensors various environmental conditions, using mathematical tools of algebra multi-linear, whether stress caused by the presence of high dose of a metal or a nutrient deficiency caused by his absence. This identification is based on quantitative analysis of multidimensional signals at the bacterial population-scale. It is based in particular on (i) the acquisition of multivariate spectral data on suspensions of multicolored biosensors interacting with metals and (ii) the development of algorithms for tensor decomposition. The proposed methods, developed and used in this study attempt to identify functional response of biosensors without \textsl{a priori} by decomposition of tensor containing the spectral signals. These methods take advantage of the variability of systemic responses and allow to determine the basic sources identifying the system and their behavior to external factors. They are inspired by the CP and PARALIND methods. The advantage of this approach, compared to conventional approaches, is the unique identification of the responses of biosensors at low constraints. The work was to develop efficient algorithms for the source separation of fluorescent signals emitted by bacterial sensors, ensuring the sources separability and the uniqueness of the decomposition. The original point of this thesis is the consideration of the physical constraints of analyzed phenomena such as (i) the sparsity of mixing coefficients or positivity of sources signals in order to minimize the use of a priori or (ii) the non-empirical determination of the order of decomposition (number of sources).This posture has also improved the identification optimizing physical measurements by the use of synchronous spectra or providing sufficient diversity in design of experiments. The use of synchronous spectra proved crucial both to improve the separation of fluorescent sources, but also to increase the signal to noise ratio of the lowest biosensors. This original method of spectral analysis can greatly expand the color range of multicolored fluorescent biosensors used simultaneously. Finally, a new method of estimating the concentration of metal pollutants present in a sample from the spectral response of a mixture of non-specific biosensor was developed

Les algèbres centrales simples ont de nombreuses applications en théorie des nombres, mais leur algorithmique est encore peu développée. Dans cette thèse, j’apporte une contribution dans deux directions. Premièrement, je présente des algorithmes de complexité prouvée, ce qui est nouveau dans la plupart des cas. D’autre part, je développe des algorithmes heuristiques mais très efficaces dans la pratique pour les exemples qui nous intéressent le plus, comme en témoignent mes implantations. Les algorithmes sont à la fois plus rapides et plus généraux que les algorithmes existants. Plus spécifiquement, je m’intéresse aux problèmes suivants : calcul du groupe des unités d’un ordre et problème de l’idéal principal. Je commence par étudier le diamètre du domaine fondamental de certains groupes d’unités grâce à la théorie des représentations. Je décris ensuite un algorithme prouvé pour calculer des générateurs et une présentation du groupe des unités d’un ordre maximal dans une algèbre à division, puis un algorithme efficace qui calcule également un domaine fondamental dans le cas où le groupe des unités est un groupe kleinéen. Je donne en outre un algorithme de complexité prouvée qui détermine si un idéal d’un tel ordre est principal, et qui en calcule un générateur le cas échéant, puis je décris un algorithme heuristiquement sous-exponentiel pour résoudre le même problème dans le cas d’une algèbre de quaternions indéfinie. / Central simple algebras have many applications in number theory, but their algorithmic theory is not yet fully developed. I present algorithms to compute effectively with central simple algebras that are both faster and more general than existing ones. Some of these algorithms have proven complexity estimates, a new contribution in this area; others rely on heuristic assumptions but perform very efficiently in practice.Precisely, I consider the following problems: computation of the unit group of an order and principal ideal problem. I start by studying the diameter of fundamental domains of some unit groups using representation theory. Then I describe an algorithm with proved complexity for computing generators and a presentation of the unit group of a maximal order in a division algebra, and then an efficient algorithm that also computes a fundamental domain in the case where the unit group is a Kleinian group. Similarly, I present an algorithm with proved complexity that decides whether an ideal of such an order is principal and that computes a generator when it is. Then I describe a heuristically subexponential algorithm that solves the same problem in indefinite quaternion algebras.

De nos jours, les services Web sont très utilisés notamment par les entreprises pour rendre accessibles leurs métiers, leurs données et leurs savoir-faire via le Web. L'émergence des services Web a permis aux applications d'être présentées comme un ensemble de services métiers bien structurés et correctement décrits, plutôt que comme un ensemble d'objets et de méthodes. La composition automatique de services est une tâche complexe mais qui rend les services interopérables, ainsi leur interaction permet d’offrir une valeur ajoutée dans le traitement des requêtes des utilisateurs en prenant en compte des critères fonctionnels et non fonctionnels de la qualité de service. Dans ce travail de thèse, nous nous intéressons plus précisément aux services à base de localisation (LBS) qui permettent d'intégrer des informations géographiques, et de fournir des informations accessibles depuis des appareils mobiles via, les réseaux mobiles en faisant usage des positions géographiques de ces appareils. L'objectif de ce travail est de proposer une approche orientée modèles pour spécifier, valider et mettre en œuvre des processus de composition automatique de services à des fins de sécurité routière dans les transports. Cette approche est basée sur deux outils formels à savoir les Réseaux de Petri (RdP) et l'algèbre (max,+). Pour cela, nous préconisons l'utilisation des workflow patterns dans la composition, où chaque pattern est traduit par un modèle RdP et ensuite par une équation mathématique dans l'algèbre (max,+). Les modèles formels développés ont conduits, d'une part, à la description graphique et analytique des processus considérés, et d'autre part, à l'évaluation et la vérification quantitatives et qualitatives de ces processus. Une plateforme, appelée TransportML, pour la collaboration et l'interopérabilité de services à base de positionnement a été implémentée. Les résultats obtenus par la simulation des modèles formels sont comparés à ceux issus des simulations du fonctionnement de la plateforme et des expérimentations sur le terrain.Cette thèse est effectuée dans le cadre des projets Européens FP7 ASSET (2008-2011) et TeleFOT (2008-2012). / Web services are widely used by organizations to share their knowledge over the network and facilitate business-to-business collaboration. The emergence of Web services enabled applications to be presented as a set of business services well structured and correctly described. However, combining Web services and making them interoperable, to satisfy user requests taking into account functional and non-functional quality criteria, is a complex process. In this work, we focus specifically on location-based services (LBS) that integrate geographic information and provide information reachable from mobile devices, through wireless network by making use of the geographical positions of the devices. The aim of this work is to develop a model driven approach to specify, validate and implement service composition process in an automatic fashion for road security. This approach is based on two formal tools namely Petri nets (PN) and (max, +) algebra used to model, to verify and to evaluate the performance of service composition process. Workflow patterns are used to represent service composition processes. The behavior of each pattern is modeled by a PN model and then by a (max,+) state equation. The developed formal models allow the graphical and analytical description of the considered processes. Also, these models enable to evaluate some quantitative and qualitative properties of the considered processes. A platform, called TransportML, has been developed for collaboration and interoperability of different LBS. The obtained simulation results from the formal models are compared, on one hand, to those obtained from trials of the platform, and on the other hand, to those obtained from the real experimentations on the field.This work is a part of the FP7 European projects ASSET (2008-2011) and TeleFOT (2008-2012).

No description available.

Cette thèse étudie d'un point de vue historique la genèse de la cohomologie des groupes, théorie qui vit le jour dans les années 1940. Il s'agit d'une théorie à la fois algébrique, au sens où elle donne des résultats sur les groupes, et topologique par les méthodes qu'elle met en œuvre . Le présent travail analyse les mécanismes par lesquels la topologie et l'algèbre se sont interpénétrées pour donner naissance à cette théorie abstraite et élaborée, en mettant notamment en perspective ce phénomène par rapport à ceux, plus globaux, de la naissance et de l'expansion de l'algèbre moderne. Y sont notamment discutées l'influence d'Emmy Noether dans l'algébrisation de la topologie et les motivations respectives de Heinz Hopf et d'Eilenberg & Mac Lane les ayant menés à l'élaboration de l'homologie des groupes. L'analyse minutieuse de plusieurs articles phares - dus aux auteurs cités précédemment mais aussi à Schur, Vietoris ou encore Eckmann - permet de mettre en lumière le fait que la volonté de répondre à des problèmes mathématiques précis fut peut-être plus motrice, dans l'émergence de cette théorie architectonique qu'est la cohomologie des groupes, que de grandes idées directrices conçues au sein de représentations structurales des mathématiques.

Cette thèse s'intéresse d'une part au problème de décomposition technologique orienté surface sur des réseaux programmables de type FPGAs (Field Programmable Gate Arrays) et d'autre part à la synthèse des macro-générateurs sur ASICs et plus précisément de la synthèse des additionneurs. La décomposition s'articule autour de deux axes essentiels: tout d'abord, il s'agit d'optimiser la taille de la représentation des fonctions booléennes. Les représentations de base choisies ici sont les ROBDDs (Reduced Ordered Binary Decision Diagrams) ainsi qu'une structure dérivée, les ITE (If Then Else). La deuxième étape concerne la décomposition proprement dite. Les technologies cibles sont ici des FPGAs à base de LUT-k (Look Up Table), en particulier les FPGAs XC5200 de Xilinx et Orca de AT&T. Les deux méthodes de décomposition technologique orienté surface proposées permettent une décomposition hétérogène en prenant en compte non pas une seule configuration mais un ensemble de configurations possibles de la cellule cible. La première méthode est fondée sur un parcours descendant et optimisé du ROBDD. La seconde méthode s'appuie sur une modélisation en recouvrement d'hypergraphe du problème de décomposition technologique. Dans les deux méthodes, le coût exact en terme de surface finale du circuit est pris en compte à chaque étape de la décomposition. L'étude menée dans la deuxième partie de la thèse sur la macro-génération conduit dans un premier temps à l'exploration de l'espace des solutions possibles puis à l'optimisation d'une solution sélectionnée par un algorithme de dérivation discrète. L'utilisation d'un filtre permet la restriction de l'espace des solutions à explorer et d'autre part guide le processus de dérivation en éliminant les solutions trivialement médiocres. La combinaison des processus d'exploration et de dérivations permet la génération de macros dont les caractéristiques physiques sont les plus proches possibles de celles fixées par un utilisateur potentiel. Ces méthodes ont été intégrées au sein d'un outil universitaire ASYL+ développé au laboratoire CSI

Cette thèse explore la relation entre les catégories de modules sur les catégories différentielles graduées (abrégées DG) petites, d'une part, et les catégories triangulées bien engendrées d'autre part. Dans la première partie, on construit la catégorie dérivée $\alpha$-continue D_\alpha A d'une catégorie DG $\alpha$-cocomplète petite A, où $\alpha$ est un cardinal régulier. Cette construction jouit d'une propriété très intéressante, qui est la clef pour démontrer le théorème principal de la thèse. Les catégories D_\alpha A s'avèrent être les prototypes des catégories triangulées algébriques à engendrement $\alpha$-compact. On entend par algébrique, équivalente, en tant que catégorie triangulée à la catégorie stable d'une catégorie de Frobenius. Le résultat principal établit que les catégories algébriques bien engendrées sont précisément celles qui sont des localisations de la catégorie dérivée d'une catégorie DG petite. Ce résultat rappelle beaucoup un théorème de Gabriel et Popescu de 1964, qui caractérise les catégories abéliennes de Grothendieck comme des localisations de catégories de modules sur des anneaux. Il donne aussi une réponse positive à une question de Drinfeld qui demandait si toutes les catégories triangulées bien engendrées sont des localisations de catégories triangulées à engendrement compact, pour la classe des catégories triangulées algébriques. Dans la deuxième partie, on étudie les catégories DA et D_\alpha A en utilisant la structure projective de catégories de modèles de Quillen présente sur la catégorie des DG modules. On introduit la sous-catégorie des DG modules cofibrants homotopiquement $\alpha$-compacts et on montre que sa catégorie homotopique est précisément la catégorie dérivée $\alpha$-continue D_\alpha A. Cela nous permet de donner une deuxième preuve, complètement différente du résultat-clef de la première partie.