Дисертації з теми "Problèmes paramétrés"

Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courtschemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multidimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes. Nous montrons la décidabilité et la complexité du problème quel que soit le nombre de paramètres et de dimensions lorsque les paramètres prennent des valeurs entières. Nous montrons également l’indécidabilité de ce problème avec au moins un paramètre lorsque la dimension est supérieure ou égale à deux. Nous étudions enfin des jeux de parité à un et deux joueurs sur les graphes paramétrés dont l’objectif est la conjonction d’une condition qualitative sur la parité et d’une condition quantitative : l’énergiedoit rester positive. Nous montrons la décidabilité et prouvons des bornes de la complexité du problème de la recherche d’une stratégie gagnante dans les cas à un et à deux joueurs
We are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We alsoprove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study paritygames on parametrized graphs with one and two players whose objective is the conjunction of a qualitative condition on the parity andquantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searchinga winning strategy in both cases with one and two players

Cette thèse s'intéresse à la question récurrente qu'est la résolution d'un problème pour un grand nombre de configurations différentes. Malgré l'augmentation constante de la puissance de calcul que l'on connait aujourd'hui, le traitement direct d'un tel problème reste souvent hors de portée. La technique qui est développée ici est basée sur l'utilisation de la Proper Generalized Decomposition (PGD) dans le cadre de la méthode LATIN. On étudie tout d'abord la capacité de cette technique de réduction de modèle à résoudre un problème paramétré pour un espace de conception donné. Lors du traitement d'un tel problème, on génère une base réduite que l'on peut réutiliser et éventuellement enrichir en traitant un par un les problèmes correspondants aux jeux de paramètres étudiés. Le but devient alors de développer une stratégie, inspirée par la méthode " Reduced Basis ", afin d'explorer de façon rationnelle l'espace des paramètres. L'objectif étant de construire, avec le minimum de résolutions, une base réduite " complète " qui permet de résoudre tous les autres problèmes de l'espace de conception sans enrichir cette base. On commence dès lors par montrer l'existence d'une telle base complète en extrayant les informations les plus pertinentes des solutions PGD d'un problème pour tous les jeux de paramètres de l'espace de conception. On propose ensuite une stratégie rationnelle pour construire cette base complète sans la nécessité préalable de la résolution du problème pour tous les jeux de paramètres. Enfin, les performances de la méthode proposée sont illustrées sur plusieurs exemples, montrant des gains conséquents lorsque des études récurrentes doivent être menées.

Dans les phases de conception, d'optimisation ou de maintenance prédictive, les ingénieurs sont amenés à tester diverses configurations de chargement, de géométrie ou de propriétés matériaux pour construire des métamodèles, effectuer des analyses de sensibilité ou ajuster des paramètres incertains. Pour ce faire, des appels répétés à des modèles numériques sont requis afin de résoudre un grand nombre de problèmes physiques semblables. Cependant, une telle démarche peut entraîner un coût de calcul prohibitif, surtout dans un cadre multiphysique --- au cœur des études réalisées aujourd'hui dans les industries de pointe. En effet, chaque simulation comporte alors des millions de degrés de liberté, et doit intégrer plusieurs physiques ainsi que leurs interactions mutuelles. Dans ce contexte, cette thèse propose une stratégie de calcul performante pour résoudre de nombreux problèmes multiphysiques similaires. La stratégie développée repose sur l'association de la méthode LATIN-PGD et d'un processus d'initialisation qui tire partie des calculs précédemment réalisés pour aborder un nouveau jeu de paramètres. En particulier, une base réduite est construite indépendamment pour chaque physique ; chacune de ces bases est réutilisée et enrichie au fil des calculs lorsque cela s'avère nécessaire. Les performances de la méthode sont illustrées sur un cas test thermo-mécanique fortement couplé de taille représentative. Une étude paramétrique complète, comportant une centaine de résolutions, est accélérée d'un facteur 5 par rapport à une application naïve de la méthode LATIN-PGD, et d'un facteur 45 comparé à une approche monolithique classique
During design, optimization or predictive maintenance stages, engineers need to test various configurations of loading, geometry or material properties in order to build metamodels, perform sensitivity analyses or adjust uncertain parameters. Repeated calls to numerical models are then required to solve numerous related physical problems. However, such an approach can lead to prohibitive computational costs, especially in a multiphysics framework, which is a major focus of today's studies in cutting-edge industries. Indeed, each simulation involves millions of degrees of freedom, and must encompass several physics and their mutual interactions. In this context, this thesis proposes a computational strategy for efficiently solving many similar multiphysics problems. The developed approach is based on the combination of the LATIN-PGD solver and an initialization procedure that takes advantage of previously performed calculations to tackle a new set of parameters. More specifically, a reduced-order basis is built independently for each physics; each basis is then reused and enriched throughout the calculations when deemed necessary. The performances of the method are illustrated on a test case of representative size involving a strong thermo-mechanical coupling. A complete parametric study, involving around a hundred resolutions, is accelerated by a factor of 5 compared with a naive application of the LATIN-PGD method, and by a factor of 45 in comparison with a conventional monolithic approach

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.

