Cette thèse aborde les difficultés de mise au point de codes multicibles - c'est-à-dire de codes dont les performances sont portables entre différentes cibles matérielles. Nous avons identifié deux principales difficultés à surmonter : l'unification de l'expression du parallélisme d'une part et la nécessité d'adapter le format de stockage des données d'autre part. Afin de mettre au point une version multicible de la bibliothèque d'algèbre linéaire Legolas++ mise au point à EDF R&D, nous avons conçu MTPS (MultiTarget Parallel Skeleton), une bibliothèque dédiée à la mise au point de codes multicible. MTPS permet d'obtenir une implémentation multicible pour les problèmes appliquant une même fonction aux différents éléments d'une collection. MTPS prend alors en charge l'adaptation du format de stockage des données en fonction de l'architecture ciblée. L'intégration des concepts de MTPS dans Legolas++ a conduit à l'obtention d'un prototype multicible de Legolas++. Ce prototype a permis de mettre au point des solveurs dont les performances sont proches de l'optimal sur différentes architectures matérielles.

Le présent travail est intégré au sein du logiciel interne de synthèse d'images, ILLUMINES. Il porte sur deux points : Les lampes de bureau, les phares de voitures, les lampadaires dans les rues, ... éclairent le plus souvent selon une direction et une portée déterminées. Nous présentons dans la première partie de la thèse une méthode permettant de simuler ce type de source lumineuse, avec une modélisation par arbre de construction, dans un environnement de tracé de rayons. Notre méthode permet de visualiser les zones éclairées par le faisceau de la source lumineuse, mais également le faisceau lui-même. La conception d'une image de synthèse s'avère, pour un non-spécialiste, une réalisation pénible et difficile. A partir d'une hiérarchie orientée objet, d'un moteur d'inférence et des techniques interactives traditionnelles, nous proposons à l'utilisateur un outil d'aide à la conception d'images de synthèse simple et efficace. Une construction par les contraintes est générée par le moteur d'inférence et rendue accessible par l'utilisation de la fonction de contrainte : poser_sur. Diverses autres fonctions de haut niveau sont proposées pour la modification de la scène : déplacer_ vers, modifier_taille, éloigner_de, rapprocher_de, ... La préservation des contraintes est effectuée par envoi de messages. Ce prototype d'interface évolué interactif a été implanté au sein du logiciel ILLUMINES et permet d'envisager ce qui est en droit de s'appeler, la conception d'images de synthèse assistée par ordinateur.

Medical images have been used to depict the anatomy or function. Their high-dimensionality and their non-linearity nature makes their analysis a challenging problem. In this thesis, we address the medical image analysis from the viewpoint of statistical learning theory. First, we examine regularization methods for analyzing MRI data. In this direction, we introduce a novel regularization method, the k-support regularized Support Vector Machine. This algorithm extends the 1 regularized SVM to a mixed norm of both '1 and '2 norms. We evaluate our algorithm in a neuromuscular disease classification task. Second, we approach the problem of graph representation and comparison for analyzing medical images. Graphs are a technique to represent data with inherited structure. Despite the significant progress in graph kernels, existing graph kernels focus on either unlabeled or discretely labeled graphs, while efficient and expressive representation and comparison of graphs with continuous high-dimensional vector labels, remains an open research problem. We introduce a novel method, the pyramid quantized Weisfeiler-Lehman graph representation to tackle the graph comparison problem for continuous vector labeled graphs. Our algorithm considers statistics of subtree patterns based on the Weisfeiler-Lehman algorithm and uses a pyramid quantization strategy to determine a logarithmic number of discrete labelings. We evaluate our algorithm on two different tasks with real datasets. Overall, as graphs are fundamental mathematical objects and regularization methods are used to control ill-pose problems, both proposed algorithms are potentially applicable to a wide range of domains.

Les techniques de planification de mouvement actuelles sont maintenant capables de résoudre des problèmes mettant en jeu des mécanismes complexes plongés au sein d'environnements encombrés. Néanmoins, l'adaptation de ces planificateurs à des scènes comprenant à la fois des obstacles statiques et des obstacles mobiles s'est avérée limitée jusqu'ici. Une des raisons en est le coût associé à la mise à jour des structures de données qui sont précalculées pour capturer la connexité de l'espace libre. Notre contribution principale concerne la proposition d'un nouveau planificateur capable de traiter des problèmes comprenant à la fois obstacles statiques et obstacles mobiles. Ce planificateur hybride combine deux grandes familles de techniques. D'une part les techniques dites PRM, initialement conçues pour résoudre des problèmes à requêtes multiples et que nous avons étendu à des problèmes de scènes dynamiques. D'autre part, de nouvelles techniques de diffusion, alors que celles-ci sont généralement dédiées aux problèmes simple requête ne nécessitant aucune opération de prétraitement. Les principaux développements accompagnant la construction de ce planificateur sont les suivants : - La proposition d'une architecture originale pour le planificateur dédié aux environnements changeants. Cette architecture inclut notamment plusieurs mécanismes dits d' "évaluation paresseuse" qui permettent de minimiser les test de collision et ainsi d'assurer de bonnes performances. - Le développement d'une nouvelle méthode de diffusion permettant de reconnecter localement certaines portions du réseau invalidées par la présence des obstacles mobiles. Cette méthode, appelée RRT à Domaine Dynamique correspond en fait une extension des planificateur bien connus à bases de RRTs. Un des intérêt propre à notre approche est d'équilibrer automatiquement deux comportements propres au planificateur : l'exploration vers des régions encore inconnues et l'affinage du modèle des régions de l'espac e déjà explorées. - Deux méthodes originales de création de réseaux cycliques qui servent à initialiser notre planificateur. La première assume que les obstacles mobiles sont confinés dans une région donnée, pour construire un réseau adapté aux différents types de changements de position possibles. La seconde est une méthode qui construit des réseaux appelés "réseaux de rétraction". A l'aide d'une structure de donnée de faible taille, cette structure parvient à capturer les différentes variétés de chemins de l'espace, à travers notamment chacune des classes d'homotopie de l'espace libre. Toutes ces méthodes sont implémentées au sein de la plate-forme de travail Move3D développée au LAAS-CNRS et sont évaluées sur différents types de systèmes mécaniques plongés au sein d'environnements 3D.

