Allocation optimale des ressources pour les applications et services de grille de calcul

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Identification d’une architecture à base de composants dans une application orientée objets à l’aide d’une analyse dynamique

Un système, décrit avec un grand nombre d'éléments fortement interdépendants, est complexe, difficile à comprendre et à maintenir. Ainsi, une application orientée objet est souvent complexe, car elle contient des centaines de classes avec de nombreuses dépendances plus ou moins explicites. Une même application, utilisant le paradigme composant, contiendrait un plus petit nombre d'éléments, faiblement couplés entre eux et avec des interdépendances clairement définies. Ceci est dû au fait que le paradigme composant fournit une bonne représentation de haut niveau des systèmes complexes. Ainsi, ce paradigme peut être utilisé comme "espace de projection" des systèmes orientés objets. Une telle projection peut faciliter l'étape de compréhension d'un système, un pré-requis nécessaire avant toute activité de maintenance et/ou d'évolution. De plus, il est possible d'utiliser cette représentation, comme un modèle pour effectuer une restructuration complète d'une application orientée objets opérationnelle vers une application équivalente à base de composants tout aussi opérationnelle. Ainsi, La nouvelle application bénéficiant ainsi, de toutes les bonnes propriétés associées au paradigme composants. L'objectif de ma thèse est de proposer une méthode semi-automatique pour identifier une architecture à base de composants dans une application orientée objets. Cette architecture doit, non seulement aider à la compréhension de l'application originale, mais aussi simplifier la projection de cette dernière dans un modèle concret de composant. L'identification d'une architecture à base de composants est réalisée en trois grandes étapes: i) obtention des données nécessaires au processus d'identification. Elles correspondent aux dépendances entre les classes et sont obtenues avec une analyse dynamique de l'application cible. ii) identification des composants. Trois méthodes ont été explorées. La première utilise un treillis de Galois, la seconde deux méta-heuristiques et la dernière une méta-heuristique multi-objective. iii) identification de l'architecture à base de composants de l'application cible. Cela est fait en identifiant les interfaces requises et fournis pour chaque composant. Afin de valider ce processus d'identification, ainsi que les différents choix faits durant son développement, j'ai réalisé différentes études de cas. Enfin, je montre la faisabilité de la projection de l'architecture à base de composants identifiée vers un modèle concret de composants.

Apprentissage de représentations musicales à l'aide d'architectures profondes et multiéchelles

L'apprentissage machine (AM) est un outil important dans le domaine de la recherche d'information musicale (Music Information Retrieval ou MIR). De nombreuses tâches de MIR peuvent être résolues en entraînant un classifieur sur un ensemble de caractéristiques. Pour les tâches de MIR se basant sur l'audio musical, il est possible d'extraire de l'audio les caractéristiques pertinentes à l'aide de méthodes traitement de signal. Toutefois, certains aspects musicaux sont difficiles à extraire à l'aide de simples heuristiques. Afin d'obtenir des caractéristiques plus riches, il est possible d'utiliser l'AM pour apprendre une représentation musicale à partir de l'audio. Ces caractéristiques apprises permettent souvent d'améliorer la performance sur une tâche de MIR donnée. Afin d'apprendre des représentations musicales intéressantes, il est important de considérer les aspects particuliers à l'audio musical dans la conception des modèles d'apprentissage. Vu la structure temporelle et spectrale de l'audio musical, les représentations profondes et multiéchelles sont particulièrement bien conçues pour représenter la musique. Cette thèse porte sur l'apprentissage de représentations de l'audio musical. Des modèles profonds et multiéchelles améliorant l'état de l'art pour des tâches telles que la reconnaissance d'instrument, la reconnaissance de genre et l'étiquetage automatique y sont présentés.

Cell wall composition regulates cell shape and growth behaviour in pollen tubes

