La robustesse est un attribut spécifique de la fiabilité qui caractérise la réaction d'un système aux fautes externes. Par conséquent, le test de robustesse consiste à tester un système en présence de fautes ou dans des conditions environnementales stressantes afin d'étudier son comportement lorsqu'il évolue dans un environnement hostile. Le test de robustesse peut être soit empirique ou formel. Les méthodes d'injection de fautes sont très communément utilisées pour évaluer le degré de robustesse d'un système. Cependant, elles ne se basent sur aucun oracle de test pour valider leurs résultats. D'autre part, les méthodes formelles de test de robustesse formalisent et la génération de fautes et le processus d'analyse. Elles présentent cependant quelques limitations par rapport aux types de fautes considérées qui dépendent fortement du modèle fonctionnel du système testé. Le travail que nous présentons dans cette thèse, consiste en un ensemble de propositions qui ont pour objectif de répondre aux défis auxquels font face les approches de test de robustesse existantes. D'abord, nous proposons une approche formelle pour la spécification et la vérification du processus d'injection de fautes. Cette approche consiste à formaliser les fautes injectées par un ensemble de triplet de Hoare et ensuite d'utiliser cette spécification pour vérifier la bonne exécution des campagnes d'injections. Notre seconde contribution concerne la spécification et la vérification des propriétés de robustesse. Nous proposons de formaliser les propriétés de robustesse en utilisant une extension de la logique temporelle linéaire qui permet la spécification de contraintes temps réel (XCTL) et nous proposons un algorithme de test passif qui permet de tester la satisfiabilité de ce type de contraintes sur des traces d'exécution finies. Nous contribuons aussi par une nouvelle approche de test de robustesse. Nous proposons une approche hybride basée sur l'injection de fautes et le test passif. L'injection de fautes est utilisée pour créer des conditions environnementales stressantes, et le test passif permet de vérifier la satisfiabilité des propriétés de robustesse sur les traces d'exécution collectées. Les fautes injectées ainsi que les propriétés de robustesse sont formellement spécifiées. Nous utilisons la logique de Hoare pour la spécification des fautes et la logique XCTL pour la formalisation des propriétés de robustesse. Ce qui nous permet de vérifier à la fois le processus d'injection et les exigences de robustesse en appliquant les approches de test passives proposées dans nos contributions précédentes. Finalement, nous proposons une plateforme de modélisation et de vérification de la robustesse des services Web. Cette plateforme est en réalité une instanciation de notre approche de test de robustesse, adaptée aux services Web. Le choix des services Web est motivé par l'émergence de cette technologie qui tend progressivement à s'imposer comme un standard du paradigme de communication programme-à-programme. Ils fournissent aussi un excellent exemple de systèmes hétérogènes fortement distribués.

Notre motivation est de combler le fossé terminologique qui grandit avec la production massive de nouveaux concepts (50 quotidiens) dans divers domaines, pour lesquels les termes sont souvent inventés d'abord dans une certaine langue bien dotée, telle que l'anglais ou le français. Trouver des termes équivalents dans différentes langues est nécessaire pour de nombreuses applications, telles que la RI translingue et la TA. Cette tâche est très difficile, particulièrement pour certaines langues très utilisées telles que l'arabe, parce que (1) seule une petite proportion de nouveaux termes est correctement enregistrée par des terminologues, et pour peu de langues ; (2) des communautés spécifiques créent continuellement des termes équivalents sans les normaliser ni même les enregistrer (terminologie latente) ; (3) dans de nombreux cas, aucuns termes équivalents ne sont créés, formellement ou informellement (absence de terminologie). Cette thèse propose de remplacer le but impossible de construire d'une manière continue une terminologie à jour, complète et de haute qualité pour un grand nombre de langues par celui de construire une preterminologie, en utilisant des méthodes non conventionnelles et des contributions passives ou actives par des communautés d'internautes : extraction de termes parallèles potentiels non seulement à partir de textes parallèles ou comparables, mais également à partir des logs (traces) des visites à des sites Web tels que DSR (Route de la Soie Digitale), et à partir de données produites par des jeux sérieux. Une préterminologie est un nouveau genre de ressource lexicale qui peut être facilement construit et a une bonne couverture. Suivant en ceci une tendance croissante en lexicographie computationnelle et en TALN en général, nous représentons une préterminologie multilingue par une structure de graphe (Preterminological Multilingual Graph, MPG), où les nœuds portent des prétermes et les arcs des relations préterminologiques simples (synonymie monolingue, traduction, généralisation, spécialisation, etc.) qui sont des approximations des relations (terminologiques ou ontologiques) usuelles. Un Système complet pour Éliciter une Préterminologie (SEPT) a été développé pour construire et maintenir des MPG. Des approches passives ont été expérimentées en développant un MPG pour le site Web culturel de DSR, et un autre pour le domaine de l'onirologie arabe : les ressources produites ont atteint une bonne couverture informationnelle et linguistique. L'approche indirecte par contribution active est testée depuis 8-9 mois sur l'instance arabe du jeu sérieux JeuxDeMots.

