Notre mémoire se penche sur un corpus de films spécifique; il s’agit des westerns américains racontant la construction d’un chemin de fer. Nous traitons ces films comme un sous-genre du western que nous intitulons Railroad Building Story. Est proposé dans notre étude que la structure narrative étant à la base de tous les récits du sous-genre provient d’une idéalisation des faits historiques entourant la construction du premier chemin de fer transcontinental aux États-Unis. Dans le premier chapitre, nous présentons une adaptation de la méthode d’analyse de Vladimir Propp, telle que présentée dans la Morphologie du conte, dans le but d’identifier la structure narrative stable des films du corpus et d’en décrire les unités narratives constantes. L’application de la méthode est effectuée dans le second chapitre, où chacune des unités narratives constantes est expliquée. De plus, nous confrontons ces unités narratives à l’histoire du chemin de fer transcontinental afin d’analyser les rapports idéologiques existant entre ces récits fictionnels et leur référent historique. Cette description sémionarrative et historique de la Railroad Building Story met en évidence sa fonction idéologique permanente en tant que mythe cinématographique du chemin de fer américain. Dans le troisième chapitre, les films sont analysés d’après leur contexte sociohistorique de production. Le chapitre est divisé selon les quatre périodes historiques dans lesquels les films du sous-genre furent réalisés, soit les années 1920, la Grande Dépression, l’ère maccarthyste et le début des années 1960. En analysant les films d’après une approche sociocritique, nous démontrons comment ceux-ci traduisent des préoccupations idéologiques liées au climat social de la nation américaine. Nous expliquons donc comment le mythe du chemin de fer américain se voit réapproprié à chaque période historique, et ce, afin de répondre aux exigences idéologiques contemporaines à la production des films de la Railroad Building Story. / This master’s thesis takes a close look at a very specific corpus of films; the westerns that narrate the construction of a railroad. We treat these movies as a sub-genre of the western that we call the Railroad Building Story. Our study proposes that the narrative structure at the basis of all the sub-genre’s stories comes from an idealization of the historical facts surrounding the construction of the first American transcontinental railroad. In the first chapter, we present an adaptation of Vladimir Propp’s method of analysis, as found in his Morphology of the Folktale, in order to identify the stable narrative structure of our corpus and to describe its constant narrative units. The application of said method takes place in the second chapter, in which each constant narrative unit is thoroughly explained. We also confront these narrative units in the history of the transcontinental railroad as to analyze the ideological relations existing between these fictional narratives and their historical referent. This semionarrative and historical description of the Railroad Building Story highlights its permanent ideological function as the cinematographic myth of the American railroad. In our third chapter, we analyze the films in the light of their sociohistorical context of production. The chapter is divided between the four historical periods in which these movies were produced, that to say the 1920’s, the Great Depression, the mcccarthyism era and the early 1960’s. By analyzing these films with a sociocritical stance, we demonstrate how they express ideological concerns linked to the social climate of the American nation. Thus we explain how the American railroad myth is being reappropriated in each historical period in order to address the ideological exigencies that are contemporary to the production of the Railroad Building Story’s films.

Ce travail, à la frontière de l’analyse et des probabilités, s’intéresse à l’étude de systèmes différentiels a priori mal posés. Nous cherchons, grâce à des techniques issues de la théorie des chemins rugueux et de l’étude trajectorielle des processus stochastiques, à donner un sens à de tels systèmes puis à les résoudre, tout en montrant que les notions proposées ici étendent bien les notions classiques de solutions. Cette thèse se décompose en trois chapitres. Le premier traite des systèmes différentiels ordinaires perturbés additivement par des processus irréguliers éventuellement stochastiques ainsi que des effets de régularisation de tels processus. Le deuxième chapitre concerne l’équation de transport linéaire perturbée multiplicativement par des chemins rugueux ; enfin, le dernier chapitre s’intéresse à une équation de la chaleur non linéaire perturbée par un bruit blanc espace-temps, l’équation de quantisation stochastique phi4 en dimension 3. / In this work we investigate a priori ill-posed differential systems from an analytic and probabilistic point of view. Thanks to technics inspired by the rough path theory and pathwise study of stochastic processes, we want to define those ill-posed systems and then study them. The first chapter of this thesis is related to ordinary differential equations perturbed by some irregular (stochastic) processes and the effects induced by the regularization of such processes. The second chapter deals with the linear transport equation multiplicatively perturbed by a rough path. Finally, in the last chapter we investigate the stochastic quantization equation Phi4 in three dimensions.

