Les systèmes de traduction automatique ont connu des progrès récents avec la prise en compte d'expressions complexes telles que " vol à main armée " ("armed robbery" en anglais). Cependant, dès que l'on sort de ces listes d'expressions figées, on retombe rapidement dans des erreurs de traduction. Par exemple, le traducteur Systran traduit " caisse centrale " par "central case" au lieu de "central fund". Cette expression aurait pu être automatiquement traduite grâce au Web. Le but de cette étude est la création d'une base bilingue français-anglais de traduction automatique d'unités lexicales complexes à partir du Web. Nous axerons notre étude sur les difficultés de traduction telles que la polysémie ou le caractère idiomatique et proposerons des traitements adaptés. Au-delà des aspects linguistiques et technologiques, nous analyserons les utilisations du Web dans le domaine de la linguistique.

Une demande croissante d'outils pour construire et décrypter des réseaux génétiques contrôlant des processus cellulaires est ressentie en biologie. Nous soutenons que l'utilisation de l'approche déclarative est pertinente et applicable pour répondre aux questions des biologistes sur ces réseaux, en général partiellement connus. L'idée principale est de modéliser des connaissances portant à la fois sur la structure et la dynamique d'un réseau par un ensemble de contraintes représentant l'ensemble des solutions, de vérifier sa cohérence, de réparer une incohérence éventuelle par un relâchement automatique, et d'inférer des propriétés sur la structure et la dynamique du réseau. Pour montrer la faisabilité de l'approche, nous formalisons les réseaux discrets de R. Thomas et les propriétés biologiques pertinentes, proposons un outil reposant sur la programmation logique par contraintes en coopération avec un solveur SAT, et la validons sur des applications biologiques significatives.

En raison de ses vulnérabilités physiques et logiques, une infrastructure critique (IC) peut subir des défaillances, et en raison des interdépendances entre IC, de simples défaillances peuvent avoir des conséquences dramatiques sur lensemble de linfrastructure. Dans notre travail, nous nous concentrons principalement sur les systèmes dinformation et de communication (lIIC : infrastructure dinformation critique) dédiés au réseau d'énergie électrique. Nous proposons une nouvelle approche pour répondre aux problèmes de sécurité que rencontre une IIC, plus particulièrement, ceux liés au contrôle d'accès et à la collaboration. Le but est doffrir à chaque organisation faisant partie de lIIC la possibilité de collaborer avec les autres, tout en maintenant un contrôle sur ses données et sa politique de sécurité internes. Nous avons modélisé, et développé PolyOrBAC, une plateforme de contrôle daccès collaboratif, basée sur le modèle de contrôle daccès OrBAC et sur la technologie des Services Web, cette plateforme est applicable dans le contexte dune infrastructure critique en général, et plus particulièrement dans le cadre dun réseau électrique.

Les forums sont des espaces de communication très utilisés sur Internet : publicset asynchrones, ils offrent une place pour exposer différents points de vue et alimenter les dé-bats ; permanents, ils gardent trace des activités passées. Leurs archives constituent une mined'informations pour la communauté qui a animé le forum ou pour des chercheurs. Elles sontsous-exploitées car la lecture à posteriori en est fastidieuse. La cohérence temporelle perdue, lecontexte de lecture est dificile à reconstituer sans une bonne connaissance préalable de l'his-toire du forum. Face au constat que les interfaces de lecture actuelles des forums, bien adaptéesà l'usage en temps réel, sont inadaptées à l'exploration des archives, nous proposons d'autresmodes de présentation. Le premier mode fait appel à des analyses statistiques sur la participa-tion au forum. Le deuxième mode propose des analyses textuelles sur le contenu des messages.La comparaison interne du lexique sans ressources externes permet des analyses robustes. L'in-teractivité avec le lecteur lui permet d'ajuster progressivement les paramètres de présentationet les ressources spécifiques pour mieux appréhender le contexte de lecture. La plate-forme Fo-rumExplor nous a permis de mettre en oeuvre ces nouvelles présentations, et de les évaluer enfonction de divers objectifs de lecture dans le contexte des jeux de rôle en ligne. D'autres expé-rimentations dans le cadre d'études de listes de diffusion d'enseignants montrent la portée et lecaractère générique d'un tel outil.

