.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Cette thèse porte sur l’étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d’optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d’autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d’un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l’écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l’étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d’approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d’infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.

Dans ce travail, nous nous intéressons principalement à l'étude de deux équations classiques : l'équation de Cauchy-Riemann dans certains domaines de ${\Bbb C}^n$ et l'équation de Cauchy-Riemann tangentielle dans certains domaines d'une sous-variété CR générique $q$-concave. L'étude, liée à chaque équation, consiste, dans un premier temps, à obtenir des résultats de résolution locale avec des solutions ayant des propriétés de régularité jusqu'au bord des domaines considérés. Dans le cadre complexe, la méthode de résolution consiste à construire explicitement une solution grâce à la théorie des représentations intégrales, théorie dont l'essor date des années 70 grâce aux résultats de H. Grauert, G.M. Henkin, I. Lieb et E. Ramirez. On en deduit ainsi des estimations ${\cal C}^k$ sur des domaines à coins $q$-convexes et $q$-concaves locaux. Dans le cadre CR, la résolution se déduit des résultats obtenus dans le cas complexe grâce à des outils d'algèbre homologique et de théorie des faisceaux découlant en particulier de travaux de A. Andreotti, G. Fredericks, C.D. Hill et M. Nacinovich. On obtient alors des résultats locaux de résolution du $\bar \partial _b$ pour des formes de classe ${\cal C}^\infty$ jusqu'au bord des domaines considérés. Ensuite, on utilise les résultats locaux ainsi que la méthode <> due à H. Grauert pour montrer des théorèmes globaux d'annulation, de finitude ou de séparation des groupes de cohomologie.

L'analyse idempotente étudie les espaces linéaires de dimension infinie dans lesquels l'opération maximum se substitue à l'addition habituelle. Nous démontrons un ensemble de résultats dans ce cadre, en soulignant l'intérêt des outils d'approximation fournis par la théorie des domaines et des treillis continus. Deux champs d'étude sont considérés : l'intégration et la convexité. En intégration idempotente, les propriétés des mesures maxitives à valeurs dans un domaine, telles que la régularité au sens topologique, sont revues et complétées ; nous élaborons une réciproque au théorème de Radon-Nikodym idempotent ; avec la généralisation Z de la théorie des domaines nous dépassons différents travaux liés aux représentations de type Riesz des formes linéaires continues sur un module idempotent. En convexité tropicale, nous obtenons un théorème de type Krein-Milman dans différentes structures algébriques ordonnées, dont les semitreillis et les modules idempotents topologiques localement convexes ; pour cette dernière structure nous prouvons un théorème de représentation intégrale de type Choquet : tout élément d'un compact convexe K peut être représenté par une mesure de possibilité supportée par les points extrêmes de K. Des réflexions sont finalement abordées sur l'unification de l'analyse classique et de l'analyse idempotente. La principale piste envisagée vient de la notion de semigroupe inverse, qui généralise de façon satisfaisante à la fois les groupes et les semitreillis. Dans cette perspective nous examinons les propriétés "miroir" entre semigroupes inverses et semitreillis, dont la continuité fait partie. Nous élargissons ce point de vue en conclusion.

Dans cette thèse, nous avons considéré des problèmes de minimisation de fonctionnelles relatives à des objets géométriques en dimension 2 et 3 sous contraintes de bord. Nous considérons d'abord le cas des corps de largeur constante en dimension 2 et nous redémontrons le théorème de Blaschke-Lebesgue par la théorie du contrôle optimal en utilisant le principe de Pontryagin. Nous étudions aussi le problème de la minimisation du volume dans la classe des corps de largeur constante en dimension 3 et à symétrie de révolution. Par le principe de Pontryagin, nous obtenons des conditions nécessaires sur un minimiseur. Nous étudions également le problème de minimisation de l'aire dans la classe des rotors d'un polygone à n côtés, ce qui constitue une généralisation du problème précédent. Par le principe de Pontryagin, nous démontrons qu'un minimiseur est une réunion finie d'arcs de cercles de rayon r_i où les r_i prennent des valeurs quantifiées. Nous étudions plus spécifiquement certaines propriétés des rotors réguliers en s'intéressant à leur optimalité locale pour la fonctionnelle d'aire, et pour un certain type de déformations admissibles. Par le théorème de Kuhn-Tucker, nous généralisons au cas des rotors un résultat de Firey en montrant que les rotors réguliers du triangle équilatéral sont des maxima locaux de l'aire, et que les rotors réguliers des polygones réguliers à n>4 côtés, sont des points selles de l'aire. Enfin, nous étudions le problème de minimisation du volume en dimension 3 dans la classe des corps de largeur constante. Nous introduisons d'abord un espace fonctionnel prenant en compte la contrainte de convexité et celle de largeur. Puis nous en déduisons des conditions d'optimalité faibles, vérifiées par le solide de Meissner, dont on conjecture depuis 1934 qu'il minimise le volume dans cette classe.

L'objet de cette thèse est d'étudier la théorie du transport optimal sur un espace de Wiener abstrait. Les résultats qui se trouvent dans quatre principales parties, portent :Sur la convexité de l'entropie relative. On prolongera des résultats connus en dimension finie, sur l'espace de Wiener muni d'une norme uniforme, à savoir que l'entropie relative est (au moins faiblement) 1-convexe le long des géodésiques induites par un transport optimal sur l'espace de Wiener.Sur les mesures à densité logarithmiquement concaves. Le premier des résultats importants consiste à montrer qu'une inégalité de type Harnack est vraie pour le semi-groupe induit par une telle mesure sur l'espace de Wiener. Le second des résultats obtenus nous fournit une inégalité en dimension finie (mais indépendante de la dimension), contrôlant la différence de deux applications de transport optimal.Sur le problème de Monge. On s'intéressera au problème de Monge sur l'espace de Wiener, muni de plusieurs normes : des normes à valeurs finies, ou encore la pseudo-norme de Cameron-Martin.Sur l'équation de Monge-Ampère. Grâce aux inégalités obtenues précédemment, nous serons en mesure de construire des solutions fortes de l'équation de Monge-Ampère (induite par le coût quadratique) sur l'espace de Wiener, sous de faibles hypothèses sur les densités des mesures considérées

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal