Les langages logico-fonctionnels sont des langages de programmation de très haut niveau permettant de définir dans un formalisme unifié des types de données, des fonctions et des prédicats (relations). Plusieurs propositions de langages logico-fonctionnels ont été faites mais toutes se restreignent à des calculs basés sur les termes du premier ordre. Cette restriction permet de programmer avec des types abstraits algébriques mais elle rend difficile la manipulation des structures de données du monde réel, modélisées sous la forme de graphes cycliques. L'objectif de cette thèse est donc d'introduire les graphes cycliques comme structure de données de base des langages logico-fonctionnels. Pour cela, nous voyons les programmes comme des systèmes de réécriture de graphes cycliques et nous étudions les relations de réécriture et de surréduction qu'ils induisent (sémantique opérationnelle). Une propriété importante de la réécriture concerne la confluence : elle exprime le déterminisme des calculs effectués. De nombreux résultats de confluence existent pour la réécriture de termes mais ils ne s'étendent généralement pas aux graphes cycliques. Nous mettons en évidence une classe de graphes cycliques particuliers, les graphes admissibles, pour laquelle nous donnons une preuve de confluence de la réécriture. Concernant la relation de surréduction, nous en proposons une définition puis nous montrons que ce calcul est cohérent et complet par rapport à celui de la réécriture dans le cadre des graphes admissibles. Nous étudions ensuite plusieurs stratégies de réécriture et de surréduction de graphes admissibles, c'est-à-dire des algorithmes permettant d'éliminer des calculs inutiles ou redondants. Nous montrons que nos stratégies sont optimales selon de nombreux critères dépendants des systèmes de réécriture considérés.

Nous presentons un modele de systemes de ressources partagees sur lequel nous definissons un parametre de performances fondamental : $\gamma$. Nous cherchons ensuite a etudier ce parametre de performances pour une classe de systemes stochastiques. Apres avoir presente quelques proprietes analytiques de $\gamma$, nous nous interessons a son evaluation. Les calculs exacts etant rarement possibles, nous recherchons des bornes. Plusieurs approches sont presentees. Les resultats mettent en valeur une notion importante : celle de graphe d'exclusion d'un systeme de ressources partagees. En effet, les bornes obtenues sont fonctions de quantites simples definies sur ce graphe, telles que le degre moyen ou le nombre chromatique. Nous montrons ensuite les resultats qu'apportent les bornes que nous avons trouvees pour l'estimation d'exposants de Lyapunov de matrices stochastiques dans l'algebre (max,+).

Ce travail se situe dans le domaine de l'optimisation combinatoire. Nous étudions plus particulièrement des caractérisations d'objets pour lesquels des problèmes, qui dans le cas général sont NP-complets, deviennent polynomiaux. Nous traitons d'abord le problème de la faisabilité d'un multiflot, qui possède des applications trés importantes en recherche opérationnelle. C'est à dire, étant donnée la spécification du problème, avec le réseau, les capacités et les demandes, on veut démontrer l'existence ou la non-existence d'une solution. Une façon d'aborder ce problème est de donner des conditions nécessaires et suffisantes pour l'existence d'un multiflot, comme celle connue par condition de coupe. Nous présentons la condition (CC, K_5, F_7), qui généralise la condition de coupe et "raffine" une autre condition existante, la (CC3). La structure du problème de multiflot nous permet aussi de regarder un problème étroitement associé, celui du "packing" de métriques. Nous traitons le cas des packing entiers et demi-entiers, quand la famille de métriques comprend les métriques CC3 et les métriques K_5 et F_7. Nous caractérisons la classe de graphes, et plus généralement de matroïdes, ou l'on peut trouver des packings entiers et demi-entiers, sous quelques hypothèses additionnelles. Puis nous nous intéressons aux propriétés générales des graphes h- et t-parfaits, et au problème de coloration associé. Les résultats que nous présentons donnent des bornes pour leur nombres chromatiques, et des classes qui satisfont une conjecture de Shepherd. Enfin nous présentons la hiérarchie des graphes étudiés, qui est obtenu grâce à des outils comme les graphes faiblement bipartis, les clutters binaires et les matrices à composantes 0,1. Nous clôturons ce mémoire en précisant quelques directions de recherche qui pourront donner suite à ce travail, aussi bien sur le sujet de la faisabilité des problèmes de multiflot, que sur la coloration des graphes h- et t-parfaits.

