Le célèbre théorème de Birkhoff affirme que l'espace Dₙ des matrices doublement stochastiques d'ordre n est un polytope convexe dont les matrices de permutation constituent les points extrémaux. De cette structure particulière émerge une structure géométrique intéressante que nous explorons en détail dans ce mémoire. Plus précisément, nous explorons quelques propriétés géométriques de Dₙ, vu comme un espace métrique muni de deux différents types de normes, à savoir les p-normes de Schatten et les normes d'opérateurs induites par les normes vectorielles ℓᵖ. En particulier, nous étudions la norme des matrices doublement stochastiques ainsi que le rayon de Tchebychev, les centres de Tchebychev et le diamètre de Dₙ. Ce faisant, de nouvelles connexions avec le célèbre problème d'affectation sont établies. Nous utilisons également les propriétés géométriques de Dₙ établies dans ce mémoire pour améliorer un résultat de Štefan Schwarz sur la convergence de produits infinis de matrices doublement stochastiques. / The celebrated Birkhoff theorem states that the space of n × n doubly stochastic matrices Dₙ is a convex polytope whose extreme points are the permutation matrices. From this particular structure emerges an interesting geometric structure that we explore in detail in this dissertation. Specifically, we explore some geometric properties of Dₙ, seen as a metric space equipped with two different type of norms, which are the Schatten p-norms and the operator norms induced by the ℓᵖ vector norms. In particular, we study the norm of the doubly stochastic matrices along with the Chebyshev radius, the Chebyshev centers and the diameter of Dₙ. In doing so, new connections with the well-known assignment problem are made. We also use the geometric properties of Dₙ established in this dissertation to improve a result of Štefan Schwarz about the convergence of infinite product of doubly stochastic matrices.