L’objectif de cette thèse est d’analyser les contributions de Clément Colson à la science économique dans le but de mieux connaître sa pensée, de mieux connaître l’École libérale française au début du XXème siècle, d’étudier l’influence qu’a pu avoir cet auteur sur ses principaux élèves, Divisia, Roy et Rueff, et d’évaluer l’actualité de certaines de ses recommandations.Le premier chapitre montre quels sont les apports théoriques de Colson à la science économique.Pour ses élèves, son principal apport serait la théorie de la détermination conjointe du salaire et du taux d’intérêt. Nous montrerons que cette théorie est proche de la règle de gestion optimale en microéconomie attribuée à Clark ; nous verrons alors que l’on peut parler de découverte multiple.Colson est également intéressant au point de vue de la méthode utilisée. Nous verrons alors qu’il utilise les statistiques et les mathématiques dans ses développements : il est à l’origine d’une évaluation pionnière du revenu de la France, son enseignement impulse le calcul économique, il peut être considéré comme un précurseur de l’économétrie en France. Le deuxième chapitre montre que Colson développe la méthode de tarification des voies de communication exploitées en monopole de Jules Dupuit en proposant des moyens pratiques de révélation des préférences. Nous verrons également que cette théorie est reprise de nos jours avec le Yield Management et par les compagnies aériennes à bas coûts. Le troisième chapitre a pour but de voir comment Colson prend en compte la question sociale. Nous verrons qu’il défend une intervention de l’État plus importante que d’autres économistes libéraux afin d’éviter que les ouvriers ne se tournent vers le socialisme. Le quatrième chapitre étudie l’intervention de l’État préconisée par Colson dans le domaine des chemins de fer. Nous verrons que dans ce domaine où l’État est très présent, l’auteur souhaite le limiter. Il préfère ainsi la concession à la régie et souhaite la construction de nouvelles lignes uniquement si elles sont rentables. Nous verrons qu’à nouveau, la crainte du socialisme n’est pas étrangère à ses positions. Sur chacun des thèmes, nous verrons que Colson accorde à la pratique une place importante. Au niveau théorique tout part de l’observation et se termine par l’observation, au niveau pratique il est marqué par les préoccupations de son époque. / The object of this dissertation is to analyse the contributions of Clément Colson to the economics in order to be better acquainted with his thought, with the French Liberal School at the beginning of the 20th century, to see the influence he had on his main students, Divisia, Roy and Rueff, and to evaluate the actuality of his recomandations. The first chapter develops the Colson’s theoretical contributions.For his students, his main contribution would be the theory of the joint setting of wage and of the interest rate. We will explain this theory is close to the optimal management rule in microeconomics attributed to Clark; we will see we can speak then about multiple discovery.Colson is interesting too from the point of view of the method used. We will see he uses statistics and mathematics in his developments: he makes one of the first assesments of the French income, his lectures develop economics calculus, he can be seen as a precursor of econometrics in France. The second chapter shows that Colson develops the Jules Dupuit pricing method for means of communications exploited by a monopoly by proposing practical way of preferences revelation. We will show too that this theory is used nowadays with the Yield Management and by airline lowcost companies.The third chapter has for purpose to see how Colson takes into account the social question. We will see he argues for a more important State intervention than other liberal economists in order to avoid workers to turn to socialism. The fourth chapter is devoted to the State intervention recommended by Colson in the field of railways. We will see that in this field in which the State is very present, the author wishes to limit it. So he prefers the concession to the public exploitation and wishes construction of new railway lines just if they are profitable. We will see again that the fear of socialism is not stranger to his positions. On each theme, we will see that Colson gives an important place to the practice. At the theoretical level all starts and finishes with the observation, at the practice level he is influenced by the preoccupations of his time.

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed. We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time. We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results. After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances. Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them. Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case. ------------------------------------------------ Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits. Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes. Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3. Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème. Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas.

