Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.

Les systèmes LTI à contrôler sont soumis à des contraintes physiques et technologiques. Nous avons montré que celles-ci limitent la bande passante atteignable en boucle fermée. Il s'en suit qu'il suffit de modéliser et d'analyser ces systèmes dans une bande de fréquences limitée, et non pas sur toutes les fréquences, et que l'utilisation de correcteurs d'ordres réduits est tout à fait efficace. Dans cette thèse, nous nous intéressons à la synthèse de correcteurs d'ordres réduits fixés sous contraintes de robustesse, et à la réduction de modèles pour de tels systèmes. La méthode proposée consiste à déterminer un correcteur de structure donnée qui optimise le rejet de la perturbation de commande de type échelon au sens de la norme H2, en respectant des contraintes de robustesse, i.e. marge de module minimum, marge de phase minimum et amplification maximum du bruit de mesure sur la commande. En s'appuyant sur une base de modèles génériques d'ordres réduits, la méthode aboutit à une formulation d'optimisation mixte H2/H-infini semi-analytique de la fonction objectif et de contraintes d'inégalités en termes des gains inconnus du correcteur. Lorsque le système à contrôler est d'ordre élevé, nous proposons une méthode de réduction de modèle avec garantie de marges de robustesse en boucle fermée afin d'obtenir les paramètres des modèles génériques d'ordres réduits. Si le modèle du système à contrôler n'est pas disponible, nous présentons une méthode d'identification expérimentale par la méthode du relais sur la base de modèles génériques. Dans le but de rendre l'approche proposée plus accessible à un usage industriel, nos développements in fine ont été intégrés à des outils logiciels d'aide à la conception d'un système de commande.

Ce manuscrit de thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.<br /><br />La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles d'ensembles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci-dessus : celle concernant les décompositions de graphes.<br /><br />La deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude.<br />Dans chacun des trois, il est montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace.<br />Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.

La modélisation du transport réactif du contaminant en milieu poreux est un problème complexe cumulant les difficultés de la modélisation du transport avec celles de la modélisation de la chimie et surtout du couplage entre les deux. Cette modélisation conduit à un système d'équations aux dérivées partielles et algébriques dont les inconnues sont les quantités d'espèces chimiques. Une approche possible, déjà utilisée par ailleurs, est de choisir la méthode globale DAE : l'utilisation d'une méthode de lignes, correspondant à la discrétisation en espace seulement, conduit à un système différentiel algébrique (DAE) qui doit être résolu par un solveur adapté. Dans notre cas, on utilise le solveur IDA de Sundials qui s'appuie sur une méthode implicite, à ordre et pas variables, et qui requiert à chaque pas de temps la résolution d'un grand système non linéaire associé à une matrice jacobienne. Cette méthode est implémentée dans un logiciel qui s'appelle GRT3D (Transport Réactif Global en 3D). Le présent travail présente une amélioration de la méthode GDAE, du point de vue de la performance, de la stabilité et de la robustesse. Nous avons ainsi enrichi les possibilités de GRT3D, par la prise en compte complète des équations de précipitation-dissolution permettant l'apparition ou la disparition d'une espèce précipitée. En complément de l'étude de la méthode GDAE, nous présentons aussi une méthode séquentielle non itérative (SNIA), qui est une méthode basée sur le schéma d'Euler explicite : à chaque pas de temps, on résout explicitement l'équation de transport et on utilise ces calculs comme données pour le système chimique, résolu dans chaque maille de façon indépendante. Nous présentons aussi une comparaison entre cette méthode et l'approche GDAE. Des résultats numériques pour deux cas tests, celui proposé par l'ANDRA (cas-test 2D) d'une part, celui proposé par le groupe MoMas (Benchmark "easy case") d'autre part, sont enfin présentés, commentés et analysés.

La modélisation du transport réactif du contaminant en milieu poreux est un problème complexe cumulant les difficultés de la modélisation du transport avec celles de la modélisation de la chimie et surtout du couplage entre les deux. Cette modélisation conduit à un système d'équations aux dérivées partielles et algébriques dont les inconnues sont les quantités d'espèces chimiques. Une approche possible, déjà utilisée par ailleurs, est de choisir la méthode globale DAE : l'utilisation d'une méthode de lignes, correspondant à la discrétisation en espace seulement, conduit à un système différentiel algébrique (DAE) qui doit être résolu par un solveur adapté. Dans notre cas, on utilise le solveur IDA de Sundials qui s'appuie sur une méthode implicite, à ordre et pas variables, et qui requiert à chaque pas de temps la résolution d'un grand système non linéaire associé à une matrice jacobienne. Cette méthode est implémentée dans un logiciel qui s'appelle GRT3D (Transport Réactif Global en 3D). Le présent travail présente une amélioration de la méthode GDAE, du point de vue de la performance, de la stabilité et de la robustesse. Nous avons ainsi enrichi les possibilités de GRT3D, par la prise en compte complète des équations de précipitation-dissolution permettant l'apparition ou la disparition d'une espèce précipitée. En complément de l'étude de la méthode GDAE, nous présentons aussi une méthode séquentielle non itérative (SNIA), qui est une méthode basée sur le schéma d'Euler explicite : à chaque pas de temps, on résout explicitement l'équation de transport et on utilise ces calculs comme données pour le système chimique, résolu dans chaque maille de façon indépendante. Nous présentons aussi une comparaison entre cette méthode et l'approche GDAE. Des résultats numériques pour deux cas tests, celui proposé par l'ANDRA (cas-test 2D) d'une part, celui proposé par le groupe MoMas (Benchmark "easy case") d'autre part, sont enfin présentés, commentés et analysés. / Modeling reactive transport of contaminants in porous media is a complex problem combining the difficulties of modeling the trasport with those of modeling the chemistry and especially the coupling between the two .This model leads to a system of partial differential equations and algebraic equations whose unknowns are the quantities of chemical species. One approach , already used elsewhere , is choosing the global DAE method : using the method of lines, discretization in space only, leads to a differential algebraic system (DAE ) to be solved by a suitable solver . In our case , the solver IDA Sundials relies on an implicit method, order is used but not variables, and requires at each time solving a large nonlinear system associated with a Jacobian matrix . This method is implemented in a software called GRT3D (Global Reactive Transport in 3D). This paper presents an improved GDAE method , from the standpoint of performance, the stability and robustness. We have enriched the possibilities of GRT3D , by taking full account of the equations of dissolution – precipitation for the appearance or disappearance of precipitated species. In addition to the study of the GDAE method, we also present a non-iterative sequential method ( SNIA ) which is a method based on the explicit Euler scheme : at each time step, we explicitly solve the transport equation and we use these calculations as data for the chemical system which is resolved in each cell independently. We also present a comparison between this method and GDAE approach . Numerical results for two test cases , one proposed by ANDRA ( 2D test case ) on one hand and one proposed by the group MOMAS ( Benchmark "easy case" ) on the other hand, are finally presented , discussed and analyzed.