L’une des particularités fondamentales caractérisant les cellules végétales des cellules animales est la présence de la paroi cellulaire entourant le protoplaste. La paroi cellulaire joue un rôle primordial dans (1) la protection du protoplaste, (2) est impliquée dans les mécanismes de filtration et (3) est le lieu de maintes réactions biochimiques nécessaires à la régulation du métabolisme et des propriétés mécaniques de la cellule. Les propriétés locales d’élasticité, d’extensibilité, de plasticité et de dureté des composants pariétaux déterminent la géométrie et la forme des cellules lors des processus de différentiation et de morphogenèse. Le but de ma thèse est de comprendre les rôles que jouent les différents composants pariétaux dans le modelage de la géométrie et le contrôle de la croissance des cellules végétales. Pour atteindre cet objectif, le modèle cellulaire sur lequel je me suis basé est le tube pollinique ou gamétophyte mâle. Le tube pollinique est une protubérance cellulaire qui se forme à partir du grain de pollen à la suite de son contact avec le stigmate. Sa fonction est la livraison des cellules spermatiques à l’ovaire pour effectuer la double fécondation. Le tube pollinique est une cellule à croissance apicale, caractérisée par la simple composition de sa paroi et par sa vitesse de croissance qui est la plus rapide du règne végétal. Ces propriétés uniques font du tube pollinique le modèle idéal pour l’étude des effets à courts termes du stress sur la croissance et le métabolisme cellulaire ainsi que sur les propriétés mécaniques de la paroi. La paroi du tube pollinique est composée de trois composantes polysaccharidiques : pectines, cellulose et callose et d’une multitude de protéines. Pour comprendre les effets que jouent ces différents composants dans la régulation de la croissance du tube pollinique, j’ai étudié les effets de mutations, de traitements enzymatiques, de l’hyper-gravité et de la gravité omni-directionnelle sur la paroi du tube pollinique. En utilisant des méthodes de modélisation mathématiques combinées à de la biologie moléculaire et de la microscopie à fluorescence et électronique à haute résolution, j’ai montré que (1) la régulation de la chimie des pectines est primordiale pour le contrôle du taux de croissance et de la forme du tube et que (2) la cellulose détermine le diamètre du tube pollinique en partie sub-apicale. De plus, j’ai examiné le rôle d’un groupe d’enzymes digestives de pectines exprimées durant le développement du tube pollinique : les pectate lyases. J’ai montré que ces enzymes sont requises lors de l’initiation de la germination du pollen. J’ai notamment directement prouvé que les pectate lyases sont sécrétées par le tube pollinique dans le but de faciliter sa pénétration au travers du style.

Reconceptualisation encyclopédique du corps cyborg dans les textes d’Élisabeth Vonarburg et de Catherine Dufour

Le cyborg est un avatar de ce que permet la science-fiction lorsqu’elle s’offre comme terrain où développer une heuristique des identités genrées. Donna Haraway, dans le Manifeste cyborg, a relevé le potentiel de liberté discursive que promettait cette figure romanesque. Il m’apparaît que, depuis sa fictionnalisation puis sa théorisation dans les années 1980 et 1990, le cyborg a muté au sein de l’entreprise science-fictionnelle littéraire. Le Silence de la Cité d’Élisabeth Vonarburg et Le Goût de l’immortalité de Catherine Dufour présentent des personnages dont la cyborgitude problématise les questions identitaires du genre humain, à travers une écriture spécifique, affectée par les technologies. Mon analyse des procédés scripturaux s’effectue de pair avec une analyse gender, ce qui me permet de mieux saisir la fictionnalisation toujours changeante des cyborgs dans les oeuvres de Vonarburg et de Dufour. Ces cyborgs déconstruisent les frontières des systèmes binaires traditionnels, en explorant les possibilités trans-genres et trans-espèces que permettent les métamorphoses de leurs corps excentriques. En tant que représentations fantasmées de désirs autrement inavouables, les cyborgs science-fictionnels témoignent du malaise inhérent de couples comme homme/femme, humain/animal ou organique/artificiel.

Évolution des projets de formation de futurs enseignants du primaire au contact de situations probabilistes

