Dans cette thèse nous étudions le problème de détection et localisation de défauts (FDI) diagonal avec une banque d'observateurs. Nous étudions ce problème sur la classe des systèmes linéaires structurés avec leurs graphes associés. Les systèmes structurés sont une classe particulière des systèmes linéaires où les éléments des matrices sont soit fixés à zéro soit des paramètres libres. On présente une condition nécessaire et suffisante pour la solubilité générique du problème FDI. Cette condition est à vérifier sur le graphe orienté associé au système structuré. Dans le cas où cette condition n'est pas vérifiée, nous présentons une décomposition du système qui donne des informations structurelles sur le placement de capteurs additionnels qui sont nécessaires pour remplir la condition. Dans le cas où la condition de solubilité générique du problème FDI est vérifiée, nous présentons aussi une classification des capteurs selon leur importance pour la solubilité générique du problème FDI.

Un graphe mixte est un graphe simple tel que un sous-ensemble des arêtes a une orientation. Pour entiers non négatifs j et k, un graphe mixte-(j,k) est un graphe mixte avec j types des arcs and k types des arêtes. La famille de graphes mixte-(j,k) contient graphes simple, (graphes mixte−(0,1)), graphes orienté (graphes mixte−(1,0)) and graphe coloré arête −k (graphes mixte−(0,k)).Un homomorphisme est un application sommet entre graphes mixte−(j,k) que tel les types des arêtes sont conservés et les types des arcs et leurs directions sont conservés. Le nombre chromatique−(j,k) d’un graphe mixte−(j,k) est le moins entier m tel qu’il existe un homomorphisme à une cible avec m sommets. Quand on observe le cas de (j,k) = (0,1), on peut déterminer ces définitions correspondent à les définitions usuel pour les graphes.Dans ce mémoire on etude le nombre chromatique−(j,k) et des paramètres similaires pour diverses familles des graphes. Aussi on etude les coloration incidence pour graphes and digraphs. On utilise systèmes de représentants distincts et donne une nouvelle caractérisation du nombre chromatique incidence. On define le nombre chromatique incidence orienté et trouves un connexion entre le nombre chromatique incidence orienté et le nombre chromatic du graphe sous-jacent. / A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j,k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j,k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)−mixed graphs) and k−edge- coloured graphs ((0,k)−mixed graphs).A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. The (j,k)−chromatic number of a (j,k)−mixed graph is the least m such that an m−colouring exists. When (j,k)=(0,1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring.In this thesis we study the (j,k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1,0)−chromatic number, more commonly called the oriented chromatic number, and the (0,k)−chromatic number.In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.

Les applications temps réel durs sont celles qui doivent exécuter en respectant des contraintes temporelles. L'ordonnancement temps réel a bien été étudié sur mono-processeurs depuis plusieurs années. Récemment, l'utilisation d'architectures multiprocesseurs a augmenté dans les applications industrielles et des architectures parallèles sont proposées pour que le logiciel devienne compatible avec ces plateformes. L'ordonnancement multiprocesseurs de tâches parallèles dépendantes n'est pas une simple généralisation du cas mono-processeur et la problématique d'ordonnancement devient plus complexe et difficile.
Dans cette thèse, nous étudions le problème d'ordonnancement temps réel de graphes de tâches parallèles acycliques sur des plateformes multiprocesseurs. Dans ce modèle, un graphe est composé d'un ensemble de sous-tâches dépendantes sous contraintes de précédence qui expriment les relations de précédences entre les sous-tâches. L'ordre d'exécution des sous-tâches est dynamique, c'est-à-dire que les sous-tâches peuvent s'exécuter en parallèle ou séquentiellement par rapport aux décisions de l'ordonnanceur temps réel. Pour traiter les contraintes de précédence, nous proposons deux méthodes pour l'ordonnancement des graphes : par transformation du modèle de graphe de sous tâches parallèles en un modèle de tâches séquentielles indépendantes, plus simple à ordonnancer et par ordonnancement direct des graphes en prenant en compte les relations de dépendance entre les sous-tâches. Nous proposons un ordonnancement des graphes en prenant directement en compte les paramètres temporels des graphes et un ordonnancement au niveau des sous-tâches, par rapport à des paramètres temporels attribués aux sous-tâches par un algorithme spécifique.
Enfin, nous prouvons que les deux méthodes d'ordonnancement de graphes ne sont pas comparables. Nous fournissons alors des résultats de simulation pour comparer ces méthodes en utilisant les algorithmes d'ordonnancement globaux EDF et DM. Nous avons développé un logiciel nommé YARTISS pour générer des graphes aléatoires et réaliser les simulations / The interest for multiprocessor systems has recently been increased in industrial applications, and parallel programming API's have been introduced to benefit from new processing capabilities. The use of multiprocessors for real-time systems, whose execution is performed based on certain temporal constraints is now investigated by the industry. Real-time scheduling problem becomes more complex and challenging in that context. In multiprocessor systems, a hard real-time scheduler is responsible for allocating ready jobs to available processors of the systems while respecting their timing parameters.
In this thesis, we study the problem of real-time scheduling of parallel Directed Acyclic Graph (DAG) tasks on homogeneous multiprocessor systems. In this model, a DAG task consists of a set of subtasks that execute under precedence constraints. At all times, the real-time scheduler is responsible for determining how subtasks execute, either sequentially or in parallel, based on the available processors of the system. We propose two DAG scheduling approaches to determine the execution form of DAG tasks. The first approach is the DAG Stretching algorithm, from the Model Transformation approach, which forces DAG tasks to execute as sequentially as possible. The second approach is the Direct Scheduling, which aims at scheduling DAG tasks while respecting their internal dependencies. We provide real-time schedulability analyses for Direct Scheduling at DAG-Level and at Subtask-Level.
Due to the incomparability of DAG scheduling approaches, we use extensive simulations to compare performance of global EDF with global DM scheduling using our simulation tool YARTISS

La visualisation d'information est une approche des plus prometteuses pour l'exploration, l'analyse et la comprehension de donnees. Dans le cadre de cette these, les dierentes collaborations avec les utilisateurs naux de nos methodes (biologistes et geographes) ont permis d'elaborer de nouvelles visualisations et interactions adaptees aux besoins speciques de leur domaine. La notion d'exploration \focus+contexte" est ici centrale. Nous l'avons abordee tant au travers de la visualisation de donnees multidimensionnelles que de graphes hierarchiques. Une methode permettant de visualiser et d'interagir sur des donnees multidimensionnelles est proposee. Cette methode permet d'identier visuellement des correlations non lineaires a l'aide d'une matrice de graphes de correlation. Nous presentons alors une technique permettant de visualiser de facon interactive les structures hierarchiques sous forme de graphes orientes acycliques (DAGs). Les resultats d'une evaluation formelle de la methode sont alors presentes. Une extension a des donnees plus massive utilisant des techniques de visualisation "focus+context" est alors proposee.

Les événements spatio-temporels regroupent une large diversité de phénomènes comportant des caractéristiques propres. Par exemple, l’étude de flux migratoires se révèle ainsi très différente de l’étude de propagation de maladies. En effet, le domaine d’intérêt de la première porte sur le suivi des trajectoires, tandis que celui de la deuxième porte sur les facteurs de la propagation. De plus, chaque classe d’un problème spatio-temporel peut être abordée différemment, que l’on considère ou non un voisinage spatial, une caractérisation des objets d’étude unique ou multiple, ou bien une (in)dépendance entre les événements. Ainsi, les techniques de fouilles de données développées sont souvent restées spécifiques à une sous-classe de problème spatio-temporel, c’est-à-dire sous un ensemble restreint d’hypothèses.Or, pour réussir à dégager des connaissances nouvelles à partir de données, il est nécessaire d’élargir cet ensemble d’hypothèses, c’est-à-dire élargir le champs des possibles quant aux corrélations qu’il peut exister entre événements. Nous proposons donc une modélisation de ces phénomènes spatio-temporels permettant de prendre en compte plus de considérations que dans l’état de l’art. En outre, cette modélisation permet d’exprimer des événements qui existent dans les phénomènes d’érosion : un objet d’étude peut se diviser en plusieurs objets, ou fusionner avec d’autres objets pour n’en former qu’un seul. Plus précisément, nous modélisons les dynamiques spatio-temporelles sous la forme d’un unique graphe orienté, que la composante temporelle des problèmes rend acyclique, et dont les sommets sont attribués par plusieurs caractéristiques. / Spatio-temporal events denote a large range of phenomena with different characteristics. For example, migration flows studies appear to be very different from disease spread studies. Indeed, interestingness of the first relies on tracking trajectories, whereas the second is about finding the factors of spread. Moreover, each class of a spatio-temporal problem can be tackled differently, depending on which parameters are considered: the studied spatial neighbourhood, the number of characteristics associated with the objects, or whether events are supposed correlated or independent. As a result, data mining techniques are often specificto a sub-class of spatio-temporal problem, that is to say, to a limited set of hypothesis.In order to bring out new knowledge from data, it seems to be necessary to enlarge this set of hypothesis, that is to say, to widen the field of possibilities regarding correlations that may exist between events. For this, we propose a new model that allows to take into account more considerations than existing studies. For example, this representation allows to model the complex spatio-temporal dynamic of erosion phenomenon: an object can be split up in several other objects, or can merge with other objects into one. More precisely, we use a single directed graph, that becomes acyclic thanks to the temporal component of the problem, and that is attributed by several characteristics.

On considère le problème d'advection-diffusion stationnaire v(∇u, ∇v)+( β*∇u, v) = (f, v) et non stationnaire d/dt (u(t), v) + v(∇u, ∇v)+( β*∇u, v) = (g(t), v), ainsi que le problème d'advection (β*∇u, v) = (f, v) sur un domaine polygonal borné du plan. Le terme de diffusion est approché par des éléments de Crouzeix Raviart et le terme de convection par une méthode upwind sur des volumes barycentriques finis avec un maillage triangulaire. Pour le problème stationnaire d'advection-diffusion, la L²-stabilité (c'est-à-dire indépendante du coefficient de diffusion v) est démontrée pour la solution du problème approché obtenue par cette méthode d'éléments finis et de volumes finis. Pour cela une condition sur la géométrie doit être satisfaite. Des exemples de maillages sont donnés. Toujours avec cette condition géométrique sur le maillage, une inégalité de stabilité (où la discrétisation en temps n'est pas couplée à une condition sur la finesse du maillage) est obtenue pour le cas non-stationnaire. La discrétisation en temps y est faite par un schéma d'Euler implicite. Une majoration de l'erreur, proportionnelle au pas en temps et à la finesse du maillage, est ensuite proposée et exprimée explicitement en fonction des données du problème. Pour le problème d'advection, une approche utilisant la théorie des graphes est utilisée pour obtenir l'existence et l'unicité de la solution, ainsi que le résultat de stabilité. Comme pour la stabilité du problème d'advection-diffusion, une condition géométrique - qui est équivalente pour les points intérieurs du maillage à celle du problème d'advection-diffusion - est nécessaire.

