Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

La régionalisation est autant un processus spatial qu'un processus territorial. Elle est spatiale parce qu'elle se réalise sur des structures spatiales héritées tout en les mettant en oeuvre. Nous avons voulu mettre en perspective dans le processus ou les volontés de régionalisation, le système formé des notions de territoires, de villes et de réseaux.<br />Aussi, nous proposons de définir des territoires autour de réseaux de villes qui donnent à penser les régionalisations souhaitables ou souhaitées à partir des propriétés des territoires et de leur organisation par la représentation des interactions spatiales entre les villes. Sont alors créés des réseaux de villes autour desquels la régionalisation des territoires serait possible.<br />Les mises en réseaux de villes se basent sur le corpus conceptuel et théorique du fonctionnement et des propriétés des systèmes de villes, et tiennent compte des caractéristiques du système de villes étudié à travers les critères de la taille des villes et de leur localisation. Ces seuls critères déterminent les espacements entre les villes et leur position dans la hiérarchie de niveaux dans le système, ce qui intègre et révèle les structures spatiales sous-jacentes ou locales.<br />Sont alors définies deux catégories de réseaux de villes :<br />• les réseaux de villes de proximité et de voisinage, sur des contraintes d'espacement entre les villes ;<br />• les réseaux de villes hiérarchisés, sur des contraintes de taille des villes et de principes d'emboîtement de structures hiérarchiques (type administratif, à la hiérarchie stricte, ou type principe de marché, à la hiérarchie non stricte).<br />La formalisation et les représentations des mises en réseaux de villes sont réalisées par la théorie des graphes qui permet une modélisation aisée des organisations hiérarchiques, en particulier des emboîtements de niveaux, par un de ses sous-ensembles, les arbres.<br />La mise en place de ces méthodes et l'évaluation des performances des régionalisations qu'elles engendrent se fait sur deux exemples à problématiques et échelles différentes. La première application montre une approche spatiale en archéologie pour aider à dégager les principales structures d'un système de peuplement d'un territoire autour de la Cité antique de Luteva (Lodève, Hérault, France) durant la période du Haut-Empire (Ier siècle ap. J.-C. - IIIe siècle ap. J.-C.). La seconde application consiste à définir un arc méditerranéen théorique à partir du système de villes européennes sans maillage administratif.

Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.

Cette thèse s'intéresse au probleme de la reconnaissance d'objets en présence d'une vaste base de modèles. L'indexation de modèles peut être décrite comme suit: étant donne un groupe d'indices image, extraire rapidement de la base de modèles, les modèles contenant le groupe d'indices. La combinatoire du paradigme classique d'appariement indices-modèles étant prohibitive dans ce cas, nous proposons une methode d'indexation par une technique de hachage de graphes. Nous décrivons d'abord les principes: codage d'image et des modelés sous une forme de graphes, gestion d'une base de modèles par tables hash-codees, comparaison de graphes sur la base de leur caractérisation polynomiale, accès a la base de modèles. Ensuite, nous décrivons le système mis en œuvre selon ces principes, et nous présentons quelques résultats d'expérimentation

