Cette thèse s'inscrit dans le cadre de l'évolution des Systèmes d'Informations Géographiques (SIG) et de leur capacité à répondre à des problématiques environnementales qui s'expriment de manière globale et transversale. Dans un contexte ou l'information géographique est en plein essor et où la quantité de données disponible ne cesse de croitre, le besoin en terme d'outil d'aide a la décision n'a jamais été aussi fort. Cette étude s'attache tout particulièrement au cadre de la résolution de problématiques liées à l'eau et l'environnement lorsque les données deviennent trop volumineuses pour être traitées par des moyens de calculs séquentiels classiques. Nous proposons une plateforme de calculs répartis sur une grappe d'ordinateurs qui parallélise le calcul de la délimitation des bassins versants des grands fleuves et la détermination des flots d'accumulation. A cette fin nous introduisons une technique de calcul parallèle d'une forêt d'arbres couvrants minimums représentant le parcours de l'eau de chaque point du Modèle Numérique de Terrain (MNT) vers la mer. Cette technique débute par une délimitation des cuvettes (ensemble de points allant vers le même minimum local) contenues dans le MNT. Ensuite une hiérarchie de déversement des cuvettes les unes dans les autres est construite jusqu'à obtenir les bassins versants des fleuves. L'étude se poursuit par la description d'un algorithme parallèle pour le calcul très couteux des flots d'accumulation en chaque point du MNT. Enfin cette thèse présente une version ≪out-of-core≫ de nos algorithmes parallèles afin d'étendre la portée de nos travaux a des grappes de dimensions modestes qui ne peuvent pas charger en mémoire la totalité du MNT traite.

Cette thèse porte sur l'inférence de réseaux. Le cadre statistique naturel à ce genre de problèmes est celui des modèles graphiques, dans lesquels les relations de dépendance et d'indépendance conditionnelles vérifiées par une distribution multivariée sont représentées à l'aide d'un graphe. Il s'agit alors d'apprendre la structure du modèle à partir d'observations portant sur les sommets. Nous considérons le problème d'un point de vue bayésien. Nous avons également décidé de nous concentrer sur un sous-ensemble de graphes permettant d'effectuer l'inférence de manière exacte et efficace, à savoir celui des arbres couvrants. Il est en effet possible d'intégrer une fonction définie sur les arbres couvrants en un temps cubique par rapport au nombre de variables à la condition que cette fonction factorise selon les arêtes, et ce malgré le cardinal super-exponentiel de cet ensemble. En choisissant les distributions a priori sur la structure et les paramètres du modèle de manière appropriée, il est possible de tirer parti de ce résultat pour l'inférence de modèles graphiques arborescents. Nous proposons un cadre formel complet pour cette approche.Nous nous intéressons également au cas où les observations sont organisées en série temporelle. En faisant l'hypothèse que la structure du modèle graphique latent subit un certain nombre de brusques changements, le but est alors de retrouver le nombre et la position de ces points de rupture. Il s'agit donc d'un problème de segmentation. Sous certaines hypothèses de factorisation, l'exploration exhaustive de l'ensemble des segmentations est permise et, combinée aux résultats sur les arbres couvrants, permet d'obtenir, entre autres, la distribution a posteriori des points de ruptures en un temps polynomial à la fois par rapport au nombre de variables et à la longueur de la série. / In this dissertation we investigate the problem of network inference. The statistical frame- work tailored to this task is that of graphical models, in which the (in)dependence relation- ships satis ed by a multivariate distribution are represented through a graph. We consider the problem from a Bayesian perspective and focus on a subset of graphs making structure inference possible in an exact and e cient manner, namely spanning trees. Indeed, the integration of a function de ned on spanning trees can be performed with cubic complexity with respect to number of variables under some factorisation assumption on the edges, in spite of the super-exponential cardinality of this set. A careful choice of prior distributions on both graphs and distribution parameters allows to use this result for network inference in tree-structured graphical models, for which we provide a complete and formal framework.We also consider the situation in which observations are organised in a multivariate time- series. We assume that the underlying graph describing the dependence structure of the distribution is a ected by an unknown number of abrupt changes throughout time. Our goal is then to retrieve the number and locations of these change-points, therefore dealing with a segmentation problem. Using spanning trees and assuming that segments are inde- pendent from one another, we show that this can be achieved with polynomial complexity with respect to both the number of variables and the length of the series.

Maitriser les coûts de fabrication des circuits intégrés tout en augmentant leur densité est d'une importance primordiale pour maintenir une certaine rentabilité dans l’industrie du semi-conducteur. Parmi les différents composants d’un circuit, nous nous intéressons aux connections verticales et métalliques, connues sous le nom de « vias ». Durant la fabrication, un processus de lithographie complexe est utilisé pour former une disposition de vias est formée sur une plaque de silicium, à l’aide d’un un masque optique. Pour des raisons de fabrication, une distance minimum entre les vias doit être respectée. Lorsque cette distance n’est pas respectée, nous parlons de « conflit ». Afin de supprimer ces conflits, l’industrie utilise une technique qui permet de décomposer une disposition de vias cible en plusieurs sous-ensembles, où les contraintes de distance minimum sont respectées : la formation des sous-ensembles individuels se fait en séquence sur la plaque de silicium en utilisant un masque optique par sous-ensemble. Cette technique est appelée Multiple Patterning (MP). Il y a de nombreuses façons de décomposer une disposition de vias et le but est d’assigner les vias à un nombre minimum de masques, car les masques sont coûteux. Minimiser le nombre de masques est équivalent à minimiser le nombre de couleurs dans un graphe disque unitaire. Ce problème est NP-difficile, mais un certain nombre de « bonnes » heuristiques existent. Une technique récente et prometteuse basée sur l’auto-assemblage et direction des molécules, aussi connue sous le nom Directed Self Assembly (DSA), permet de grouper les vias en conflits à condition de respecter certaines contraintes. L’objectif est de trouver la meilleure façon de grouper les vias afin de minimiser le nombre de masques tout en respectant les contraintes liées à DSA. Ce problème est un problème de coloration de graphes où les sommets de chaque couleurs définissent un ensemble de chemins « indépendants » de longueurs au plus k que nous appelons aussi le problème de coloration par k-chemins. Durant la modélisation, nous avons distingué deux problèmes de coloration par k-chemins pertinents: le problème général et le problème induit. Les deux problèmes sont connus pour être NP-difficile, ce qui explique l’utilisation d’heuristiques dans l’industrie pour trouver une décomposition valide en sous-ensembles. Dans cette étude, nous nous intéressons à des méthodes exactes afin de concevoir des solutions optimales et d’évaluer la qualité de l’heuristique développée en industrie (chez Mentor Graphics). Nous présentons différentes méthodes: une approche par programmation linéaire en nombre entier (ILP) où nous étudions plusieurs formulations, une approche par programmation dynamique pour résoudre le cas induit quand k=1 ou k=2 et lorsque les graphes ont une petite longueur arborescente ; enfin, nous étudions le cas particulier des graphes lignes. Les résultats des différentes études numériques montrent que les formulations ILP « naïves » sont les meilleures. Elles listent tous les chemins possibles de longueur au plus k. Les tests sur des données industrielles ayant au plus 2000 sommets (plus grande composante connexe parmi celles qui constituent une instance) ont montré que les deux problèmes, général et induit, sont résolus en moins de 6 secondes, pour k=1 et k=2. La programmation dynamique, appliquée au problème induit de coloration par k-chemins quand k=1 et k=2, montre des résultats équivalents à ceux de la formulation ILP naïve. Cependant, nous nous attendons à de meilleurs résultats par programmation dynamique quand la valeur de k augmente. Enfin, nous montrons qu’un cas particuliers des graphes lignes peut être résolu en temps polynomial en exploitant les propriétés de l’algorithme d'Edmonds et des couplages dans les graphes bipartis. / Controlling the manufacturing costs of integrated circuits while increasing their density is of a paramount importance to maintain a certain degree of profitability in the semi-conductor industry. Among various components of a circuit, we are interested in vertical metallic connections known as “vias”. During manufacturing, a complex lithography process is used to form an arrangement of vias on a silicon wafer support, using an optical mask. For manufacturing reasons, a minimum distance between the vias must be respected. Whenever this is not the case, we are talking about a “conflict”. In order to eliminate these conflicts, the industry uses a technique that decomposes an arrangement of vias in several subsets, where minimum distance constraints are respected: the formation of the individual subsets is done, in sequence, on a silicon wafer using one optical mask per subset. This technique is called Multiple Patterning (MP). There are several ways to decompose an arrangement of vias, the goal being to assign the vias to a minimum number of masks, since the masks are expensive. Minimizing the number of masks is equivalent to minimizing the number of colors in a unit disk graph. This is a NP-hard problem however, a number of “good” heuristics exist. A recent and promising technique is based on the direction and self-assembly of the molecules called Directed Self Assembly (DSA), allows to group vias in conflict according to certain conditions. The main challenge is to find the best way of grouping vias to minimize the number of masks while respecting the constraints related to DSA. This problem is a graph coloring problem where the vertices within each color define a set of independent paths of length at most k also called a k-path coloring problem. During the graph modeling, we distinguished two k-path coloring problems: a general problem and an induced problem. Both problems are known to be NP-hard, which explains the use of heuristics in the industry to find a valid decomposition into subsets. In this study, we are interested in exact methods to design optimal solutions and evaluate the quality of heuristics developed in the industry (at Mentor Graphics). We present different methods: an integer linear programming (ILP) approach where we study several formulations, a dynamic programming approach to solve the induced case when k=1 or k=2 and when the graphs have small tree-width; finally, we study a particular case of line graphs. The results of the various numerical studies show that the naïve ILP formulations are the best, they list all possible paths of length at most k. Tests on a snippet of industrial instances of at most 2000 vertices (a largest connected component among those constituting an instance) have shown that the two problems, general and induced, are solved in less than 6 seconds, for k=1 and k=2. Dynamic programming, applied to the induced k-path coloring when k=1 and k=2, shows results equivalent to those of the naïve ILP formulation, but we expect better results by dynamic programming when the value of k increases. Finally, we show that the particular case of line graphs can be solved in polynomial time by exploiting the properties of Edmonds’ algorithm and bipartite matching.