Il semble y avoir des attentes réciproques non comblées en formation initiale à l’enseignement des mathématiques. Cherchant à comprendre la genèse de ces attentes, nous nous sommes intéressée à la vision que les étudiants nourrissent des phénomènes d’enseignement. Ayant postulé que les étudiants ont une vision déterministe de ces phénomènes, et considérant que leur anticipation oriente leur projet de formation, nous nous sommes attaquée au problème de la rencontre des projets des étudiants et des formateurs. Deux objectifs généraux ont été formulés : le premier concerne la description des projets de formation des étudiants tandis que le second concerne l’expérimentation d’une séquence de situations susceptible de faire évoluer leurs projets. Cette recherche a été menée auprès de 58 étudiants du baccalauréat en enseignement en adaptation scolaire et sociale d’une même université, lesquels entamaient leur formation initiale à l’enseignement des mathématiques. Afin d’explorer les projets qu’ils nourrissent a priori, tous les étudiants ont complété un questionnaire individuel sur leur vision des mathématiques et de leur enseignement et ont participé à une première discussion de groupe sur le sujet. Une séquence de situations probabilistes leur a ensuite été présentée afin d’induire une complexification de leur projet. Enfin, cette expérimentation a été suivie d’une seconde discussion de groupe et complétée par la réalisation de huit entretiens individuels. Il a été mis en évidence que la majorité des étudiants rencontrés souhaitent avant tout évoluer en tant qu’enseignant, en développant leur capacité à enseigner et à faire apprendre ou comprendre les mathématiques. Bien que certaines visées se situent dans une perspective transmissive, celles-ci ne semblent pas représentatives de l’ensemble des projets "visée". De plus, même si la plupart des étudiants rencontrés projettent de développer des connaissances relatives aux techniques et aux méthodes d’enseignement, la sensibilité à la complexité dont certains projets témoignent ne permet plus de réduire les attentes des étudiants à l’endroit de leur formation à la simple constitution d’un répertoire de techniques d’enseignement réputées efficaces. En ce qui a trait aux modes d’anticipation relevés a priori, nos résultats mettent en relief des anticipations se rattachant d’abord à un mode adaptatif, puis à un mode prévisionnel. Aucune anticipation se rattachant à un mode prospectif n’a été recensée a priori. La séquence a permis aux étudiants de s’engager dans une dialectique d’action, de formulation et de validation, elle les a incités à recourir à une approche stochastique ainsi qu’à porter un jugement de probabilité qui prenne en compte la complexité de la situation. A posteriori, nous avons observé que les projets "visée" de certains étudiants se sont complexifiés. Nous avons également noté un élargissement de la majorité des projets, lesquels considèrent désormais les autres sommets du triangle didactique. Enfin, des anticipations se rattachant à tous les modes d’anticipation ont été relevées. Des anticipations réalisées grâce à un mode prospectif permettent d’identifier des zones d’incertitude et de liberté sur lesquelles il est possible d’agir afin d’accroître la sensibilité à la complexité des situations professionnelles à l’intérieur desquelles les futurs enseignants devront se situer.

Heuristic solution methods for multi-attribute vehicle routing problems

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques.

Algorithmes d'apprentissage pour la recommandation

L'ère numérique dans laquelle nous sommes entrés apporte une quantité importante de nouveaux défis à relever dans une multitude de domaines. Le traitement automatique de l'abondante information à notre disposition est l'un de ces défis, et nous allons ici nous pencher sur des méthodes et techniques adaptées au filtrage et à la recommandation à l'utilisateur d'articles adaptés à ses goûts, dans le contexte particulier et sans précédent notable du jeu vidéo multi-joueurs en ligne. Notre objectif est de prédire l'appréciation des niveaux par les joueurs. Au moyen d'algorithmes d'apprentissage machine modernes tels que les réseaux de neurones profonds avec pré-entrainement non-supervisé, que nous décrivons après une introduction aux concepts nécessaires à leur bonne compréhension, nous proposons deux architectures aux caractéristiques différentes bien que basées sur ce même concept d'apprentissage profond. La première est un réseau de neurones multi-couches pour lequel nous tentons d'expliquer les performances variables que nous rapportons sur les expériences menées pour diverses variations de profondeur, d'heuristique d'entraînement, et des méthodes de pré-entraînement non-supervisé simple, débruitant et contractant. Pour la seconde architecture, nous nous inspirons des modèles à énergie et proposons de même une explication des résultats obtenus, variables eux aussi. Enfin, nous décrivons une première tentative fructueuse d'amélioration de cette seconde architecture au moyen d'un fine-tuning supervisé succédant le pré-entrainement, puis une seconde tentative où ce fine-tuning est fait au moyen d'un critère d'entraînement semi-supervisé multi-tâches. Nos expériences montrent des performances prometteuses, notament avec l'architecture inspirée des modèles à énergie, justifiant du moins l'utilisation d'algorithmes d'apprentissage profonds pour résoudre le problème de la recommandation.