L'extraction de motifs séquentiels est devenue, depuis son introduction, une technique majeure du domaine de la fouille de données avec de nombreuses applications (analyse du comportement des consommateurs, bioinformatique, sécurité, musique, etc.). Les motifs séquentiels permettent la découverte de corrélations entre événements en fonction de leurs chronologies d'apparition. Il existe de nombreux algorithmes permettant l'extraction de tels motifs. Toutefois, ces propositions ne prennent en compte qu'une seule dimension d'analyse (e.g le produit dans les applications de type étude des achats des consommateurs) alors que la plupart des données réelles sont multidimensionnelles par nature. Dans ce manuscrit, nous définissons les motifs séquentiels multidimensionnels afin de prendre en compte les spécificités inhérentes aux bases de données multidimensionnelles (plusieurs dimensions, hiérarchies, valeurs agrégées). Nous définissons des algorithmes permettant l'extraction de motifs séquentiels multi- dimensionnels en tenant compte des ces spécificités. Des expérimentations menées sur des données synthétiques et sur des données réelles sont rapportées et montrent l'intérêt de nos propositions. Nous nous intéressons également à l'extraction de comportements temporels atypiques dans des données multidimensionnelles. Nous montrons qu'il peut y avoir plusieurs interprétations d'un comportement atypique (fait ou connaissance). En fonction de chaque interprétation, nous proposons une méthode d'extraction de tels comportements. Ces méthodes sont également validées par des expérimentations sur des données réelles.

Extraction de séquences fréquentes : des bases de données statiques aux flots de données Il est reconnu aujourd'hui que l'être humain est généralement noyé sous une profusion d'informations et que sa capacité d'analyse n'est plus capable de faire face au volume sans cesse croissant de données. C'est dans ce contexte qu'est né le processus d'Extraction de Connaissance dans les bases de Données. Un des buts de ce processus est de passer d'un grand volume d'informations à un petit ensemble de connaissances à fortes valeurs ajoutées pour l'analyste ou le décideur. De plus, le processus d'ECD n'est pas un processus monolithique et univoque au cours duquel il s'agirait d'appliquer un principe général à tous les types de données stockées ou récupérées. Ainsi, une des étapes de ce processus qu'est la fouille de données peut se dériver sous plusieurs formes tels que : le clustering, la classification, l'extraction d'itemset et de règles d'associations, l'extraction de structures plus complexes tels que les épisodes, les graphes ou comme dans le cadre de cette thèse l'extraction de motifs séquentiels. Malheureusement, dans un monde sans cesse en évolution, le contexte dans lequel les travaux d'ECD ont été définis ces dernières années considérait que les données, sur lesquelles la fouille était réalisée, étaient disponibles dans des bases de données statiques. Aujourd'hui, suite au développement de nouvelles technologies et applications associées, nous devons faire face à de nouveaux modèles dans lesquels les données sont disponibles sous la forme de flots. Une question se pose alors : quid des approches d'extraction de connaissances traditionnelles ? Dans ce mémoire, nous présentons un ensemble de résultat sur les motifs séquentiels dans les bases de données d'un point de vue des représentations condensées et des méthodes d'échantillonnage puis nous étendons nos différentes approches afin de prendre en compte le nouveau modèle des flots de données. Nous présentons des algorithmes permettant ainsi l'extraction de motifs séquentiels (classiques et multidimensionnels) sur les flots. Des expérimentations menées sur des données synthétiques et sur des données réelles sont rapportées et montrent l'intérêt de nos propositions.

Les avancées technologiques du monde du " sans fil " ont conduit au développement d'applications dédiées à l'informatique mobile. Leurs caractéristiques propres posent de nouveaux défis pour leur vérification. Ce mémoire traite de la technologie de test pour les systèmes mobiles. Nous avons débuté notre travail par un état de l'art sur le test des applications mobiles conjointement avec une analyse d'une étude de cas, un protocole d'appartenance de groupe (GMP) dans le domaine des réseaux ad hoc, pour nous permettre de mieux comprendre les problèmes liés au test de ces applications. En conséquence, nous avons décidé d'avoir une approche de test qui se base sur les descriptions de scénarios. Nous avons constaté que les scénarios d'interactions doivent tenir compte des configurations spatiales des nœuds comme un concept majeur. Afin de couvrir les nouvelles spécificités des systèmes mobiles dans les langages de descriptions, nous avons introduit des extensions qui portent essentiellement sur les relations spatio-temporelles entre nœuds et sur la communication par diffusion. Le traitement de l'aspect spatial a conduit au développement de l'outil GraphSeq. GraphSeq a pour but d'analyser des traces de test afin d'y identifier des occurrences de configurations spatiales successives décrites à partir d'un scénario abstrait. L'application de GraphSeq (support à l'implémentation des cas de test, vérification de la couverture des traces) est présentée avec les analyses des sorties d'un simulateur de mobilité et des traces d'exécution de l'étude de cas GMP.