Dans la pratique, énormément de problèmes concrets peuvent être modélisés par un graphe. Par exemple, une carte géographique est typiquement un graphe dans lequel on serait amener à chercher des chemins courts entre les villes, ou à passer par toutes les routes ou toutes les villes.... Cela explique pourquoi la théorie des graphes est certainement le domaine le plus populaire des mathématiques discrètes malgré son jeune âge....

Cette thèse relève de l'indexation et de la représentation par le contenu des données multimédias, dans le contexte spécifique de la normalisationinternationale de l'image et notamment dans le cadre du processus de standardisation MPEG-7.<br /><br />Nous proposons tout d'abord de nouvelles mesures de similarité pour les descriptions de mouvement par modèles paramétriques 2D, fondées sur une famille de fonctions distance entre les champs de vitesses. Les problèmes d'optimisation en temps de calcul, d'alignement spatio-temporel et de pondération des composantes translationnelle et homogène de mouvement sont analysés et une solution mathématique proposée, mise en oeuvre et évaluée objectivement sur les bases de test naturelle et synthétique avec vérité terrain, que nous avons constituées et qui ont été retenues pour l'évaluation des descripteurs de mouvement MPEG-7.<br /><br />Deux descripteurs de forme pour indexer des modèles 3D maillés sont ensuite proposés. Partant des propriétés d'invariance géométrique et topologique que doit satisfaire naturellement un descripteur de forme d'objet 3D maillé, nous avons tout d'abord défini le spectre de forme 3D, que nous avons proposé et promu dans le standard MPEG-7. Celui-ci exploite uniquement la structure géométrique locale d'une surface 3D, fournit une représentation très compacte, mais présente une grande sensibilité aux descriptions topologiques des maillages. En considérant la transformée de Hough 3D d'un maillage, nous avons ensuite construit le descripteur de Hough 3D optimisé, intrinsèquement invariant aux changements de connexité, rendu indépendant aux transformations géométriques et optimisé en terme de compacité de représentation, via une partition invariante aux changements de repère canonique de la sphère unité.<br /><br />Enfin, nous proposons une plate-forme d'indexation compatible MPEG-7, intégrant des outils d'annotation, de navigation, de visualisation et de requêtes par similarité, et supportant des applications comme l'archivage vidéo, la vidéo cliquable ou l'indexation MPEG-7 de la langue des signes française. L'ensemble logiciel ainsi réalisé démontre pour la première fois en grandeur réelle, pour les applications d'indexation multimédia considérées, le caractère effectivement opérationnel des schémas de description génériques, normalisés MPEG7.

Cette thèse décrit et analyse un nouvel algorithme de génération de maillages tri-dimensionnels pour des domaines bornés par des surfaces lisses ou lisses par morceaux, c'est à dire des surfaces composées d'une collection de morceaux de surfaces lisses, joints en des courbes lisses. Cet algorithme utilise un processus glouton de raffinement de Delaunay et échantillonne l'intérieur et la frontière du domaine simultanément. Les résultats sont des maillages dont la qualité est certifiée, et où la taille des éléments est contrôlée par l'intermédiaire d'un champ de taille défini par l'utilisateur. L'analyse de l'algorithme montre de plus des guaranties sur la précision de l'approximation de la frontière du domaine, à condition que les angles entre deux morceaux de surfaces lisses soient supérieurs à 90°. La levée de cette limitation importante fera partie du travail de recherche qui suivra cette thèse. Une particularité intéressante de cet algorithme est qu'il ne nécessite de connaître le domaine qu'à travers un oracle capable de décider si un point de requête est à l'intérieur ou à l'extérieur du domaine, si un segment de droite intersecte ou non la frontière, et si un triangle intersecte les courbes lisses de la frontière. De ce fait, cet algorithme est générique et peut s'appliquer dans de nombreuses circonstances, allant du maillage d'objets définis par des surfaces implicites au maillage de domaines définis par une ou plusieurs zones dans une image tri-dimensionnelle, en passant par les objets dont la surface est déjà définie par un maillage triangulaire.