Les systèmes complexes se caractérisent par l’émergence de phénomènes macroscopiques qui ne s’expliquent pas uniquement par les propriétés de leurs composantes de base. La synchronisation est l’un de ces phénomènes par lequel les interactions entre des oscillateurs engendrent des mouvements collectifs coordonnés. Une représentation sous forme de graphe permet de modéliser précisément les interactions, alors que les oscillations se décrivent par des dynamiques non linéaires. Étant donné le lien subtil entre le graphe et la dynamique des oscillateurs, il est difficile de prédire l’émergence de la synchronisation. L’objectif de ce mémoire est de développer de nouvelles méthodes pour simplifier les systèmes complexes d’oscillateurs afin de révéler les mécanismes engendrant la synchronisation. À cette fin, nous introduisons des notions de la théorie des graphes et des systèmes dynamiques pour définir la synchronisation sur des bases mathématiques. Nous présentons ensuite des approches existantes sophistiquées pour réduire la dimension de dynamiques d’oscillateurs. Ces techniques sont toutefois limitées lorsque les dynamiques évoluent sur des graphes plus complexes. Nous développons alors une technique originale—spécialement adaptée pour les graphes aux propriétés plus hétérogènes—pour réduire la dimension de dynamiques non linéaires. En plus de généraliser des approches récentes, notre méthode dévoile plusieurs défis théoriques reliés à la simplification d’un système complexe. Entre autres, la réduction de la dimension du système se bute à une trichotomie : il faut favoriser la conservation des paramètres dynamiques, des propriétés locales du graphe ou des propriétés globales du graphe. Finalement, notre méthode permet de caractériser mathématiquement et numériquement l’émergence d’états exotiques de synchronisation. / Complex systems are characterized by the emergence of macroscopic phenomena that cannot be explained by the properties of their basic constituents. Synchronization is one of these phenomena in which the interactions between oscillators generate coordinate collective behaviors. Graphs allow a precise representation of the interactions, while nonlinear dynamics describe the oscillations. Because of the subtle relationship between graphs and dynamics of oscillators, it is challenging to predict the emergence of synchronization. The goal of this master’s thesis is to develop new methods for simplifying complex systems of oscillators in order to reveal the mechanism causing synchronization. To this end, we introduce notions of graph theory and dynamical systems to define synchronization on sound mathematical basis. We then present existing sophisticated approaches for reducing the dimension of oscillator dynamics. Yet, the efficiency of these techniques is limited for dynamics on complex graphs. We thus develop an original method—specially adapted for graphs with heterogeneous properties—for reducing the dimensions of nonlinear dynamics. Our method generalizes previous approaches and uncovers multiple challenges related to the simplification of complex systems. In particular, the dimension reduction of a system comes up against a trichotomy: one must choose to conserve either the dynamical parameters, the local properties of the graph, or the global properties of the graph. We finally use our method to characterize mathematically and numerically the emergence of exotic synchronization states.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'automatique est une discipline qui traite entre autres de la commande et du diagnostic des systèmes industriels. Une première étape à l'obtention de schémas de commande et de diagnostic est d’analyser les propriétés du système considéré. Les principales propriétés analysées sont la commandabilité, l'observabilité, la diagnosticabilité, la stabilité… Des critères, souvent basés sur des approches algébriques ou géométriques, permettent de caractériser ces propriétés. En outre, des travaux publiés dans les années 1970 ont permis d’introduire une nouvelle représentation de systèmes à base de graphes orientés. De ces travaux, il résulte que l'approche graphique fournit des solutions simples et est ainsi très bien adaptée pour analyser des systèmes de grande dimension et/ou incertains. Malheureusement, peu de travaux basés sur des méthodes graphiques traitent des systèmes non linéaires. Par notre travail, nous avons souhaité combler ce manque en étudiant les propriétés d’observabilité et de diagnosticabilité des systèmes bilinéaires structurés à l’aide d’une approche graphique. Des conditions graphiques nécessaires et suffisantes d’observabilité de l’ensemble et d’une partie de l’état d’un système sont formulées. Par la suite le problème de placement de capteurs est abordé afin de recouvrer les propriétés d’observabilité. Enfin, nous nous sommes focalisés sur la propriété de diagnosticabilité. Après avoir donné une condition graphique nécessaire et suffisante de solubilité du problème de détection de défauts, nous avons alors étudié différents cas particuliers de commande afin de donner des conditions de solubilité au problème actif de détection de défauts. / Automation is a discipline which treats inter alia control and diagnosis of industrial systems. A first stage to obtain control and diagnosis schemes is to analyze the properties of the considered system. The main analyzed properties are controllability, observability, diagnosticability, stability… Criteria, often based on algebraic or geometrical approaches, make it possible to characterize these properties. Moreover, some works published in the 70’s introduced a new representation of systems based on directed graphs. From these works, it results that graphical approach provides simple solutions and thus is very well suited to analyze great dimension and/or uncertain systems. Unfortunately, few works based on graphic methods treats nonlinear systems. By our work, we wished to fill this lack by studying observability and diagnosticability properties for structured bilinear systems using a graphical approach. Necessary and sufficient graphic conditions for the observability of the whole and part of the system state are formulated. Thereafter the sensor placement problem is tackled in order to recover the observability property. Lastly, we focused ourselves on the diagnosticability property. After having given a necessary and sufficient graphic condition of fault detection problem solubility, we then studied various particular cases of control in order to give conditions of active fault detection problem solubility.

Safety-critical systems depend on the fact that their software components provide services that behave correctly (i.e. satisfy their requirements). Additionally, in many cases, these systems have to be adapted or reconfigured in case of failures or when changes in requirements or in quality of service occur. When these changes appear at the software level, they can be handled by the notion of substitution. Indeed, the software component of the source system can be substituted by another software component to build a new target system. In the case of safety-critical systems, it is mandatory that this operation enforces that the new target system behaves correctly by preserving the safety properties of the source system during and after the substitution operation. In this thesis, the studied systems are modeled as state-transition systems. In order to model system substitution, the Event-B method has been selected as it is well suited to model such state-transition systems and it provides the benefits of refinement, proof and the availability of a strong tooling with the Rodin Platform. This thesis provides a generic model for system substitution that entails different situations like cold start and warm start as well as the possibility of system degradation, upgrade or equivalence substitutions. This proposal is first used to formalize substitution in the case of discrete systems applied to web services compensation and allowed modeling correct compensation. Then, it is also used for systems characterized by continuous behaviors like hybrid systems. To model continuous behaviors with Event-B, the Theory plug-in for Rodin is investigated and proved successful for modeling hybrid systems. Afterwards, a correct substitution mechanism for systems with continuous behaviors is proposed. A safety envelope for the output of the system is taken as the safety requirement. Finally, the proposed approach is generalized, enabling the derivation of the previously defined models for web services compensation through refinement, and the reuse of proofs across system models.