Cette thèse porte sur la conception des méthodes robustes de réduction d’ordre de modèles numériques de type Éléments Finis (EF) avec contrôle de la précision. La réduction d’ordre est en général nécessaire pour réduire drastiquement les temps de calcul et permettre ainsi une analyse paramétrique, une étude de faisabilité ou de performance de système (avion, unité de production, procédé complexe, etc). Dans cette étude, la technique de décomposition orthogonale aux valeurs propres (POD) sera utilisée pour construire des modèles réduits locaux. Informatiquement parlant, le “modèle” sera considéré comme une base de données de résultats de calcul avec capacité d’extrapolation et d’interpolation locale. Une stratégie adaptative pour stocker et accéder à la base de données est étudiée en étendant l’algorithme In situ Adaptive Tabulation (ISAT) proposé initialement par Pope. En fonction de l’usage et des exigences en précision des résultats, la base de données est enrichie en ligne (online) par des appels au modèle fin en respectant une précision spécifiée jusqu’à couvrir le domaine paramétrique entier, après quoi l’évaluation d’une solution devient très peu couteuse. L’approche couplée POD-ISAT proposée dans cette thèse fournit une méthode de réduction de modèle EF très performante. La méthodologie est évaluée sur un cas réel de conditionnement d’air en régime stationnaire de cabine d’avion dépendant de plusieurs paramètres de conception (température et vitesse d’entrée d’air, mode de ventilation personnalisée, conductivité thermique du fuselage, etc.). Pour les problèmes d’évolution en temps, nous explorons une piste de chainage de modèles et d’utilisation d’algorithme de parallélisation en temps tel que l’algorithme pararéel initialement proposé par Lions, Maday et Turinici (2001). Nous proposons ici une variante quasi-Newton de l’algorithme pararéel que nous appelons algorithme Broyden-pararéel. Il est appliqué au calcul de la diffusion d’un gaz dans la cabine d’avion. Cette thèse s’insère dans le cadre du projet CSDL (Complex System Design Lab, Fond Unique Interministériel) visant à développer une plate-forme logicielle multidisciplinaire pour la conception de systèmes complexes
In this thesis, an efficient Reduced Order Modeling (ROM) technique with control of accuracy for parameterized Finite Element solutions is proposed. The ROM methodology is usually necessary to drastically reduce the computational time and allow for tasks like parameter analysis, system performance assessment (aircraft, complex process, etc.). In this thesis, a ROM using Proper Orthogonal Decomposition (POD) will be used to build local models. The “model” will be considered as a database of simulation results store and retrieve the database is studied by extending the algorithm In Situ Adaptive Tabulation (ISAT) originally proposed by Pope (1997). Depending on the use and the accuracy requirements, the database is enriched in situ (i.e. online) by call of the fine (reference) model and construction of a local model with an accuracy region in the parameter space. Once the trust regions cover the whole parameter domain, the computational cost of a solution becomes inexpensive. The coupled POD-ISAT, here proposed, provides a promising effective ROM approach for parametric finite element model. POD is used for the low-order representation of the spatial fields and ISAT for the local representation of the solution in the design parameter space. This method is tested on a Engineering case of stationary air flow in an aircraft cabin. This is a coupled fluid-thermal problem depending on several design parameters (inflow temperature, inflow velocity, fuselage thermal conductivity, etc.). For evolution problems, we explore the use of time-parallel strategies, namely the parareal algorithm originally proposed by Lions, Maday and Turinici (2001). A quasi-Newton variant of the algorithm called Broyden-parareal algorithm is here proposed. It is applied to the computation of the gas diffusion in an aircraft cabin. This thesis is part of the project CSDL (Complex System Design Lab) funded by FUI (Fond Unique Interministériel) aimed at providing a software platform for multidisciplinary design of complex systems

Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérir
In this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer

Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérir
In this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer

Afin de mieux comprendre le fonctionnement d'un système biologique, il est nécessaire d'étudier les différentes entités qui le composent. Pour cela, on peut modéliser ces interactions biologiques sous la forme de graphes. Pour certains de ces graphes, les sommets sont colorés afin d'apporter une information supplémentaire sur la couleur qui leur est associée. Dans ce cadre, une problématique courante consiste à y rechercher un sous-graphe d'intérêt appelé motif. Dans la première partie de ce manuscrit, on présente un état de l'art d'un point de vue algorithmique sur le problème GRAPH MOTIF, qui consiste à rechercher des motifs dits fonctionnels dans ce type de graphes. La modélisation de systèmes biologiques sous la forme de graphes peut également être appliquée em spectrométrie de masse. Ainsi, on introduit le problème MAXIMUM COLORFUL ARBORESCENCE (MCA) dans le but de déterminer de novo la formule moléculaire de métabolites inconnus. Dans la deuxième partie de ce manuscrit, on réalise une étude algorithmique du problème MCA. Alors que MCA est algorithmiquement difficile à résoudre même dans des classes de graphes très contraintes, notre modélisation nous permet notamment d'obtenir de nouveaux algorithmes d'approximation dans ces mêmes classes, ainsi que de déterminer une nouvelle classe de graphes dans laquelle MCA se résout en temps polynomial. On montre également des résultats de complexité paramétrée pour ce problème, que l'on compare ensuite à ceux de la littérature sur des instances issues de données biologiques
Ln order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To this aim, these biological interactions can be modelled in the form of graphs. ln some of these graphs, the vertices are colored in order to provide additional information on the entity which is associated with them. ln this context, a common subproblem consists in searching for a subgraph of interest, called a motif, in these graphs. ln the first part of this manuscript, we present a state of the art from an algorithmical point of view of the GRAPH MOTIF problem, which consists in searching for so-called functional motifs in vertex-colored graphs. The modeling of biological systems in graphs form can also be applied in mass spectrometry. Thus, we introduce the MAXIMUM COLORFUL ARBORESCENCE problem (MCA) in order to de novo determine the molecular formula of unknown metabolites. ln the second part of this manuscript, we carry out an algorithmic study of the MCA problem. While MCA is algorithmically difficult to solve even in very constrained graph classes, our modeling allows us to obtain new approximation algorithms in these same classes, as well as to determine a new graph class in which MCA is solved in polynomial time. Parameterized complexity results for this problem are also shown, which are then compared to those in the literature on instances from biological data

Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.

Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement, étant impossible d'écarter les puces défectueuses sans découper la plaque de silice, le problème de la superposition d'une puce viable avec une puce défectueuse se pose. Une pile de puces, étant considérées comme défectueuse si elle contient ne serait-ce qu'une puce défectueuse, la superposition non réfléchie des wafers entre eux mènerait à un rendement désastreux.Afin de générer un nombre minimum de piles défectueuses, une "cartographie" de chaque wafer candidat à la superposition est réalisée lors d'une phase de test, permettant de situer les puces défectueuses sur le wafer. Une fois cette cartographie réalisée, l'objectif est de sélectionner les wafers qui seront assemblés ensembles de manière à faire correspondre les défauts de chacun des wafers.Ce problème peut être modélisé à l'aide d'un problème d'affectation multidimensionnelle. Chaque wafer est représenté par un vecteur comportant autant de composantes que de puces sur le wafer qu'il représente. Une composante égale à zéro matérialise une puce défectueuse tandis qu'un un matérialise une puce viable. Chaque lot de wafers est représenté par un lot de vecteurs. Formellement, une instance d'empilement de wafers est représenté par m ensembles de n vecteurs binaires p-dimensionnels. L'objectif est alors de réaliser n m-uplets disjoints contenant exactement un vecteur par ensemble. Ces m-uplets représenteront les piles. Chaque m-uplet peut être représenté par un vecteur binaire p-dimensionnels, chaque composante étant calculée en réalisant le ET binaire des composantes correspondantes des vecteurs qui composent le m-uplet. Autrement dit, une composante du vecteur représentant le m-uplet est égale à un si et seulement si tous les vecteurs ont cette composante égale à un. Et donc une pile de puces est viables si toutes les puces qui la composent sont viables. L'objectif est alors de minimiser le nombre de zéros ou de maximiser le nombre de un.La thèse comporte deux grandes parties. Une partie théorique abordant la complexité des différentes versions du problèmes en fonction de certains paramètres tels que m, n, p ou encore le nombre maximum de zéros par vecteurs. Nous montrons entre autre que ces problèmes peuvent être utilisés pour modéliser des problèmes plus classiques tels que Maximum Clique, Minimum Vertex Cover ou encore k-Dimensional Matching, permettant de prouver un certain nombre de résultats négatifs que ce soit d'un point de vue de la complexité classique, l'approximabilité ou la complexité paramétrée. Nous fournissons également des résultats positifs pour des cas particuliers du problème.Dans un second temps, nous nous intéressons à la résolution pratique du problème en fournissant et comparant un certain nombre de formulations en Programmation Linéaire en Nombres Entiers. Mais nous nous intéressons également aux performances en pratique de certaines heuristiques à garantie de performances détaillées dans la partie théorique
In this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part

