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.

Cette thèse traite de l'utilisation des algorithmes évolutionnaires (AE) pour résoudre des problèmes de satisfaction de contrainte (CSP) en domaines finis sans spécialisation ni hybridation particulière. Après avoir présenté les CSP et les méthodes couramment utilisées pour les résoudre (chapitres 1 et 2), nous présentons le paradigme évolutionnaire et ses applications (chapitres 3 et 4). Ensuite, nous proposons une comparaison entre les méthodes de recherche arborescente et les métaheuristiques sur des coloriages de graphe sur-contraints, dans un contexte de réglage des paramètres minimal (chapitre 5). Nous étudions le paysage de recherche pour comprendre les raisons des différences d'efficacité des méthodes. Enfin, nous proposons de nouveaux opérateurs génétiques (croisement, mutation, diversification) dont le paramétrage est moins fastidieux qu'avec les opérateurs classiques (chapitre 6). Nous concluons sur l'intérêt d'exploration des réseaux de neutralité.

Un des rôles des SIG 3D est d'intégrer et de mettre en cohérence des données issues de producteurs de données variés tout en respectant les choix faits en fonction des besoins des utilisateurs, en termes de géométrie et de topologie. Les SIG 3D actuels utilisent généralement une modélisation géométrique et topologique unique qui facilite, entre autres, les requêtes comme celles calculées à partir des modèles topologiques tels que le parcours de proche en proche des primitives géométriques d'un objet ou de ses voisins. En contrepartie, cette homogénéisation entraîne une perte des spécificités des modèles, de lourds calculs de conversion et ne corrige pas, sans une aide extérieure, les problèmes inhérents à l'acquisition et à la modélisation. Cette thèse propose un modèle d'analyse pour les SIG 3D permettant d'opérer des requêtes sur un objet (analyse intra-objet), quel que soit le choix technique de l'utilisateur, ou sur un ensemble d'objets (analyse inter-objets), même s'ils ne sont pas parfaitement cohérents. A partir de principes issus de la cristallographie, ce modèle, nommé Cristage, analyse les symétries de chaque objet pour décrire sa structure, c'est-à-dire la manière dont les primitives sont agencées entre elles. Complémentaire des modèles topologiques, cette première abstraction donne une vision globale de l'objet, ce qui facilite certaines requêtes comme l'extraction du toit d'une cavité ou la simplification géométrique d'un bâtiment 3D. L'analyse des différents éléments de symétrie (plans, axes et centre) offre une seconde abstraction : la maille. Considérée en cristallographie comme l'enveloppe du plus petit parallélépipède conservant les propriétés géométriques, elle est utilisée comme une boîte englobante adaptée à la forme de l'objet. Elle permet, en particulier, la mise en relation logique des objets géographiques, quelle que soit leur dimension. A l'aide des mailles, deux graphes sont calculés. Le premier, qualifié de graphe d'incidence, décrit les relations entre objets et facilite le parcours entre eux. Le second, appelé graphe temporel, dessine, pour un objet, l'évolution de ses relations avec son environnement

Cette thèse a pour cadre la spécification et la vérification de systèmes informatiques distribués, concurrents ou réactifs au moyen de graphes infinis associés à des spécifications de Thue et à certaines machines. Nous montrons que la classe des graphes des spécifications de Thue est fermée par produit synchronisé. Nous établissons aussi ce fait pour la classe des graphes des machines de Turing et pour certaines de ses sous-classes. Nous nous intéressons également à la conservation par produit synchronisé de la décidabilité de la théorie du premier ordre de graphes infinis. Nous montrons que le produit synchronisé de graphes de machines à pile restreint à sa partie accessible depuis un sommet donné à une théorie du premier ordre qui n'est pas décidable. Cependant, le produit synchronisé de graphes sans racine distinguée et dont la théorie du premier oordre est décidable a une théorie du premier ordre qui est décidable. Enfin nous mettons en évidence des liens qui unissent les graphes des machines de Turing à ceux des spécifications de Thue.