Le travail de thèse présenté dans ce document traite de l'analyse de différentes propriétés liées à l'observabilité des systèmes à entrée inconnue par approche graphique. La simplicité de mise en œuvre de l'approche graphique permet de se défaire des difficultés numériques inhérentes aux approches géométrique et algébrique. Ce constat a conduit ces dernières décennies, à une série d'études structurelles basées sur l'approche graphique. <br />Parmi les propriétés encore non abordées graphiquement, l'observabilité forte traduit l'observabilité des variables d'état d'un système pour toute valeur d'entrée ainsi que l'observabilité conjointe de l'état et de l'entrée. Ces propriétés plus fortes que l'observabilité simple et le diagnostic nous ont paru utiles et pertinentes à étudier. En effet, les outils d'analyse développés peuvent s'avérer importants dans le cadre de la synthèse d'observateurs ou d'estimateurs d'entrées utile à la synthèse de lois de commandes tolérantes aux défauts ou robustes aux perturbations, ou encore quand il s'agit de vérifier si la propriété d'observabilité d'un système n'est pas altérée lorsqu'il est soumis à des perturbations, voire à des défauts d'amplitude trop importante pour être négligés. <br />Le manuscrit est structuré en trois parties. Dans la première, nous avons abordé l'analyse de différentes propriétés d'observabilité. Plus précisément, nous avons tout d'abord donné des conditions nécessaires et suffisantes d'observabilité de l'entrée et de l'état d'un système. Des conditions nécessaires et suffisantes pour l'observabilité forte d'une partie donnée des composantes de l'entrée et de l'état ont ensuite été établies. Le dernier résultat de cette partie concerne l'observabilité forte de tout l'état d'un système à entrée inconnue. Des conditions nécessaires et suffisantes ont été démontrées. <br />La seconde partie de cette thèse a consisté à étudier le problème du placement des capteurs afin de recouvrer des propriétés d'observabilité forte lorsque les conditions de la première partie ne sont pas vérifiées. Deux cas ont été traités. Le premier concerne la propriété d'observabilité forte d'une partie donnée de l'état. La stratégie de placement de capteurs consiste alors en une condition nécessaire permettant d'imposer qu'au moins une sortie du système soit sensible à chacune des composantes de l'état devant être fortement observables, puis en un système de relations graphiques, utilisé comme condition suffisante à ce qu'une configuration de capteurs assure l'observabilité forte des composantes de l'état choisies. Le second problème de placement de capteurs a pour objectif de rendre observables toutes les composantes de l'état. Le problème a été traité en trois étapes. Pour chacune d'elles, des conditions nécessaires et suffisantes sur le placement de capteurs ont été trouvées. Le nombre minimal de capteurs nécessaire et suffisant a aussi été déterminé. Les conditions trouvées sont fondées essentiellement sur des algorithmes classiques de la théorie des graphes.<br />La troisième partie traite de l'implémentation des résultats établis dans une boîte à outils dédiée à l'analyse structurelle (lisa) des systèmes linéaires et bilinéaires structurés. En premier lieu, les motivations qui ont conduit à la conception de cette boîte à outils sont exposées. La structure de lisa est ensuite présentée. Elle repose entièrement sur des algorithmes de base tels que la détermination des ensembles de successeurs et de prédécesseurs, le calcul des tailles de lien et de couplages maximaux entre deux ensembles de sommets et la caractérisation des ensembles de sommets essentiels dans des liens de taille maximale ou encore des séparateurs d'entrée et de sortie. Tous ces algorithmes ont des ordres de complexité polynomiaux. Nous avons montré comment en associant certains algorithmes de base, nous sommes arrivés à analyser l'observabilité de l'état et de l'entrée et à établir des conditions de détection et de localisation de défauts. Enfin, il est présenté des fonctions pouvant être rajoutées à lisa concernant différentes propriétés structurelles pour en faire un outil d'analyse plus complet.

.

Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

On considère la métropolisation comme un ensemble de processus, qui, depuis les années 1980, bouleversent les rapports des sociétés à leurs territoires. En particulier, ces changements ont réinterrogé le rôle du transport comme outil d‟aménagement du territoire. Les réseaux de transport présentent ainsi des aptitudes à structurer les territoires métropolitains, en permettant un fonctionnement des lieux en interaction et une appropriation de la part des individus et des sociétés qui les gèrent et les utilisent. L‟objectif de cette recherche est de construire un outil d‟aide à la décision en aménagement du territoire et politique des transports qui puisse rendre compte du potentiel que les réseaux de transports offrent à la structuration du territoire métropolitain. Dans l‟esprit de proposer une alternative au tout-automobile, le travail se concentre sur les réseaux de transport collectif. Concrètement, une démarche modélisatrice est menée et mobilise les notions d‟accessibilité et de capillarité, qui font l‟objet de mesures chiffrées. Ces indicateurs peuvent informer les décideurs sur les qualités des réseaux de transport étudiés. L‟application est menée sur les réseaux de transport collectifs des régions Nord-Pas-de-Calais et Provence-Alpes-Côte d‟Azur. Les analyses mettent en relief certains dysfonctionnements, c‟est pour y remédier que des projets d‟aménagement en matière de transport ont été simulés dans chacune des régions. Les résultats montrent comment les réseaux de transport collectif peuvent favoriser une construction métropolitaine, mais aussi leurs limites. En effet, la thèse plaide pour une conception coordonnée des politiques de transport et d‟aménagement.