Effect of levodopa on cortico-striatal and cortico-cerebellar circuits in Parkinson's disease

La maladie de Parkinson (MP) est la deuxième maladie neurodégénérative la plus commune. Les symptômes principalement observés chez les patients atteints de la MP sont la rigidité, les tremblements, la bradykinésie et une instabilité posturale. Leur sévérité est souvent asymétrique. La cause principale de ces symptômes moteurs est la dégénérescence du circuit dopaminergique nigro-striatal qui mène à un débalancement d’activité du circuit cortico-striatal. Ce débalancement de circuits est le point essentiel de cette thèse. Dans les protocoles de recherche décrits ici, des patients atteints de la MP (avant et après une dose de levodopa) et des participants contrôles sains ont effectué des mouvements auto-initiés ou en réponse à des stimulis externes pendant que l’on mesurait leur activité cérébrale en imagerie par résonance magnétique fonctionnelle (IRMf). Dans cette thèse, nous abordons et mettons en évidence quatre (4) points principaux. En première partie (chapitre 2), nous présentons un recensement de la littérature sur les cicruits cortico-striataux et cortico-cérébelleux dans la MP. En utilisant des méthodes de neuroimagerie, des changements d’activité cérébrale et cérébelleuse ont été observés chez les patients atteints de la MP comparés aux participants sains. Même si les augmentations d’activité du cervelet ont souvent été attribuées à des mécanismes compensatoires, nos résultats suggèrent qu’elles sont plus probablement liées aux changements pathophysiologiques de la MP et à la perturbation du circuit cortico-cérébelleux. En général, nous suggérons (1) que le circuit cortico-cérébelleux est perturbé chez les patients atteints de la MP, et que les changements d’activité du cervelet sont liés à la pathophysiologie de la MP plutôt qu’à des mécanismes compensatoires. En deuxième partie (chapitre 3), nous discutons des effets de la levodopa sur les hausses et baisses d’activité observés chez les patients atteints de la MP, ainsi que sur l’activité du putamen pendant les mouvements d’origine interne et externe. De nombreuses études en neuroimagerie ont montré une baisse d’activité (hypo-activité) préfrontale liée à la déplétion de dopamine. En revanche, l’utilisation de tâches cognitives a montré des augmentations d’activité (hyper-activité) corticale chez les patients atteints de la MP comparés aux participants sains. Nous avons suggéré précédemment que ces hypo- et hyper-activités des régions préfrontales dépendent de l’implication du striatum. Dans cette thèse nous suggérons de plus (2) que la levodopa ne rétablit pas ces hyper-activations, mais plutôt qu’elles sont liées à la perturbation du circuit méso-cortical, et aussi possiblement associées à l’administration de médication dopaminergique à long terme. Nous montrons aussi (3) que la levodopa a un effet non-spécifique à la tâche sur l’activité du circuit cortico-striatal moteur, et qu’elle n’a pas d’effet sur l’activité du circuit cortico-striatal cognitif. Nous montrons enfin (chapitre 4) que la levodopa a un effet asymétrique sur les mouvements de la main droite et gauche. À peu près 50% des patients atteints de la MP démontrent une asymétrie des symptômes moteurs, et ceci persiste à travers la durée de la maladie. Nos résultats suggèrent (4) que la levodopa pourrait avoir un plus grand effet sur les patrons d’activations des mouvements de la main la plus affectée.

La résolution du problème de formation de cellules dans un contexte multicritère

