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.

La tomographie consiste à reconstruire un objet nD à partir de projections (n-1)D. Cette discipline soulève plusieurs questions auxquelles la recherche essaie d'apporter des réponses. On s'intéresse dans cette thèse à trois aspects de cette problématique : 1) la reconstruction de l'image 2D à partir de projections dans un cadre rarement étudié qui est celui des sources ponctuelles ; 2) l'unicité de cette reconstruction ; 3) l'estimation d'informations concernant un objet sans passer par l'étape de reconstitution de son image. Afin d'aborder le problème de reconstruction pour la classe des ensembles convexes, nous définissons une nouvelle classe d'ensembles ayant des propriétés de convexité qu'on appelle convexité par quadrants pour des sources ponctuelles. Après une étude de cette nouvelle classe d'ensembles, nous montrons qu'elle présente des liens forts avec la classe des ensembles convexes. Nous proposons alors un algorithme de reconstruction d'ensemblesconvexes par quadrants qui, si l'unicité de la reconstruction est garantie, permet de reconstruire des ensembles convexes en un temps polynomial. Nous montrons que si une conjecture, que nous avons proposée, est vraie, les conditions de l'unicité pour les ensembles convexes par quadrants sont les mêmes que celles pour les ensembles convexes. Concernant le troisième aspect étudié dans cette thèse, nous proposons une méthode qui permet d'estimer, à partir d'une seule projection, la surface d'un ensemble 2D. Concernant l'estimation du périmètre d'un ensemble 2D, en considérant les projections par une deuxième source d'un ensemble convexe, nous obtenons deux bornes inférieures et une borne supérieure pour le périmètre de l'objet projeté.

La tomographie consiste à reconstruire un objet nD à partir de projections (n-1)D. Cette discipline soulève plusieurs questions auxquelles la recherche essaie d'apporter des réponses. On s'intéresse dans cette thèse à trois aspects de cette problématique : 1) la reconstruction de l'image 2D à partir de projections dans un cadre rarement étudié qui est celui des sources ponctuelles ; 2) l'unicité de cette reconstruction ; 3) l'estimation d'informations concernant un objet sans passer par l'étape de reconstitution de son image. Afin d'aborder le problème de reconstruction pour la classe des ensembles convexes, nous définissons une nouvelle classe d'ensembles ayant des propriétés de convexité qu'on appelle convexité par quadrants pour des sources ponctuelles. Après une étude de cette nouvelle classe d'ensembles, nous montrons qu'elle présente des liens forts avec la classe des ensembles convexes. Nous proposons alors un algorithme de reconstruction d'ensemblesconvexes par quadrants qui, si l'unicité de la reconstruction est garantie, permet de reconstruire des ensembles convexes en un temps polynomial. Nous montrons que si une conjecture, que nous avons proposée, est vraie, les conditions de l'unicité pour les ensembles convexes par quadrants sont les mêmes que celles pour les ensembles convexes. Concernant le troisième aspect étudié dans cette thèse, nous proposons une méthode qui permet d'estimer, à partir d'une seule projection, la surface d'un ensemble 2D. Concernant l'estimation du périmètre d'un ensemble 2D, en considérant les projections par une deuxième source d'un ensemble convexe, nous obtenons deux bornes inférieures et une borne supérieure pour le périmètre de l'objet projeté.

L’objectif de cette thèse est d’étudier divers concepts de positivité en géométrie kählerienne. En particulier,pour une variété kählerienne compacte de dimension n, nous étudions la positivité des classes transcendantes de type (1,1) et (n-1, n-1) - ces classes comprennent donc en particulier les classesde diviseurs et les classes de courbes. / The goal of this thesis is to study various positivity concepts in Kähler geometry. In particular, for a compact Kähler manifold of dimension n, we study the positivity of transcendental (1,1) and (n-1, n-1) classes. These objects include the divisor classes and curve classes over smooth complex projective varieties.

