Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.

Les peptides non-ribosomiaux sont des molécules produites par les micro-organismes et présentant un large éventail d'activités biologiques et pharmaceutiques. Par exemple, ils peuvent présenter des activités antibiotiques, immuno-modulatrices ou anti-tumorales. Ces peptides sont synthétisés par de grands complexes multi-enzymatiques, appelés synthétases ou NRPS (NonRibosomal Peptide Synthetases). Deux traits caractéristiques distinguent ces peptides des peptides ribosomiaux classiques : le premier est que leur structure primaire n'est pas toujours linéaire mais peut être totalement ou partiellement cyclique, branchée voir même poly-cyclique, et le second est la diversité des monomères incorporés au sein de ces peptides qui dépasse largement les vingt acides aminés protéogéniques. Nous avons développé Norine, la première ressource publique entièement dédiée aux peptides nonribosomiaux. Norine contient actuellement plus de 1 000 peptides, modélisés par des graphes étiquetés non-orientés, ainsi que des outils informatiques permettant leur analyse, comme la comparaison de compositions en monomères, la recherche de motifs structuraux ou la recherche par similarité. Des analyses statistiques sur les données contenues dans Norine ont permis de mettre en évidence des caractéristiques biologiques intéressantes comme la spécificité des monomères en fonction de l'activité biologique qui nous a conduit à l'élaboration d'un outil d'aide à la prédiction de la fonction biologique d'un peptide à partir de sa composition monomérique. En trois ans, Norine est devenue la ressource internationale pour les peptides non-ribosomiaux.

Dans le cadre de l'émergence des nouvelles formes organisationnelles (réseau d'entreprises, entreprise virtuelle, entreprise entendue, ...) ce travail s'intéresse plus particulièrement aux groupements de PME. Dans un environnement économique de plus en plus instable caractérisé par une concurrence accrue, les entreprises sont appelées à faire face et à répondre en conséquence pour rester concurrentielle. La coopération au sein d'une structure organisationnelle est devenue une option incontournable pour les PME. Cependant, cette option comporte des risques et doit être maîtrisée et pilotée pour être efficace et pertinente. Les entreprises doivent donc s'appuyer sur des outils et méthodes pour rationaliser leurs différents choix et prendre les bonnes décisions lors de situations critiques. Cette thèse vient s'inscrire dans cette problématique. L'objet de ce travail est de formaliser les liens de coopération inter-entreprises au sein de réseaux de PME, et de représenter leurs trajectoires d'évolution. Cette formalisation se traduit par la construction d'une cartographie organisationnelle des modes de coordination potentiels du réseau. L'évolution de cette cartographie est représentée par un arbre de scénarios. Cette modélisation est basée sur les caractéristiques structurelles des entreprises. Deux critères clés sont identifiés pour le choix d'un mode de coordination entre deux PME : la similarité des compétences et la complémentarité des activités. Ces deux critères sont appuyés par des paramètres explicatifs qui viennent enrichir l'approche proposée (paramètres internes, paramètres relationnels, proximités, ...). Finalement, un outil d'aide à la décision pour les managers et les divers acteurs économiques est proposé pour détecter des liens de coopération potentiels dans un réseau. Il permet de proposer des préconisations pour piloter la trajectoire organisationnelle du réseau. Deux études de cas viennent confronter la méthodologie proposée à la réalité.

Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.

