Les fonds d'archives forment de grandes quantités de documents difficiles à interpréter automatiquement : les approches classiques imposent un lourd effort de conception, sans parvenir à empêcher la production d'erreurs qu'il faut corriger après les traitements. Face à ces limites, notre travail vise à améliorer la processus d'interprétation, en conservant un fonctionnement page par page, et en lui apportant des informations contextuelles extraites du fonds documentaire ou fournies par des opérateurs humains. Nous proposons une extension ciblée de la description d'une page qui permet la mise en place systématique d'échanges entre le processus d'interprétation et son environnement. Un mécanisme global itératif gère l'apport progressif d'informations contextuelles à ce processus, ce qui améliore l'interprétation. L'utilisation de ces nouveaux outils pour le traitement de documents du XVIIIe siècle a montré qu'il était facile d'intégrer nos propositions à un système existant, que sa conception restait simple, et que l'effort de correction pouvait être diminué.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

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.