L'idée d'établir des relations entre des objets et de les représenter dans la base de connaissances d'un système informatique est le propre de toute approche en Intelligence Artificielle. Cependant, la plupart des formalismes de représentation de connaissances n'exploitent pas toute la richesse de la sémantique de ces relations, ni le comportement qui leur est associé. En recherche d'informations, les traitements de ces relations ne sont guère mieux élaborés et l'impact de leur prise en compte lors de la phase de correspondance n'a jamais été établi, même s'il reste vrai que de nombreuses approches tiennent compte de leur présence dans le document et tentent ainsi de les représenter lors du processus d'indexation. Pourtant la recherche de documents structurés ou complexes exige plus que jamais, outre un langage d'indexation robuste et expressif, la prise en charge de la sémantique des relations ainsi que leurs propriétés. À travers une étude des nouvelles exigences auxquelles la recherche d'informations d'aujourd'hui doit répondre, nous proposons un modèle d'indexation relationnel pour les documents. L'approche consiste à considérer qu'un terme d'indexation est fondé sur des concepts complexes où les connecteurs sémantiques sont vus comme des opérateurs, ou des relations permettant de construire des expressions nouvelles représentant des concepts nouveaux ou des situations nouvelles. Le modèle proposé ne se contente pas de représenter les relations, mais permet aussi d'offrir un cadre général précisant les principes généraux de manipulation de ces relations et la prise en compte de leurs propriétés dans un processus de recherche fondé sur une approche logique. Le modèle proposé comporte deux composantes: le langage de représentation des informations, permettant une approche d'indexation relationnelle, et les règles de dérivation qui, reprenant ce langage, permettent de diriger le processus de correspondance. Nous utilisons la théorie des situations comme langage de représentation et un système de dérivation de pertinence, reposant sur une axiomatisation de la notion de correspondance entre les documents et la requête pour la prise en compte des relations. Une caractéristique intéressante de ce modèle est qu'il conduit à étendre certains formalismes de représentation de connaissances par des notions utiles en recherche d'informations. Les limitations de la famille des logiques terminologiques, utilisée par ailleurs comme base formelle de l'approche d'indexation relationnelle proposée, peuvent ainsi être surmontées. Cependant, la complexité des traitements associés à cette famille de logiques empêche de les utiliser comme un modèle opérationnel. Nous proposons alors le formalisme des graphes conceptuels comme un bon compromis entre la complexité des démonstrateurs de théorèmes et la simplicité des approches algébriques. Ce formalisme est alors vu, à travers une interprétation logique adéquate, comme une implantation d'une logique terminologique étendue et du modèle d'indexation. Notre approche a été implantée sur une plate-forme de gestion de graphes conceptuels, réalisée sur le système de gestion de base de données à objets O2. Le prototype RELIEF résultant de notre expérimentation a été testé sur une collection d'images et a démontré l'applicabilité et le bien-fondé de notre approche.

Le but principal de ce manuscrit est de montrer que certaines familles de graphes sont des graphes plongeables dans l'hypercube. Un problème d'une autre nature sera traité, il concerne la partition de l'hypercube en des cycles sommet-disjoints de longueur paires. Nous prouvons que l'hypercube de dimension n peut être partitionné en k cycles sommet-disjoints si k

Dans le cadre des variétés hyperboliques, Thurston a conjecturé que toute variété hyperbolique de dimension trois connexe, orientable, complète et de volume fini possède un revêtement fini qui est fibré sur le cercle. En lien avec cette conjecture, le résultat principal de cette thèse donne des conditions suffisantes pour qu'un revêtement fini d'une variété hyperbolique M de dimension trois fibre sur le cercle, ou du moins contienne une fibre virtuelle. Soit F une surface close, orientable, plongée et proche d'une surface minimale, dans un revêtement fini M' de M et séparant M' en corps en anses. La condition pour qu'il existe une fibre virtuelle dans le complémentaire de F est donnée par une inégalité faisant intervenir le degré d du revêtement, le genre g de la surface, le nombre q de corps en anses et une constante k ne dépendant que du volume et du rayon d'injectivité de M. En appliquant ce théorème à un scindement de Heegaard de genre minimal du revêtement M', on obtient une version sous-logarithmique des conjectures de Lackenby sur le gradient de Heegaard et le gradient de Heegaard fort. Le théorème principal s'applique également dans le cadre d'une décomposition circulaire associée à une classe d'homologie non triviale. Nous obtenons par exemple des conditions suffisantes pour qu'une classe d'homologie non triviale de M corresponde à une fibration sur le cercle. Des méthodes analogues permettent aussi de donner une condition suffisante pour qu'une surface incompressible plongée dans M soit une fibre virtuelle. Enfin, nous donnons un critère pour que dans une tour de revêtements finis le premier nombre de Betti tende vers l'infini.