Les systèmes biologiques présentent de nombreux phénomènes complexes, aux interactions encore plus complexes. La modélisation a pour but de faciliter l'étude et la compréhension des systèmes biologiques, par l'observation ou la simulation des modèles créés. Les réseaux d'interactions biomoléculaires sous-tendent ces modèles. Les travaux de thèse que nous présentons portent sur la prédiction systématique de réseaux d'interactions biomoléculaires, afin de fournir les éléments d'entrée nécessaires au processus de modélisation. Les deux thèmes centraux seront la prédiction de réseaux d'interactions protéine-protéine et l'extrapolation de voies métaboliques. Nous définissons tout d'abord un cadre formel d'extraction de graphes d'interactions dictée par des politiques, qui permet de créer des résumés intelligents à partir de jeux de données hétérogènes. Une séparation claire des tâches d'extraction et de visualisation de l'information nous permet d'exprimer différents algorithmes existants, estimant par exemple la qualité des réseaux d'interactions biomoléculaires prédits. Nous avons mis en oeuvre ce cadre formel dans le logiciel ProViz [Iragne et al., 2005]. Nous présentons par la suite, des méthodes informatiques d'extrapolation de voies métaboliques, inspirées du précédent formalisme et basées sur l'utilisation de voies de référence et sur une identification robuste d'équivalents fonctionnels. Ces méthodes nous permettent de prédire un ensemble de voies métaboliques centrales, formant la base de modèles pour des organismes dont seules les données génomiques sont disponibles. Les différents résultats, disponibles en ligne [Sherman et al., 2006] ou en cours de publication, nous permettent de valider notre approche.

Mesure du mouvement d'objets déformables - applications à la mécanique des fluides<br />Utilisation de méthodes multiéchelles à base de transformée en ondelettes

Dans cette thèse, j'étudie la manière dont les ressources lexicales basées sur l'organisation de la connaissance lexicale dans des classes qui partagent des propriétés communes (syntactiques, sémantiques, etc.) permettent le traitement automatique de la langue naturelle et en particulier la reconnaissance symbolique d'implications textuelles. Tout d'abord, je présente une approche robuste et à large couverture sur la reconnaissance de paraphrases verbales lexico-structurelle basée sur la classification de verbes anglais par Levin. Puis, je montre qu'en étendant le cadre proposé par Levin pour traiter les modèles d'inférence généraux, on obtient une classification d'adjectifs anglais qui, comparée à des approches antérieures, propose une caractérisation sémantique à grain plus fin de leurs propriétés déductives. De plus, je développe un cadre sémantique compositionnel pour assigner à des adjectifs une représentation sémantique sur la base d'une approche ontologiquement variée (Hobbs85) et qui permet ainsi l'inférence de premier ordre pour tous les types d'adjectifs, y compris les adjectifs extensionnels. Enfin, je présente un corpus de test pour l'inférence basée sur les adjectifs que j'ai développée comme ressource pour l'évaluation de systèmes de traitement automatique de l'inférence de la langue naturelle.