Les techniques de groupement technologique sont aujourd’hui utilisées dans de nombreux ateliers de fabrication; elles consistent à décomposer les systèmes industriels en sous-systèmes ou cellules constitués de pièces et de machines. Trouver le groupement technologique le plus efficace est formulé en recherche opérationnelle comme un problème de formation de cellules. La résolution de ce problème permet de tirer plusieurs avantages tels que la réduction des stocks et la simplification de la programmation. Plusieurs critères peuvent être définis au niveau des contraintes du problème tel que le flot intercellulaire,l’équilibrage de charges intracellulaires, les coûts de sous-traitance, les coûts de duplication des machines, etc. Le problème de formation de cellules est un problème d'optimisation NP-difficile. Par conséquent les méthodes exactes ne peuvent être utilisées pour résoudre des problèmes de grande dimension dans un délai raisonnable. Par contre des méthodes heuristiques peuvent générer des solutions de qualité inférieure, mais dans un temps d’exécution raisonnable. Dans ce mémoire, nous considérons ce problème dans un contexte bi-objectif spécifié en termes d’un facteur d’autonomie et de l’équilibre de charge entre les cellules. Nous présentons trois types de méthodes métaheuristiques pour sa résolution et nous comparons numériquement ces métaheuristiques. De plus, pour des problèmes de petite dimension qui peuvent être résolus de façon exacte avec CPLEX, nous vérifions que ces métaheuristiques génèrent des solutions optimales.

Ni hypersexualisées ni voilées ! Tensions et enjeux croisés dans les discours sur l’hypersexualisation et le port du voile «islamique» au Québec

Cette thèse identifie une cooccurrence des discours à propos de l’hypersexualisation des jeunes filles et ceux concernant le port du voile islamique qui sont, depuis quelques années, au cœur des préoccupations sociales au Québec comme ailleurs en Occident. Plus spécifiquement, elle propose une « économie générale des discours » (Foucault, 1976) contemporains sur l’hypersexualisation et le port du voile, dans une perspective conjoncturelle, par et à travers trois contextes d'analyse particuliers : féministe, médiatique et public. Elle démontre comment l’hypersexualisation et le port du voile sont problématisés (Foucault, 2001/1984), c'est-à-dire qu’ils sont posés comme nouveaux problèmes sociaux engendrant et cristallisant bon nombre de craintes et d’anxiétés contemporaines. Ainsi, la thèse est composée de trois chapitres centraux qui reprennent chacun des contextes de problématisation identifiés. Le chapitre intitulé « Féminisme(s) et égalité des sexes », avance que l’égalité des sexes est invoquée comme valeur moderne, féministe et québécoise par excellence et qu’elle participe, à ce titre, de la problématisation du port du voile et de l’hypersexualisation. Le chapitre suivant, « Médias, diversité et (hyper) visibilité », concentre l’analyse sur les médias et la culture populaire, à la fois sujets énonciateurs, régimes et objets de discours, participant à construire et à délimiter l’adolescence et la religion/culture musulmane comme des mondes à part, mystérieux, tout en les exposant au public. Enfin, à partir d’une analyse des discours publics à propos de l’hypersexualisation et du port du voile, le chapitre intitulé « Laïcité, sexualité et neutralité » met en lumière les façons par lesquelles ces problèmes sont constitutifs de chartes, de codes et d’autres formes de règlementations qui viennent non seulement normaliser mais également discipliner la conduite de chacun, au nom du bien commun et de la neutralité de l’État. Un « Retour sur la conjoncture » vient conclure la thèse en mettant en lumière certains éléments conjoncturels qui traversent ses principaux chapitres, dont les questions du consensus et de l’extrême.

Parallelization of SAT on Reconfigurable Hardware

Quoique très difficile à résoudre, le problème de satisfiabilité Booléenne (SAT) est fréquemment utilisé lors de la modélisation d’applications industrielles. À cet effet, les deux dernières décennies ont vu une progression fulgurante des outils conçus pour trouver des solutions à ce problème NP-complet. Deux grandes avenues générales ont été explorées afin de produire ces outils, notamment l’approche logicielle et matérielle. Afin de raffiner et améliorer ces solveurs, de nombreuses techniques et heuristiques ont été proposées par la communauté de recherche. Le but final de ces outils a été de résoudre des problèmes de taille industrielle, ce qui a été plus ou moins accompli par les solveurs de nature logicielle. Initialement, le but de l’utilisation du matériel reconfigurable a été de produire des solveurs pouvant trouver des solutions plus rapidement que leurs homologues logiciels. Cependant, le niveau de sophistication de ces derniers a augmenté de telle manière qu’ils restent le meilleur choix pour résoudre SAT. Toutefois, les solveurs modernes logiciels n’arrivent toujours pas a trouver des solutions de manière efficace à certaines instances SAT. Le but principal de ce mémoire est d’explorer la résolution du problème SAT dans le contexte du matériel reconfigurable en vue de caractériser les ingrédients nécessaires d’un solveur SAT efficace qui puise sa puissance de calcul dans le parallélisme conféré par une plateforme FPGA. Le prototype parallèle implémenté dans ce travail est capable de se mesurer, en termes de vitesse d’exécution à d’autres solveurs (matériels et logiciels), et ce sans utiliser aucune heuristique. Nous montrons donc que notre approche matérielle présente une option prometteuse vers la résolution d’instances industrielles larges qui sont difficilement abordées par une approche logicielle.

