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.

Un des objectifs majeurs de cette thèse est la construction d'un formalisme algébrique englobant la notion de graphe orienté pondéré et celle de cogèbre coassociative. On montre la nécessité de travailler avec des cogèbres équipées de deux coproduits ou co-opérations. Ce faisant on retrouve la notion de digèbre associative introduite dix ans plus tôt par Jean-Louis Loday, notion motivée par la K-théorie, proposant ainsi un point de vue complémentaire à son formalisme. Le développement du formalisme algébrique introduit dans cette thèse propose aussi une extension de la notion de graphe orienté ainsi que l'utilisation de cogèbres équipées de plusieurs coproduits. La construction de graphes orientés sur des objets algébriques tels que les produits. La construction de graphes orientés sur des objets algébriques tels que les algèbres, bigèbres ou algèbres de Hopf motive ainsi la construction naturelle d'autres types d'algèbres tels que les trigèbres associatives, trigèbres cubiques, algèbres dendriformes, algèbres diptères et algèbres pré-dendriformes introduites par Jean-Louis Loday et Maria Ronco et re-découvertes par l'auteur. La construction de pavages ou de recouvrements coassociatifs de graphes orientés par des cogèbres coassociatives ou cogèbres codiptères permet la construction d'objets algèbriques plus généraux qu'on appelle variétés coassociatives. D'autres objectifs développés dans cette thèse sont liés à l'utilisation de grammaires coassociatives ou au formalisme de Quillen appliqué aux dérivées de type Leibniz-Ito, outils apparaissant en calculs stochastiques classique et quantique et reliés de très près au formalisme proposé par l'auteur.

Pour modéliser le fonctionnement d'un système, décrire une situation ou représenter des idées, on se met intuitivement à dessiner des bulles et les lier par des flèches sous forme de graphes étiquetés. Les logiques modales constituent un cadre formel expressif et extensible qui permet de définir ces graphes sous forme de « modèles », et d'exprimer certaines propriétés de ces graphes sous forme de « formules » afin de pouvoir raisonner là-dessus: model checking, test de satisfiabilité ou de validité, etc. Pour des formules et modèles de tailles importantes, ces tâches deviennent compliquées. De ce fait, un outil permettant de les réaliser automatiquement s'avère nécessaire. LoTREC en est un exemple. Il permet à son utilisateur de créer sa propre méthode de preuve, grâce à un langage simple et de haut niveau, sans avoir besoin d'aucune expertise spécifique en programmation. Durant ma thèse, j'ai revu le travail qui était déjà accompli dans LoTREC et j'ai apporté de nouvelles extensions qui s'avéraient nécessaires pour pouvoir traiter de nouvelles logiques (K.alt1, universal modality, Hybrid Logic HL(@),Intuitionistic logic, Public Announcement Logic, ...) et offrir à l'utilisateur certaines nouvelles techniques. D'autre part, j'ai examiné les origines de LoTREC dans le monde de réécriture de graphes et j'ai spécifié la sémantique de son moteur de réécriture. Cela a permis d'éclaircir comment l'on peut hériter dans nos méthodes de preuve des résultats et des propriétés théoriques déjà bien établies dans le domaine de la réécriture de graphes.

Depuis 1995, l'Union européenne cherche à trouver des solutions pour impulser le cabotage afin de rééquilibrer la distribution modale des transports en Europe. Les "autoroutes de la mer" sont une alternative de transport moins polluante que le mode routier, ainsi qu'une solution pour éviter la congestion des autoroutes. Mais en raison des caractéristiques du transport maritime international, le développement du cabotage n'est pas seulement une alternative écologique, il est aussi une nécessité économique pour le développement ou le maintien des activités maritimes et portuaires. Le cabotage pourrait être une source de trafic de fret non négligeable. L'auteur a analysé les flux routiers entre 112 villes de la péninsule ibérique et de l'Europe du nord-ouest, qui seront la source éventuelle du fret à transférer vers le cabotage. Il a identifié trois principaux pôles d'expédition et de réception du fret routier qui devront fournir les principaux volumes. Ensuite, l'auteur a développé un modèle de choix modal multicritère qui permet la comparaison directe entre les alternatives unimodales de transport combiné. Ce modèle a été utilisé dans le cas de la concurrence entre le mode routier et le mode maritime du cabotage, en fonction du critère du coût de transport. La concentration des liaisons compétitives de cabotage sur les ports permet de définir un potentiel de développement du cabotage pour 57 ports. L'auteur utilise la distribution des flux routiers pour définir les lignes de cabotage les plus "porteuse", en touchant les ports à plus fort potentiel. Finalement, en supposant un transfert de fret routier de 30 pour cent et en ayant connaissance de la distribution spatiale qui devra suivre, l'auteur attribue des volumes de fret aux lignes identifiées afin de construire un scénario de transfert. Mais il faut une volonté politique de l'Union européenne pour impulser ces lignes de cabotage maritime.