In this thesis, we presented three different methods for enumerating special subnetworks containedin a metabolic network: metabolic stories, minimal precursor sets and chemical organisations. Foreach of the three methods, we gave theoretical results, and for the two first ones, we further providedan illustration on how to apply them in order to study the metabolic behaviour of living organisms.Metabolic stories are defined as maximal directed acyclic graphs whose sets of sources and targets arerestricted to a subset of the nodes. The initial motivation of this definition was to analyse metabolomicsexperimental data, but the method was also explored in a different context. Metabolic precursor setsare minimal sets of nutrients that are able to produce metabolites of interest. We present threedifferent methods for enumerating minimal precursor sets and we illustrate the application in a studyof the metabolic exchanges in a symbiotic system. Chemical organisations are sets of metabolites thatare simultaneously closed and self-maintaining, which captures some stability feature in the

Dans cette thèse, nous explorons la complexité algorithmique de plusieurs problèmes issus de la génomique comparative, et nous apportons des solutions à certains de ces problèmes sous la forme d'algorithmes d'approximation ou paramétrés. Le dénominateur commun aux problèmes soulevés est la mise en commun d'informations génomiques provenant de plusieurs espèces dans le but de tirer des conclusions pertinentes pour l'étude de ces espèces. Les problèmes de tri par transpositions et de tri par inversions pré xes permettent de retrouver l'histoire évolutive des deux espèces. Les problèmes de distance exemplaire et de plus petite partition commune ont pour but de comparer deux génomes dans les cas algorithmiquement di ciles où chaque gène apparait avec plusieurs copies indistinguables dans le génome. En n, les problèmes d'extraction de bandes et de linéarisation visent à préciser ou corriger l'information génomique a n qu'elle soit plus pertinente pour des traitements ultérieurs. Les résultats principaux que nous présentons sont la NP-di culté des problèmes de tri (par transpositions et par inversions pré xes) dont la complexité est restée longtemps une question ouverte; une étude complète de la complexité du calcul des distances exemplaires; un algorithme paramétré pour le calcul de plus petite partition commune (avec un unique paramètre étant la taille de la partition); une étude à la fois large et approfondie des problèmes d'extraction de bandes et en n une nouvelle structure de données permettant de résoudre plus e cacement le problème de linéarisation.

Les joueurs exigeants acquièrent dès que possible une carte graphique capable de satisfaire leur soif d'immersion dans des jeux dont la précision, le réalisme et l'interactivité redoublent d'intensité au fil du temps. Depuis l'avènement des cartes graphiques dédiées au calcul généraliste, ils n'en sont plus les seuls clients. Dans un premier temps, nous analysons l'apport de ces architectures parallèles spécifiques pour des simulations physiques à grande échelle. Cette étude nous permet de mettre en avant un goulot d'étranglement en particulier limitant la performance des simulations. Partons d'un cas typique : les fissures d'une structure complexe de type barrage en béton armé peuvent être modélisées par un ensemble de particules. La cohésion de la matière ainsi simulée est assurée par les interactions entre elles. Chaque particule est représentée en mémoire par un ensemble de paramètres physiques à consulter systématiquement pour tout calcul de forces entre deux particules. Ainsi, pour que les calculs soient rapides, les données de particules proches dans l'espace doivent être proches en mémoire. Dans le cas contraire, le nombre de défauts de cache augmente et la limite de bande passante de la mémoire peut être atteinte, particulièrement en parallèle, bornant les performances. L'enjeu est de maintenir l'organisation des données en mémoire tout au long de la simulation malgré les mouvements des particules. Les algorithmes de tri standard ne sont pas adaptés car ils trient systématiquement tous les éléments. De plus, ils travaillent sur des structures denses ce qui implique de nombreux déplacements de données en mémoire. Nous proposons PaVo, un algorithme de tri dit adaptatif, c'est-à-dire qu'il sait tirer parti de l'ordre pré-existant dans une séquence. De plus, PaVo maintient des trous dans la structure, répartis de manière à réduire le nombre de déplacements mémoires nécessaires. Nous présentons une généreuse étude expérimentale et comparons les résultats obtenus à plusieurs tris renommés. La diminution des accès à la mémoire a encore plus d'importance pour des simulations à grande échelles sur des architectures parallèles. Nous détaillons une version parallèle de PaVo et évaluons son intérêt. Pour tenir compte de l'irrégularité des applications, la charge de travail est équilibrée dynamiquement par vol de travail. Nous proposons de distribuer automatiquement les données en mémoire de manière à profiter des architectures hiérarchiques. Les tâches sont pré-assignées aux cœurs pour utiliser cette distribution et nous adaptons le moteur de vol pour favoriser des vols de tâches concernant des données proches en mémoire.

