Comme la complexité des circuits VLSI croit, la tache de vérification des masques devient de plus en plus longue. L'utilisation des descriptions hiérarchiques permet le développement de méthodes d'analyse hiérarchique plus efficaces. Cette thèse explore une méthode de recherche géométrique par hiérarchie de Quadtrees et l'utilisation hiérarchique de l'algorithme d'équivalence union-find pour la recherche et la mise à jour des équivalences électriques. Des algorithmes hiérarchiques et géométriques utilisables pour l'édition, la vérification géométrique et topologique (connectique) de conceptions VLSI sont présentés. L'intérêt de telles méthodes dans la vérification et le compactage de ces conceptions est aussi aborde. Des quadtrees adaptatifs particuliers (mixed-quadtrees) ont été conçus et testés pour optimiser les outils conventionnels d'extraction et de vérification de la description géométrique des masques de conceptions non structurées et pour permettre une édition rapide de conceptions structurées. Ce document présente les arguments qui ont contribue à la conception d'un tel sous-systeme de recherche géométrique et topologique, le sous-système lui-même et certains algorithmes hiérarchiques. Les méthodes hiérarchiques, géométriques et topologiques ainsi explorées, sont applicables à un grand nombre de taches, comme l'extraction des conceptions, leur vérification, leur édition et leur compactage et sur des descriptions symboliques ou réelles. Ces méthodes permettent l'utilisation interactive d'un certain nombre d'algorithmes d'extraction, de vérification et d'adaptation des conceptions éditées à un ensemble de règles technologiques. Un extracteur et vérificateur géométrique et topologique de conceptions structurées est actuellement réalisé dans le but d'évaluer hiérarchiquement l'efficacité de tels algorithmes. Un aperçu des problèmes qui peuvent être résolus plus rapidement ou dans un mode interactif est également présenté

Cette recherche porte sur l'usage des outils graphiques et leur évolution dans les relations entre concepteurs et constructeurs d'objets et de systèmes techniques. Elle prend appui sur une analyse de publications et d'ouvrages scientifiques et techniques relatifs à des domaines d'activité tels que l'architecture navale, l'architecture civile, et la mécanique.<br /><br />L'étude de ces ouvrages édités entre 1750 et 1850 conduit aux développements de points de vue concernant le dessin à vue d'objet, la perspective, la géométrie descriptive et les projections orthogonales. L'architecture navale est choisie afin de tenter de cerner la place du dessin technique dans ses fonctions de description et de construction. Quant au dessin lié aux arts mécaniques, il est étudié dans ses rôles d'information, de description, de fonctionnement et de réalisation d'objets et de systèmes techniques. Les réflexions, initialement ciblées dans le contexte breton, ont vite porté sur l'espace national ; le langage étudié, par son caractère universel, ne s'accommodant pas de frontière géographique. Afin de limiter les risques d'une dispersion des recherches, la dimension internationale a été volontairement écartée.<br /><br />Il est fait état du caractère pluridisciplinaire du dessin technique et de ses exigences pour sa mise en œuvre, étant entendu qu'il constitue un carrefour avec mécanique appliquée, sciences physiques, géométrie, etc. Cette transcription sur plans de projets techniques est alors, à son tour, outil de transmission des connaissances scientifiques et technologiques et de savoir-faire technique, procédé régulièrement retenu par les savants et ingénieurs des divers domaines de productions artisanales ou industrielles. Le dessin est pièce d'un contrat associant concepteur et constructeur.<br /><br />Il est bien question de l'évolution du trait du dessinateur avec les connaissances scientifiques et techniques sous-jacentes dont il est porteur. Son art qui, en raison de l'extension des domaines de production humaine, demandera que se mette en place une formation des acteurs aux différents niveaux de qualification. Cette étude mène au seuil de l'âge d'or du dessin technique, estimé se situer entre 1850 et 1970, espace qui nous ferait alors entrer dans les bureaux d'étude où s'installent les outils informatiques dont l'usage est aujourd'hui généralisé.

