No description available.

La coloration de graphes est un problème central de l'optimisation combinatoire. C'est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d'arêtes d'un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n'ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d'arêtes ℓ-distance, qui est une généralisation de la coloration d'arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L'étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d'arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d'arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s'appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

.

Ce travail a pour motivation une meilleure compréhension des graphes parfaits. La preuve en 2002 de la conjecture des graphes parfaits de Claude Berge par Chudnovsky, Robertson, Seymour et Thomas a jeté une lumière nouvelle sur ce domaine de la combinatoire, mais a laissé plusieurs questions en suspens, notamment l'existence d'un algorithme combinatoire de coloration des graphes parfaits. Une paire d'amis d'un graphe est une paire de sommets telle que tous les chemins les reliant sont de longueur paire. Comme l'ont montré Fonlupt et Urhy, la contraction d'une paire amis préserve le nombre chromatique du graphe, et appliquée récursivement, permet dans certains cas de colorier optimalement le graphe. Nous prouvons une conjecture de Everett et Reed affirmant que cette approche fonctionne pour une classe de graphes parfaits: les graphes d'Artémis. Nous en déduisons un algorithme de coloration des graphes Artémis de complexité O(mn^2). Nous donnons un algorithme de complexité O(n^9) pour la reconnaissance des graphes d'Artémis. D'autres algorithmes de reconnaissance sont donnés, tous fondés sur des routines de détection de sous-graphes dans des graphes de Berge. Nous montrons que ces problèmes de détection sont NP-complets si on cherche à les étendre aux graphes quelconques.

Ce travail se situe dans le domaine de l'optimisation combinatoire. Nous étudions plus particulièrement des caractérisations d'objets pour lesquels des problèmes, qui dans le cas général sont NP-complets, deviennent polynomiaux. Nous traitons d'abord le problème de la faisabilité d'un multiflot, qui possède des applications trés importantes en recherche opérationnelle. C'est à dire, étant donnée la spécification du problème, avec le réseau, les capacités et les demandes, on veut démontrer l'existence ou la non-existence d'une solution. Une façon d'aborder ce problème est de donner des conditions nécessaires et suffisantes pour l'existence d'un multiflot, comme celle connue par condition de coupe. Nous présentons la condition (CC, K_5, F_7), qui généralise la condition de coupe et "raffine" une autre condition existante, la (CC3). La structure du problème de multiflot nous permet aussi de regarder un problème étroitement associé, celui du "packing" de métriques. Nous traitons le cas des packing entiers et demi-entiers, quand la famille de métriques comprend les métriques CC3 et les métriques K_5 et F_7. Nous caractérisons la classe de graphes, et plus généralement de matroïdes, ou l'on peut trouver des packings entiers et demi-entiers, sous quelques hypothèses additionnelles. Puis nous nous intéressons aux propriétés générales des graphes h- et t-parfaits, et au problème de coloration associé. Les résultats que nous présentons donnent des bornes pour leur nombres chromatiques, et des classes qui satisfont une conjecture de Shepherd. Enfin nous présentons la hiérarchie des graphes étudiés, qui est obtenu grâce à des outils comme les graphes faiblement bipartis, les clutters binaires et les matrices à composantes 0,1. Nous clôturons ce mémoire en précisant quelques directions de recherche qui pourront donner suite à ce travail, aussi bien sur le sujet de la faisabilité des problèmes de multiflot, que sur la coloration des graphes h- et t-parfaits.

Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

