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.

Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.

Dénes Kőnig est connu comme mathématicien avec ses œuvres importants sur la théorie des graphes. Avant de commencer son travail professionnel, en 1902 et en 1905 quand il était étudiant, il a successivement publié deux livres sur les récréations mathématiques en hongrois, mais ces livres ne sont pas encore beaucoup examinés par des historiens. Dans la présente thèse, j'ai traduit ces livres en anglais, et comparé le contenu avec sa monographie sur la théorie des graphes publiée en 1936. J'ai trouvé que beaucoup de problèmes traités dans le second livre sur les récréations mathématiques de 1905 ont été traités à nouveau dans la monographie de 1936, et que beaucoup de problèmes traités dans la monographie de 1936 ont déjà été traités dans le second livre de 1905. Dans ces deux publications, des mêmes problèmes étaient traités de manières différentes. Pour clarifier les rapports entre les récréations mathématiques et la théorie des graphes, j'ai analysé comment des éléments des diagrammes de la théorie des graphes et des concepts de celle-ci ont été formés dans le contexte de récréations mathématiques. J'ai trouvé que Tarry, dans sa conférence sur la géométrie de situation lors d'un congrès en 1886, a intégré certains concepts de sujets différents de récréations mathématiques, et qu'il a utilisé la même sorte de diagrammes pour examiner des problèmes des sujets différents. Les éléments des diagrammes de Tarry sont similaires à ceux utilisés dans la monographie de Kőnig de 1936, et les concepts qui y correspondent peuvent être considérés comme certaines représentations des concepts de la théorie des graphes définis dans la monographie de Kőnig de 1936.

La génomique comparative est une discipline de la biologie qui s'intéresse à l'évolution des génomes par le biais de la comparaison entre espèces de leur structure et de l'information qu'ils contiennent. Implicitement, identifier des similarités entre deux génomes revient à décrire une propriété ancestrale qu'ils partagent encore de nos jours. L'abondance de données génomiques provenant de centaines d'espèces différentes rend possible de nombreuses comparaisons de ce type, mais souvent restreinte à deux espèces comparées l'une à l'autre, hors de tout cadre unifié et sans références particulières. Ce travail de thèse décrit une nouvelle méthode, appelée AGORA (Algorithms for Gene Order Reconstruction in Ancestors), pour reconstruire de manière automatique et systématique l'ordre des gènes et les caryotypes de toutes les espèces ancestrales dans une phylogénie donnée. AGORA est capable de gérer les duplications de gènes, les délétions, et les gains, et interprète de manière réaliste des phylogénies complexes de gènes. Nous avons appliqué la méthode chez 46 espèces de vertébrés séquencées et annotées (en utilisant 8 espèces supplémentaires en référence externe) pour reconstruire des ordres de gènes ancestraux dans 43 génomes ancestraux sur près de 600 millions d'années d'évolution. Les performances d'AGORA ont été mesurées par des simulations de génomes de vertébrés, et par confrontation à des génomes ancestraux déjà connus. Les données, présentées graphiquement dans un serveur web nommé Genomicus (http://www.dyogen.ens.fr/genomicus) fournissent un nouveau cadre unifié dans lequel les génomes ancestraux peuvent servir de référence naturelle auxquelles comparer les génomes modernes qui en descendent. À ce titre, ces données fournissent une nouvelle ressource pour étudier l'évolution de l'organisation de l'information génétique dans les génomes.

Dans cette th`ese, nous proposons l'´etude d'un nouveau syst`eme de trafic a´erien, caract´eris´e par un tr`es haut degr´e d'organisation. Dans ce syst`eme, les avions sont assujettis `a suivre des points mobiles fictifs durant leur trajet. Ces points mobiles sont organis´es et s´equenc´es de fa¸con `a ´eviter les conflits entre avions, notamment lorsque ces derniers convergent vers une mˆeme intersection. Cette th`ese propose la mod´elisation d'un probl`eme sous-jacent `a ce paradigme. Ce probl`eme peut ˆetre vu comme la recherche d'un stable dans un graphe infini sous certaines contraintes. Apr`es une ´etude th´eorique de ce probl`eme, nous proposons une heuristique de r´esolution, amenant `a pr´esenter un syst`eme global de trafic a´erien, puis nous exposons des r´esultats num´eriques.

