Dans cette thèse, nous étudions les triangulations définies par un ensemble de points dans des espaces de topologies différentes. Nous proposons une définition générale de la triangulation de Delaunay, valide pour plusieurs classes d'espaces, ainsi qu'un algorithme de construction. Nous fournissons une implantation pour le cas particulier du tore plat tridimensionnel. Ce travail est motivé à l'origine par le besoin de logiciels calculant des triangulations de Delaunay périodiques, dans de nombreux domaines dont l'astronomie, l'ingénierie des matériaux, le calcul biomédical, la dynamique des fluides, etc. Les triangulations périodiques peuvent être vues comme des triangulations du tore plat. Nous fournissons une définition et nous développons un algorithme incrémentiel efficace pour calculer la triangulation de Delaunay dans le tore plat. L'algorithme est adapté de l'algorithme incrémentiel usuel dans R^d. Au contraire des travaux antérieurs sur les triangulations périodiques, nous évitons de maintenir plusieurs copies périodiques des points, lorsque cela est possible. Le résultat fourni par l'algorithme est toujours une triangulation du tore plat. Nous présentons une implantation de notre algorithme, à présent disponible publiquement comme un module de la bibliothèque d'algorithmes géométriques CGAL. Nous généralisons les résultats à une classe plus générale d'espaces quotients plats, ainsi qu'à des espaces quotients de courbure constante positive. Enfin, nous considérons le cas du tore double, qui est un exemple de la classe beaucoup plus riche des espaces quotients de courbure négative constante.

La conception d'une plate-forme matérielle pour un noeud de réseaux de capteurs (RdC) est un véritable défi car elle est soumise à des contraintes sévères. La consommation d'énergie est souvent considérée comme la contrainte la plus forte donnée la petite taille et les besoins d'autonomie d'un noeud. De nos jours, les noeuds s'appuient sur des microcontrôleurs (MCUs) faible consommation disponibles dans le commerce. Ces MCUs ne sont pas adaptés au contexte de RdC car ils sont basés sur une structure de calcul généraliste et ils consomment trop d'énergie par rapport au budget d'énergie d'un noeud. Dans cette thèse, nous proposons un flot de conception complet, depuis le niveau système, se basant sur le concept de micro-tâches matérielles avec coupure de la tension d'alimentation (Power Gating). Dans cette approche, l'architecture d'un noeud est constituée d'un ensemble de micro-tâches matérielles qui sont activées selon un principe événementiel, chacune étant dédiée à une tâche spécifique du système (ex. la couche MAC, le routage, etc.). Ces micro-tâches sont gérées par un ordonnanceur matériel (System Monitor) qui est automatiquement généré à partir d'une description système, dans un langage spécifique (DSL), du graphe des tâches d'un noeud de RdC. En combinant la spécialisation du matériel et la technique du power gating, nous réduisons considérablement les énergies dynamique et statique d'un noeud de RdC. Les résultats montrent que des gains en énergie dynamique de 1 à 2 ordres de grandeur sont possibles par rapport aux mises en oeuvre à base des MCUs (ex. le MSP430). De plus, des gains de 1 ordre de grandeur en énergie statique sont également obtenus grâce à l'utilisation du power gating.

Cette thèse s'intéresse dans un premier temps aux automates cellulaires réversibles, et dans un second temps aux tas de sable linéaires. Nous construisons diverses simulations reliant les automates cellulaires aux automates à partitions, en particulier celle des automates cellulaires réversibles par les automates à partitions réversibles, ce qui était une conjecture depuis 1990. Par des constructions successives, nous montrons que le ``Billiard ball model'' de Toffoli et Margolus est capable de simuler tous les automates à partitions réversibles de dimension 2. En rassemblant ces résultats, nous montrons qu'il existe des automates cellulaires réversibles capables de simuler tous les automates cellulaires réversibles de même dimension. Dans un espace linéaire, ``Tas de sable'' et ``Chip firing game'' sont équivalents. Nous portons notre attention sur le cas où les grains tombent un à un. Des motifs délimités par des signaux apparaissent au sein des configurations engendrées. Nous étudions la dynamique du système et démontrons un équivalent asymptotique. Nous étendons nos méthodes et nos résultats à d'autres types de configurations initiales. Dans chaque cas étudié, le temps parallèle est inférieur au temps séquentiel dans un rapport de l'ordre du nombre de piles mises en œuvre.