Cette thèse porte sur la modélisation mathématique de la contagion de défaut. Une première approche est donnée par les modèles à forme réduite, dans laquelles les occurrences de défaut son modelises par des instants d'arrivée d'un processus ponctuel marqué. On propose une approche rigoureuse de la calibration de ces modeles a partir de prix de produits dérivés de crédit, en utilisant des méthodes de projection Markovienne et de contrôle d'intensité. Une deuxième approche est celle des modèles structurels de risque de défaut: on modélis les liens économiques entre bilans des differentes entreprises comme un réseau de contreparties. Dans de tel réseau, un choc macroéconomique, qui induit des pertes initiales et le défaut de quelques institutions, peut etre amplifié par une contagion, via des cascades d'illiquidité ou d'insolvabilité, qui engendrent alors des défauts à grande échelle. Les principaux types de contagion sont l'illiquidité et l'insolvabilité. En modélisant le réseau financier par un graphe aléatoire pondéré et orienté on obtient des résultats asymptotiques pour l'amplitude de la contagion dans un grand réseau financier. On aboutit en particulier à une expression analytique pour la fraction finale de défauts en fonction des caractéristiques du réseau. Ces résultats donnent un critère de robustesse d'un grand réseau financier et peuvent s'appliquer dans le cadre des stress tests effectués par les régulateurs. Enfin, on étudie la taille et la dynamique des cascades d'illiquidité dans les marchés de gré a gré et l'impact, en terme de risque systémique, dû à l'introduction d'une chambre de compensation pour les Credit default swaps (CDS).

L'espace et le temps sont des concepts indissociables et nécessaires à l'analyse de l'évolution d'entités spatio-temporelles. Modéliser ces évolutions passe par la détection des changements et des relations qui modifient et caractérisent ces entités. Ces changements sont en particulier caractérisés par des modifications liées à la position, à l'empreinte spatiale de ces entités, ou même à leur identité. Une modélisation spatio-temporelle nécessite le développement de solutions de représentation qui permettent d'identifier et d'étudier les processus mis en jeu, leurs causes et leurs conséquences. Le fait que la représentation formelle et informatique d'un phénomène entraîne une description plus ou moins simplifiée de la réalité, implique qu'une telle modélisation retienne le niveau de détail disponible et/ou souhaité de cette description. Idéalement, il devrait être possible d'étudier un phénomène à plusieurs niveaux de granularité dans l'espace et dans le temps. Si de nombreux modèles et approches ont été proposés pour modéliser des évolutions d'entités au sein de phénomènes spatio-temporels, aucun ne permet de disposer d'une structure de représentation permettant de saisir complètement la sémantique de ces applications. Cette recherche propose un modèle de graphe spatio-temporel qui permet de caractériser les principales propriétés de l'évolution d'entités spatiales. Nous distinguons dans ce cadre plusieurs concepts structurants comme les notions d'identité et de relations à travers les dimensions spatiales et temporelles. Pour un temps donné, nous catégorisons les relations spatiales et de filiation et, à travers le temps, les filiations temporelles et les relations spatio-temporelles. Les structures de graphe émergeantes permettent non seulement de caractériser l'évolution d'un ensemble d'entités spatiales, mais aussi de découvrir de nouvelles propriétés. Des fonctions de manipulation de graphe sont développées et appliquées au modèle de graphe spatiotemporel. Ces fonctions identifient des processus génériques ( e.g. vie et mort d'une entité) ou liés à une application spécifique et à sa sémantique. Afin de combiner plusieurs sources d'informations au sein d'un même graphe, des fonctions de jointure permettent l'intégration de plusieurs graphes au sein d'une représentation unifiée. Les propriétés des graphes ainsi constitués et le rôle des différentes entités présentes au sein de ces graphes sont étudiés par une qualification des différents types de routes les reliant. La consistance du modèle de graphe spatio-temporel est abordée à partir d'un algorithme de vérification de contraintes. Nous faisons la différence entre les contraintes de domaine intrinsèques au modèle de graphe, et les contraintes sémantiques dépendantes d'une application en particulier. Une extension de la démarche de modélisation est réalisée à partir d'une structure basée sur les bigraphes qui permet de représenter explicitement un phénomène spatio-temporel selon plusieurs niveaux de granularité spatiale.

