Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariement.

Les travaux présentés dans cette thèse portent sur l'exécution d'applications sur les environ- nements hétérogènes et distribués que sont les grilles de calcul. Nous étudions de bout en bout le processus permettant à des utilisateurs d'exécuter des applications scientifiques complexes. Les contributions de cette thèse se situent donc à plusieurs niveaux. 1) Déploiement d'inter- giciel hiérarchique : nous proposons dans un premier temps un modèle d'exécution pour les intergiciels hiérarchiques. À partir de ce modèle, nous présentons plusieurs heuristiques pour définir automatiquement la meilleure hiérarchie en fonction des exigences des utilisateurs et du type de plate-forme. Nous évaluons la qualité de ces heuristiques en conditions réelles avec l'intergiciel Diet. 2) Partitionnement de graphe : nous proposons un algorithme distribué et auto-stabilisant pour partitionner un graphe quelconque ayant des arêtes pondérées entre les nœuds. Le partitionnement est réalisé en fonction des distances pondérées entre les nœuds et forme des grappes au sein desquelles les nœuds sont à une distance maximale k d'un nœud élu dans la grappe. 3) Ordonnancement : nous étudions l'ordonnancement de tâches indépen- dantes sous des contraintes de limitation d'utilisation des ressources. Nous définissons des formulations en programme linéaire pour résoudre ce problème dans deux cas : lorsque les tâches arrivent toutes en même temps et lorsqu'elles ont des dates d'arrivée. 4) Simulations cosmologiques : nous avons étudié le comportement d'applications nécessaires à l'exécution de workflows de simulations cosmologiques. Puis, en se basant sur l'intergiciel de grille Diet, nous avons mis en place une infrastructure complète permettant à des utilisateurs non expérimentés de soumettre facilement des simulations cosmologiques sur une grille de calcul.

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 porte sur deux thèmes : 1)Percolation et connexité sur les graphes géométriques aléatoires dits "type AB". 2)Comparaison stochastique directionnellement convexe de processus ponctuels et leurs propriétés de percolation et connexité. Dans le premier sujet, nous définissons un graphe biparti, dit "de type AB", sur deux processus ponctuels de Poisson indépendants. Cet graphe est une extension continue de graphe dit "type AB" sur une grille régulière. Nous montrons l'existence de percolation pour toute dimension supérieure à deux et nous établissons des bornes pour l'intensité critique. Dans le cas de dimensions deux, nous caractérisons exactement l'intensité critique. Pour le problème de connexité, nous étudions le modelé sur les processus ponctuels de Poisson indépendant dans le cube de volume un avec des intensités n et c_n pour une constante c > 0. Nous établissons des bornes asymptotiques presque sûres pour le seuil de connexité. 2) Le but du deuxième sujet de travail est de définir l'ordre directionnellement convexe de processus ponctuels est de lier cet ordre aux propriétés de regroupement des points de processus ponctuels et, dans un contexte applicatif, aux caractéristiques de la performance des réseaux de communication sans fil. La dernière partie de cette thèse porte sur la comparaison des intensités critiques de percolation pour les processus ponctuels ordonnés selon cet ordre et les applications de ces résultats de comparaison pour les réseaux sans fils. Nous concluons en montrant que les processus ponctuels inférieurs, selon cet ordre, à un processus ponctuel de Poisson ont une transition de phase non-triviale dans plusieurs modelés des percolation.

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.

Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. Mots clés : Optimisation Combinatoire, Polyèdres, Algorithme à Plans Coupants, Graphes

Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.

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.

Les travaux présentés dans cette thèse effectuée au LaBRI portent sur la mise en place d'une flotte de drones et le portage sur celle-ci d'applications collaboratives distribuées utilisant des communications asynchrones non sûres. Ces applications sont formalisées grâce au modèle de réétiquetage de graphes Asynchronous Dynamicity Aware Graph Relabeling System (ADAGRS) que nous proposons. Au delà des contributions théoriques, ces travaux ont débouché sur la mise en place du démonstrateur CARUS dans lequel cinq drones se partagent la surveillance d'une grille de 15 points d'incidents potentiels (au sol). Lorsqu'un drone détecte un incident, il s'en rapproche pour le traiter. Le reste de la flotte doit alors prendre en charge les points que ce drone ne traite plus.Les réorganisations nécessaires de la flotte se font en totale autonomie vis-à-vis du sol et sous hypothèse de perte éventuelle de drones et de messages.