Cette thèse est consacrée à l'étude des revêtements galoisiens et à la recherche du revêtement universel et du groupe fondamental pour les algèbres de dimension finie, connexes et basiques sur un corps algébriquement clos. Pour ce faire, nous partons d'une construction déjà existante: le groupe fondamental associé à toute présentation d'une telle algèbre A par son carquois ordinaire Q et des relations admissibles. Nous commençons par comparer les différentes présentations de A. Les automorphismes de l'algèbre kQ des chemins de Q permettent de relier deux présentations de A et parmi ceux-là, nous distinguons les dilatations et les transvections: elles engendrent le groupe des automorphismes de kQ, en outre, les groupes fondamentaux de deux présentations de A reliées par une dilatation ou une transvection sont liés entre eux par un passage au quotient. Ceci permet d'exhiber un groupe fondamental pour A lorsque le corps de base est de caractéristique nulle et lorsque Q n'a pas de double raccourci. Ces raisonnements se transposent à l'étude des revêtements galoisiens de A puisqu'à chaque présentation de A est associé un revêtement galoisien de A et de groupe le groupe fondamental de la présentation. Ainsi, sous les hypothèses précédentes fournissant le groupe fondamental de A, un revêtement universel de A existe. Ce dernier résultat est également démontré pour un corps de caractéristique quelconque, lorsque A est monomiale et lorsque Q n'a ni flèches multiples ni cycle orienté tout en admettant d'éventuels double raccourcis.