Depuis plusieurs années, de nombreuses recherches ont été menées autour du diagnostic. Cependant, il est impératif de se préoccuper dès la phase de conception d'un système des objectifs de diagnostic à atteindre. Aussi, de nombreux travaux se sont intéressés à analyser et à caractériser les propriétés de la diagnosticabilité d'un système. La diagnosticabilité est la propriété d'un système garantissant qu'il génère des observations permettant de détecter et discriminer les fautes en temps fini après leur occurrence.Le sujet de cette thèse porte sur les méthodes permettant d'établir les propriétés de la diagnosticabilité des systèmes à événements discrets dans le cadre distribué, sans construction du modèle global du système. Ce cadre est de première importance pour les applications réelles : systèmes naturellement distribués, systèmes trop complexes pour traiter leur modèle global, confidentialité des modèles locaux les uns par rapport aux autres. L'analyse de la diagnosticabilité de tels systèmes distribués se fonde sur des opérations de synchronisation des modèles locaux, par les observations et les communications. D'abord, nous étudions comment optimiser cette analyse de la diagnosticabilité en faisant abstraction de l'information nécessaire et suffisante à partir des objets locaux pour décider la diagnosticabilité globale. L'efficacité de l'algorithme peut être grandement améliorée par la synchronisation des objets locaux et abstraits en comparaison avec celle des objets locaux et non abstraits.Ensuite, nous proposons, dans le cadre distribué, l'algorithme de la diagnosticabilité de motifs d'événements particuliers a priori inobservables dans les systèmes. Ces motifs peuvent être simplement l'occurrence, brutale ou graduelle, d'une faute permanente ou transitoire, plusieurs occurrences d'une faute, plusieurs fautes en cascade, etc. Dans le cadre distribué, la reconnaissance du motif d'événements s'effectue d'abord progressivement dans un sous-système et ensuite la diagnosticabilité de ce motif peut être déterminée par la méthode abstraite et distribuée. Nous prouvons la correction et l'efficacité de notre algorithme à la fois en théorie et en pratique par la mise en œuvre de l'implémentation sur des exemples.Finalement, nous étudions le problème de la diagnosticabilité dans les systèmes distribués avec composants autonomes, où l'information observable est distribuée au lieu d'être centralisée comme jusqu'alors. En d'autres termes, chaque composant ne peut appréhender que ses propres événements observables. Nous donnons la définition de la diagnosticabilité conjointe. Et puis nous discutons de l'indécidabilité de diagnosticabilité conjointe dans le cas général, c'est à dire, les événements de communication ne sont pas observables, avant de proposer un algorithme pour tester sa condition suffisante. De plus, nous obtenons également un résultat de décidabilité et de l'algorithme lorsque les communications sont observables.

Nous avons proposé une architecture de sécurité apte à répondre aux besoins généraux de sécurité de des systèmes hétérogènes distribués ouverts à grande échelle. Nous avons procédé à d'importants travaux de terrain pour déterminer les limitations et les failles des solutions de sécurité actuellement proposées pour ces systèmes et pour établir quels sont les véritables besoins que doit satisfaire l'architecture de sécurité, de manière à réduire les pertes de performances et à assurer une sécurité robuste. Nous avons notamment identifié l'analyse des besoins, l'analyse du risque, la modélisation des menaces et la faisabilité de mise en œuvre. Le concept de virtualisation des services de sécurité est introduit pour les services en question. Il est nécessaire de disposer d'une totale liberté de choix des mécanismes de sécurité sous-jacents. Du point de vue de la sécurité, la virtualisation de la définition d'un service tient compte des besoins de sécurité qui permettent d'accéder à ce service. Il permet à chaque terminaison participante d'exprimer la politique qu'elle souhaite voir appliquer lorsqu'elle s'engage dans un échange sécurisé avec une autre terminaison. Un mécanisme configurable d'appel des services de sécurité est proposé pour répondre aux besoins de sécurité des différentes catégories d'utilisateurs. Cette approche permet de faire évoluer l'infrastructure de sécurité avec des effets moindres sur les fonctionnalités de gestion des ressources, qui sont encore en pleine phase d'évolution. En outre, elle permet aux utilisateurs et aux fournisseurs de ressources de configurer l'architecture de sécurité en fonction de leurs besoins et de leur niveau de satisfaction.