Cette thèse a pour cadre l'étude de l'organisation spatiale des fibres du muscle cardiaque à partir de séries d'images tridimensionnelles acquises par IRM du Tenseur de Diffusion (IRMTD). Cette organisation constitue une propriété fondamentale du coeur sous-tendant la fonction contractile. Néanmoins elle est très complexe à obtenir au vu des difficultés inhérentes au mouvements cardiaque et respiratoire. Notre objectif consiste à développer de nouvelles approches, basées sur la prise en compte du mouvement du coeur et de la sensibilité au bruit de l'acquisition, pour l'estimation, l'analyse et la visualisation des fibres du myocarde. Dans ce cadre, mes travaux se déclinent selon trois axes principaux. Le premier compare, dans le contexte d'études cliniques ex vivo, les principales approches de régularisation opérant soit sur les images pondérées en diffusion soit sur les champs de tenseurs de diffusion. Les différences sont suffisamment faibles pour conclure que la qualité de nos données IRMTD est suffisante pour considérer toutes les méthodes de régularisation comme équivalentes. Partant de ce constat, une méthode de régularisation simple et rapide apparaî satisfaisante. Le second concerne la mise en place d'une méthode de tractographie spécialement conçue pour la spécificité cardiaque. Celle-ci est guidée par une fonctionnelle de coût globale qui permet l'estimation automatique des fibres cardiaques en une seule fois pour l'ensemble des données, et ce sans l'utilisation de points d'initialisation. Le dernier axe consiste en la distinction d'une population de fibres cardiaques en sous-groupes. Celle-ci s'appuie sur la comparaison de méthodes de classification de type géométrique et de type topologique exploitant toutes trois modes différents de représentation des fibres. Les résultats établissent que la classification pourrait permettre l'identification automatique de régions spécialisées dans le myocarde, ce qui pourrait grandement faciliter l'analyse et la comparaison des données IRMTD cardiaques pour la conception de thérapies patient-spécifiques.

Les travaux de recherche effectués dans le cadre de cette thèse concernent essentiellement la conception en avant-projet de systèmes d'usinage dédiés à la production en grande série. Lors de cette phase de conception, l'objectif principal est de trouver, pour une pièce donnée, une configuration du système d'usinage qui satisfaisait, à coût minimal, les contraintes technologiques, techniques et économiques existantes. Plusieurs problèmes combinatoires posés par cet objectif sont étudiés dans la thèse. Plus concrètement, nous nous sommes intéressés aux problèmes d'optimisation de la configuration des trois types de systèmes d'usinage suivants : machines de transfert, machines à table mobile et machines à table circulaire pivotante. Pour chacun de ces systèmes, nous avons proposé, dans un premier temps, différents modèles mathématiques. Dans un deuxième temps, nous avons développé de nombreux outils d'optimisation dédiés à leur résolution, tels que des algorithmes de calcul des bornes inférieures, des procédures de pré-traitement, des algorithmes de résolution exacte et approchée, et des approches mixtes utilisant plusieurs de ces algorithmes. Ces travaux ont permis de concevoir un prototype de logiciel destiné à supporter les différentes étapes de conception en avant projet d'un système d'usinage. Ce logiciel a été testé avec succès sur plusieurs cas industriels.