La modélisation des procédés de mise en forme de composites est confrontée à de nombreux verrous scientifiques malgré les avancées récentes en matière de modélisation mécanique, analyse numérique, stratégies de discrétisation et capacité de calcul. En effet, la mise en forme de composites est confrontée à la nécessité de la prise en compte des comportements non-linéaires anisotropes et fortement couplés, définis dans des géométries très complexes. De plus, l'optimisation des procédés ainsi que l'identification par calcul inverse nécessite de multiples résolutions du problème direct. Dans ce contexte les techniques de réduction de modèles offrent de nouvelles possibilités, permettant d'accélérer les calculs de quelques ordres de magnitude, et même de résoudre des modèles jamais résolus jusqu'à présent. La "Proper Generalized Decomposition" ou PGD est une des trois grandes familles des méthodes de réduction de modèles, susceptible de constituer un changement de paradigme en mécanique numérique. En effet, la PGD permet de résoudre des problèmes multidimensionnels résultants de l'introduction de paramètres physiques ou de conformation tout en évitant la malédiction de la dimensionnalité. Dans ce travail, on utilise la PGD pour adresser la solution de problèmes thermiques rencontrés lors de la mise en forme des composites. De plus, une approche de calcul "off-line/on-line" pour l'optimisation et le contrôle en temps réel est proposée. En effet, la PGD est utilisée pour calculer "off-line" des solutions paramétriques, exploitées ensuite "on-line" sur des plateformes de calcul légères (Smartphones ou tablettes).

De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah
Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah

Notre première partie correspond à un besoin exprimé par le commissariat à l'énergie atomique, et relatif à la construction d'un système de stockage de déchets. Celui-ci est constitué d'un dispositif, dit module de stockage, avec une répartition périodique des puits et des galeries. Les puits et les galeries sont comblés par des remblais dont la perméabilité optimale est recherchée, de manière à limiter les circulations d'eau et les possibilités de fuite résiduelle de radioéléments. Les excavations constituent alors des drains qui orientent vers eux les circulations d'eau dans le massif. Les paramètres caractéristiques du problème sont la taille de la période, le rapport entre la hauteur du matériau et la taille de la période, et le rapport des perméabilités des matériaux en présence. Nous étudions différents types de structures, et nous envisageons différents passages à la limite en fonction des valeurs relatives de ces trois paramètres. Dans notre seconde partie, nous étudions un problème d'évolution défini sur une plaque mince perforée périodiquement. Les paramètres caractéristiques du problème sont l'épaisseur de la plaque, la période des perforations et le rapport entre cette période et les barres qui constituent le matériau. Nous faisons tendre ces trois paramètres vers zéro, et nous donnons les coefficients du matériau limite obtenu. En particulier, on montre que les barres qui ne traversent pas entièrement la frontière ne jouent aucun rôle
The first part of this work meets requirements of the C. E. A. It concerns the construction of a device assigned to the stocking of radioactive waste. This one is constituted with tunnels and wells, that are periodically distributed. Tunnels and wells are impacted in filling material, for which an optimal permeability is inquired, in the hope of limiting water infiltration and leak of radioactive material. Then, excavations constitute drains which angle water infiltration towards themselves. Characteristic parameters of the problems are the period (epsilon), the ratio between the altitude of the device and the period (delta), and the ratio between the permeabilities of the two materials (êta). We study several kind of structures, and we pass to the limit in different orders according to the relative size of the different parameters. In the second part, we study an evolution an evoltion problem defined on a perforated thin plate. Characteristic parameters of the problem are the thickness of the plate, the period of the holes, and the ratio between this period and the thickness of the bars. We make these three parameters tend towards zero, and we give the coefficients of the limit material. In particular, we show that bars which do not completely cross the period have no role

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux
The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms

Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps $2^{O(plog p)}n^{O(1)}$.Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la compétitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus k
We study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1

Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.

