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.

Le dimensionnement d'ouvrages importants, comme les centrales nucléaires sous sollicitations vibratoires ou sismiques, requiert l'étude du comportement des sols de fondation sous l'effet de chargements dynamiques intenses. Dans le but de mieux connaître les phénomènes d'amortissement du sol, un code de calcul capable de simuler la propagation d'une onde sismique de cisaillement dans un milieu dissipatif a été développé. Ce programme, fondé sur un modèle non linéaire hystérétique utilisant les algorithmes de Newmark-Wilson, Newton-Raphson et une discrétisation spatiale à pas variables, s'affranchit des difficultés liées aux discontinuités accéléromètriques. Ces simulations pourraient permettre l'identification des paramètres du sol par comparaison avec des mesures in situ.

Nucleotide sequence alignment is a method used to identify regions of similarity between organisms at the genomic level. In this thesis we focus on the alignment of millions of short sequences produced by Next-Generation Sequencing (NGS) technologies against a reference database. Particularly, we direct our attention toward the analysis of metagenomic and metatranscriptomic data, that is the DNA and RNA directly extracted for an environment. Two major challenges were confronted in our developed algorithms. First, all NGS technologies today are susceptible to sequencing errors in the form of nucleotide substitutions, insertions and deletions and error rates vary between 1-15%. Second, metagenomic samples can contain thousands of unknown organisms and the only means of identifying them is to align against known closely related species. To overcome these challenges we designed a new approximate matching technique based on the universal Levenshtein automaton which quickly locates short regions of similarity (seeds) between two sequences allowing 1 error of any type. Using seeds to detect possible high scoring alignments is a widely used heuristic for rapid sequence alignment, although most existing software are optimized for performing high similarity searches and apply exact seeds. Furthermore, we describe a new indexing data structure based on the Burst trie which optimizes the search for approximate seeds. We demonstrate the efficacy of our method in two implemented software, SortMeRNA and SortMeDNA. The former can quickly filter ribosomal RNA fragments from metatranscriptomic data and the latter performs full alignment for genomic and metagenomic data.

Attention, ce résumé comporte un peu d'ironie et d'humour. Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité importantes que la complexité de la structure combinatoire sous-jacente et en définitive d'un graphe sous-jacent. Pour prendre l'exemple des circuits booléens ou algébriques comme modèles, tout ce qui importe est la complexité du graphe orienté sous-jacent au circuit. Par modèle de calcul raisonnable, nous entendons, comme il se doit, un modèle qui étudié sur une classe de graphes standard nous donne la classe de complexité standard attendue afin de satisfaire aux règles élémentaires des tautologies. On pourrait aussi choisir comme modèles raisonnables les modèles Turing-complet (ou une autre notion de complétude plus adaptée selon les objets calculés), formalisables dans une logique simple (afin d'éviter les "tricheries" et les modèles conçus spécialement pour faire échouer la belle idée défendue). Néanmoins, cette seconde option n'étant pas sans risque, nous nous contentons de la proposer. La thèse défendue est une version un peu plus formalisée et précise mathématiquement de cette idée aux contours un peu flous et qui est donc nécessairement un peu fausse telle quelle.