Les biopuces sont utilisées en biologie moléculaire et pour le diagnostic. La lecture est généralement réalisée en «end-point» mais le suivi en temps réel donne accès à des données complémentaires. Avec les biopuces à fluorescence, ces expériences sont limitées par 1fluorescence de la solution d'hybridation contenant les cibles marquées. Pour atténuer ce signal parasite, il est possible d'exciter sélectivement la surface avec une onde guidée dans le substrat. L'utilisation de guides d'ondes minces permet de diminuer le signal parasite d'un facteur 103 et d'augmenter l'éclairement d'un facteur 104 par effet de confinement. La principale difficulté concerne le couplage de l'onde guidée. Dans ce travail, nous proposons un système de couplage innovant, simple et efficace basé sur l'incorporation de fluorophores dans les guides. Tout d'abord, un procédé sol-gel de synthèse à basse température de guide d'ondes à haut indice avec de faibles pertes optiques a été développé. Un chélate d'europium est ensuite incorporé à la matrice pour le couplage. Les couches dopées ont de bonnes propriétés optiques et des taux d'absorption élevés. La fluorescence guidée des sources permet l'excitation de spots biologiques ce qui valide l'architecture proposée. L'éclairement est homogène avec une sensibilité équivalente à celle d'un système conventionnel. Enfin, la fonctionnalisation de la surface a été étudiée pour permettre l'accrochage de biomolécules en surface. Le système développé a permis la réalisation d'expériences biologiques complètes en présence d'une solution d'hybridation. Une diminution significative de la fluorescence parasite a été mesurée par rapport au système conventionnel.

In this thesis, we introduce the Partitioning-Hub Location-Routing problem (PHLRP), which can be classied as a variant of the hub location problem. PHLRP consists of partitioning a network into sub-networks, locating at least one hub in each subnetwork and routing the traffic within the network such that all inter-subnetwork traffic is routed through the hubs and all intra-subnetwork traffic stays within the sub-networks all the way from the source to the destination. Obviously, besides the hub location component, PHLRP also involves a graph partitioning component and a routing component. PHLRP finds applications in the strategic planning or deployment of the Intermediate System-Intermediate System (ISIS) Internet Protocol networks and the Less-than-truck load freight distribution systems. First, we introduce three IP formulations for solving PHLRP. The hub location component and the graph partitioning components of PHLRP are modeled in the same way in all three formulations. More precisely, the hub location component is represented by the p-median variables and constraints; and the graph partitioning component is represented by the size-constrained graph partitioning variables and constraints. The formulations differ from each other in the way the peculiar routing requirements of PHLRP are modeled. We then carry out analytical and empirical comparisons of the three IP formulations. Our thorough analysis reveals that one of the formulations is provably the tightest of the three formulations. We also show analytically that the LP relaxations of the other two formulations do not dominate each other. On the other hand, our empirical comparison in a standard branch-and-cut framework that is provided by CPLEX shows that not the tightest but the most compact of the three formulations yield the best performance in terms of solution time. From this point on, based on the insight gained from detailed analysis of the formulations, we focus our attention on a common sub-problem of the three formulations: the so-called size-constrained graph partitioning problem. We carry out a detailed polyhedral analysis of this problem. The main benet from this polyhedral analysis is that the facets we identify for the size-constrained graph partitioning problem constitute strong valid inequalities for PHLRP. And finally, we wrap up our efforts for solving PHLRP. Namely, we present the results of our computational experiments, in which we employ some facets of the size-constrained graph partitioning polytope in a branch-and-cut algorithm for solving PHLRP. Our experiments show that our approach brings signicant improvements to the solution time of PHLRP when compared with the default branch-and-cut solver of XPress. / Dans cette thèse, nous introduisons le problème Partitionnement-Location des Hubs et Acheminement (PLHA), une variante du problème de location de hubs. Le problème PLHA partitionne un réseau afin d'obtenir des sous-réseaux, localise au moins un hub dans chaque sous-réseau et achemine le traffic dans le réseau de la maniére suivante : le traffic entre deux sous-réseaux distincts doit être éxpedié au travers des hubs tandis que le traffic entre deux noeuds d'un même sous-réseau ne doit pas sortir de celui-ci. PLHA possède des applications dans le planning stratégique, ou déploiement, d'un certain protocole de communication utilisé dans l'Internet, Intermediate System - Intermediate System, ainsi que dans la distribution des frets. Premièrement, nous préesentons trois formulations linéaires en variables entières pour résoudre PLHA. Le partitionnement du graphe et la localisation des hubs sont modélisées de la même maniére dans les trois formulations. Ces formulations diffèrent les unes des autres dans la maniére dont l'acheminement du traffic est traité. Deuxièmement, nous présentons des comparaisons analytiques et empiriques des trois formulations. Notre comparaison analytique démontre que l'une des formulations est plus forte que les autres. Néanmoins, la comparaison empirique des formulations, via le solveur CPLEX, montre que la formulation la plus compacte (mais pas la plus forte) obtient les meilleures performances en termes de temps de résolution du problème. Ensuite, nous nous concentrons sur un sous-problème, à savoir, le partitionnement des graphes sous contrainte de taille. Nous étudions le polytope des solutions réalisables de ce sous-problème. Les facettes de ce polytope constituent des inégalités valides fortes pour PLHA et peuvent être utilisées dans un algorithme de branch-and-cut pour résoudre PLHA. Finalement, nous présentons les résultats d'un algorithme de branch-and-cut que nous avons développé pour résoudre PLHA. Les résultats démontrent que la performance de notre méthode est meilleure que celle de l'algorithme branch-and-cut d'Xpress.