Stéréotypes et auto-exotisme : les représentations de la sexualité de l'homme noir chez René Depestre et Dany Laferrière

Ce mémoire fait appel aux notions de stéréotype (tel que théorisé par Ruth Amossy, Jean- Louis Dufays et Mireille Rosello) et d’auto-exotisme (défini par Nathalie Schon) afin d’étudier les représentations de la sexualité de l’homme noir dans Alléluia pour une femme-jardin de René Depestre et La chair du maître de Dany Laferrière. Le stéréotype et l’exotisme, tous deux tributaires d’une vision de l’autre généralisante, superficielle et éphémère, nous intéressent dans la mesure où ils sont employés de façon auto-référentielle par ces auteurs d’origine haïtienne, qui mettent en scène des protagonistes noirs correspondant souvent au stéréotype du Noir hyper-sexuel, qui est pourtant issu de fantasmagories coloniales avilissantes. Dans le cadre de cette recherche, nous analysons les différentes postures de la sexualité masculine dans les œuvres susmentionnées afin d’y révéler un emploi varié des stéréotypes, tantôt reconduits, tantôt déplacés, voire rendus désuets ou incertains, grâce à diverses stratégies textuelles comme l’humour, l’ironie, l’exagération ou l’omission. Ce faisant, nous remarquons que l’usage complexe des stéréotypes, chez Depestre et Laferrière, quoi qu’il fasse appel aux mêmes tropes, dénote différents moyens de négocier avec sa propre « étrangeté ».

Genetic studies on the role of type IA DNA topoisomerases in DNA metabolism and genome maintenance in Escherichia coli