L'équipe SCEE de Supélec travaille dans le domaine de la radio logicielle et intelligente, encore appelée Radio Cognitive (CR - Cognitive Radio). Dans cette thèse, nous avons présenté une solution pour l'analyse de visage temps réel dans un équipement de radio cognitive. Dans ce cadre particulier, nous proposons des solutions d'analyse de visage, à savoir "l'estimation de la pose et des caractéristiques faciale d'un visage inconnu orienté ". Nous proposons deux systèmes d'alignement de visages. 1) Le premier exploite un AAM 2.5D et une seule caméra. La phase d'optimisation de cet AAM est hybride: elle mixe un algorithme génétique et une descente de gradient. Notre contribution tient dans l'opérateur de descente de gradient qui travaille de concert avec l'opérateur classique de mutation : de cette manière sa présence ne pénalise pas la vitesse d'exécution du système. 2) Le second met en œuvre un AAM 2.5D mais exploite plusieurs caméras. La recherche de la meilleure solution découle également d'une approche hybride qui mixe une optimisation multi-objectifs : le NSGA-II, avec une descente de gradient. Notre contribution tient dans la proposition d'une méthode efficace pour extraire des informations concernant la pertinence de chacune des vues, ces informations sont ensuite exploitées par la descente de gradient. Des comparaisons quantitatives et qualitatives avec d'autres approches mono et multi-objectifs montrent l'intérêt de notre méthode lorsqu'il s'agit d'évaluer la pose et les traits caractéristiques d'un visage inconnu.

Ces dernières années ont connu l'avènement des réseaux sans fil, dopés par leur facilité de déploiement et par leur usage dans de multiples domaines : réseaux domestiques Wi-Fi, téléphonie mobile, réseaux ad-hoc, réseaux de capteurs, ... L'objet de cette thèse porte sur l'étude de problèmes algorithmiques directement inspirés des contraintes de fonctionnement rencontrées dans de tels réseaux, et se découpe en trois parties.<br />La première partie de nos travaux s'intéresse à l'étude du problème de la diffusion d'un message émis depuis un noeud source unique vers l'ensemble des noeuds participant au réseau. Ce problème est abordé dans plusieurs modèles de communication, qui supposent tous des émissions omnidirectionnelles à portée fixée et l'existence de phénomènes d'interférences. Il en résulte l'incapacité pour un noeud donné de garantir la réception correcte de deux transmissions voisines simultanées. Nous étudions la complexité de ce problème et proposons des stratégies de résolution exactes ou avec garantie de performance. <br />Dans une seconde partie, l'un des modèles de communication précédemment introduits sert de support à l'étude d'un autre problème algorithmique, dont l'objet est la satisfaction de requêtes de communications. Les travaux menés sur ce problème visent à établir sa complexité ainsi que les facteurs dont elle dépend. <br />La dernière partie nous amène au problème de conception de réseaux sans fil. L'objectif est d'assurer une distribution de flux depuis des noeuds sources vers des noeuds clients, en minimisant le coût de l'infrastructure déployée. Les communications établies ici à l'aide d'antennes directionnelles ne sont pas sujettes aux phénomènes d'interférences. La difficulté du problème réside dans la satisfaction de contraintes de déploiement (nombre d'antennes limitées par noeud, résistance aux pannes, ...). Nous étudions la complexité de ce problème, et proposons plusieurs méthodes de résolution exactes et approchées pour des instances de taille raisonnable.

L'étude des cycles, flots et chemins des graphes est intimement liée au développement de l'optimisation combinatoire. Dans l'introduction nous mettons en parallèle ces concepts à partir de résultats classiques, et les deux autres parties de la thèse développent les nouveaux résultats dans deux directions différentes. La première porte sur les problèmes d'existence de multiflots entiers. Plusieurs paramètres naturels s'appliquent à ces problèmes, générant plus d'une centaine de cas. Après un rappel des résultats de la littérature sous une forme synthétique, nous résolvons plusieurs problèmes ouverts. En particulier, nous montrons que trouver deux flots disjoints dans les graphes planaires est un problème NP-complet. Nous donnons aussi un algorithme polynomial pour router les digraphes planaires acycliques eulériens, lorsque le nombre de classes d'arcs de demande est fixé. Ensuite, nous nous intéressons au problème consistant à trouver une plus courte marche fermée passant par tous les sommets d'un graphe. Spéciquement, nous cherchons à caractériser les graphes pour lesquels une bonne caractérisation est donnée par des empilements d'ensembles éclatants. Nous présentons quelques résultats de nature polyédrale, puis étudions le cas des cographes et des graphes d'intervalles.