Ce document est divisé en deux parties principales. La première partie concerne les résultats que nous avons obtenu au travers de diverses collaborations sur les communications dans les réseaux. Afin de ne pas multiplier les chapitres dans cette partie, nous avons choisi en premier lieu de présenter l'évolution du contexte des réseaux sur lesquels j'ai travaillé durant ces 10 dernières années. En particulier, nous montrons plusieurs facettes que peut recouvrir l'expression \textbf{communications optiques}. Dans un deuxième temps, nous avons regroupé les problèmes abordés en deux chapitres: - le premier s'intéresse à des aspects structurels des graphes utiles pour la construction de protocoles de communication dans les réseaux. - le second aborde une problématique importante dans le contexte actuel de la recherche de la compétitivité: l'optimisation de ressources. La deuxième partie s'intéresse à deux représentations de graphes qui s'avèrent pertinentes pour les problèmes considérés. Elle présente deux problèmes principaux donnant deux chapitres indépendants. Le premier problème abordé dans cette partie concerne un très vieux (au sens informatique) problème issu de la théorie de flots: les flots multi-terminaux. Nous nous sommes attachés à montrer la puissance d'un outil permettant de représenter ces types de flots: les arbres de Gomory-Hu, ainsi que leur utilité dans une version paramétrée du problème. Le second problème présente au travers du calcul du polynôme chromatique une représentation des graphes sous la forme d'arbre de cliques augmenté.

Le concept de radio logicielle (SDR) est une solution pertinente pour concevoir des équipements multi-standards. Une façon de réaliser de tels équipements est d'identifier les fonctions et opérateurs communs entre les standards. Cette approche s'appelle la paramétrisation et est divisée en deux catégories : l'approche pragmatique qui est une version pratique pour créer et développer des opérateurs communs à partir d'opérateurs existants, et l'approche théorique dont l'objectif est de réaliser une exploration graphique d'un équipement multi-standards selon différents niveaux de granularité, accompagnée d'un problème d'optimisation. C'est cette dernière approche qui a constitué le sujet de base de cette thèse. Ainsi, une fonction de coût doit être optimisée afin de sélectionner les opérateurs communs entre les différentes normes, ce qui permet de proposer une configuration optimale à partir de laquelle sont déduits les opérateurs communs. Dans notre travail, nous avons dans un premier temps modélisé théoriquement la structure graphique d'un système multi-standards par un hypergraphe orienté. En outre, nous avons fourni une expression mathématique alternative de la fonction de coût suggérée, en utilisant des définitions propres à la théorie des graphes. Ensuite, nous avons montré que le problème d'optimisation associé était un problème NP sous une certaine contrainte, ce qui a entraîné une preuve d'exclusion de certaines configurations dont les coûts ne peuvent être minimaux. Ceci a constitué la deuxième contribution de cette thèse. Enfin, nous avons proposé un nouvel algorithme permettant de résoudre le problème d'optimisation donné, et dont l'intérêt est de donner une solution optimale du problème au lieu d'une solution approchée fournie par les méthodes heuristiques classiques. Un programme associé à cet algorithme a été développé en langage C, puis appliqué à plusieurs exemples de cas génériques afin d'en étudier les performances.