De nos jours, nous sommes entourés de systèmes critiques complexes tels que les microprocesseurs, les trains, les appareils intelligents, les robots, les avions, etc. Ces systèmes sont extrêmement complexes et critiques en termes de sûreté, et doivent donc être vérifiés et validés. L'utilisation de méthodes formelles à états s'est avérée efficace pour concevoir des systèmes complexes. Event-B a joué un rôle clé dans le développement de tels systèmes. Event-B est une méthode formelle de conception de systèmes à états avec une approche correcte par construction, qui met l'accent sur la preuve et le raffinement. Event-B facilite la vérification de propriétés telles que la préservation des invariants, la convergence et le raffinement en générant des obligations de preuve et en permettant de les décharger.Certaines propriétés additionnelles du système, telles que l'absence d'inter-blocage, l'atteignabilité ou encore la vivacité, doivent être explicitement encodées et vérifiées par le concepteur, ou formalisées à l'aide d'une autre méthode formelle. Une telle approche pénalise la réutilisabilité des modèles et des techniques, et peut introduire des erreurs, en particulier dans les systèmes complexes.Pour pallier cela, nous avons introduit un "framework" réflexif EB4EB, formalisé au sein de Event-B. Dans ce cadre, chacun des concepts d'Event-B est formalisé comme un objet de première classe en utilisant la logique du premier ordre (FOL) et la théorie des ensembles. EB4EB permet la manipulation et l'analyse de modèles Event-B, et permet la définition d'extensions afin de réaliser des analyses supplémentaires non intrusives sur des modèles, telles que la validation de propriétés temporelles, l'analyse de la couverture d'un invariant, ou encore l'absence de blocage. Ce framework est réalisé grâce aux théories d'Event-B, qui étendent le langage d'Event-B avec des éléments définis dans des théories, et aussi en formalisant de nouvelles obligations de preuves, qui ne sont pas présentes initialement dans Event-B.De plus, la sémantique opérationnelle d'Event-B (basée sur les traces) a été formalisée, de même qu'un cadre qui sert à garantir la correction des théorèmes définis, y compris les opérateurs et les obligations de preuve. Enfin, le cadre proposé et ses extensions ont été validés dans de multiples études de cas, notamment l'horloge de Lamport, le problème du lecteur/rédacteur, l'algorithme de Peterson, les distributeurs automatiques de billets (DAB), les véhicules autonomes, etc
Nowadays, we are surrounded by complex critical systems such as microprocessors, railways, home appliances, robots, aeroplanes, and so on. These systems are extremely complex and are safety-critical, and they must be verified and validated. The use of state-based formal methods has proven to be effective in designing complex systems. Event-B has played a key role in the development of such systems. Event-B is a formal system design method that is state-based and correct-by-construction, with a focus on proof and refinement. Event-B facilitates verification of properties such as invariant preservation, convergence, and refinement by generating and discharging proof obligations.Additional properties for system verification, such as deadlock-freeness, reachability, and liveness, must be explicitly defined and verified by the designer or formalised using another formal method. Such an approach reduces re-usability and may introduce errors, particularly in complex systems.To tackle these challenges, we introduced the reflexive EB4EB framework in Event-B. In this framework, each Event-B concept is formalised as a first-class object using First Order Logic (FOL) and set theory. This framework allows for the manipulation and analysis of Event-B models, with extensions for additional, non-intrusive analyses such as temporal properties, weak invariants, deadlock freeness, and so on. This is accomplished through Event-B Theories, which extend the Event-B language with the theory's defined elements, and also by formalising and articulating new proof obligations that are not present in traditional Event-B. Furthermore, Event-B's operational semantics (based on traces) have been formalised, along with a framework for guaranteeing the soundness of the defined theorems, including operators and proof obligations. Finally, the proposed framework and its extensions have been validated across multiple case studies, including Lamport's clock case study, read/write processes, the Peterson algorithm, Automated Teller Machine (ATM), autonomous vehicles, and so on