Ces dernières années, les ontologies ont suscité de nombreux travaux dans le domaine du web sémantique. Elles sont utilisées pour fournir le vocabulaire sémantique permettant de rendre la connaissance du domaine disponible pour l'échange et l'interprétation au travers des systèmes d'information. Toutefois, en raison de la nature décentralisée du web sémantique, les ontologies sont très hétérogènes. Cette hétérogénéité provoque le problème de la variation de sens ou ambiguïté dans l'interprétation des entités et, par conséquent, elle empêche le partage des connaissances du domaine. L'alignement d'ontologies, qui a pour but la découverte des correspondances sémantiques entre des ontologies, devient une tâche cruciale pour résoudre ce problème d'hétérogénéité dans les applications du web sémantique. Les principaux défis dans le domaine de l'alignement d'ontologies ont été décrits dans des études récentes. Parmi eux, la sélection de mesures de similarité appropriées ainsi que le réglage de la configuration de leur combinaison sont connus pour être des problèmes fondamentaux que la communauté doit traiter. En outre, la vérification de la cohérence sémantique des correspondances est connue pour être une tâche importante. Par ailleurs, la difficulté du problème augmente avec la taille des ontologies. Pour faire face à ces défis, nous proposons dans cette thèse une nouvelle approche, qui combine différentes techniques issues des domaines de l'apprentissage automatique, d'appariement de graphes et de recherche d'information en vue d'améliorer la qualité de l'alignement d'ontologies. En effet, nous utilisons des techniques de recherche d'information pour concevoir de nouvelles mesures de similarité efficaces afin de comparer les étiquettes et les profils d'entités de contexte au niveau des entités. Nous appliquons également une méthode d'appariement de graphes appelée propagation de similarité au niveau de la structure qui découvre effectivement des correspondances en exploitant des informations structurelles des entités. Pour combiner les mesures de similarité au niveau des entités, nous transformons la tâche de l'alignement d'ontologie en une tâche de classification de l'apprentissage automatique. Par ailleurs, nous proposons une méthode dynamique de la somme pondérée pour combiner automatiquement les correspondances obtenues au niveau des entités et celles obtenues au niveau de la structure. Afin d'écarter les correspondances incohérentes, nous avons conçu une nouvelle méthode de filtrage sémantique. Enfin, pour traiter le problème de l'alignement d'ontologies à large échelle, nous proposons deux méthodes de sélection des candidats pour réduire l'espace de calcul. Toutes ces contributions ont été mises en œuvre dans un prototype nommé YAM++. Pour évaluer notre approche, nous avons utilisé des données du banc d'essai de la compétition OAEI : Benchmark, Conference, Multifarm, Anatomy, Library and Large Biomedical Ontologies. Les résultats expérimentaux montrent que les méthodes proposées sont très efficaces. De plus, en comparaison avec les autres participants à la compétition OAEI, YAM++ a montré sa compétitivité et a acquis une position de haut rang.

Actuellement, la résolution de problèmes d'optimisation sous contraintes tire rarement parti de la structure du problème trait. Or, il existe de nombreux problèmes réels fortement structurés dont la décomposition arborescente pourrait s'avérer très profitable. Les travaux menés jusqu'à présent exploitent les décompositions arborescentes uniquement dans le cadre des méthodes de recherche complète. Dans cette thèse, nous étudions l'apport des décompositions arborescentes pour les méthodes de recherche locale de type VNS (Variable Neighborhood Search), dont l'objectif est de trouver une solution de très bonne qualité en un temps limité. Cette thèse apporte trois contributions. La première est un schéma générique (DGVNS), exploitant la décomposition arborescente pour guider efficacement l'exploration de l'espace de recherche. Trois différentes stratégies visant à équilibrer l'intensification et la diversification de DGVNS sont étudiées et comparées. La seconde contribution propose deux raffinements de la décomposition arborescente. Le premier exploite la dureté des fonctions de coût pour identifier les parties du graphe de contraintes les plus difficiles à satisfaire. Le second raffinement cherche à augmenter la proportion de variables propres dans les clusters. La troisième contribution consiste en deux extensions de DGVNS qui exploitent à la fois le graphe de clusters et les séparateurs. Chaque contribution proposée est évaluée et comparée au travers d'expérimentations menées sur de multiples instances de quatre problèmes réels.

Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.