La modélisation des objets géométriques est incontournable dans de nombreuses disciplines et applications. L'évolution des moyens l'acquisition et de stockage a produit une hausse énorme des volumes utilisés pour stocker ces objets. La réduction des tailles de ces volumes fait l'objet de plusieurs domaines de recherches ; comme la compression, qui vise à compresser le volume au maximum, et l'élaboration de structures théoriques compactes qui minimisent la taille nécessaire à la représentation. Le but de cette thèse est de concevoir, et d'évaluer des solutions pratiques et exploitables pour représenter de<br />façon compacte les triangulations. Pour ce faire, deux issues sont explorées : modifier la représentation interne en mémoire des objets géométriques, et redéfinir les types abstraits des objets géométriques correspondants. Une première solution consiste à utiliser des indices sur une taille arbitraire de bits, au lieu des références absolues. Les gains dépendent de la taille de la triangulation, et aussi de la taille du mot mémoire de la machine. Le handicap majeur est le coût élevé de la méthode en termes de temps d'exécution. Une deuxième piste consiste à utiliser des catalogues stables. L'idée consiste à regrouper les triangles dans des micro-triangulations, et de représenter la triangulation comme un ensemble de ces micro-triangulations. Le nombre des références multiples vers les sommets, et des références réciproques entre voisins est alors nettement réduit. Les résultats sont <br />prometteurs, sachant que le temps d'exécution n'est pas dramatiquement altéré par la modification des méthodes d'accés aux triangles. Une troisième solution consiste à décomposer la triangulation en plusieurs sous-triangulations permettant ainsi de coder les références dans une sous-triangulation sur un nombre réduit de bits par rapport aux références absolues. Les résultats de cette techniques sont encourageants, et peuvent être amplifiés par d'autres techniques comme le codage relatif des références, ou le partage de l'information géométrique des sommets sur les bords entre les différentes sous-triangulations. L'élaboration de structures compactes nécessite encore plus d'intérêts, et plusieurs pistes sont à explorer pour pouvoir arriver à des solutions plus économiques en termes d'espace mémoire.

Ce document présente une vue synthétique de mes travaux de recherche menés ces cinq dernières années, au sein du LaBRI.<br />Les activités de recherche d'un enseignant-chercheur ne s'inscrivent pas souvent dans un plan de recherche soigneusement pensé. Elles évoluent en fonction de multiples impondérables, dont notamment les rencontres avec d'autres chercheurs ou encore les opportunités ``stratégiques'' de financement. De ce fait, il n'est pas toujours facile de dégager un fil conducteur qui permette de regrouper un ensemble des résultats obtenus ``au fil de l'eau'' sans avoir recours à des raccourcis un peu ``artificiels''. <br /><br />Lorsque je me suis efforcé de dégager un point commun à mes travaux, je me suis aperçu que des objets mathématiques bien particuliers n'étaient jamais très loin de mes activités: les groupes cycliques finis. En creusant un peu plus cette perception, il m'est apparu que mes travaux accordent une place considérable à des graphes élémentaires associés aux groupes cycliques, dits graphes ou encore webs.<br /><br />Ce document est donc consacré à la mise en valeur des multiples facettes de ces graphes. ``Facettes'' est ici à double sens, puisqu'une partie conséquente de mes résultats est précisément dédiée à la détermination des facettes de certains polytopes associés aux graphes!<br /><br />Sur la forme, les preuves ont été omises afin d'alléger le texte, à l'exception de quelques preuves sélectionnées pour leur brièveté et pour la pertinence du résultat qu'elles procurent. Des hyperliens pointent vers la version anglaise des preuves manquantes, telles qu'elles figurent dans le recueil d'articles en annexe. Pour faciliter également la lecture, l'index à la fin de l'ouvrage redonne toutes les principales définitions.<br /><br />Sur le fond, ce document est structuré de la manière suivante.<br /><br />Le premier chapitre est consacré aux principaux résultats connus sur les graphes parfaits. Ceci permet de définir les objets mathématiques utilisés par la suite, et de rappeler l'extraordinaire richesse conceptuelle des graphes parfaits.<br /><br />Dans le second chapitre, nous abordons un raffinement de la coloration usuelles des graphes, appelé ``coloration circulaire''. Cette coloration est à l'origine d'une généralisation récente des graphes parfaits: les ``graphes circulaires-parfaits''. Nous étudions la possibilité d'une caractérisation analogue à celles des graphes parfaits, que ce soit par sous-graphes exclus ou bien polyédrale. <br /><br />Dans le troisième chapitre, nous nous intéressons à une généralisation naturelle des webs: ``les graphes quasi-adjoints''. Il s'agit d'une sous-famille des graphes sans griffe, et à ce titre, l'étude de leur polytope des stables est de première importance.<br /><br />Dans le quatrième chapitre, nous menons des investigations directes sur le polytope des stables des graphes sans griffe.<br /><br />La conclusion est donnée dans le dernier et cinquième chapitre, qui contient également une brève présentation de quelques résultats préliminaires quant au calcul en temps polynomial du nombre circulaire-chromatique des graphes circulaires-parfaits et au calcul du nombre de stabilité des graphes quasi-adjoints. Tout repose sur l'introduction d'un nouveau polytope construit à partir des webs ...