On considère le problème d’advection-diffusion stationnaire v(∇u, ∇v)+( β•∇u, v) = (f, v) et non stationnaire d/dt (u(t), v) + v(∇u, ∇v)+( β•∇u, v) = (g(t), v), ainsi que le problème d’advection (β•∇u, v) = (f, v) sur un domaine polygonal borné du plan. Le terme de diffusion est approché par des éléments de Crouzeix Raviart et le terme de convection par une méthode upwind sur des volumes barycentriques finis avec un maillage triangulaire. Pour le problème stationnaire d’advection-diffusion, la L²-stabilité (c’est-à-dire indépendante du coefficient de diffusion v) est démontrée pour la solution du problème approché obtenue par cette méthode d’éléments finis et de volumes finis. Pour cela une condition sur la géométrie doit être satisfaite. Des exemples de maillages sont donnés. Toujours avec cette condition géométrique sur le maillage, une inégalité de stabilité (où la discrétisation en temps n’est pas couplée à une condition sur la finesse du maillage) est obtenue pour le cas non-stationnaire. La discrétisation en temps y est faite par un schéma d’Euler implicite. Une majoration de l’erreur, proportionnelle au pas en temps et à la finesse du maillage, est ensuite proposée et exprimée explicitement en fonction des données du problème. Pour le problème d’advection, une approche utilisant la théorie des graphes est utilisée pour obtenir l’existence et l’unicité de la solution, ainsi que le résultat de stabilité. Comme pour la stabilité du problème d’advection-diffusion, une condition géométrique - qui est équivalente pour les points intérieurs du maillage à celle du problème d’advection-diffusion - est nécessaire. / We consider the stationary linear convection-diffusion equation v(∇u, ∇v)+( β•∇u, v) = (f, v), the time dependent d/dt (u(t), v) + v(∇u,∇v)+( β•∇u, v)= (g(t), v) equation and the linear advection equation (β•∇u, v) = (f, v) on a two dimensional bounded polygonal domain. The diffusion term is discretized by Crouzeix-Raviart piecewise linear finite elements, and the convection term by upwind barycentric finite volumes on a triangular grid. For the stationary convection-diffusion problem, L²-stability (i.e. independent of the diffusion coefficient v) is proven for the approximate solution obtained by this combined finite-element finite-volume method. This result holds if the underlying grid satisfies a condition that is fulfilled, for example, by some structured meshes. Using again this condition on the grid, stability is shown for the time dependent convection-diffusion equation (without any link between mesh size and time step). An implicit Euler approach is used for the time discretization. It is shown that the error associated with this scheme decays linearly with the mesh size and the time step. This result holds without any link between mesh size and time step. The dependence of the corresponding error bound on the diffusion coefficient is completely explicit. For the stationary advection equation, an approach using graph theory is used to obtain existence, uniqueness and stability. As in the stationary linear convection-diffusion equation, the underlying grid must satisfy some geometric condition. / Gegenstand der Arbeit ist die zweidimensionale stationäre Konvektion-Diffusionsgleichung v(∇u, ∇v)+( β•∇u, v) = (f, v), die zeitabhängige Konvektion-Diffusionsgleichung d/dt (u(t), v) + v(∇u,∇v)+( β•∇u, v)= (g(t), v), sowie die Konvektionsgleichung (β•∇u, v) = (f, v). Der Diffusionsterm ist diskretisiert mittels Crouzeix-Raviart stückweise lineare Finite Elemente. Das Gebiet ist in Dreiecke unterteilt und der Konvektionsterm ist mittels einer upwind Methode auf Baryzentrische Finite Volumenelemente definiert. Für die stationäre Konvektion-Diffusionsgleichung, wird (d.h. von v unabhängige) L²-Stabilität der numerischen Lösung bewiesen. Voraussetzung dafür, ist die Erfüllung gewisser geometrischer Bedingungen an die Unterteilung des Gebiets. Beispiele von Unterteilungen die diese Bedingungen erfüllen, werden gegeben. Wieder an dieser geometrischen Bedingung geknüpft, wird Stabilität (d.h. die Zeitdiskretisierung ist entkoppelt von der Netzweite) für die zeitabhängige Konvektion-Diffusionsgleichung, bewiesen. Für die Zeitableitung wird dabei eine Implizite Euler Diskretisierung verwendet. Eine obere Schranke für den Diskretisierungsfehler, proportional zum Zeitdiskretisierungsparameter und zur Netzfeinheit, ausgedrückt als Funktion der Daten der Differenzialgleichung, wird gezeigt. Für die Konvektionsgleichung wird ein graphentheoretischer Zugang verwendet, der es ermöglicht Existenz, Eindeutigkeit und Stabilität, zu bekommen. Für die Stabilität, werden ähnliche geometrische Bedingungen an die Unterteilung des Gebiets gestellt, wie beim stationären Konvektion-Diffusionsproblem.