Le Web 3D atteint actuellement un nouveau stade de maturité grâce à la convergence de nouvelles technologies et l'émergence de nouveaux standards permettant l'exploitation du matériel graphique depuis les navigateurs Web. Malgré l'émergence de ces technologies, nous pouvons constater une faible pénétration des contenus 3D sur le Web, due entre autre au manque d'outils de création de haut niveau facilitant la production d'interfaces graphiques 3D pour le Web. Afin de palier ce manque, nous proposons un formalisme basé sur les technologies Web permettant de définir des métaphores complètes, attractives et efficientes pour la visualisation de grands ensembles de données, ainsi que la génération des interfaces graphiques 3D correspondantes. Ce formalisme doit être flexible en termes d'extensibilité, de modularité, de généricité en ce qui concerne les formats de données en entrée et en sortie du système, ainsi qu'en terme de gamme d'interfaces graphiques 3D pouvant être définies par le concepteur d'une interface Web. Le pipeline de création que nous proposons permet la description de métaphores de visualisation d'information prenant en compte à la fois la structuration des données (la façon dont l'utilisateur explore et accède aux données), et la présentation (la géométrie et la présentation des données) et les interactions utilisateur. Les interfaces générées peuvent être de complexité variable allant des interfaces graphiques 3D immersives à l'intérieur desquelles l'utilisateur final est représenté par un avatar et peut interagir avec d'autres utilisateurs, à des interfaces graphiques 3D très simples.

Représenter l'espace est une préoccupation constante des aménageurs. Ces visualisations (carte, diagramme, plan, coupe, élévation, photographies, images de synthèse...) sont à la fois, des outils graphiques d'analyse, des outils de conception, des outils de communication assurant la nécessaire coordination entre les acteurs de l'aménagement. Parallèlement la difficulté d'intégration des connaissances sur les phénomènes sonores situés dans les projets d'aménagement est doublée d'une véritable carence dans les moyens graphiques mis à disposition pour visualiser le sonore dans un contexte construit. Réalisé à partir d'un corpus d'images pluridisciplinaire (phonétique, acoustique, musique, électroacoustique, écologie sonore, arts plastiques, photographie) l'inventaire général mis en oeuvre constitue l'essentiel de ce travail exploratoire : analyser les images en s'inspirant des méthodes de la sémiotique visuelle, synthétiser le corpus d'images sous forme d'un catalogue raisonné, classer et classifier les images. Quatre grands types de dispositifs visuels (cartographie, transcription temporelle, diagramme et perspective) sont définis comme fond support des phénomènes sonores représentables selon trois approches (flux, chose sonifère, auditum). Leurs fonctions communicatives (décrire des qualités sonores, montrer des faits sonores, expliquer des concepts sonores) sont liées à leur degré de schématisation dont nous avons relevé 4 niveaux : image indicielle de type photographique, dessin technique, croquis, schéma de principe. Réalisé à titre expérimental sur un parcours sonore urbain, le test de validité de la transcription temporelle sur fond sonagraphique (logiciel Acousmographe (INA-GRM) conçu pour la notation musicale) semble confirmer l'intérêt des emprunts d'outil de visualisation et des transferts de connaissances entre disciplines. Toutefois, des adaptations sont nécessaires pour appliquer les analyses aux différentes échelles d'écoute: objet sonore, figure sonore.

Le travail, exposé dans ce rapport, se divise en deux parties. La première partie a fait l'objet d'un rapport de recherche publié en Avril 1984 [Tall]. La deuxième partie résulte d'un travail qui s'est déroulé de juin 1984 i juin 1985. Pour produire des images de hautes qualités, on est obligé de manipuler des grandes quantités de données. D'où l' intérêt d'étudier des algorithmes et des structures de données efficaces pour résoudre ~es problèmes géométriques. On pourra ainsi obtenir des méthodes efficaces pour la manipulation de données graphiques. On peut citer i ce propos, les travaux pionners de SHAMOS dans le domaine de la complexité géométrique [Sham]. La deuxième partie contient la description d 'un logiciel interactif *de manipulation de graphes et d'ordres. A notre connaissnce, la plus ancienne réalisation de ce type de logiciel est le "Graph theory interactive system" de WOLFBERG [Wolf]. Suivant les travaux de GUIDO sur CABRI (CAhier de BRouillon Informatisé), nous desirons offrir un poste de travail sur les graphes pour des chercheurs en théorie des graphes. CABRI est une bonne approche du problème, mais reste d'un emploi malaisé. Nous avons donc étudiés de nouveau le problème en nous attachant à décrire une meilleure interface utilisateur. Nous nous sommes inspirés des travaux sur les logiciels interactif existant, comme ceux développés chez XEROX, au PALO-ALTO RESEARCH CENTER (Smit] chez NIEVERGELT [Sere].

Les algorithmes Branch and Bound (B&B) sont attractifs pour la résolution exacte de problèmes d'optimisation combinatoire (POC) par exploration d'un espace de recherche arborescent. Néanmoins, ces algorithmes sont très gourmands en temps de calcul pour des instances de problèmes de grande taille (exemple : benchmarks de Taillard pour FSP) même en utilisant le calcul sur grilles informatiques [Mezmaz et al., IEEE IPDPS'2007]. Le calcul massivement parallèle fourni à travers les plates-formes de calcul hétérogènes d'aujourd'hui [TOP500 ] est requis pour traiter effi cacement de telles instances. Le dé fi est alors d'exploiter tous les niveaux de parallélisme sous-jacents et donc de repenser en conséquence les modèles parallèles des algorithmes B&B. Dans cette thèse, nous nous attachons à revisiter la conception et l'implémentation des ces algorithmes pour la résolution de POC de grande taille sur (larges) plates-formes de calcul multi-coeurs et multi-GPUs. Le problème d'ordonnancement Flow-Shop (FSP) est considéré comme étude de cas. Une étude expérimentale préliminaire sur quelques grandes instances du FSP a révélé que l'arbre de recherche est hautement irrégulier (en forme et en taille) et très large (milliards de milliards de noeuds), et que l'opérateur d'évaluation des bornes est exorbitant en temps de calcul (environ 97% du temps de B&B). Par conséquent, notre première contribution est de proposer une approche GPU avec un seul coeur CPU (GB&B) dans laquelle seul l'opérateur d'évaluation est exécuté sur GPU. L'approche traite deux dé fis: la divergence de threads et l'optimisation de la gestion de la mémoire hiérarchique du GPU. Comparée à une version séquentielle, des accélérations allant jusqu'à ( 100) sont obtenues sur Nvidia Tesla C2050. L'analyse des performances de GB&B a montré que le surcoût induit par le transfert des données entre le CPU et le GPU est élevé. Par conséquent, l'objectif de la deuxième contribution est d'étendre l'approche (LL-GB&B) a fin de minimiser la latence de communication CPU-GPU. Cet objectif est réalisé grâce à une parallélisation à grain fin sur GPU des opérateurs de séparation et d'élagage. Le défi majeur relevé ici est la divergence de threads qui est due à la nature fortement irrégulière citée ci-dessus de l'arbre exploré. Comparée à une exécution séquentielle, LL-GB&B permet d'atteindre des accélérations allant jusqu'à ( 160) pour les plus grandes instances. La troisième contribution consiste à étudier l'utilisation combinée des GPUs avec les processeurs multi-coeurs. Deux scénarios ont été explorés conduisant à deux approches: une concurrente (RLL-GB&B) et une coopérative (PLL-GB&B). Dans le premier cas, le processus d'exploration est eff ectué simultanément par le GPU et les coeurs du CPU. Dans l'approche coopérative, les coeurs du CPU préparent et transfèrent les sous-problèmes en utilisant le streaming CUDA tandis que le GPU eff ectue l'exploration. L'utilisation combinée du multi-coeur et du GPU a montré que l'utilisation de RLL-GB&B n'est pas bénéfi que et que PLL-GB&B permet une amélioration allant jusqu'à (36%) par rapport à LL-GB&B. Sachant que récemment des grilles de calcul comme Grid5000 (certains sites) ont été équipées avec des GPU, la quatrième contribution de cette thèse traite de la combinaison du calcul sur GPU et multi-coeur avec le calcul distribué à grande échelle. Pour ce faire, les diff érentes approches proposées ont été réunies dans un méta-algorithme hétérofigène qui sélectionne automatiquement l'algorithme à déployer en fonction de la con figuration matérielle cible. Ce méta-algorithme est couplé avec l'approche B&B@Grid proposée dans [Mezmaz et al., IEEE IPDPS'2007]. B&B@Grid répartit les unités de travail (sous-espaces de recherche codés par des intervalles) entre les noeuds de la grille tandis que le méta-algorithme choisit et déploie localement un algorithme de B&B parallèle sur les intervalles reçus. L'approche combinée nous a permis de résoudre à l'optimalité et e fficacement les instances (20 20) de Taillard.

Les recherches que nous présentons dans ce mémoire s'inscrivent dans le cadre de l'intégration statistique de données post-génomiques hétérogènes. La classification non supervisée de gènes vise à regrouper en ensembles significatifs les gènes d'un organisme, vu comme un système complexe, conformément aux données expérimentales afin de dégager des actions concertées de ces gènes dans les mécanismes biologiques mis en jeu. <br /><br />Nous basons notre approche sur des modèles probabilistes graphiques. Plus spécifiquement, nous utilisons l'outil de champs de Markov cachés qui permet la prise en compte simultanée de données propres à chacun des gènes grâce a des distributions de probabilités et de données traduisant un réseau d'interaction au sein de l'organisme à l'aide d'un graphe non-orienté entre les gènes. <br /><br />Apres avoir présenté la problématique et le contexte biologique, nous décrivons le modèle utilisé ainsi que les stratégies algorithmiques d'estimation des paramètres (i.e. approximations de type champ moyen). Puis nous nous intéresserons à deux particularités des données auxquelles nous avons été confrontés et qui amènent des développements du modèle utilisé, notamment la prise en compte de l'absence de certaines observations et la haute dimensionnalité de celles-ci. Enfin nous présenterons des expériences sur données simulées ainsi que sur données réelles sur la levure qui évaluent le gain apporté par notre travail. Notamment, nous avons voulu mettre l'accent sur des interprétations biologiques plausibles des résultats obtenus.

La problématique de cette thèse se place à l'interface entre le domaine scientifique du contrôle non destructif par ultrasons (CND US) et l'adéquation algorithme architecture. Le CND US comprend un ensemble de techniques utilisées pour examiner un matériau, qu'il soit en production ou maintenance. Afin de détecter d'éventuels défauts, de les positionner et les dimensionner, des méthodes d'imagerie et de reconstruction ont été développées au CEA-LIST, dans la plateforme logicielle CIVA.L'évolution du matériel d'acquisition entraine une augmentation des volumes de données et par conséquent nécessite toujours plus de puissance de calcul pour parvenir à des reconstructions en temps interactif. L'évolution multicoeurs des processeurs généralistes (GPP), ainsi que l'arrivée de nouvelles architectures comme les GPU rendent maintenant possible l'accélération de ces algorithmes.Le but de cette thèse est d'évaluer les possibilités d'accélération de deux algorithmes de reconstruction sur ces architectures. Ces deux algorithmes diffèrent dans leurs possibilités de parallélisation. Pour un premier, la parallélisation sur GPP est relativement immédiate, contrairement à celle sur GPU qui nécessite une utilisation intensive des instructions atomiques. Quant au second, le parallélisme est plus simple à exprimer, mais l'ordonnancement des nids de boucles sur GPP, ainsi que l'ordonnancement des threads et une bonne utilisation de la mémoire partagée des GPU sont nécessaires pour obtenir un fonctionnement efficace. Pour ce faire, OpenMP, CUDA et OpenCL ont été utilisés et comparés. L'intégration de ces prototypes dans la plateforme CIVA a mis en évidence un ensemble de problématiques liées à la maintenance et à la pérennisation de codes sur le long terme.

L'adoption du langage XML dans de nombreux domaines pour la représentation des documents et des données a simplifié les manipulations associées aux documents du World Wide Web en offrant des solutions d'analyse et de traitement génériques. Ces manipulations se traduisent souvent par des opérations de transformation de la structure et du contenu des documents et jouent un rôle essentiel dans la chaîne de traitement documentaire. Les solutions existantes pour la transformation de documents XML sont pour la plupart basées sur un langage textuel, et même si certains outils proposent une interface graphique au-dessus de langages tels que XSLT, les transformations sont toujours spécifiées textuellement. L'objectif de ce travail est d'étudier l'intérêt des représentations graphiques de structures logiques et des techniques de programmation visuelle pour la visualisation et la transformation des documents et classes de documents XML. C'est dans ce cadre qu'a été conçu VXT (Visual XML Transformer), un langage de programmation visuel pour la spécification de transformations de documents XML. Cette thèse est articulée en deux parties principales : -une partie théorique, constituée dune étude des solutions existantes pour la manipulation de documents XML, dun état de lart traitant des techniques de programmation visuelle, et de la définition théorique du langage VXT, incluant une étude formelle de la syntaxe visuelle et de la fonction de traduction de programmes VXT en feuilles de transformation XSLT. -une partie pratique, dans laquelle sont détaillés les différents outils développés dans le cadre de ce travail, à savoir une boîte à outils pour la création dinterfaces graphiques zoomables et deux des applications reposant sur celle-ci et constituant le cur de ce travail : l'environnement de développement associé au langage VXT défini dans la partie précédente et IsaViz, un environnement pour la visualisation et l'édition de méta-données structurées RDF.

La technologie de numérisation des données manuscrites a atteint son essor après l'invention du stylo numérique. Les recherches se sont concentrées alors sur le développement des applications IHM qui facilitent la manipulation des données encre numérique. Dans un contexte de recherche, la technologie du papier et stylo numériques s'avère utile pour la collecte des données expérimentales dans différents domaines. Notre but est de fournir une aide pour le traitement et la visualisation des données, notamment les données temps, recueillies avec un stylo numérique dans deux cas d'usage en sciences de l'éducation à savoir les tests d'évaluation et la prise de notes d'observation. Notre démarche consiste à étudier ces cas d'usage en terme de besoin dans quatre expériences concrètes et à développer, en participation avec l'utilisateur, des prototypes de système de traitement et de visualisation des données. Dans le but de concevoir un modèle général de tel système, nous avons analysé l'interface d'utilisation des prototypes en terme de fonctionnalités, de visualisation et d'interaction. Notre modèle décrit le processus de visualisation en mettant en œuvre trois types de tâches d'utilisateur à savoir les tâches d'analyses, les tâches de manipulation et les tâches d'interaction.