Le travail effectué dans le cadre de cette thèse intitulée " Outil d'aide au diagnostic du réseau d'eau potable pour la ville de Chisinau par analyse spatiale et temporelle des dysfonctionnements hydrauliques " porte sur le développement d'une maquette du futur outil d'aide à la gestion des infrastructures et notamment du réseau d'eau potable de la ville de Chisinau Moldavie (1200 Km de canalisations - 800 000 habitants). La méthode proposée est basée sur l'analyse de l'état de fonctionnement du réseau d'eau potable. Cet état de fonctionnement du réseau d'AEP peut être connu à partir : - d'informations directes fournies par un système de télésurveillance (mesure de pression, de vitesse, de débit, de qualité....), - d'informations indirectes (analyse des incidents survenus sur le réseau, des interventions, de l'environnement du réseau....) obtenues. Dans notre cas, l'absence de mesures directes ne permet pas de quantifier l'état de fonctionnement du réseau sur l'ensemble du réseau sauf en quelques points critiques connus (station de pompage, station de relèvement..), c'est pourquoi, cet état est défini en se basant sur la liste des incidents, et des interventions survenues sur le réseau entre 1996 et 2001, ainsi que sur des informations portant sur l'environnement du réseau (nature des sols, aménagement du territoire ...) Ce travail de recherche comprend deux volets : Ü Aspect " Diagnostic " : Analyser qualitativement et quantitativement tous les aléas pouvant exister sur le réseau et se manifester par des observations. Il s'agit dans tous les cas d'établir le cheminement possible entre les observations, les causes possibles, et d'évaluer les conséquences induites. Il s'agit par une analyse successive et récursive (à l'aide de requêtes temporelles), de détecter la simultanéité de 2 ou plusieurs observations (manifestations de dysfonctionnement) se produisant dans un même laps de temps et la mise en évidence de relations topologiques et hydrauliques pouvant exister entre les sites où sont observés les dysfonctionnements. L'utilisation également de la théorie des graphes, plus particulièrement du réseau de Petri, permet de passer d'une analyse espace-temps entre 2 ou m événements à une analyse intégrant la causalité entre 2 événements. Ü Aspect " Aide à la décision " : Associer un " niveau d'urgence " à chaque tronçon du réseau afin d'assurer le suivi de la réhabilitation des infrastructures, l'assistance à la réhabilitation avec la détermination de zones prioritaires, la gestion/maintenance du réseau pour la pérennité du réseau. Ce niveau d'urgence est quantifié à l'aide d'une Méthode Hiérarchique Multicritères développée par SAATY (en considérant des critères techniques, économiques, sociaux, environnementaux ainsi que la politique des gestionnaires). La méthodologie développée utilise différents outils et méthodes issues : des bases de données temporelles, d'analyse spatiale et de SIG, de raisonnement cognitif et de modélisation hydraulique des écoulements, théorie de graphes et réseau de Petri. L'outil est testé sur un secteur pilote de la ville, qui représente environ 7% du réseau d'eau potable sur la ville, l'ensemble du réseau sera pris en compte ultérieurement lorsque la validation de cette portion de réseau sera faite par les services techniques de la ville de Chisinau (Moldavie). Mots clés : Vieillissement, réseau d'eau potable, Système d'Information Géographique, base de données géographique, renouvellement, méthode hiérarchique multicritère, dysfonctionnements, analyse spatio-temporelle, théorie des graphes, réseau de Petri, diagramme cause à effets.

La thése poursuit les travaux de la théorie des Jeux évolutionnaires Cette théorie est un cadre de modehsation de la dynamique des populations dans lequel les interactions entre agents sont modélisées par des dilemmes classiques de la théorie des Jeux. Les agents interagissent avec leurs pairs et les meilleurs comportements se diffusent. les moins performants tendent à disparaître. Les modèles spécifiés mettent notamment en évidence des conditions sur les rapports inter-individuels qui permettent de faire émerger des équilibres coopératifs. En supposant que chaque agent a des relations non plus avec tous les agents de la population mais seulement avec un sous-ensemble des agents de la population et toujours avec les mêmes, on augmente considérablement le nombre des dynamiques possibles. Cette démarche fait apparaître un réseau des interactions,.soit un graphe. La contrainte spatiale s'avère une condition favorable au maintien des comportements coopératifs et de la biodiversité des comportements. L'analyse formelle de la convergence n'est généralement plus possible et les modèles sont étudiés par simulation. La these poursuit l'étude de l'impact de la répartition spatiale. Elle introduit un nouveau modèle de répartition spatiale où des communautés d'agents sont en réseau et non plus des agents. Ce modèle permet de mettre en évidence de nouvelles formes d'attracteurs coopératifs et de nouvelles conditions au maintien de la biodiversité. La thèse montre aussi la possibilité de convergence de marchés vers des équilibres non concurrentiels et de maintien de comportements coopératifs, des comportements de cartel.