Les systèmes multi-agents (SMA) permettent à ce jour de simuler des phénomènes impliquant des entités en interactions. Ces entités peuvent représenter des experts et doivent alors utilisent des processus cognitifs de haut niveau (perception, prise de décision, raisonnement, stockage de l'information en mémoire). Depuis longtemps, la psychologie cognitive étudie ces processus cognitifs et a proposé des modèles conceptuels de la cognition humaine. L'approche « Naturalistic Decision Making » (prise de décision naturelle) et plus particulièrement RPD (Recognition-Primed-Decision), modélise la prise de décisions efficaces par des individus dans des situations complexes en fonction de leur expérience et du contexte. L'objectif de cette thèse est d'intégrer au sein d'un SMA, via l'approche Agent-Groupe-Rôle, le modèle RPD pour simuler les comportements d'experts. L'expérience des individus est stockée à l'aide d'une base de patrons. Un patron associe à une situation prototypique une décision générique. Le modèle de prise de décision qui en découle : DBP (Décision à Base de Patrons) est décomposé en quatre phases. La première ; la perception de la situation courante est basée sur des sous-ensembles flous. Ils sont employés pour transformer des données quantitatives en données qualitatives. Une phase d'appariement de la situation courante à une ou plusieurs situations prototypiques est alors lancée. Puis, le patron optimal, en fonction de critères spécifiques au profil de chaque agent, est retenu. Finalement, la décision est traduite en une action. DBP est validé par une extension du simulateur TRANS (Tractable Role Agent prototype for concurrent Navigation Systems) afin de reproduire le comportement d'experts maritimes. L'extension créée ; CogTRANS (cognitive TRANS) porte plus particulièrement sur les décisions des chefs de quart à bord de ferries et de cargos. CogTRANS permet de simuler les évitements de collisions de façon réaliste. Il offre ainsi de bonnes perspectives pour une meilleure compréhension des risques maritimes et l'amélioration d'outils pédagogiques pour l'apprentissage de la navigation.

Les recherches menées dans le cadre de mon doctorat concernent le domaine de la Traduction Automatique (TA), ou comment traduire d'une langue source vers une langue cible sans aucune intervention humaine. Mes travaux se sont plus particulièrement concentrés sur l'approche statistique de la TA qui consiste à utiliser différents modèles probabilistes appris sur des quantités importantes de corpus parallèles alignés afin de trouver la traduction la plus vraisemblable d'une phrase source. Deux problèmes étroitement liés à l'approche statistique de la TA sont abordés dans ce manuscrit : la collecte de corpus parallèles et l'estimation de modèles de traduction à partir de ces corpus. Un système de TA statistique extrait la connaissance dont il a besoin pour produire des traductions à partir de corpus parallèles dans lesquels chaque phrase source est associée à sa traduction dans la langue cible. De nombreux travaux utilisent comme corpus parallèle les actes du Parlement Européen disponibles gratuitement en différentes langues. De tels corpus ne sont pas adéquats pour la traduction de parole spontanée, c'est pourquoi j'ai décidé de construire des corpus parallèles à partir de sous-titres de films afin de construire un système de traduction plus réaliste. Les sous-titres sont des données complexes, ils ne peuvent constituer un corpus parallèle aligné dans leur état brut. Ils nécessitent une phase de pré-traitement et d'alignement. J'ai pour cela proposé une méthode originale basée sur la Programmation Dynamique qui aligne automatiquement les sous-titres. J'ai ainsi constitué une ressource importante et riche pour l'apprentissage des systèmes de TA statistique. La TA statistique repose sur l'utilisation de plusieurs modèles statistiques comme le modèle d'alignement, la table de traduction ou encore le modèle de distortion. La table de traduction est le modèle le plus indispensable à un système de TA statisque pour calculer la traduction la plus vraisemblable d'une phrase source. En effet, celle-ci donne les probabilités de traduction entre les couples de mots sources et cibles. Il existe différentes méthodes permettant l'estimation de ces tables de traduction. Elles ont habituellement recours à un alignement des mots obtenu automatiquement sur les corpus parallèles. Cette tâche d'alignement est une étape longue et fastidieuse qui fait appel à des algorithmes complexes. Le coeur de mon travail a été de repenser le problème et d'explorer de nouvelles pistes pour estimer les tables de traduction de mots et de séquences de mots, totalement différentes des méthodes état-de-l'art. J'ai proposé une approche originale basée sur le concept de triggers inter-langues qui ne nécessite aucun alignement des mots au sein des corpus parallèles. Les triggers inter-langues permettent de mettre en évidence des unités fortement corrélés en se basant sur l'Information Mutuelle. Dans notre cas les unités sont des séquences de mots sources et cibles. L'idée derrière ce concept est que si une séquence de mots sources est fortement corrélée à une séquence de mots cibles en termes d'IM, alors nous pouvons supposer que la présence de la première dans une phrase source déclenchera la présence de la seconde dans sa traduction et vice versa. J'ai proposé d'utiliser les triggers inter-langues sur les corpus parallèles dans le but de trouver les traductions possibles de séquences de mots et ainsi constituer une table de traduction. L'Information Mutuelle est une mesure de co-occurence qui se calcule simplement en un seul passage sur le corpus parallèle. Pour sélectionner les triggers interlangues, nous supposons que deux séquences sources et cibles co-occurent si elles apparaissent dans une même paire de phrases du corpus parallèle. De ce fait, ma méthode ne requiert qu'un alignement au niveau des phrases et non au niveau des mots au sein du corpus parallèle. L'utilisation des triggers inter-langues pour estimer une table de traduction rend mon approche moins complexe mais tout aussi efficace que les approches existantes. Dans un contexte de traduction mot-à-mot, la table de traduction obtenue grâce aux triggers inter-langues conduit à des traductions automatiques de meilleur qualité, en termes de score BLEU, que celles produites avec une table de traduction de mots estimée selon le modèle 3 d'IBM. Dans un contexte de traduction par groupe de mots, la table de traduction basée sur les triggers inter-langues amènent à des traductions automatiques dont le score BLEU est supérieur à 34 et proche de celui des traductions automatiques produites par une table de traduction de séquences estimées à partir de l'alignement des mots suivant les approches état-de-l'art. Mots-clés: Traduction Automatique Statistique, Triggers Inter-langues, Traduction Automatique à base de séquences

Depuis une quinzaine d'années, l'étude des enregistrements de musique de chambre se focalise sous deux points de vue distincts : la séparation de sources et la transcription polyphonique. La séparation de sources cherche à extraire des enregistrements les signaux correspondant aux instruments présents. La transcription polyphonique vise à les décrire par un ensemble de paramètres : noms des instruments, hauteurs et volumes des notes jouées, etc. Les méthodes existantes, fondées sur l'analyse spatiale et spectro-temporelle des enregistrements, fournissent des résultats satisfaisants sur des cas simples. Mais généralement leur performance se dégrade vite au-delà d'un nombre d'instruments limite ou en présence de réverbération, d'instruments de même tessiture ou de notes à intervalle harmonique. Notre hypothèse est que ces méthodes souffrent souvent de modèles de sources instrumentales trop génériques. Nous proposons d'y remédier par la création de modèles d'instruments spécifiques basés sur un apprentissage. Dans ce travail, nous justifions cette hypothèse par l'étude des informations pertinentes présentes dans les enregistrements musicaux et de leur exploitation par les méthodes existantes. Nous construisons ensuite de nouveaux modèles probabilistes d'instruments inspirés de l'Analyse en Sous-espaces Indépendants (ASI) et nous donnons quelques exemples d'instruments appris. Enfin nous appliquons ces modèles à la séparation et la transcription d'enregistrements réalistes, parmi lesquels des pistes de CD et des mélanges synthétiques convolutifs ou sous-déterminés de ces pistes.

Depuis quelques années, la plupart des constructeurs automobiles innovent en faisant appel aux techniques de la réalité virtuelle (RV). Cette approche possède un fort potentiel en termes de gain de temps et de réduction des coûts. Elle permet également d'évaluer de nouvelles approches liées au processus de conception lui-même. Cependant, un certain nombre de verrous technologiques et méthodologiques subsistent. Ils concernent en particulier (i) la simplification et la physicalisation des maquettes numériques issues des logiciels de CAO, (ii) le développement de configurations visuo-haptiques adaptées aux différentes tâches impliquées par le prototypage virtuel, et (iii) l'identification des retours sensoriels les plus pertinents, permettant à l'opérateur d'effectuer ces tâches efficacement. Un ensemble de problématiques soulevées par le service R&D de Valeo Lighting Systems (Angers) nous a conduit à traiter les trois aspects évoqués ci-dessus. Les tâches étudiées sont l'accessibilité, l'extraction et la manipulation de lampes sur prototype virtuel à l'échelle 1:1. Dans le manuscrit, nous commençons par aborder les limites du prototypage réel et les apports liés au prototypage virtuel. Ces apports sont examinés en particulier pour les phases de création et de validation des prototypes. Puis, nous présentons un état de l'art exhaustif des dispositifs d'affichage et des interfaces à retour d'effort, que nous avons classées en fonction de leur architecture mécanique et de leur support de référence. Ensuite, nous traitons la simplification et l'intégration de maquettes virtuelles ainsi que l'intégration du modèle biomécanique de l'opérateur humain. Différentes simulations permettant de valider la méthodologie d'intégration proposée sont décrites. Celles-ci sont basées sur l'utilisation de notre plate-forme de réalité virtuelle. Enfin, nous décrivons une série cohérente et progressive d'expérimentations permettant d'évaluer la pertinence et l'influence de différentes modalités sensorielles (visuelle, sonore, vibro-tactile, et kinesthésique) sur la performance humaine. L'objectif est d'identifier les avantages et inconvénients de ces retours d'information dans différentes configurations matérielles. Les résultats sont analysés via différents indicateurs de performance (temps de réalisation des tâches, précision de placement). Des données subjectives sont également recueillies via l'observation des sujets pendant l'exécution des tâches et à partir de questionnaires.

Les travaux présentés dans cette thèse portent sur le prototypage virtuel des systèmes embarqués hétérogènes. La complexité des systèmes embarqués fait qu'il est difficile de trouver une solution optimale. Ainsi, les approches adoptées par les ingénieurs reposent sur la simulation qui requiert le prototypage virtuel. L'intérêt du prototypage virtuel est de fournir des modèles exécutables de systèmes embarqués afin de les étudier du point de vue fonctionnel et non-fonctionnel. Notre contribution consiste en la définition d'une nouvelle approche à composants pour le prototypage virtuel des systèmes embarqués, appelé 42. 42 n'est pas un nouveau langage pour le développement des systèmes embarqués, mais plutôt un outil pour la description et l'assemblage de composants pour les systèmes embarqués, au niveau système. Un modèle pour le prototypage virtuel des systèmes embarqués doit prendre en compte leur hétérogénéité. Des approches comme Ptolemy proposent un catalogue de MoCCs (Models of Computation and Communication) qui peuvent être organisés en hiérarchie afin de modéliser l'hétérogénéité. 42 s'inspire de Ptolemy dans l'organisation hiérarchique de composants et de MoCCs. Cependant, les MoCCs dans 42 ne sont pas fournis sous forme de catalogue, ils sont décrits par des programmes qui manipulent un petit ensemble de primitives de base pour activer les composants et gérer les communications entre eux. Une approche à composants comme 42 requiert un formalisme de spécification de composants. Nous étudierons les moyens proposés par 42 pour décrire les composants. Nous nous intéresseront particulièrement aux contrats de contrôle de 42. 42 est indépendant de tout langage ou formalisme. Il est conçu dans l'optique d'être utilisé conjointement avec les approches existantes. Nous donnerons une preuve de concept afin de montrer l'intérêt d'utiliser 42 et les contrats de contrôle associés aux composants, conjointement avec des approches existantes.

Dans les simulations centrées individu, la variété et la cohérence du comportement des agents sont des critères importants pour le réalisme et la validité de la simulation. Dans ce travail, nous nous sommes intéressés à la prise en compte simultanée de ces deux éléments. Nous proposons un modèle de différenciation comportementale, qui se décline en un outil dont les principaux apports sont d'être générique, non-intrusif, et de permettre une conception en dehors de l'agent. Le modèle s'articule selon trois axes. Tout d'abord, il décrit les comportements des agents par des normes. Celles-ci fournissent un profil comportemental à la conception, et un contrôle de la conformité à l'exécution. Ensuite, le processus de génération des comportements permet d'autoriser la création d'agents déviants ou en violation. Il inlfue pour cela sur le déterminisme du mécanisme. Enfin, les normes peuvent être inférées à partir de simulations enregistrées ou de situations réelles, afin d'analyser les résultats des expérimentations et d'automatiser la configuration du modèle. Nous avons appliqué cet outil à la simulation de trafic dans SCANeR, l'application développée et utilisée par Renault pour ses simulateurs de conduite. Les développements réalisés au cours de la thèse introduisent dans le trafic des styles de conduite spécifiés sous forme de normes, par exemple des conducteurs prudents ou agressifs. Ils permettent ensuite de peupler l'environnement de manière automatisée. Au delà de l'amélioration subjective du réalisme, les expérimentations réalisées démontrent les apports de l'outil sur la variété et la représentativité des comportements obtenus.

Dans cette thèse, nous adoptons une approche formelle pour définir et découvrir des mappings d'inclusion probabilistes entre deux taxonomies avec une sémantique claire, dans l'optique d'échange collaboratif de documents. Nous comparons deux façons de modéliser des mappings probabilistes tout en étant compatible avec les contraintes logiques déclarées dans chaque taxonomie selon une propriété de monotonie, puis nous montrons que ces modèles sont complémentaires pour distinguer les mappings pertinents. Nous fournissons un moyen d'estimer les probabilités d'un mapping par une technique bayésienne basée sur les statistiques des extensions des classes impliquées dans le mapping. Si les ensembles d'instances sont disjoints, on utilise des classifieurs pour les fusionner. Nous présentons ensuite un algorithme de type "générer et tester" qui utilise les deux modèles de mappings pour découvrir les plus probables entre deux taxonomies. Nous menons une analyse expérimentale fouillée de ProbaMap. Nous présentons un générateur de données synthétiques qui produit une entrée contrôlée pour une analyse quantitative et qualitative sur un large spectre de situations. Nous présentons aussi deux séries de résultats d'expériences sur des données réelles : l'alignement du jeu de donnée "Directory" d'OAEI, et une comparaison pour l'alignement de Web Directories sur lesquels ProbaMap obtient de meilleurs résultats que SBI (IJCAI 2003). Les perspectives pour ces travaux consistent à concevoir un système de réponse à des requêtes probabilistes en réutilisant des mappings probabilites, et la conversion des coefficients retournés par les méthodes de matching existantes en probabilités.