On s'attache dans cette thèse à plusieurs aspects liés à la résolution de problèmes multi-objectifs, sans se limiter au cas biobjectif. Nous considérons la résolution exacte, dans le sens de la détermination de l'ensemble des points non dominés, ainsi que la résolution approchée dans laquelle on cherche une approximation de cet ensemble dont la qualité est garantie a priori.Nous nous intéressons d'abord au problème de la détermination d'une représentation explicite de la région de recherche. La région de recherche, étant donné un ensemble de points réalisables connus, exclut la partie de l'espace des objectifs que dominent ces points et constitue donc la partie de l'espace des objectifs où les efforts futurs doivent être concentrés dans la perspective de déterminer tous les points non dominés.Puis nous considérons le recours aux algorithmes de séparation et évaluation ainsi qu'aux algorithmes de ranking afin de proposer une nouvelle méthode hybride de détermination de l'ensemble des points non dominés. Nous montrons que celle-ci peut également servir à obtenir une approximation de l'ensemble des points non dominés. Cette méthode est implantée pour le problème de l'arbre couvrant de poids minimal. Les quelques propriétés de ce problème que nous passons en revue nous permettent de spécialiser certaines procédures et d'intégrer des prétraitements spécifiques. L'intérêt de cette approche est alors soutenu à l'aide de résultats expérimentaux. / This thesis deals with several aspects related to solving multi-objective problems, without restriction to the bi-objective case. We consider exact solving, which generates the nondominated set, and approximate solving, which computes an approximation of the nondominated set with a priori guarantee on the quality.We first consider the determination of an explicit representation of the search region. The search region, defined with respect to a set of known feasible points, excludes from the objective space the part which is dominated by these points. Future efforts to find all nondominated points should therefore be concentrated on the search region.Then we review branch and bound and ranking algorithms and we propose a new hybrid approach for the determination of the nondominated set. We show how the proposed method can be adapted to generate an approximation of the nondominated set. This approach is instantiated on the minimum spanning tree problem. We review several properties of this problem which enable us to specialize some procedures of the proposed approach and integrate specific preprocessing rules. This approach is finally supported through experimental results.

Un système couvrant est un ensemble fini de progressions arithmétiques avec la propriété que chaque entier appartient à au moins une des progressions. L’étude des systèmes couvrants a été initié par Erdős dans les années 1950, et il posa dans les années qui suivirent plusieurs questions sur ces objets mathématiques. Une de ses questions les plus célèbres est celle du plus petit module : est-ce que le plus petit module de tous les systèmes couvrants avec modules distinct est borné uniformément? En 2015, Hough a montré que la réponse était affirmative, et qu’une borne admissible est 1016. En se basant sur son travail, mais en simplifiant la méthode, Balister, Bollobás, Morris, Sahasrabudhe et Tiba on réduit cette borne a 616, 000. Leur méthode a menée a plusieurs applications supplémentaires. Entre autres, ils ont compté le nombre de système couvrant avec un nombre fixe de module. La première partie de ce mémoire vise a étudier une question similaire. Nous allons essayer de compter le nombre de système couvrant avec un ensemble de module fixé. La technique que nous utiliserons nous mènera vers l’étude des symmétries de système couvrant. Dans la seconde partie, nous répondrons à des variantes du problème du plus petit module. Nous regarderons des bornes sur le plus petit module d’un système couvrant de multiplicité s, c’est-à-dire un système couvrant dans lequel chaque module apparait au plus s fois. Nous utiliserons ensuite ce résultat afin montrer que le plus petit module d’un système couvrant de multiplicité 1 d’une progression arithmétique est borné, ainsi que pour montrer que le n-eme plus petit module dans un système couvrant de multiplicité 1 est borné. / A covering system is a finite set of arithmetic progressions with the property that every integer belongs to at least one of them. The study of covering systems was started by Erdős in the 1950’s, and he asked many questions about them in the following years. One of the most famous questions he asked was if the minimum modulus of a covering system with distinct moduli is bounded uniformly. In 2015, Hough showed that it is at most 1016. Following on his work, but simplifying the method, Balister, Bollobás, Morris, Sahasrabudhe and Tiba showed that it is at most 616, 000. Their method led them to many further applications. Notably, they counted the number of covering systems with a fixed number of moduli. The first part of this thesis seeks to study a related question, that is to count the number of covering systems with a given set of moduli. The technique developped to do this for some sets will lead us to look at symmetries of covering systems. The second part of this thesis will look at variants of the minimum modulus problem. Notably, we will be looking at bounds on the minimum modulus of a covering system of multiplicity s, that is a covering system in which each moduli appears at most s times, as well as bounds on the minimum modulus of a covering system of multiplicity 1 of an arithmetic progression, and finally look at bounds for the n-th smallest modulus in a covering system.