Environ 3% des antiprotons (p) stoppés dans l'heliurn survivent plusieurs microsecondes contre quelques picosecondes dans tout autre matériau. Cette métastabilité inhabituelle résulte d'une capture sur des états liés de l'atome exotique pHe+, dénommé atomcule car il s'apparente à la fois à un atome de Rydberg quasi-circulaire quasi-classique de grand moment angulaire l ~ n - 1 ~ 37 et à une molécule diatomique composée d'un noyau chargé négativement et caractérisée par une forte excitation rotationnelle J = l. En dehors de cette structure duale originale accessible par spectroscopie laser, la physico-chimie de leur interaction avec d'autres atomes ou molécules a fait l'objet de mesures résolues en état. Alors que les atomcules résistent à des millions de collisions dans l'helium pur, des contaminants moléculaires comme H2 les détruisent immédiatement, même à basse température. Dans le cadre Born-Oppenheimer, nous interprétons l'interaction moléculaire, calculée par des techniques de chimie quantique ab initio, en termes de chemins réactifs classiques, qui présentent des barrières d'activation compatibles avec celles mesurées pour He et H2. Nous montrons par une approche Monte Carlo de trajectoires classiques que la thermalisation détruit fortement les populations initiales, portant la fraction estimée des états de capture à 3 %. Nous étudions aussi la recombinaison dissociative pHé + é + e- dans une approche de trajectoires classiques pour les noyaux: nous prédisons la synthèse d'antihydrogène avec un rapport de branchement de 10 %, ainsi qu'une nouvelle classe d'atomcules métastables (alpha, p, e+, 2e-), qui pourrait être confirmée par spectroscopie. Ce travail illustre la transférabilité des concepts de chimie physique à l'étude de processus exotiques en présence d'antimatière, et apporte un éclairage nouveau sur la physico-chimie des radicaux interstellaires froids.

Un système multi-agents est composé de plusieurs agents autonomes qui interagissent entre eux dans un environnement commun. Ce mémoire vise à démontrer l’utilisation d’un système multi-agents pour le développement d’un jeu vidéo. Tout d’abord, une justification du choix des concepts d’intelligence artificielle choisie est exposée. Par la suite, une approche pratique est utilisée en effectuant le développement d’un jeu vidéo. Pour ce faire, le jeu fut développé à partir d’un jeu vidéo mono-agent existant et mo- difié en système multi-agents afin de bien mettre en valeur les avantages d’un système multi-agents dans un jeu vidéo. Le développement de ce jeu a aussi démontré l’applica- tion d’autres concepts en intelligence artificielle comme la recherche de chemins et les arbres de décisions. Le jeu développé pour ce mémoire viens appuyer les conclusions des différentes recherches démontrant que l’utilisation d’un système multi-agents per- met de réaliser un comportement plus réaliste pour les joueurs non humains et bien plus compétitifs pour le joueur humain. / A multi-agent system is composed of several autonomous agents that interact with each other in a common environment. This thesis aims to demonstrate the use of a multi- agent system for the development of a video game. First, a justification of the artificial intelligence’s concepts used in this master’s thesis is exposed. Subsequently, a practical approach is used in developping a video game. To do this, the game was developed from an existing single-agent video game and modified into a multi-agent system in order to properly highlight the benefits of a multi-agent system in a video game. The development of this game also demonstrate the application of other concepts in artificial intelligence such as pathfindinig and behaviour trees. In summary, the use of a multi- agent system has achieved a more realistic behavior for the non-human players and a more competitive gameplay for the human player.