Le sujet de ce mémoire est l'étude et la réalisation d'un composant pour la reconnaissance structurelle des formules mathématiques typographiées et manuscrites. Ces travaux s'inscrivent dans une thématique plus large : l'analyse et la reconnaissance de documents. La problématique générale que nous avons considérée peut se résumer de la manière suivante ; il s'agit d'identifier la structure, ou arbre de syntaxe abstraite, d'une formule à partir des données graphiques et géométriques (les symboles composant la notation et leur position). L'architecture logicielle retenue permet d'adapter très facilement le composant, baptisé OFR (Reconnaissance Optique de Formules), aux logiciels fournissant les symboles, ainsi qu'aux diverses notations mathématiques identifiées. Pour effectuer cette reconnaissance structurelle, nous avons eu recours à une modélisation à base de graphes. Elle permet une abstraction des données receuillies et une transformation de ces informations par la définition d'une grammaire de graphes contextuelle attribuée, spécialement adaptée aux opérateurs mathématiques. En nous appuyant sur des protocoles de communication d'objets mathématiques, comme OpenMath, nous pouvons envisager l'utilisation de l'interface développée autour d'OFR comme une alternative à la saisie des formules mathématiques.

La modélisation de propriétés et d'activités de molécules constitue un champ de recherche important, qui permet par exemple de guider la synthèse de médicaments. Les méthodes traditionnelles de modélisation établissent des relations non linéaires entre les propriétés étudiées et les caractéristiques structurelles des molécules, appelées descripteurs. Leurs principaux inconvénients résident dans la difficulté du choix des descripteurs et leur calcul préalable. Nous avons mis au point une nouvelle technique de modélisation qui s'affranchit de ces problèmes, en établissant une relation directe entre la structure des données et la propriété modélisée. L'apprentissage s'effectue non plus à partir de vecteurs de données, mais à partir de graphes. Les molécules peuvent en effet être représentées par des graphes, qui tiennent compte des liaisons chimiques, de la nature des atomes ou encore de la stéréochimie du composé initial. Chaque graphe de la base étudiée est alors associé à une fonction de même structure mathématique, appelée graph machine, obtenue par combinaison de fonctions paramétrées identiques. Ces paramètres sont alors déterminés par apprentissage. Nous montrons que les techniques traditionnelles de sélection de modèle peuvent être utilisées dans le cadre des graph machines ; elles permettent d'évaluer les capacités en généralisation des modèles proposés, mais aussi de détecter les catégories de molécules sous-représentées dans la base d'apprentissage, et d'estimer les intervalles de confiance des prédictions. De très bons résultats ont été obtenus par l'utilisation de cette technique sur un grand nombre de bases de données de propriétés ou d'activités moléculaires.

Les réseaux spatiaux sont des réseaux dans lesquels les sommets occupent une position dans l'espace Euclidien. Les interactions dans ces réseaux sont déterminées par cette géometrie sous-jacente des sommets. Les réseaux de communications offrent un vaste champ d'application et une source de nouveaux modèles autour de ce thème. La thèse aborde trois sujets dans des domaines differents. Le premier concerne l'étude de certains arbres couvrant géométriques de processus ponctuels de Poisson. Ces travaux portent notamment sur le phenomene "petit monde", les arbres couvrants radiaux et l'arbre couvrant minimal. Un autre sujet de recherche porte sur la stabilité stochastique de réseaux de files d'attente pour lesquelles les files ont des interactions spatiales. La dernière partie de la thèse aborde des thèmes reliés à la géometrie stochastique: une étude du modèle de feuilles mortes et un travail sur la sensibilité de fonctionnelles de processus ponctuels de Poisson.