A (convex) polytope P is said to be 2-level if every hyperplane H that is facet-defining for P has a parallel hyperplane H' that contains all the vertices of P which are not contained in H.Two level polytopes appear in different areas of mathematics, in particular in contexts related to discrete geometry and optimization. We study the problem of enumerating all combinatorial types of 2-level polytopes of a fixed dimension d. We describe the first algorithm to achieve this. We ran it to produce the complete database for d <= 8. Our results show that the number of combinatorial types of 2-level d-polytopes is surprisingly small for low dimensions d.We provide an upper bound for the number of combinatorially inequivalent 2-level d-polytopes. We phrase this counting problem in terms of counting some objects called 2-level configurations, that capture the class of "maximal" rank d 0/1-matrices, including (maximal) slack matrices of 2-level cones and 2-level polytopes. We provide a proof that the number of d-dimensional 2-level configurations coming from cones and polytopes, up to linear equivalence, is at most 2^{O(d^2 log d)}.Finally, we prove that the extension complexity of every stable set polytope of a bipartite graph with n nodes is O(n^2 log n) and that there exists an infinite class of bipartite graphs such that, for every n-node graph in this class, its stable set polytope has extension complexity equal to Omega(n log n). / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Les mathématiques tropicales sont une branche des mathématiques correspondant à l'étude d'une algèbre modifiée grâce à la redéfinition de l'addition et de la multiplication. Les mathématiques tropicales sont généralement définies grâce au minimum et à l'addition (algèbre min-plus) mais le terme est parfois utilisé pour désigner l'algèbre max-plus, définie grâce au maximum et à l'addition. Briec et Horvath ont introduit une notion de convexité très proche qui apparait comme un cas limite d’opérateurs utilisés en théorie de l’optimisation par Avriel (1972) et de Ben-Tal (1977). En suivant cette ligne d’investigation, nous allons proposer, dans le domaine de l’économie de la production et de l’optimisation de portefeuille, une certaine classe de modèles économiques à élaborés à partir de ces notions. Pour ce faire, nous introduisons une nouvelle classe de technologie de production permettant de prendre en compte les structures d’homothe´tie-translation dans la mesure de productivité au travers du concept de la Convexité Max-Plus. Ensuite, nous allons établir une relation topologique entre plusieurs classes de modèles convexes généralisés connus. Nous analysons pour cela la limite de Painlevé-Kuratowski des modèles CES-CET et des technologies non paramétriques satisfaisant une hypothèse de rendements d’échelle alpha. On montre que leurs limites topologiques convergent vers les modèles de production B-convexe et Cobb-Douglas. Enfin, nous allons montrer que l'amélioration de l'efficacité technique d’une coalition d’entreprises s'avère compatible avec les technologies de semi-treillis dans un jeu coopératif. Nous introduisons ensuite, le concept d’écart absolu moyen dans la sélection du portefeuille en utilisant le « Shortage Function » qui prend en compte simultanément la réduction des inputs et l’augmentation des outputs comme dans la théorie de la production. Enfin, nous allons étendre le concept de B-convexité et de l’inverse B-convexité en se concentrant sur le calcul des mesures d’efficacité technique dans le graphe. / Tropical algebra is the tropical analogue of linear algebra by redefining the usual operation addition by the maximization operation and the usual addition operation as multiplication. Briec and Horvath introduced a concept of convexity very close to this concept quoted above which appears as one of the limits of use of the theory of optimization by Avriel (1972) and Ben-Tal (1977). Following this line of investigation, we give an overview of contributions involving a semilattice structure of production technologies and an optimization portfolio. To do that, firstly, we propose a framework allowing to consider both semilattice structure and translation homothetic properties in productivity measurement. We introduce the concept of Max-Plus convexity which combine both an upper semilattice structure and an additivity assumption. We establish a topological relation between several classes of known generalized convex models using some basic algebraic convex structures. We analyze the Painlevé-Kuratowski limit of the CES-CET and Alpha-returns to scale models. It is shown that their topological limits yield the B-convex and Cobb-Douglas production models. Moreover, we show that the improvement of technical efficiency is compatible with semilattice technologies in a cooperative game. Then, we introduce a criterion to measure portfolio efficiency based upon the minimization of the maximum absolute deviation and minimum absolute deviation from the expected return using the Shortage function. Finally, we derive simple closed-form expressions to calculate the hyperbolic measure in the case of inverse and B-Convexity that evaluates technical efficiency in the full input-output space.

