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é.

La pratique quotidienne d'une activité génère un ensemble de connaissances qui se traduisent par un savoir-faire, une maîtrise, une compétence qu'une personne acquiert au cours du temps. Pour les préserver, la capitalisation des connaissances est devenue une activité essentielle dans les entreprises. Nos travaux de recherche ont pour objectif de modéliser et mettre en œuvre un système afin d'extraire et de formaliser les connaissances issues des anomalies qui surviennent dans un contexte de production industrielle et de les intégrer dans un framework facilitant la maintenance corrective et préventive. Ce framework structure la connaissance sous la forme de groupes d'anomalies. Ces groupes peuvent être rapprochés des patterns : ils représentent un problème auquel une ou plusieurs solutions sont associées. Ils ne sont pas définis a priori, c'est l'analyse des anomalies passées qui génère des groupes pertinents, qui peuvent évoluer avec l'ajout de nouvelles anomalies. Pour identifier ces patterns, supports de la connaissance, un processus complet d'extraction et de formalisation de la connaissance est suivi, Knowledge Discovery in Databases. Ce processus a été appliqué dans des domaines très variés. Nous lui donnons ici une nouvelle dimension, le traitement d'anomalies et plus particulièrement celles qui surviennent au cours de processus de production industrielle. Les étapes génériques qui le composent, depuis la simple sélection des données jusqu'à l'interprétation des patterns qui supportent les connaissances, sont considérées pour affecter à chacune un traitement spécifique pertinent par rapport à notre contexte applicatif.

Le pattern mining est un domaine du data mining dont le but est l'extraction de régularité dans les données. Ce document présente nos contributions au domaine selon 3 axes : 1. Le domaine du pattern mining est jeune et il y existe encore beaucoup de types de régularités qu'un analyste serait intéressé de découvrir mais qui ne sont pas encore gérées. Nous avons contribué à deux nouveaux types de patterns: les patterns graduels et les patterns périodiques avec "ruptures". Nous avons aussi proposé ParaMiner, un algorithme original pour le pattern mining générique, qui permet à des analystes de spécifier directement le type de patterns qui les intéressent. 2. Le pattern mining demande beaucoup de ressources de calcul. Pour réduire le temps de calcul, nous avons étudié comment exploiter le parallélisme des processeurs multicoeurs. Nos résultats montrent que des techniques classiques en pattern mining sont mal adaptées au parallélisme, et nous avons proposé des solutions. 3. Notre objectif à long terme est de rendre le pattern mining plus facile à utiliser par les analystes. Il y a beaucoup à faire dans ce but, actuellement les analystes doivent travailler sur de longues listes de millions de patterns. Nous présentons nos premiers résultats, dans le contexte de la fouille de traces d'exécution de processeurs.

Différents modes d'acquisition permettent d'obtenir des images de plusieurs gigaoctets. L'analyse de ces grandes images doit faire face à deux problèmes majeurs. Premièrement, le volume de données à traiter ne permet pas une analyse globale de l'image, d'où la difficulté d'en construire une partition. Deuxièmement, une approche multi-résolution est nécessaire pour distinguer les structures globales à faible résolution. Par exemple, dans le cadre des images d'histologie, les récentes améliorations des scanners permettent d'observer les structures cellulaires sur l'ensemble de la lame. En contrepartie, les images produites représentent jusqu'à 18 Go de données. De plus, l'agencement de ces cellules en tissus correspond à une information globale qui ne peut être observée qu'à faible résolution. Ces images combinent donc un aspect multi-échelle et multi-résolution. Dans ce manuscrit, nous définissons un modèle topologique et hiérarchique adapté à la segmentation de grandes images. Nos travaux sont fondés sur les modèles existants de carte topologique et de pyramide combinatoire. Nous présentons le modèle de carte tuilée pour la représentation de grandes partitions ainsi qu'une extension hiérarchique, la pyramide descendante tuilée, qui représente la dualité des informations multi-échelle et multi-résolution. Enfin, nous utilisons notre modèle pour la segmentation de grandes images en histologie.

Les maillages volumiques sont très répandus en informatique graphique, en visualisation scientifique et en calcul numérique. Des opérations de subdivision, de simplification ou de remaillage sont parfois utilisées afin d'accélérer les traitements sur ces maillages. Afin de maîtriser la complexité de l'objet et des traitements numériques qui lui sont appliqués, une solution consiste alors à le représenter à différentes échelles. Les modèles existants sont conçus pour des approches spécifiques rendant leur utilisation limitée aux applications pour lesquelles ils ont été pensés. Nos travaux de recherche présentent un nouveau modèle pour la représentation de maillages multirésolutions en dimension quelconque basé sur le formalisme des cartes combinatoires. Nous avons d'abord appliqué notre modèle aux volumes de subdivision multirésolutions. Dans ce cadre, nous présentons plusieurs algorithmes de raffinement d'un maillage grossier initial. Ces algorithmes supportent des hiérarchies obtenues par subdivision régulière et adaptative. Nous proposons ensuite deux représentations, opposés en terme de coût spatial et temporel, pour ce modèle.

