Les résultats obtenus dans cette thèse portent principalement sur l'étude des "communications dans les réseaux optiques par multiplexage en longueur d'onde". Ils s'inscrivent dans une thématique d'allocation des ressources en vue de réaliser des communications dans un réseau. La problématique générale que nous avons considérée peut se résumer de la manière suivante. Il s'agit de satisfaire dans un réseau optique une famille de requêtes de connexion, appelée instance de communication et formée de couples de noeuds (source, destination). La satisfaction d'une requête passe par l'attribution d'un chemin dans le réseau et d'une longueur d'onde sur les liens utilisés, avec la contrainte que deux requêtes ne peuvent pas utiliser le même lien avec la même longueur d'onde. L'objectif dans ce cadre est de minimiser l'utilisation des ressources optiques, c'est-à-dire le nombre total de longueurs d'onde permettant de satisfaire l'instance donnée. Dans le chapitre 1, nous présentons la technologie optique pour les télécommunications, afin de préciser le cadre technique de notre recherche et d'aider le lecteur informaticien à la compréhension des contraintes physiques sous-jacentes à la modélisation théorique. Dans le chapitre 2, nous posons la problématique étudiée au cours de la thèse et nous donnons la modélisation qui a servi de base à nos recherches. Le chapitre 3 est une synthèse des résultats obtenus dans la littérature concernant principalement le problème du routage optique. Le reste de la thèse est constituée des annexes qui rassemblent les articles publiés, dans le format des rapports de recherche.

Ce travail est axé autour de l'analyse assistée par ordinateur, dans un cadre musicologique ciblant la musique contemporaine. Une approche computationnelle de l'analyse musicale pose la question de sa modélisation et de sa formalisation, puisque touchant à une activité souvent empirique et dont la pratique n'est pas définie à l'aide de normes communes. Cette question implique la mesure de l'importance de la représentation graphique dans l'interprétation analytique. Face au rôle croissant de la représentation, nous nous intéressons d'une part à la manière dont elle relie l'analyse et la composition en proposant, à partir d'une analyse connue des Structures IA de Pierre Boulez réalisée par le compositeur György Ligeti, des modèles de machinerie informatique en vue de générer des pièces musicales sous deux interfaces, OpenMusic et Rubato. Parmi ces deux environnements de programmation visuelle, le second se base sur un puissant paradigme mathématique reposant sur la théorie des catégories. Ce paradigme constitue également une base pour modéliser les K-réseaux, outil d'analyse reposant sur des graphes décrivant les relations entre les notes. Ces relations sont formalisées dans la Set Theory d'Allen Forte qui propose une méthode de classification des structures musicales à partir des douze hauteurs de la gamme chromatique occidentale. Une application de ces réseaux et plus généralement l'apport des structures de graphe est abordée ensuite dans la modélisation de l'analyse d'une autre pièce, le Klavierstück III de Karlheinz Stockhausen : cette analyse a été faite par le théoricien David Lewin en deux étapes que nous étudierons dans leurs aspects à la fois computationnel et d'interface-homme machine. En premier lieu, la segmentation, non expliquée par l'analyste, fait l'objet d'une reconstitution dans laquelle nous tentons de la retrouver par le biais d'une exploration dans un ensemble de segmentations possibles. Il s'agit ainsi non seulement de reconstituer mais également de voir s'il est possible de la dépasser et l'améliorer selon des critères comme la couverture de la partition. Nous verrons dans ce cadre si les K-réseaux peuvent affiner cette analyse et en constituer un angle d'attaque pertinent. En second lieu, Lewin organise ses segments selon un réseau qui ne suit plus un quelconque agencement chronologique mais une disposition spatiale qui offre un nouveau parcours de la pièce. Cette difficulté s'inscrit dans le contexte plus général de la sélection et de la formation d'un graphe décrivant la structure d'une oeuvre musicale, que nous envisageons à l'intérieur du problème de l'utilisation d'un réseau en analyse computationnelle.

L'objet de cette thèse est d'obtenir une description des plongements élémentaires (au sens de la logique du premier ordre) dans un groupe hyperbolique sans torsion. Le résultat principal décrit ces plongements en terme d'une structure définie par Sela dans sa solution au problème de Tarski: la structure de tour hyperbolique. Ainsi, si H est plongé élementairement dans un groupe hyperbolique sans torsion G, on peut obtenir G en amalgamant successivement des groupes de surfaces à bord à un produit libre de H avec des groupes libres et des groupes de surfaces sans bord. Ceci permet en corollaire de montrer qu'un sous-groupe plongé élémentairement dans un groupe libre de type fini est un facteur libre. Les techniques utilisées pour obtenir cette description sont essentiellement géométriques: actions sur des arbres réels ou simpliciaux, existence de décompositions JSJ. On s'appuie également sur des résultats d'existence d'ensembles de factorisation qui affirment que pour certains groupes A de type fini, étant donné un groupe hyperbolique sans torsion G, il existe un ensemble fini de quotients de A tel que tout morphisme non injectif de A vers G se factorise par l'un de ces quotients après précomposition par un automorphisme de A. On expose une preuve de ces résultats, y compris une version complète et détaillée du shortening argument de Rips et Sela. Le shortening argument montre, grâce à l'analyse de Rips des actions sur des arbres réels, que si une suite d'action d'un groupe A sur des espaces hyperboliques converge vers un A-arbre réel d'un certain type, alors une infinité de ces actions peuvent être raccourcies.

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.