Les outils UML intégrant le support de l’utilisation des patrons de conception doivent permettent une mise en œuvre correcte des solutions de patrons, sans remettre en cause la cohérence des modèles UML. Ils doivent permettre aussi de vérifier que les solutions des patrons appliqués résolvent réellement les problèmes de conception auxquels ces solutions sont destinées et que les contextes d’application ne contrarient pas les principes de conception que ces solutions utilisent pour résoudre les problèmes. Nous nous intéressons dans cette thèse aux aspects ‘‘solution’’ et ‘‘problème’’ des patrons de conception. Nous proposons un ensemble de contraintes et de transformations permettant : i) une intégration correcte et cohérente des solutions de patrons dans les modèles UML. Ii) spécifier la partie des problèmes de conception liés au couplage des patrons de conception GOF. Nous utilisons l’ensemble de contraintes et de transformations obtenues sous forme d’une extension au standard UML.

Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielle
The problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied

Cette thèse porte sur la théorie de Galois différentielle. Elle est divisée en deux parties. La première concerne la théorie de Galois différentielle paramétrée, et la seconde, les équations aux q-différences. Dans le chapitre 2, nous exposons une généralisation de l'algorithme de Kovacic qui permet de calculer le groupe de Galois paramétré de certaines équations différentielles paramétrées d'ordre 2. Dans le chapitre 3, nous présentons une généralisation du théorème de densité de Ramis qui donne un ensemble de générateurs topologiques du groupe de Galois pour les équations différentielles linéaires paramétrées à coefficients dans un anneau convenable. Nous obtenons une contribution au problème inverse dans cette théorie de Galois, donnons un critère d'isomonodromie, et répondons partiellement à une question posée par Sibuya. Dans le chapitre 4, il est question de confluence et d'équations aux q-différences. Nous prouvons comment la transformée de Borel-Laplace d'une série formelle divergente solution d'une équation différentielle linéaire à coefficients dans C(z) peut être uniformément approchée par un q-analogue de la transformée de Borel-Laplace appliqué à une série formelle solution d'une famille d'équations aux q-différences linéaires qui discrétise l'équation différentielle. Nous faisons directement les calculs dans le cas des séries hypergéométriques basiques, et nous prouvons sous des hypothèses raisonnables, qu'une matrice fondamentale d'une équation différentielle linéaire à coefficients dans C(z) peut être uniformément approchée par une matrice fondamentale d'une famille d'équations aux q-différences linéaires correspondante.

Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s'est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l'intérêt pratique n'est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communautés en fournissant des méthodes polynomiales pour tester automatiquement l'appartenance d'une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu'ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteuses
The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results

Un problème courant en logistique, gestion d’entrepôt, industrie manufacturière ou gestion d’énergie dans les centres de données est de placer des objets dans un espace limité, ou conteneur. Ce problème est appelé problème de placement. De nombreux travaux dans la littérature gèrent le problème de placement en considérant des objets de formes particulières ou en effectuant des approximations polygonales. L’objectif de cette thèse est d’autoriser toute forme qui admet une définition mathématique (que ce soit avec des inégalités algébriques ou des fonctions paramétrées). Les objets peuvent notamment être courbes et non-convexes. C’est ce que nous appelons le problème de placement générique. Nous proposons un cadre de résolution pour résoudre ce problème de placement générique, basé sur les techniques d’intervalles. Ce cadre possède trois ingrédients essentiels : un algorithme évolutionnaire plaçant les objets, une fonction de chevauchement minimisée par cet algorithme évolutionnaire (coût de violation), et une région de chevauchement qui représente un ensemble pré-calculé des configurations relatives d’un objet (par rapport à un autre) qui créent un chevauchement. Cette région de chevauchement est calculée de façon numérique et distinctement pour chaque paire d’objets. L’algorithme sous-jacent dépend également du fait qu’un objet soit représenté par des inégalités ou des fonctions paramétrées. Des expérimentations préliminaires permettent de valider l’approche et d’en montrer le potentiel
A common problem in logistic, warehousing, industrial manufacture, newspaper paging or energy management in data centers is to allocate items in a given enclosing space or container. This is called a packing problem. Many works in the literature handle the packing problem by considering specific shapes or using polygonal approximations. The goal of this thesis is to allow arbitrary shapes, as long as they can be described mathematically (by an algebraic equation or a parametric function). In particular, the shapes can be curved and non-convex. This is what we call the generic packing problem. We propose a framework for solving this generic packing problem, based on interval techniques. The main ingredients of this framework are: An evolutionary algorithm to place the objects, an over lapping function to be minimized by the evolutionary algorithm (violation cost), and an overlapping region that represents a pre-calculated set of all the relative configurations of one object (with respect to the other one) that creates an overlapping. This overlapping region is calculated numerically and distinctly for each pair of objects. The underlying algorithm also depends whether objects are described by inequalities or parametric curves. Preliminary experiments validate the approach and show the potential of this framework

Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.