Java est une technologie attractive pour les équipements embarqués et contraints, de par ses propriétés de sûreté, de portabilité et de faible empreinte mémoire du code. Cependant, la taille imposante d'un environnement Java complet a obligé les producteurs d'équipements embarqués à utiliser des spécifications dégradées de Java aux fonctionnalités limitées, telles que J2ME ou Java Card. Ces spécialisations précoces de Java perdent la compatibilité au niveau applicatif avec l'édition standard, et ne peuvent ainsi s'adresser qu'à des cas d'utilisation particuliers.Notre travail consiste à permettre l'utilisation de l'édition standard de Java sur les systèmes contraints, au travers d'une spécialisation tardive et agressive du système qui intervient après déploiement de ses applications. L'occurrence tardive de la spécialisation permet de mieux déterminer les conditions d'utilisation du système, et donc de le spécialiser « sur mesure » par rapport aux applications qu'il exécute.Nos contributions sont les suivantes : dans un premier temps, nous définissons la notion de « romization », consistant à déployer un système hors-ligne avant de capturer et de transférer son image mémoire vers l'équipement sur lequel il doit s'exécuter. De cette définition, nous proposons une architecture de romization capable de capturer une image mémoire du système à n'importe quel moment de son exécution. Dans un second temps, nous traitons des moyens d'analyse et de spécialisation permettant de rendre cette image mémoire embarquable. L'évaluation effectuée montre que cette spécialisation tardive, appliquée à un environnement Java standard déployé, permet effectivement d'en obtenir une version minimaliste et embarquable sur un équipement contraint.

Soit Г un graphe de Coxeter. Soient W le groupe de Coxeter, A le groupe d'Artin, et A+ le monoïde d'Artin, associés à Г. Soit G un groupe de symétries du graphe de Coxeter Г. Alors G agit sur W, A et A+, et il est connu que le sous-groupe fixe, WG, est un groupe de Coxeter, le sous-monoïde fixe, A+G, est un monoïde d'Artin, et, lorsque Г est de type sphérique, le sous-groupe fixe, AG, est un groupe d'Artin. Cette thèse étudie le comportement de WG, A+G et AG par rapport à des représentations fidèles de W, A et A+, respectivement.Dans un premier temps nous considérons les représentations enracinées introduites par Krammer dans sa thèse. Ce sont une généralisation des représentations canoniques. On se donne une telle représentation f : W → GL(V ) et on suppose que l'action de G sur les racines simples s'étend à V . Dans ce cas f induit une représentation linéaire fG : WG → GL(V G). Nous démontrons que cette représentation est aussi une représentation enracinée. En particulier, elle est fidèle.Dans un second temps nous supposons que Г est simplement lacé, c'est-à-dire que les arêtes de Г n'ont pas de poids. Nous considérons une représentation linéaire fidèle ψ : A+ → GL(E) introduite par Paris. Si Г est de type sphérique, alors cette représentation induit une représentation fidèle ψ : A → GL(E) du groupe. Dans le cas des groupe de tresses, c'est la célèbre représentation linéaire fidèle étudiée par Bigelow et Krammer. Nous démontrons que G agit aussi sur E, que la représentation ψ : A+ → GL(E) est équivariante, et qu'elle induit une représentation fidèle ψ : A+G → GL(EG). Si Г est de type sphérique, alors on obtient une représentation fidèle du groupe fixe, ψ : AG → GL(EG). Finalement, nous déterminons les cas où EG admet une base naturelle en bijection avec le système de racines positives de WG. Ce dernier résultat est motivé par la recherche d'une extension de la représentation ψ : A+ → GL(E) aux graphes qui ne sont pas simplement lacés. / Let Г be a Coxeter graph. Let W be the Coxeter group, A be the Artin group, and A+ be the Artin monoid associated with Г. Let G be a group of symmetries of Г. Then G acts on W, A and A+. The fixed subgroup WG is known to be a Coxeter group, the fixed submonoid A+G is known to be an Artin monoid, and, when Г is of spherical type, the fixed subgroup AG is known to be an Artin group. This thesis studies the behavior of WG, A+G and AG with respect to some faithful linear representations of W, A and A+, respectively.Firstly, we consider the rooted representations of the Coxeter groups introduced by Krammer in his Ph. D. Thesis. These are a generalization of the canonical representations. We take such a linear representation f : W → GL(V ), assuming that the action of G on the simple roots extends to V . Then f induces a linear representation fG : WG → GL(V G). We prove that fGis a rooted representation of WG. In particular, fG is faithful.Afterwards, we assume that Г is simply laced, that is, all the edges of Г are label free. Then we consider a faithful linear representation ψ : A+ → GL(E) introduced by Paris. If Г is of spherical type, this representation extends to a faithful linear representation ψ : A → GL(E) of the Artin group. In the case of the braid groups, it is the celebrated representation studiedby Bigelow and Krammer. Take a group G of symmetries of Г. We prove that G acts on E, that the representation ψ : A+ → GL(E) is equivariant, and that it induces a faithful linear representation ψ : A+G → GL(EG). If Г is of spherical type, then we get a faithful linear representation ψ : AG → GL(EG) of the fixed subgroup. Finally, we determine the cases where EG admits a natural basis in one-to-one correspondence with the positive root system of WG. This last result is motivated by the search of an extension of the linear representation ψ : A+ → GL(E) to Artin monoids (or groups) that are not simply laced.

