Les developpements de specifications et des preuves formelles ont pris de l'ampleur durant les dernieres decennies, elabores au sein d'une diversite de canevas, de systemes et de communautes. Cependant l'heterogeneite de ces environnements gene quelques-unes des etapes fondamentales du processus de reflexion scientifique : le partage et la reutilisation des resultats. Cette dissertation propose une methode de distribution du meme developpement formel entre de divers systemes de preuve, augmentant ainsi eur interoperabilite. es chapitres 1 et 2 presentent le cadre logique qui est employe pour centraliser les specifications et les preuves formelles. Sa principale contribution est une ariation du λµ˜ µ-calcul conçu pour supporter le eveloppement interactif de preuves. Les chapitres 3 et 4 developpent les structures de recriture et categoriques necessaire a l'expression formelle de la semantique des langages de preuve. Base sur ces premiers resultats, le chapitre 5 utilise un systeme de types pour des langages de preuve pour asseoir un propriete de surete de typage, et le chapitre 6 expose une serie de traductions des developpements centralises dans d'autres cadres formels majeurs. Entre autres, le dernier contribue a une simplification des systemes de deduction a la Frege-Hilbert. En conclusion, les chapitres 7 et 8 s'interessent aux problemes resultant de l'implementation de notre systeme de developpement centralise de preuve. Ainsi, celui-ci decrit les details du logiciel cree, et celui-la fait la presentation d'une theorie de classes qui permet l'expression finie au premier ordre de schemas d'axiomes.

Cette these traite de l'algorithmique des cartes planaires (graphes dessines dans le plan sans intersection d'aretes) et propose des procedures efficaces pour le codage, la generation aleatoire, et le dessin de plusieurs familles importantes: 3-connexes, triangulations, quadrangulations... En particulier, on decrit le premier algorithme optimal de codage des incidences faces-aretes-sommets des maillages polygonaux de topologie spherique, qui atteint la borne inferieure de 2bits par arete. En partant d'un generateur de cartes 3-connexes, on developpe un nouveau generateur aleatoire uniforme de graphes planaires dont la complexite est la meilleure connue actuellement: quadratique (en esperance) en taille exacte et lineaire (en esperance) en taille approchee. Enfin, on donne plusieurs algorithmes de dessin en lignes droites (aretes representees par des segments) de cartes planaires sur la grille. Les procedures de dessin sont a la fois tres simples a decrire et donnent les meilleures performance (en probabilite) pour le dessin de deux familles de cartes: les triangulations du carre sans 3-cycle rempli —dite irreductibles— et les quadrangulations. Pour developper les algorithmes presentes dans la these, on exploite plusieurs structures combinatoires sur les cartes (orientations specifiques, partitions en arbres couvrants...) ainsi que de nouvelles constructions bijectives.

Cette thèse développe une approche originale de l'interprétation interactive de la théorie de la démonstration en logique linéaire. À l'inverse du cadre joueur/opposant communément associé aux sémantiques des jeux pour la logique, nous proposons un modèle dans lequel les deux joueurs ont des rôles symétriques. Plus précisément, nous passons d'une situation dans laquelle un joueur tente de démontrer un énoncé tandis que l'autre tente de le réfuter à une situation dans laquelle les deux joueurs tentent de démontrer des énoncés contraires. Dans la tradition du calcul vu comme comme recherche de démonstrations, chaque étape de l'interaction est vue comme une étape de deux recherches de démonstrations orthogonales en calcul des séquents. Ce travail contribue dans une certaine mesure à formaliser les liens entre la recherche de démonstrations et la normalisation de démonstrations. Nous présentons d'abord un jeu symétrique simple pour le fragment additif de la logique linéaire, en guise d'introduction à la recherche duale de démonstrations. Nous passons ensuite à un jeu symétrique bien plus complexe pour le fragment additif et multiplicatif de la logique linéaire. Afin d'obtenir un résultat de pleine complétude, nous développons ensuite un troisième jeu à la fois symétrique et concurrent. Enfin, nous étudions quelques extensions de notre modèle.

Ce document présente une synthèse des activités de recherche que j'ai menées depuis dé- but 2002 sur les mesures non additives. J'ai choisi, par souci de clarté, de présenter en détails les résultats concernant l'interprétation et l'identication de mesures non additives obtenus dans le cadre de diverses collaborations et de ne décrire que succinctement les recherches connexes que je mène de façon moins soutenue sur la classication et la sélection de variables dans le contexte de l'analyse de données et de la modélisation statistique (cf. Annexes A et A). Les travaux sur les mesures et intégrales non additives décrits dans ce document s'organisent selon deux axes : le premier axe porte sur l'interprétation de mesures non additives dans le contexte de la théorie des jeux coopératifs et de l'aide multicritère à la décision fondée sur les intégrales non additives ; le deuxième axe concerne l'identication de mesures non additives dans le contexte de l'agrégation par intégrale de Choquet. Ces deux directions de recherche sont fortement complémentaires dans la mesure où l'utilisation d'intégrales non additives dans un contexte décisionnel nécessite, dans un premier temps, l'identication d'une mesure non additive et, dans un deuxième temps, son interprétation an de rendre le modèle de décision plus transparent pour le décideur.

Les problèmes de robustesse liés à la substitution du calcul exact sur les réels par le calcul flottant approché sont souvent un obstacle à l'implantation pratique des algorithmes géométriques. Si l'adoption du paradigme exact apporte une solution satisfaisante à ce type de problèmes pour les algorithmes ayant un résultat purement combinatoire, cette solution ne permet cependant pas de résoudre en pratique le cas des algorithmes qui réutilisent voire cascadent la construction de nouveaux objets géométriques. Cette thèse aborde le problème de l'arrondi sur la grille entière du résultat d'opérations booléennes sur des régions polygonales et propose plusieurs notions d'arrondi permettant de garantir certaines propriétés métriques et topologiques intéressantes entre le résultat exact et sa version arrondie telles que la garantie de relations d'inclusion et la préservation de la convexité du résultat. Nos méthodes sont basées sur l'utilisation de constructeurs élémentaires arrondis pour lesquels nous présentons également plusieurs algorithmes efficaces. Nous proposons enfin des tests rapides permettant la détection robuste d'intersection entre plusieurs types d'objets convexes dans le plan et dans l'espace. L'ensemble de ces solutions trouvent une application directe en CAO et en graphisme.

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.