Dans cette thèse, nous nous sommes intéressés à l'analyse et la conception de réseaux étudiés sont les réseaux de fibres optiques et les réseaux de capteurs. Les problématiques étudiées sont: pour les réseaux de fibres optiques, minimiser le coût de déploiement et assurer la qualité de service; dans les réseaux de capteurs, garantir la sécurité des transmissions et l'énergie consommée par le routage des communications. Pour résoudre ces problèmes nous utilisons des techniques de théorie des graphes, de complexité, de programmation linéaire. Le premier problème consiste à concevoir un plan d'installation de fibres optiques de coût minimal permettant de connecter un ensemble de clients à un noeud de raccordement via un ensemble de coupleurs en respectant les contraintes technologiques imposées par la norme. Nous proposons une modélisation de ce problème ainsi qu'une méthode de résolution. Le deuxième problème est un problème de flot avec contrainte de délai où le délai pour traverser une liaison est proportionnel à la quantité de flot quicircule sur celle-ci. Nous proposons une preuve de NP-complétude dans le cas général, un algorithme d'approximation facteur 2 dans le cas où le graphe support est un chemin et une heuristique évaluée de façon expérimentale qui calcule en un temps raisonnable de bonnes solutions pour des instances de tailles réelles. Enfin, nous proposons deux protocoles concernant les réseaux de capteurs. Le premier, basé sur un algorithme distribué, calcule un ensemble de chemins disjoints entre les terminaux. Le second maximise la durée de vie d'un réseau de capteurs alimentés par batteries. Des résultats s'expérimentations numériques sont présentés. / In this thesis, we study some optimization problem applied to telecommunication networks. We study fiber optical networks and sensor networks. We are interested to analysis and design for these types of networks. The issues studied are: for fiber optic networks, minimize the cost of deployement and ensure quality of service; for sensors network, ensure the safety of transmissions and the energy consumed. To solve these problems we use techniques as graphs theory, complexity, linearprogramming, generalized flows and paths with resource constraints. The first problem is to minimize the cost to deploy a fiber optical network which connect a set of customers to a connection node through a set of splitter and deal about technological constraints imposed by the standard. We propose a model and a method of resolution for this problem. The second problem is a flow problem with delay constraint where time to cross a edge is proportional to the amount of flow that flows thereon. We offer a proof of NP-completeness in the general case, an approximation algorithm factor 2 in the case where the support graph is a path and an estimated experimentally an heuristic that calculates good solutions for instances of real sizes. Finally, we propose two protocols for sensor networks, which resulted in two patents. The first, based on a distributed algorithm, calculates a set of disjoint paths between terminals. The second maximizing the lifetime of sensors powered by batteries. The results of numerical experiments are also presented.