L'objectif de notre travail est de déterminer des algorithmes qui facilitent la résolution de jeux combinatoires par des calculs informatiques. En premier lieu, nous expliquons comment l'implémentation du nimber permet d'accélérer le calcul de jeux impartiaux en version normale. Puis, nous proposons des raffinements ou des généralisations d'algorithmes de parcours des arbres de jeu, en particulier le PN-search, tout en discutant de l'intérêt de l'intervention humaine lors de l'exécution de ces algorithmes. Enfin, nous présentons des algorithmes de vérification, dont le but initial était de s'assurer de la validité de nos calculs, mais qui permettent également d'obtenir des arbres solutions de taille réduite. Ces techniques sont appliquées à l'étude de deux jeux : le Sprouts, où les joueurs relient des points par des lignes, et le Dots-and-boxes, dont le but est de compléter le maximum de boîtes en plaçant des arêtes. Le Sprouts est un jeu combinatoire impartial, dont la nature topologique rend difficile la représentation informatique. Nous explicitons une telle représentation, avant d'étudier une généralisation où le jeu se déroule sur des surfaces compactes. Le Dots-and-boxes est un jeu partisan, et nous détaillons diverses simplifications théoriques qui nous ont permis d'obtenir informatiquement des résultats nouveaux sur ce jeu.

Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent être utilisés pour accélérer les calculs. Nous détaillons en particulier l'utilisation du concept d'arbre canonique réduit dans les calculs en version misère. Ces méthodes ont été appliquées avec succès au calcul de deux jeux impartiaux en apparence très différents : le Sprouts, où les joueurs relient des points par des lignes, et le Cram, qui consiste à remplir un plateau avec des dominos. Nous exposons ensuite une méthode originale de suivi des calculs de jeux, avec des interactions en temps réel par l'opérateur humain. Enfin, nous décrivons l'architecture du programme modulaire qui nous a permis de réaliser de nombreux calculs différents au sein d'un cadre commun, et qui pourrait être étendu à l'avenir à d'autres jeux ou algorithmes.

Cette thèse s’intéresse à la question de l’évaluation des Systèmes Multi-Agents (SMA). Les caractéristiques propres que possèdent ces derniers, notamment en termes d’autonomie, de distribution, de dynamique et de socialité, ont grandement contribué à l’élargissement de leurs champs d’application, mais en contrepartie, elles ont rendu leur analyse plus ardue. Ainsi, les méthodes d’évaluation dans les systèmes informatiques classiques s’avèrent insuffisantes à analyser les SMA, étant donné qu’elles ne tiennent pas compte de leurs spécificités. L’objectif de cette thèse consiste donc à proposer une approche générique pour l’évaluation des SMA en se basant sur la mesure de leurs caractéristiques fonctionnelles. A cet effet, le besoin de disposer d’informations sur l’exécution du système à évaluer est manifeste. C’est dans ce cadre qu’une nouvelle approche d’observation des SMA est proposée. Les résultats de ces observations sont exploités pour construire une abstraction du système sous forme d’un modèle, lequel est étudié pour définir les mesures de performances. L’analyse se focalise sur deux caractéristiques essentielles, à la base de la dynamique et de la socialité des SMA : la communication et l’organisation. Les expérimentations de la solution proposée portent sur deux applications multi-agents. La première est une application de diagnostic des pannes dans un environnement industriel et la seconde est une application de pilotage et de gestion de la production dans les chaînes logistiques. / This thesis focuses on the issue of MultiAgent Systems (MAS) evaluation. The MAS own characteristics, namely autonomy, distribution, dynamicity and sociality, have greatly contributed to the expansion of their application scope; but in return they made their analysis more difficult. Thus, evaluation methods in classic computer systems are insufficient to analyse MAS, since they do not take into account their specificities. The objective of this thesis is to provide a generic approach for the evaluation of MAS by measuring their functional characteristics. To this end, the need for information about the execution of the system to be evaluated is evident. In this context, a new approach to observe MAS is proposed. The results of these observations are exploited to build an abstraction model of the system which is studied in order to define performance metrics. The analysis focuses on two key characteristics, at the basis on the dynamics and sociality in MAS: communication and organization. The experiments of the proposed solution are performed on two multiagent applications. The first is an application of fault diagnosis in an industrial environment and the second is an application of control and production planning in supply chains.

Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déconnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation. / Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game, where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results.