Les formats RSS et Atom sont moins connus du grand public que le format HTML pour la publication d'informations sur le Web. Néanmoins les flux RSS sont présents sur tous les sites qui veulent publier des flux d'informations évolutives et dynamiques. Ainsi, les sites d'actualités publient des milliers de fils RSS/Atom, souvent organisés dans différentes thématiques (politique, économie, sports, société...). Chaque blog possède son propre flux RSS, et des sites de micro-blogage comme Twitter ou de réseaux sociaux comme Facebook publient les messages d'utilisateurs sous forme de flux RSS. Ces immenses quantités de sources de données continues sont accessibles à travers des agrégateurs de flux comme Google Reader, des lecteurs de messages comme Firefox, Thunderbird, mais également à travers des applications mash-up comme Yahoo! pipes, Netvibes ou Google News. Dans cette thèse, nous présentons ROSES -Really Open Simple and Efficient Syndication-, un modèle de données et un langage de requêtes continues pour des flux RSS/Atom. ROSES permet aux utilisateurs de créer des nouveaux flux personnalisés à partir des flux existants sur le web à travers un simple langage de requêtes déclaratif. ROSES est aussi un système capable de gérer et traiter des milliers de requêtes d'agrégation ROSES en parallèle et un défi principal traité dans cette thèse est le passage à l'échelle par rapport au nombre de requêtes. En particulier, on propose une nouvelle approche d'optimisation multi-requête fondée sur la factorisation des filtres similaires. Nous proposons deux algorithmes de factorisation: (i) STA, une adaptation d'un algorithme d'approximation pour calculer des arbres de Steiner minimaux [CCC+98], et (ii) VCA, un algorithme glouton qui améliore le coût CPU d'optimisation du précédant. Nous avons validé notre approche d'optimisation avec un important nombre de tests sur des données réelles.