Cette thèse s'intéresse aux réseaux de confusion comme représentation compacte et structurée des hypothèses multiples produites par un moteur de reconnaissance de parole et transmises à un module de post-traitement applicatif. Les réseaux de confusion (CN pour Confusion Networks) sont générés à partir des graphes de mots et structurent l'information sous la forme d'une séquence de classes contenant des hypothèses de mots en concurrence. Le cas d'usage étudié dans ces travaux est celui des hypothèses de reconnaissance transmises à un module de compréhension de la parole dans le cadre d'une application de dialogue déployée par France Telecom. Deux problématiques inhérentes à ce contexte applicatif sont soulevées. De façon générale, un système de dialogue doit non seulement reconnaître un énoncé prononcé par un utilisateur, mais aussi l'interpréter afin de déduire sons sens. Du point de vue de l'utilisateur, les performances perçues sont plus proches de celles de la chaîne complète de compréhension que de celles de la reconnaissance vocale seule. Ce sont ces performances que nous cherchons à optimiser. Le cas plus particulier d'une application déployée implique de pouvoir traiter des données réelles et donc très variées. Un énoncé peut être plus ou moins bruité, dans le domaine ou hors-domaine, couvert par le modèle sémantique de l'application ou non, etc. Étant donnée cette grande variabilité, nous posons la question de savoir si le fait d'appliquer les mêmes traitements sur l'ensemble des données, comme c'est le cas dans les approches classiques, est une solution adaptée. Avec cette double perspective, cette thèse s'attache à la fois à enrichir l'algorithme de construction des CNs dans le but d'optimiser globalement le processus de compréhension et à proposer une stratégie adéquate d'utilisation des réseaux de confusion dans le contexte d'une application réelle. Après une analyse des propriétés de deux approches de construction des CNs sur un corpus de données réelles, l'algorithme retenu est celui du "pivot". Nous en proposons une version modifiée et adaptée au contexte applicatif en introduisant notamment un traitement différencié des mots du graphe qui privilégie les mots porteurs de sens. En réponse à la grande variabilité des énoncés à traiter dans une application déployée, nous proposons une stratégie de décision à plusieurs niveaux qui vise à mieux prendre en compte les spécificités des différents types d'énoncés. Nous montrons notamment qu'il est préférable de n'exploiter la richesse des sorties multiples que sur les énoncés réellement porteurs de sens. Cette stratégie permet à la fois d'optimiser les temps de calcul et d'améliorer globalement les performances du système

Cette thèse est consacrée à l'étude de trois modèles combinatoires intervenant dans la théorie des probabilités. Nous nous intéressons tout d'abord à la hauteur d'arbres de fragmentation. À mesure de dislocation fixée, deux régimes bien différents peuvent apparaître selon la capacité des sommets : au-delà d'une capacité critique, les hauteurs ont même asymptotique tandis que, en deçà de ce paramètre critique, les arbres sont de plus en plus hauts à mesure que le seuil de rupture diminue. Nous présentons ensuite des résultats obtenus avec Nicolas Curien sur le quadtree. Nous explicitons les comportements asymptotiques des coûts moyens des requêtes partielles. La théorie des fragmentations joue encore un rôle clé. Nous étudions enfin les grands graphes aléatoires, critiques pour le modèle de configuration. Sous certaines hypothèses, nous prouvons que, correctement remises à l'échelle, les suites des tailles des composantes connexes de ces graphes convergent en un certain sens vers une suite aléatoire non triviale que nous caractérisons. La situation est bien différente selon que la loi des degrés d'un sommet a un moment d'ordre 3 fini ou est une loi de puissance d'exposant compris entre 3 et 4.