Avec la multiplication des objets connectés, les systèmes multi-échelles sont de plus en plus répandus. Ces systèmes sont fortement répartis, hétérogènes, dynamiques et ouverts. Ils peuvent être composés de centaines de composants logiciels déployés sur des milliers d'appareils.Le déploiement est un processus complexe qui a pour objectif la mise à disposition puis le maintien en condition opérationnelle d'un système logiciel. Pour les systèmes multi-échelles, l'expression du plan de déploiement ainsi que la réalisation et la gestion du déploiement sont des tâches humainement impossibles du fait de l'hétérogénéité, de la dynamique, du nombre, mais aussi parce que le domaine de déploiement n'est pas forcément connu à l'avance. L'objectif de cette thèse est d'étudier et de proposer des solutions pour le déploiement de systèmes répartis multi-échelles. Nous proposons tout d'abord une mise à jour du vocabulaire relatif au déploiement, ainsi qu'un état de l'art sur le déploiement automatique des systèmes logiciels répartis. Le reste de la contribution réside dans la proposition : d'un processus complet pour le déploiement autonomique de systèmes multi-échelles ; d'un langage dédié (DSL), MuScADeL, qui simplifie la tâche du concepteur du déploiement et permet d'exprimer les propriétés de déploiement ainsi que des informations concernant la perception de l'état du domaine de déploiement ; d'un middleware, MuScADeM, qui assure la génération automatique d'un plan de déploiement en fonction de l'état du domaine, sa réalisation puis le maintien en condition opérationnelle du système. / Due to increased connected objects, multiscale systems are more and more widespread. Those systems are highly distributed, heterogeneous, dynamic and open. They can be composed of hundreds of software components deployed into thousands of devices. Deployment of software systems is a complex post-production process that consists in making software available for use and then keeping it operational. For multiscale systems, deployment plan expression just as deployment realization and management are tasks impossible for a human stakeholder because of heterogeneity, dynamics, number, and also because the deployment domain is not necessarily known in advance. The purpose of this thesis is to study and propose solutions for the deployment of distributed multiscale software systems. Firstly, we provide an up-to-date terminology and definitions related to software deployment, plus a state of the art on automatic deployment of distributed software systems. The rest of the contribution lies in the proposition of: a complete process for autonomic deployment of multiscale systems ; a domain specific language, MuScADeL, which simplifies the deployment conceptor task and allows the expression of deployment properties such as informations for the domain state probing ; and a middleware, MuScADeM, which insures the automatic generation of a deployment plan according the domain state, its realization and finally the maintenance in an operational condition of the system.