La donnée sismique depuis sa conception (modélisation d'acquisitions sismiques), dans sa phase de traitement (prétraitement et migration) et jusqu'à son exploitation pour en extraire les informations géologiques pertinentes nécessaires à l'identification et l'exploitation optimale des réservoirs d'hydrocarbures (interprétation), génère un volume important de calculs. Lors de la phase d'imagerie, ce volume est d'autant plus important que les différentes simulations mises en jeu se veulent fidèles à la physique du sous sol. Une puissance de calcul importante est donc nécessaire pour réduire le temps, et donc le coût, des études en imagerie sismique et pour améliorer le résultat final de ces études en reproduisant plus fidèlement les phénomènes physiques mis en jeu et en considérant de plus larges plages de fréquences. Lors de la phase d'interprétation, le calcul d'attributs sismiques (type : cohérence, lissage, analyse spectrale, etc.) offre une aide de choix à l'interprétateur. Ces calculs se font usuellement selon un cycle itératif pour sélectionner les paramètres les plus adaptés. Ce cycle est rendu fastidieux par la complexité et donc le temps des calculs. L'exploitation optimale des ressources de calcul disponibles dans la station d'interprétation est nécessaire pour raccourcir ce cycle ainsi que pour la mise en œuvre d'algorithmes de traitements plus performants. Les technologies accélératrices permettent de déléguer certains types de calculs à des unités puissantes (GPGPU, FPGA, MIC) dans le cadre de plateformes hétérogènes en alternative au CPU utilisé habituellement. La puissance de calcul accessible par ce biais dépasse de plusieurs ordres de grandeur ce que peuvent proposer les architectures généralistes utilisées traditionnellement en calcul hautes performances. Ces nouvelles architectures sont une alternative très intéressante pour augmenter la puissance de calcul sans augmenter pour autant la puissance électrique consommée et thermique dissipée. Néanmoins, les contraintes d'utilisation font qu'à l'heure actuelle ces nouveaux types de calculateurs sont difficiles à programmer et à optimiser dans le cadre du calcul scientifique et conduisent à des codes dédiés à une architecture particulière. Les simulations reposant sur la résolution de l'équation des ondes en 2D ou 3D discrétisée sur des grilles (utilisées pour la modélisation et la migration sismiques), ainsi que les algorithmes de traitement d'images (utilisés lors de l'interprétation des données sismiques) sont des candidats potentiels pour une implémentation très efficace sur ces nouvelles architectures. Dans cette thèse, nous proposons une étude de l'apport, des contraintes ainsi que des limites éventuelles de ces technologies accélératrices pour l'imagerie et l'interprétation sismiques. Dans la première partie du manuscrit, après une brève introduction à l'imagerie sismique dans le premier chapitre, nous passons en revue dans le deuxième chapitre les algorithmes utilisés dans ce cadre pour mettre en exergue la complexité de ces algorithmes et les besoins en puissance de calcul qui en découlent. Nous exposons ensuite dans le chapitre 3 les différentes technologies matérielles et logicielles actuelles permettant de répondre à ces besoins. Dans la deuxième partie de ce manuscrit, nous étudions l'impact de l'utilisation des technologies accélératrices en imagerie sismique (chapitre 4) et dans le cadre de l'interprétation sismique (chapitre 5). Dans le chapitre 4, nous proposons ainsi diverses implémentations d'algorithmes utilisés en imagerie sismique reposant sur la simulation de la propagation des ondes sismiques dans le sous- sol via une discrétisation de l'équation d'onde en 2D et en 3D et sa résolution par différences finies. Nous analysons le comportement de ces implémentations sur divers types d'accélérateurs. Nous montrons qu'une prise en compte fine des ressources disponibles au niveau de l'unité de calcul (bandes passantes, capacité mémoire, organisation des données en mémoire et motifs d'accès à ses différents niveaux) est nécessaire pour tirer partie de chaque type d'architecture et au-delà de cela, de chaque génération d'une architecture donnée. De plus, les communications entre l'accélérateur et la machine hôte ont un coût qu'il est nécessaire de limiter pour ne pas pénaliser les temps de calcul. Nous proposons différentes techniques pour minimiser ces coûts et analysons leur comportement. Ces implémentations reposent sur une décomposition du domaine de simulation global, qui peut être de taille importante, en sous-domaines ce qui induit également des communications entre nœuds dans le cadre de systèmes à mémoire distribuée. Dans le chapitre 5, une étude similaire est proposée pour le calcul d'attributs sismiques. Contrairement aux algorithmes d'imagerie sismique, ce sont les ressources de la station de travail locale qui sont exploitées pour tendre vers un calcul interactif des attributs facilitant ainsi la tâche de l'interprétateur. Une implémentation performante de la transposition de cubes sismiques 3D est proposée. Elle sert de base aux algorithmes étudiés par la suite. Est étudiée ensuite une première classe d'algorithmes basés sur le calcul de la similarité entre traces sismiques voisines : cohérence, calcul de pendage ainsi qu'un algorithme innovant mis au point lors de cette étude. Les calculs sur accélérateur graphique du lissage gaussien par filtres FIR et IIR sont comparés. Des facteurs d'accélération variant entre 8 et 160 par rapport aux processeurs classiques sont reportés. Ces travaux ouvrent la voie à une intégration complète et systématique des accélérateurs de calcul tout le long du cycle de traitement des données sismiques et ce d'autant plus que nous avons démontré que cette intégration ne se fait pas aux dépends de la fiabilité et de la maintenabilité du code existant.

Nous abordons le développement d'une nouvelle génération de méthodes numériques pour la résolution des EDP évolutives qui modélisent des phénomènes multi-échelles en temps et en espace issus de divers domaines applicatifs. La raideur associée à ce type de problème, que ce soit via le terme source chimique qui présente un large spectre d'échelles de temps caractéristiques ou encore via la présence de fort gradients très localisés associés aux fronts de réaction, implique en général de sévères difficultés numériques. En conséquence, il s'agit de développer des méthodes qui garantissent la précision des résultats en présence de forte raideur en s'appuyant sur des outils théoriques solides, tout en permettant une implémentation aussi efficace. Même si nous étendons ces idées à des systèmes plus généraux par la suite, ce travail se focalise sur les systèmes de réaction-diffusion raides. La base de la stratégie numérique s'appuie sur une décomposition d'opérateur spécifique, dont le pas de temps est choisi de manière à respecter un niveau de précision donné par la physique du problème, et pour laquelle chaque sous-pas utilise un intégrateur temporel d'ordre élevé dédié. Ce schéma numérique est ensuite couplé à une approche de multirésolution spatiale adaptative permettant une représentation de la solution sur un maillage dynamique adapté. L'ensemble de cette stratégie a conduit au développement du code de simulation générique 1D/2D/3D académique MBARETE de manière à évaluer les développements théoriques et numériques dans le contexte de configurations pratiques raides issue de plusieurs domaines d'application. L'efficacité algorithmique de la méthode est démontrée par la simulation d'ondes de réaction raides dans le domaine de la dynamique chimique non-linéaire et dans celui de l'ingénierie biomédicale pour la simulation des accidents vasculaires cérébraux caractérisée par un terme source "chimique complexe''. Pour étendre l'approche à des applications plus complexes et plus fortement instationnaires, nous introduisons pour la première fois une technique de séparation d'opérateur avec pas de temps adaptatif qui permet d'atteindre une précision donnée garantie malgré la raideur des EDP. La méthode de résolution adaptative en temps et en espace qui en résulte, étendue au cas convectif, permet une description consistante de problèmes impliquant une très large palette d'échelles de temps et d'espace et des scénarios physiques très différents, que ce soit la propagation des décharges répétitives pulsées nanoseconde dans le domaine des plasmas ou bien l'allumage et la propagation de flammes dans celui de la combustion. L'objectif de la thèse est l'obtention d'un solveur numérique qui permet la résolution des EDP raides avec contrôle de la précision du calcul en se basant sur des outils d'analyse numérique rigoureux, et en utilisant des moyens de calculs standard. Quelques études complémentaires sont aussi présentées comme la parallélisation temporelle, des techniques de parallélisation à mémoire partagée et des outils de caractérisation mathématique des schémas de type séparation d'opérateur.