L’énergie photovoltaïque jouera un rôle déterminant dans la transition énergétique future. Bien que les cellules solaires à base de silicium dominent encore le marché, leur coût de fabrication et le poids des modules limitent leur développement. Depuis quelques années, les industriels s’intéressent de plus en plus aux dispositifs à base de couches minces en raison de leurs procédés de fabrication rapides et peu onéreux sur de larges substrats. Cette technologie utilise une large variété de matériaux; les chalcopyrites tels que Cu(In,Ga)Se2 sont les plus prometteurs. Le procédé de fabrication de couches chalcopyrites le plus répandu est la coévaporation mais l’utilisation de vides très poussés rende cette technique peu adaptée à la production à grande échelle de modules bon marché. La solution alternative décrite dans ce travail est un procédé en deux étapes basé sur le recuit sous atmosphère réactive de précurseurs métalliques électrodéposés. Le développement de cette technologie passe par une meilleure compréhension des mécanismes d’incorporation et d’homogénéisation du gallium dans les couches formées et par une optimisation des étapes de recuit. Le premier objectif de ce travail de thèse est une étude des mécanismes réactionnels mis en jeu lors du procédé de recuit à travers l’étude de différents types de précurseur. Par la suite ces connaissances sont utilisées pour modéliser et optimiser un recuit industriel innovant. Ce travail est réalisé à l’aide de plans d’expérience (DOE) où l’influence de certains paramètres, les plus critiques est mise en évidence. Des voies d’optimisation sont proposées et des hypothèses faites afin d’expliquer les phénomènes observés. / Solar energy is promised to be a major actor in the future of energy production. Even if silicon based solar cells remain the main product their fabrication is energy consuming and requires heavy cover glass for protection, which reduce their development. For several years, commercial interest has shifted towards thin-film cells for which manufacturing time, large scale production, fabrication costs and weight savings are the main advantages. For thin film technology, a wide variety of materials can be used but chalcopyrite such as Cu(In,Ga)Se2 is one of the most promising. The most current method used for chalcopyrite formation is co- evaporation but this process is very expensive and not well suitable for large scale production due to high vacuum requirements. One alternative solution described in this work consists of a two-step technology based on the sequential electro-deposition of a metallic precursor followed by a rapid reactive annealing. However to reach its full potential this technology needs a better understanding of the Ga incorporation mechanism and of the selenization/sulfurization step. This work focuses first on formation mechanisms through the study of several kinds of precursor. This knowledge is then used to explain and to optimize innovative annealing processes. This study is achieved by observing the impact of some process parameters using designs of experiment (DOE). A link between process parameters and properties of these thin films is obtained using electrical, structural and diffusion characterization of the devices. Finally we propose hypothesis to explain observed phenomena and also some improvements to meet the challenges of this process.

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 étudie des systèmes locaux de gestion de transfert de pétrole ayant une architecture de réseau de canalisation. Pour leur représentativité, deux systèmes localisés au Venezuela et appartenant à l'entreprise PDVSA (Pétroles du Venezuela) ont été retenus pour illustrer les méthodes proposées et les valider : le Terminal Maritime de Pétrole de Guaraguao et le Centre de Stockage de Punta de Palmas. Dans ces réseaux des connexions, appelées « alignements », sont établies en ouvrant/fermant des vannes à travers d'un système SCADA (Supervisory Control and Data Acquisition). Le choix d'un alignement doit tenir compte de critères d'optimisation. La minimisation des interférences avec d'autres alignements, liée à la notion de capacité opérative, a été identifiée comme le critère de choix le plus important. Les contributions de cette thèse reposent sur une modélisation sous forme de graphes, et sur des algorithmes appartenant au domaine de la recherche opérationnelle. Elles contribuent à fournir aux opérateurs de supervision des outils d'analyse permettant d'optimiser le choix des alignements. Des indicateurs permettant de quantifier l'impact des opérations d'alignement ou des défaillances, sur la capacité opérative du système, sont proposés. La minimisation de l'impact sur la capacité opérative, va correspondre à la minimisation des interférences avec des alignements potentiels. Un algorithme de calcul de ces indicateurs, est présenté, ainsi que des algorithmes de recherche de chemin, de détermination d'éléments critiques, et de recherche d'alignements utilisant des pompes. Ces algorithmes sont basés sur des algorithmes classiques s'adressant au problème du plus court chemin, du flot maximum et du nombre maximum de chemins disjoints. Cependant, ils utilisent des méthodes innovantes, comme l'ajout de contraintes considérant l'existence de sous-types d'alignements, le calcul dynamique des coûts des chemins à partir de son impact sur la capacité opérative, et la recherche de chemins via un point intermédiaire obligatoire. Les contributions sont potentiellement applicables dans des domaines autres que le transport de pétrole. Les algorithmes ont été mis en œuvre en utilisant le langage Python et ont été testés en utilisant les données réelles des réseaux étudiés. L'objectif à moyen terme de ces travaux est le développement d'un logiciel d'assistance à la prise de décision. / This thesis studies local crude oil transportation systems with a pipe network architecture. Two representative systems, belonging to PDVSA (Venezuelan oil company), have been studied: the Guaraguao Crude Oil Seaport and the Punta de Palmas Tanks Yard. In this systems, connections, called "alignments", are established by opening/closing valves using a SCADA(Supervisory Control and Data Acquisition) system. Alignment choice is made based on optimization criteria. Interferences minimization with other alignments, related to the notion of operative capacity, has been identified as the most important criterion. The contributions of this thesis are based on graph modelling and algorithms from operational research. The main goal is to provide analysis tools allowing alignment choice optimization. Indexes permitting the quantification of alignments or failures impact on the operative capacity of the system are proposed. Minimizing the impact on the operative capacity will correspond to minimizing interferences with potential alignments. An algorithm computing these indexes is presented, as well as complementary developments such as a path search algorithm, an algorithm for critical elements determination, and algorithm for alignments using pumps. These algorithms are based on classical algorithms for the shortest path problem, the maximum flow problem and the maximum disjoint paths problem. However, they use innovative methods such as adding constraints when considering alignment sub-types, the dynamic computation of path costs based on their impact on operative capacity, and path search considering an obligatory intermediate node. These contributions can potentially be applied in areas other than oil transportation. The algorithms had been implemented in Python and had been tested using real data from the studied systems. The middle term goal of these works is the development of assistance software for decision making.