Cette thèse se situe à l'interface entre l'analyse d'images, dont l'objectif est la description automatique du contenu visuel, et la géométrie discrète, qui est l'un des domaines dédiés au traitement des images numériques. Pour être stocké et manipulé sur un ordinateur, un signal observé est régulièrement échantillonné. L'image numérique, qui est le résultat de ce processus d'acquisition, est donc constituée d'un ensemble fini d'éléments distincts. La géométrie discrète se propose d'étudier les propriétés géométriques d'un tel espace dépourvu de continuité. Dans ce cadre, nous avons considéré les régions homogènes et porteuses de sens d'une image, avec l'objectif de représenter leur contour au moyen de modèles géométriques ou de les décrire à l'aide de mesures. L'étendue des applications de ce travail en analyse d'images est vaste, que ce soit au cours du processus de segmentation, ou en vue de la reconnaissance d'un objet. Nous nous sommes concentrés sur trois modèles géométriques discrets définis par la discrétisation de Gauss : la partie convexe ou concave, l'arc de cercle discret et le segment de droite discrète. Nous avons élaboré des algorithmes dynamiques (mise à jour à la volée de la décision et du paramétrage), exacts (calculs en nombres entiers sans erreur d'approximation) et rapides (calculs simplifiés par l'exploitation de propriétés arithmétiques et complexité en temps linéaire) qui détectent ces modèles sur un contour. L'exécution de ces algorithmes le long d'un contour aboutit à des décompositions ou à des polygonalisations réversibles. De plus, nous avons défini des mesures de convexité, linéarité et circularité, qui vérifient un ensemble de propriétés fondamentales : elles sont robustes aux transformations rigides, elles s'appliquent à des parties de contour et leur valeur maximale est atteinte pour le modèle de forme qui sert de comparaison et uniquement sur celui-ci. Ces mesures servent à l'introduction de nouveaux modèles dotés d'un paramètre variant entre 0 et 1. Le paramètre est fixé à 1 quand on est sûr de la position du contour, mais fixé à une valeur inférieure quand le contour est susceptible d'avoir été déplacé par un bruit d'acquisition. Cette approche pragmatique permet de décomposer de manière robuste un contour en segments de droite ou en parties convexes et concaves. / The work presented in this thesis concerns the fields of image analysis and discrete geometry. Image analysis aims at automatically describing the visual content of a digital image and discrete geometry provides tools devoted to digital image processing. A two-dimensional analog signal is regularly sampled in order to be handled on computers. This acquisition process results in a digital image, which is made up of a finite set of discrete elements. The topic of discrete geometry is to study the geometric properties of such kind of discrete spaces. In this work, we consider homogeneous regions of an image having a meaning for a user. The objective is to represent their digital contour by means of geometric patterns and compute measures. The scope of applications is wide in image analysis. For instance, our results would be of great interest for segmentation or object recognition. We focus on three discrete geometric patterns defined by Gauss digitization: the convex or concave part, the digital straight segment and the digital circular arc. We present several algorithms that detect or recognize these patterns on a digital contour. These algorithms are on-line, exact (integer-only computations without any approximation error) and fast (simplified computations thanks to arithmetic properties and linear-time complexity). They provide a way for segmenting a digital contour or for representing a digital contour by a reversible polygon. Moreover, we define a measure of convexity, a measure of straightness and a measure of circularity. These measures fulfil the following important properties: they are robust to rigid transformations, they may be applied on any part of a digital contour, they reach their maximal value for the template with which the data are compared to. From these measures, we introduce new patterns having a parameter that ranges from 0 to 1. The parameter is set to 1 when the localisation of the digital contour is reliable, but is set to a lower value when the digital contour is expected to have been shifted because of some acquisition noise. This measure-based approach provides a way for robustly decomposing a digital contour into convex, concave or straight parts.

The thesis focuses on two open problems on finite partially ordered sets: the structure of order polytopes and the approximation of the number of linear extensions of a poset by mean of graph entropy. The polytopes considered here are the linear ordering polytope, the semiorder polytope, the interval order polytope, the partial order polytope and also a generalisation of the linear ordering polytope: the linear extension polytope of a fixed poset P. Various results on the structure of theses polytopes are proved in the first part of the thesis. In the second part of the thesis, we improve the existing bounds linking the entropy of the incomparability graph of the poset P and its number of linear extension. / Le but de la thèse est d'étudier deux problèmes ouverts sur les ensembles ordonnés finis: la structure des polytopes d'ordre et l'approximation du nombre d'extensions linéaires d'un ordre partiel au moyen de la notion d'entropie de graphe. Les polytopes considérés sont le polytope des ordres totaux, le polytope des semiordres, le polytope des ordres d'intervalles, le polytope des ordres partiels, ainsi qu'une généralisation du polytope des ordres totaux: le polytope des extensions linéaires d'un ensemble ordonné fixé P. Des résultats sur la structure de ces polytopes sont présentés dans la première partie de la thèse. Dans la deuxième partie de la thèse, nous améliorons les bornes existantes liant l'entropie du graphe d'incomparabilité d'un ordre partiel et son nombre d'extensions linéaires. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

On s'intéresse à la modélisation des matériaux granulaires composés d'agrégats non-convexes et cohésifs en vue d'application à la rhéologie des poudres d'UO2. L'influence du degré de non-convexité des particules est analysé en termes de grandeurs macroscopiques (frottement interne et cohésion de Coulomb) et de paramètres micro-mécaniques tels que l'anisotropie de la texture et la transmission des efforts. Il apparaît en particulier que la compacité évolue d'une manière complexe avec la non-convexité et que la résistance au cisaillement augmente mais sature sous l'effet d'imbrication entre agrégats. Des modèles simples sont introduits pour décrire ces comportements en termes de paramètres micro-mécaniques. De même, des études systématiques par cisaillement, compaction uniaxiale et compression simple montrent que la cohésion interne augmente avec la non-convexité mais est fortement contrôlée par les conditions aux limites et l'apparition de bandes de cisaillement ou de concentrations de contraintes. / We model in this work granular materials composed of nonconvex and cohesive aggregates, in view of application to the rheology of UO2 powders. The effect of nonconvexity is analyzed in terms of bulk quantities (Coulomb internal friction and cohesion) and micro-mechanical parameters such as texture anisotropy and force transmission. In particular, we find that the packing fraction evolves in a complex manner with the shape nonconvexity and the shear strength increases but saturates due to interlocking between the aggregates. We introduce simple models to describe these features in terms of micro-mechanical parameters. Furthermore, a systematic investigation of shearing, uniaxial compaction and simple compression of cohesive packings show that bulk cohesion increases with non-convexity but is strongly influenced by the boundary conditions and shear bands or stress concentration.

.