Le surenroulement de l’ADN est important pour tous les processus cellulaires qui requièrent la séparation des brins de l’ADN. Il est régulé par l’activité enzymatique des topoisomérases. La gyrase (gyrA et gyrB) utilise l’ATP pour introduire des supertours négatifs dans l’ADN, alors que la topoisomérase I (topA) et la topoisomérase IV (parC et parE) les éliminent. Les cellules déficientes pour la topoisomérase I sont viables si elles ont des mutations compensatoires dans un des gènes codant pour une sous-unité de la gyrase. Ces mutations réduisent le niveau de surenroulement négatif du chromosome et permettent la croissance bactérienne. Une de ces mutations engendre la production d'une gyrase thermosensible. L’activité de surenroulement de la gyrase en absence de la topoisomérase I cause l’accumulation d’ADN hyper-surenroulé négativement à cause de la formation de R-loops. La surproduction de la RNase HI (rnhA), une enzyme qui dégrade l’ARN des R-loops, permet de prévenir l’accumulation d’un excès de surenroulement négatif. En absence de RNase HI, des R-loops sont aussi formés et peuvent être utilisés pour déclencher la réplication de l’ADN indépendamment du système normal oriC/DnaA, un phénomène connu sous le nom de « constitutive stable DNA replication » (cSDR). Pour mieux comprendre le lien entre la formation de R-loops et l’excès de surenroulement négatif, nous avons construit un mutant conditionnel topA rnhA gyrB(Ts) avec l’expression inductible de la RNase HI à partir d’un plasmide. Nous avons trouvé que l’ADN des cellules de ce mutant était excessivement relâché au lieu d'être hypersurenroulé négativement en conditions de pénurie de RNase HI. La relaxation de l’ADN a été montrée comme étant indépendante de l'activité de la topoisomérase IV. Les cellules du triple mutant topA rnhA gyrB(Ts) forment de très longs filaments remplis d’ADN, montrant ainsi un défaut de ségrégation des chromosomes. La surproduction de la topoisomérase III (topB), une enzyme qui peut effectuer la décaténation de l’ADN, a corrigé les problèmes de ségrégation sans toutefois restaurer le niveau de surenroulement de l’ADN. Nous avons constaté que des extraits protéiques du mutant topA rnhA gyrB(Ts) pouvaient inhiber l’activité de surenroulement négatif de la gyrase dans des extraits d’une souche sauvage, suggérant ainsi que la pénurie de RNase HI avait déclenché une réponse cellulaire d’inhibition de cette activité de la gyrase. De plus, des expériences in vivo et in vitro ont montré qu’en absence de RNase HI, l’activité ATP-dépendante de surenroulement négatif de la gyrase était inhibée, alors que l’activité ATP-indépendante de cette enzyme demeurait intacte. Des suppresseurs extragéniques du défaut de croissance du triple mutant topA rnhA gyrB(Ts) qui corrigent également les problèmes de surenroulement et de ségrégation des chromosomes ont pour la plupart été cartographiés dans des gènes impliqués dans la réplication de l’ADN, le métabolisme des R-loops, ou la formation de fimbriae. La deuxième partie de ce projet avait pour but de comprendre les rôles des topoisomérases de type IA (topoisomérase I et topoisomérase III) dans la ségrégation et la stabilité du génome de Escherichia coli. Pour étudier ces rôles, nous avons utilisé des approches de génétique combinées avec la cytométrie en flux, l’analyse de type Western blot et la microscopie. Nous avons constaté que le phénotype Par- et les défauts de ségrégation des chromosomes d’un mutant gyrB(Ts) avaient été corrigés en inactivant topA, mais uniquement en présence du gène topB. En outre, nous avons démontré que la surproduction de la topoisomérase III pouvait corriger le phénotype Par- du mutant gyrB(Ts) sans toutefois corriger les défauts de croissance de ce dernier. La surproduction de topoisomérase IV, enzyme responsable de la décaténation des chromosomes chez E. coli, ne pouvait pas remplacer la topoisomérase III. Nos résultats suggèrent que les topoisomérases de type IA jouent un rôle important dans la ségrégation des chromosomes lorsque la gyrase est inefficace. Pour étudier le rôle des topoisomérases de type IA dans la stabilité du génome, la troisième partie du projet, nous avons utilisé des approches génétiques combinées avec des tests de « spot » et la microscopie. Nous avons constaté que les cellules déficientes en topoisomérase I avaient des défauts de ségrégation de chromosomes et de croissance liés à un excès de surenroulement négatif, et que ces défauts pouvaient être corrigés en inactivant recQ, recA ou par la surproduction de la topoisomérase III. Le suppresseur extragénique oriC15::aph isolé dans la première partie du projet pouvait également corriger ces problèmes. Les cellules déficientes en topoisomérases de type IA formaient des très longs filaments remplis d’ADN d’apparence diffuse et réparti inégalement dans la cellule. Ces phénotypes pouvaient être partiellement corrigés par la surproduction de la RNase HI ou en inactivant recA, ou encore par des suppresseurs isolés dans la première partie du projet et impliques dans le cSDR (dnaT18::aph et rne59::aph). Donc, dans E. coli, les topoisomérases de type IA jouent un rôle dans la stabilité du génome en inhibant la réplication inappropriée à partir de oriC et de R-loops, et en empêchant les défauts de ségrégation liés à la recombinaison RecA-dépendante, par leur action avec RecQ. Les travaux rapportés ici révèlent que la réplication inappropriée et dérégulée est une source majeure de l’instabilité génomique. Empêcher la réplication inappropriée permet la ségrégation des chromosomes et le maintien d’un génome stable. La RNase HI et les topoisomérases de type IA jouent un rôle majeur dans la prévention de la réplication inappropriée. La RNase HI réalise cette tâche en modulant l’activité de surenroulement ATP-dependante de la gyrase, et en empêchant la réplication à partir des R-loops. Les topoisomérases de type IA assurent le maintien de la stabilité du génome en empêchant la réplication inappropriée à partir de oriC et des R-loops et en agissant avec RecQ pour résoudre des intermédiaires de recombinaison RecA-dépendants afin de permettre la ségrégation des chromosomes.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.