Les récents progrès réalisés en matière de communication (réseaux hauts débits, normalisation des protocoles et des architectures à objets répartis, explosion de l'internet) conduisent à l'apparition de systèmes de gestion de données et services largement répartis. Les données sont produites à la demande ou de manière continue au travers de divers dispositifs statiques ou mobiles. Cette thèse présente une approche pour l'évaluation de requêtes dites hybrides car intégrant différents aspects des données mobiles, continues, cachées rencontrées dans des environnements dynamiques. Notre approche consiste à représenter une telle requête comme une coordination de services comprenant des services de données et de calcul. Une telle coordination est définie par le flux de la requête et ceux d'opérateurs sur les données (e.g. join, select, union). Un flux de requête représente une expression construite avec les opérateurs de notre modèle de données. Ce flux est construit par un algorithme de ré-écriture à partir de la requête spécifiée dans notre langage de requête HSQL Les flux dit opérateurs composent des services de calcul afin de permettre l'évaluation d'un opérateur particulier. Le processeur de requêtes basées sur les services hybrides que nous avons développé met en mise en œuvre et valide nos propositions.

Soit un langage composé par tous les mots d'une longueur donnée $n$. Un cycle de de Bruijn d'ordre $n$ est un mot cyclique tel que tous les mots du langage apparaissent exactement une fois comme facteurs de ce cycle. Un algorithme pour construire le cycle de de Bruijn lexicographiquement minimal est dû à Fredricksen et Maiorana, il utilise les mots de Lyndon du langage. Cette thèse étudie comment généraliser le concept de cycles de de Bruijn pour un langage composé par un sous-ensemble de mots de longueur $n$, en particulier les langages de tous les mots de longueur $n$ sans facteurs dans une liste de facteurs interdits. Premièrement, nous étudions le cas des mots sans le facteur 11. Nous fournissons de nouvelles preuves de l'algorithme de Fredricksen et Maiorana qui nous permettent de prolonger ce resultat au cas des mots sans le facteur $1^i$ pour n'importe quel $i$. Nous caractérisons pour quels langages de mots de longueur $n$ existe un cycle de de Bruijn, et nous étudions également quelques propriétés de la dynamique symbolique de ces langages, en particulier des langages définis par des facteurs interdits. Pour ces genres de langages, nous présentons un algorithme pour produire un cycle de de Bruijn, en utilisant les mots de Lyndon du langage. Ces résultats utilisent la notion du graphe de de Bruijn et réduit le problème à construire un cycle eulérien dans ce graphe. Nous étudions le problème de la construction du cycle minimal dans un langage avec des facteurs interdits en employant le graphe de de Bruijn. Nous étudions deux algorithmes, un algorithme glouton simple et efficace qui fonctionne avec quelques familles de langages, et un algorithme plus complexe qui résout ce problème pour n'importe quel graphe eulérien.

De nombreux outils ont été développés pour faire évoluer au cours du temps une application et/ou sa plate-forme d'exécution en fonction de l'apparition de nouveaux besoins. Dans le cadre de Java, ils se présentent souvent sous la forme de nouveaux compilateurs manipulant un langage Java enrichi, de chargeurs de classes évolués qui modifient le code compilé de l'application afin d'ajouter à celle-ci de nouvelles propriétés, ou encore de machines virtuelles spécialisées. Cependant ces différents outils sont diffcilement combinables entre eux et/ou réutilisables en dehors de leur contexte. C'est pourquoi nous proposons, dans le cadre de Java, une machine virtuelle ouverte et entièrement écrite en Java pour conserver la portabilité, capable d'évoluer au cours du temps. Elle dispose d'une architecture à composants qui s'inspire le plus fidèlement possible de la spécification de Sun Microsystems. Un composant de Corosol est une abstraction des unités fonctionnelles d'une machine virtuelle (comme le chargeur de classes ou les fils d'exécution), mais aussi des unités de stockage (comme le tas ou la pile d'exécution) et de tous les mécanismes internes liés à l'exécution (comme la résolution dynamique de méthodes). L'architecture de Corosol est décrite par des interfaces, qui spécifient les services des composants mais aussi comment ils s'intègrent dans Corosol et communiquent entre eux. Une implantation par défaut est fournie pour chaque composant. L'implantation de chaque composant peut être choisie avant le démarrage de Corosol par simple paramétrage. Cependant, l'originalité principale de notre machine virtuelle est une puissante interface d'introspection. Elle permet d'une part à l'application de consulter à tout instant les caractéristiques de sa plate-forme d'exécution afin de pouvoir s'y adapter. D'autre part, elle autorise l'application qui s'exécute à créer des composants pour la machine virtuelle à partir d'objets qui lui sont propres, et à changer les composants existants par les nouveaux, à n'importe quel moment. Notre travail a principalement consisté à définir et implanter cette interface d'introspection.

Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux. Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur , celle pour les mots de longueur inférieure à , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable. Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur aux mots de longueur inférieure à , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les -semigroupes et les -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable. Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.

L'objectif de cette thèse est de représenter les émotions spontanées et les signes multimodaux associés pour contribuer à la conception des futurs systèmes affectifs interactifs. Les prototypes actuels sont généralement limités à la détection et à la génération de quelques émotions simples et se fondent sur des données audio ou vidéo jouées par des acteurs et récoltées en laboratoire. Afin de pouvoir modéliser les relations complexes entre les émotions spontanées et leurs expressions dans différentes modalités, une approche exploratoire est nécessaire. L'approche exploratoire que nous avons choisie dans cette thèse pour l'étude de ces émotions spontanées consiste à collecter et annoter un corpus vidéo d'interviews télévisées. Ce type de corpus comporte des émotions plus complexes que les 6 émotions de base (colère, peur, joie, tristesse, surprise, dégoût). On observe en effet dans les comportements émotionnels spontanés des superpositions, des masquages, des conflits entre émotions positives et négatives. Nous rapportons plusieurs expérimentations ayant permis la définition de plusieurs niveaux de représentation des émotions et des paramètres comportementaux multimodaux apportant des informations pertinentes pour la perception de ces émotions complexes spontanées. En perspective, les outils développés durant cette thèse (schémas d'annotation, programmes de mesures, protocoles d'annotation) pourront être utilisés ultérieurement pour concevoir des modèles utilisables par des systèmes interactifs affectifs capables de détecter/synthétiser des expressions multimodales d'émotions spontanées.

Les systèmes de question- réponse monolingues ou multilingues permettent de chercher dans une grande collection de documents (de type journalistique par exemple), ou sur le Web une réponse précise à une question. Cependant, il n'y a pas d'interaction possible après la réponse : on ne peut pas demander une précision, modifier sa question. Or souvent la réponse ne peut pas être apportée directement (question trop imprécise), ou n'est pas pleinement satisfaisante pour l'utilisateur. Le sujet de la thèse proposée consiste à étendre ces travaux de manière à permettre à un utilisateur d'engager un vrai dialogue, qui ne se réduise pas à une question/une réponse, en se fondant sur le travaux menés dans le cadre du dialogue homme-machine. Le contexte de cette thèse se situe dans le prolongement des travaux menés dans le groupe LIR du LIMSI. En effet, nous travaillons depuis plusieurs années sur les systèmes de Question-Réponse, et nous avons participé à plusieurs campagnes d'évaluation, tant sur le monolingue anglais (campagne TREC-QA : http: / / t rec.nist.gov/), que sur le monolingue français (campagne EqueR-EVALDA : http: / /www.elda.org/article118.html) ou sur le multi-lingue (campagne CLEF-QA : http: / / clef- qa.itc.it /). Ces campagnes présentent l'intérêt de permettre une évaluation de nos travaux par rapport à la communauté nationale et internationale. Elles nous ont également permis d'en mesurer les limites et de définir des champs de recherche très ouverts, que ce soit au niveau de notre groupe ou des perspectives envisagées dans le cadre même de ces campagnes d'évaluation. Par ailleurs, nous avons longtemps travaillé sur les systèmes de dialogue homme-machine, plus ou moins finalisés. Le cadre des systèmes ouverts (sans tâche définie a priori) que constitue la recherche dans des grandes collections de documents ou sur le web nous permet de reprendre et d'étendre ces travaux. Le but de cette thèse est donc d'ouvrir les systèmes de question/ réponse à un dialogue au cours duquel n'importe quel sujet peut être abordé. Le point de départ est une adaptation des travaux menés en dialogue Homme-Machine dans des domaines restreints à un système de Questions-Réponses. Ces recherches ont pour finalité d'apporter des perspectives nouvelles au moteur de recherche d'information classique, à la fois en terme de précision de l'information trouvée, de volume d'information traitées et de gain de temps pour accéder à cette information.

De grands corpus oraux comprenant des accents régionaux du français deviennent aujourd'hui disponibles : leurs données offrent une bonne base pour entreprendre l'étude des accents. Les outils de traitement automatique de la parole permettent de traiter des quantités de données plus importantes que les échantillons que peuvent examiner les experts linguistes, phonéticiens ou dialectologues. La langue française est parlée dans de nombreux pays à travers le monde. Notre étude porte sur le français d'Europe continentale, excluant ainsi des territoires comme le Québec, l'Afrique francophone ou encore les départements d'Outre-Mer. Nous étudierons des accents régionaux de France, de Belgique et de Suisse romande. Quelles sont les limites géographiques à l'intérieur desquelles il est possible d'affirmer que les locuteurs ont le même accent ? La réponse à cette question n'est pas évidente. Nous avons adopté la terminologie suivante, adaptée à nos données : nous parlerons d'accent lorsque nous ferons référence à une localisation précise telle qu'une ville ou une région donnée ; nous utiliserons le terme variété pour désigner un ensemble plus vaste. Bien que de nombreuses études décrivent les particularités des accents du français, il existe moins de travaux décrivant la variation de la langue dans son ensemble, et encore moins du point de vue du traitement automatique. De nombreuses questions restent ouvertes. Combien d'accents un auditeur natif du français peut-il identifier ? Quelles performances un système automatique pourrait-il atteindre pour une tâche identique? Les indices décrits dans la littérature linguistique comme caractéristiques de certains accents peuvent-ils être mesurés de manière automatique ? Sont-ils pertinents pour différencier des variétés de français ? Découvrirons-nous d'autres indices mesurables sur nos corpus ? Ces indices pourront-ils être mis en relation avec la perception ? Au cours de notre thèse, nous avons abordé l'étude de variétés régionales du français du point de vue de la perception humaine aussi bien que de celui du traitement automatique de la parole. Traditionnellement, nombre d'études en linguistique se focalisent sur l'étude d'un accent précis. Le traitement automatique de la parole permet d'envisager l'étude conjointe de plusieurs variétés de français : nous avons voulu exploiter cette possibilité. Nous pourrons ainsi examiner ce qui diffère d'une variété à une autre, ce qui n'est pas possible lorsqu'une seule variété est décrite. Nous avons la chance d'avoir à notre disposition un système performant d'alignement automatique de la parole. Cet outil, qui permet de segmenter le flux sonore suivant une transcription phonémique, peut se révéler précieux pour l'étude de la variation. Le traitement automatique nous permet de prendre en considération plusieurs styles de parole et de nombreux locuteurs sur des quantités de données importantes par rapport à celles qui ont pu être utilisées dans des études linguistiques menées manuellement. Nous avons automatiquement extrait des caractéristiques du signal par différentes méthodes ; nous avons cherché à valider nos résultats sur deux corpus avec accents. Les paramètres que nous avons retenus ont permis de classifier automatiquement les locuteurs de nos deux corpus.

Notre travail se positionne dans la thématique du traitement automatique du langage et plus précisément des systèmes de question-réponse. Il se fonde sur la notion de justification, qu'il formalise dans un modèle faisant intervenir trois types de phénomène linguistiques : les variations paradigmatiques locales d'un terme (sémantiques, morphologiques, inférences), les liens syntagmatiques entre les constituants d'une phrase, et une composante de sémantique énonciative reliant des éléments distants (anaphores, coréférences, thématisation), dans un contexte multiphrase, aussi bien mono- que multi-documents. Nous fondons notre formalisation de la structure des justifications sur un corpus de couples question-réponse extrait de façon semi-automatique. Ensuite, nous décrivons et évaluons un programme extrayant d'articles de journaux justifications structurées. Notre programme vise à conserver au système la capacité de produire une justification structurée, tout en rendant possible l'intégration modulaire d'une grande hétérogénéité de traitements linguistiques, de nature, de niveau de granularité et de fiabilité variés.

La détection de fermeture de boucle est cruciale pour améliorer la robustesse des algorithmes de SLAM. Par exemple, après un long parcours dans des zones inconnues de l'environnement, détecter que le robot est revenu sur une position passée offre la possibilité d'accroître la précision et la cohérence de l'estimation. Reconnaître des lieux déjà cartographiés peut également être pertinent pour apporter une solution au problème de la localisation globale, ou encore pour rétablir une estimation correcte suite à un

La cryptographie est devenue indispensable afin de garantir la sécurité et l'intégrité des données transitant dans les réseaux de communication modernes. Ces deux dernières décennies, des cryptosystèmes très efficaces, sûr et riches en fonctionnalités ont été construits à partir de variétés abéliennes définies sur des corps finis. Cette thèse contribue à certains aspects algorithmiques des variétés abéliennes ordinaires touchant à leurs anneaux d'endomorphismes. Cette structure joue un rôle capital dans la construction de variétés abéliennes ayant de bonnes propriétés. Par exemple, les couplages ont récemment permis de créer de nombreuses primitives cryptographiques avancées ; construire des variétés abéliennes munies de couplages efficaces nécessite de choisir des anneaux d'endomorphismes convenables, et nous montrons qu'un plus grand nombre de tels anneaux peut être utilisé qu'on ne pourrait croire. Nous nous penchons aussi le problème inverse qu'est celui du calcul de l'anneau d'endomorphisme d'une variété abélienne donnée, et qui possède en outre plusieurs applications pratiques. Précédemment, les meilleures méthodes ne résolvaient ce problème qu'en temps exponentiel ; nous concevons ici plusieurs algorithmes de complexité sous-exponentielle pour le résoudre dans le cas ordinaire. Pour les courbes elliptiques, nous algorithmes sont très efficaces, ce que nous démontrons en attaquant des problèmes de grande taille, insolvables jusqu'à ce jour. De plus, nous bornons rigoureusement la complexité de notre algorithme sous l'hypothèse de Riemann étendue. En tant que sous-routine alternative, nous nous considérons aussi une généralisation du problème du sac à dos dans les groupes finis, et montrons comment il peut être résolu en utilisant peu de mémoire. Enfin, nous généralisons notre méthode aux variétés abélienne de dimension supérieure, ce qui nécessite davantage d'hypothèses heuristiques. Concrètement, nous développons une bibliothèque qui permet d'évaluer des isogénies entre variétés abéliennes ; en utilisant cet outil important dans notre algorithme, nous appliquons notre méthode généralisée à des exemples illustratifs et de tailles jusqu'à présent inatteignables.