Les environnements pervasifs sont apparus avec l'essor des technologies de communication couplé avec celui des terminaux mobiles. Parallèlement à cela, une évolution logicielle s'est effectuée en passant de l'informatique systémique globale à une approche modulaire et granulaire. Déployer une application sur un dispositif mobile reste toutefois une problématique ouverte, à cause de l'inadéquation de celle-ci aux contraintes matérielles et contextuelles de tels environnements. En effet, les applications usuelles nécessitent plus de ressources que ne peuvent fournir les terminaux mobiles. Pour pallier cela, nous proposons une solution qui s'inscrit à la frontière de ces deux mondes~: celui des environnements pervasifs contraints et celui des applications orientées services. Dans cette thèse nous présentons une approche pour le déploiement contextuel et autonome d'applications orientées services dans des environnements contraints~: AxSeL -A conteXtual SErvice Loader- adapte le déploiement des applications en prenant en compte le contexte des services, la mémoire d'exécution disponible sur le dispositif et les préférences utilisateur. Dans les environnements pervasifs, les services fournis sont disséminés sur les dispositifs mobiles ou des serveurs de dépôts. L'accès à ceux-ci se fait grâce à des descripteurs de services intégrant l'ensemble des dépendances d'un service et sa localisation. Pour déployer une application il est nécessaire de résoudre l'ensemble de ses dépendances en termes de services. A partir de l'agrégation des descripteurs des services AxSeL construit sa propre représentation de l'application sous la forme d'un graphe de dépendances logiques de services. Les noeuds de ce graphe représentent les services et les composants les implantant et les arcs les dépendances d'exécution et de déploiement entre ceux-ci. Le graphe fournit une représentation intuitive et flexible des dépendances et nous permet de distinguer le niveau de l'exécution (services) de celui du déploiement (composants). AxSeL opère à la suite un processus de décision du chargement prenant en compte les caractéristiques des services, celles de la plate-forme matérielle et enfin les préférences utilisateurs. La décision est prise grâce à une technique de coloration sous contraintes du graphe de dépendances des services. En cas de changement du contexte, par exemple modification du dépôt ou des caractéristiques des services, de la mémoire disponible sur la machine ou des préférences utilisateurs, AxSeL le détecte et déclenche un processus d'adaptation qui intègre les changements perçus dans le processus décisionnel du déploiement. Ainsi, AxSeL propose une représentation globale et flexible pour les applications orientées services et des heuristiques permettant leur déploiement contextuel et autonome. Nous avons validé les concepts de notre approche à travers un prototype AxSeL4OSGi en utilisant une machine virtuelle java comme support d'exécution et OSGi comme plate-forme de développement et d'exécution de services. Les performances de notre plate-forme sont évaluées et comparés à une approche similaire à travers des tests réalisés dans des contextes de variation de la structure des graphes applicatifs, de la mémoire disponible sur la machine, des caractéristiques des services et des préférences utilisateurs.

Detection of both biological and chemical environmental toxicants is essential in the assessment of risk to human health. Cell-based biosensors are capable of activity- based detection of toxicity. Chromatophore cells, responsible for the pigmentation of poikilothermic animal, have shown immense potential as cell-based biosensors in the detection of a broad range of environmental toxicants. Chromatophore cells possess the motile pigment granules that intracellularly aggregate or disperse in response to external stimuli. Previous studies have assessed chromatophore cells isolated from red Betta splendens and grey Oncorhynchus tschawytscha fish for use as a biosensor. The objective of this study was to describe blue B. splendens chromatophore cells in tissue culture. Blue B. splendens chromatophore cells were assessed for their longevity in tissue culture and their responses to previously established control agents. Blue B. splendens chromatophore cells were exposed to select chemicals and pathogenic bacteria to assess their ability to respond to environmental toxicants. Three concentrations of mercuric chloride, methyl mercuric chloride, paraquat, sodium arsenite, sodium cyanide chemicals were tested. Bacillus cereus, Bacillus subtilis, Salmonella enterica serovar Enteritidis, and Salmonella enterica serovar Typhimurium were tested. Red B. splendens chromatophore cells were subjected to the select chemical and bacterial toxicants, and observed for their responses. The data collected in this and previous studies were compiled to compare chromatophore cell responses to a broad range of environmental toxicants. Chromatophore cells isolated from both blue and red B. splendens were responsive to methyl mercuric chloride and sodium arsenite. Grey O. tschawytscha chromatophore cells have shown responsiveness to mercuric chloride and sodium arsenite. Blue and red B. splendens chromatophore cells were both responsive to B. cereus and both Salmonella serovars. Grey O. tschawytscha have previously been shown to respond to B. cereus as well. In conclusion, this study reports the chromatophore cells isolated from blue B. splendens in tissue culture and showed similar responsiveness to the selected chemical and bacterial environmental toxicants as chromatophore cells isolated from red and grey colored fish. This study provides compelling evidence that the chromatophore response is not dependent on fish color and that chromatophore cells used for a cell-based detection system may be isolated from different colored fish. / Graduation date: 2012