Parallel metaheuristics for stochastic capacitated multicommodity network design

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

Étude des artefacts en tomodensitométrie par simulation Monte Carlo

En radiothérapie, la tomodensitométrie (CT) fournit l’information anatomique du patient utile au calcul de dose durant la planification de traitement. Afin de considérer la composition hétérogène des tissus, des techniques de calcul telles que la méthode Monte Carlo sont nécessaires pour calculer la dose de manière exacte. L’importation des images CT dans un tel calcul exige que chaque voxel exprimé en unité Hounsfield (HU) soit converti en une valeur physique telle que la densité électronique (ED). Cette conversion est habituellement effectuée à l’aide d’une courbe d’étalonnage HU-ED. Une anomalie ou artefact qui apparaît dans une image CT avant l’étalonnage est susceptible d’assigner un mauvais tissu à un voxel. Ces erreurs peuvent causer une perte cruciale de fiabilité du calcul de dose. Ce travail vise à attribuer une valeur exacte aux voxels d’images CT afin d’assurer la fiabilité des calculs de dose durant la planification de traitement en radiothérapie. Pour y parvenir, une étude est réalisée sur les artefacts qui sont reproduits par simulation Monte Carlo. Pour réduire le temps de calcul, les simulations sont parallélisées et transposées sur un superordinateur. Une étude de sensibilité des nombres HU en présence d’artefacts est ensuite réalisée par une analyse statistique des histogrammes. À l’origine de nombreux artefacts, le durcissement de faisceau est étudié davantage. Une revue sur l’état de l’art en matière de correction du durcissement de faisceau est présentée suivi d’une démonstration explicite d’une correction empirique.

Bundling under the Threat of Parallel Trade

This paper examines the use of bundling by a firm that sells in two national markets and faces entry by parallel traders. The firm can bundle its main product, - a tradable good- with a non-traded service. It chooses between the strategies of pure bundling, mixed bundling and no bundling. The paper shows that in the low-price country the threat of grey trade elicits a move from mixed bundling, or no bundling, towards pure bundling. It encourages a move from pure bundling towards mixes bundling or no bundling in the high-price country. The set of parameter values for which the profit maximizing strategy is not to supply the low price country is smaller than in the absence of bundling. The welfare effects of deterrence of grey trade are not those found in conventional models of price arbitrage. Some consumers in the low-price country may gain from the threat of entry by parallel traders although they pay a higher price. This is due to the fact that the firm responds to the threat of arbitrageurs by increasing the amount of services it puts in the bundle targeted at consumers in that country. Similarly, the threat of parallel trade may affect some consumers in the hight-price country adversely.

H.P. Lovecraft : étude comparative de récits des origines

Les différents commentateurs de Lovecraft se sont au fil du XXe siècle jusqu’à nos jours entendus sur un point : l’originalité de son oeuvre. Impossible à cataloguer dans un genre littéraire précis, offrant de multiples couches d’interprétation, celle-ci fut analysée à la fois sous l’angle psychanalytique et sous l’angle philosophique et scientifique. Cependant, la dimension purement esthétique semble, peut-être par négligence, avoir été oubliée. Notre mémoire propose une investigation de l’esthétique dans l’oeuvre de Lovecraft. Notre hypothèse de recherche repose sur les analogies évidentes et pourtant peu approfondies par la critique entre l’esthétique de celle-ci et l’esthétique cosmogonique de l’Antiquité. Dans un premier temps, nous situerons l’œuvre dans son contexte littéraire, c’est-à-dire que nous nous pencherons sur les rapports évidents qu’elle entretient avec des auteurs tels que J.R.R. Tolkien et Arthur Conan Doyle et sur les différences moins évidentes qui la distinguent d’autres d’auteurs tels que H.G. Wells et William Hope Hodgson. Ensuite, nous mettrons en perspective les différences qui la séparent logiquement de la cosmogonie hébraïque et de la tradition théologique et philosophique qu’elle inaugure, entre autres, tel qu’elle se cristallise dans La Divine Comédie de Dante. Finalement, nous démontrerons à partir d’une comparaison serrée de motifs analogues, présents dans la longue nouvelle de Lovecraft, At the Mountains of Madness et dans le poème d’Hésiode, La Théogonie, le parallèle révélateur entre leurs esthétiques respectives; leurs esthétiques qui découlent de paradigmes du réel historiquement et essentiellement distincts, mais non pas opposés ou contradictoires.

Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Timing verification in transaction modeling

Les systèmes Matériels/Logiciels deviennent indispensables dans tous les aspects de la vie quotidienne. La présence croissante de ces systèmes dans les différents produits et services incite à trouver des méthodes pour les développer efficacement. Mais une conception efficace de ces systèmes est limitée par plusieurs facteurs, certains d'entre eux sont: la complexité croissante des applications, une augmentation de la densité d'intégration, la nature hétérogène des produits et services, la diminution de temps d’accès au marché. Une modélisation transactionnelle (TLM) est considérée comme un paradigme prometteur permettant de gérer la complexité de conception et fournissant des moyens d’exploration et de validation d'alternatives de conception à des niveaux d’abstraction élevés. Cette recherche propose une méthodologie d’expression de temps dans TLM basée sur une analyse de contraintes temporelles. Nous proposons d'utiliser une combinaison de deux paradigmes de développement pour accélérer la conception: le TLM d'une part et une méthodologie d’expression de temps entre différentes transactions d’autre part. Cette synergie nous permet de combiner dans un seul environnement des méthodes de simulation performantes et des méthodes analytiques formelles. Nous avons proposé un nouvel algorithme de vérification temporelle basé sur la procédure de linéarisation des contraintes de type min/max et une technique d'optimisation afin d'améliorer l'efficacité de l'algorithme. Nous avons complété la description mathématique de tous les types de contraintes présentées dans la littérature. Nous avons développé des méthodes d'exploration et raffinement de système de communication qui nous a permis d'utiliser les algorithmes de vérification temporelle à différents niveaux TLM. Comme il existe plusieurs définitions du TLM, dans le cadre de notre recherche, nous avons défini une méthodologie de spécification et simulation pour des systèmes Matériel/Logiciel basée sur le paradigme de TLM. Dans cette méthodologie plusieurs concepts de modélisation peuvent être considérés séparément. Basée sur l'utilisation des technologies modernes de génie logiciel telles que XML, XSLT, XSD, la programmation orientée objet et plusieurs autres fournies par l’environnement .Net, la méthodologie proposée présente une approche qui rend possible une réutilisation des modèles intermédiaires afin de faire face à la contrainte de temps d’accès au marché. Elle fournit une approche générale dans la modélisation du système qui sépare les différents aspects de conception tels que des modèles de calculs utilisés pour décrire le système à des niveaux d’abstraction multiples. En conséquence, dans le modèle du système nous pouvons clairement identifier la fonctionnalité du système sans les détails reliés aux plateformes de développement et ceci mènera à améliorer la "portabilité" du modèle d'application.

Investigation des fonctions du corps calleux par l'étude du transfert interhémisphérique de l'information visuelle et motrice chez les individus normaux et callosotomisés

Le principal rôle du corps calleux est d’assurer le transfert de l’information entre les hémisphères cérébraux. Du support empirique pour cette fonction provient d’études investiguant la communication interhémisphérique chez les individus à cerveau divisé (ICD). Des paradigmes expérimentaux exigeant une intégration interhémisphérique de l’information permettent de documenter certains signes de déconnexion calleuse chez ces individus. La présente thèse a investigué le transfert de l’information sous-tendant les phénomènes de gain de redondance (GR), de différence croisé– non-croisé (DCNC) et d’asynchronie bimanuelle chez les ICD et les individus normaux, et a ainsi contribué à préciser le rôle du corps calleux. Une première étude a comparé le GR des individus normaux et des ICD ayant subi une section partielle ou totale du corps calleux. Dans une tâche de détection, le GR consiste en la réduction des temps de réaction (TR) lorsque deux stimuli sont présentés plutôt qu’un seul. Typiquement, les ICD présentent un GR beaucoup plus grand (supra-GR) que celui des individus normaux (Reuter-Lorenz, Nozawa, Gazzaniga, & Hughes, 1995). Afin d’investiguer les conditions d’occurrence du supra-GR, nous avons évalué le GR en présentation interhémisphérique, intrahémisphérique et sur le méridien vertical, ainsi qu’avec des stimuli requérant une contribution corticale différente (luminance, couleur équiluminante ou mouvement). La présence d’un supra-GR chez les ICD partiels et totaux en comparaison avec celui des individus normaux a été confirmée. Ceci suggère qu’une section antérieure du corps calleux, qui perturbe le transfert d’informations de nature motrice/décisionnelle, est suffisante pour produire un supra-GR chez les ICD. Nos données permettent aussi d’affirmer que, contrairement au GR des individus normaux, celui des ICD totaux est sensible aux manipulations sensorielles. Nous concluons donc que le supra-GR des ICD est à la fois attribuable à des contributions sensorielles et motrices/décisionnelles. Une deuxième étude a investigué la DCNC et l’asynchronie bimanuelle chez les ICD et les individus normaux. La DCNC réfère à la soustraction des TR empruntant une voie anatomique « non-croisée » aux TR empruntant une voie anatomique « croisée », fournissant ainsi une estimation du temps de transfert interhémisphérique. Dans le contexte de notre étude, l’asynchronie bimanuelle réfère à la différence de TR entre la main gauche et la main droite, sans égard à l’hémichamp de présentation. Les effets de manipulations sensorielles et attentionnelles ont été évalués pour les deux mesures. Cette étude a permis d’établir une dissociation entre la DCNC et l’asynchronie bimanuelle. Précisément, les ICD totaux, mais non les ICD partiels, ont montré une DCNC significativement plus grande que celle des individus normaux, alors que les deux groupes d’ICD se sont montrés plus asynchrones que les individus normaux. Nous postulons donc que des processus indépendants sous-tendent la DCNC et la synchronie bimanuelle. De plus, en raison de la modulation parallèle du GR et de l’asynchronie bimanuelle entre les groupes, nous suggérons qu’un processus conjoint sous-tend ces deux mesures.

Implantation des futures sur un système distribué par passage de messages

Ce mémoire présente une implantation de la création paresseuse de tâches desti- née à des systèmes multiprocesseurs à mémoire distribuée. Elle offre un sous-ensemble des fonctionnalités du Message-Passing Interface et permet de paralléliser certains problèmes qui se partitionnent difficilement de manière statique grâce à un système de partitionnement dynamique et de balancement de charge. Pour ce faire, il se base sur le langage Multilisp, un dialecte de Scheme orienté vers le traitement parallèle, et implante sur ce dernier une interface semblable à MPI permettant le calcul distribué multipro- cessus. Ce système offre un langage beaucoup plus riche et expressif que le C et réduit considérablement le travail nécessaire au programmeur pour pouvoir développer des programmes équivalents à ceux en MPI. Enfin, le partitionnement dynamique permet de concevoir des programmes qui seraient très complexes à réaliser sur MPI. Des tests ont été effectués sur un système local à 16 processeurs et une grappe à 16 processeurs et il offre de bonnes accélérations en comparaison à des programmes séquentiels équiva- lents ainsi que des performances acceptables par rapport à MPI. Ce mémoire démontre que l’usage des futures comme technique de partitionnement dynamique est faisable sur des multiprocesseurs à mémoire distribuée.

Our Lady of Ocotlán and our Lady of Guadalupe : investigation into the origins of parallel virgins

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Tarification logit dans un réseau

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Evaluation of mitochondrial function in a model of developmental programming of hypertension associated with transient neonatal oxygen exposure

UNE EXPOSITION NÉONATALE À L’OXYGÈNE MÈNE À DES MODIFICATIONS DE LA FONCTION MITOCHONDRIALE CHEZ LE RAT ADULTE Introduction: L’exposition à l’oxygène (O2) des ratons nouveau-nés a des conséquences à l’âge adulte dont une hypertension artérielle (HTA), une dysfonction vasculaire, une néphropénie et des indices de stress oxydant. En considérant que les reins sont encore en développement actif lors des premiers jours après la naissance chez les rats, jouent un rôle clé dans le développement de l’hypertension et qu’une dysfonction mitochondriale est associé à une augmentation du stress oxydant, nous postulons que les conditions délétères néonatales peuvent avoir un impact significatif au niveau rénal sur la modulation de l’expression de protéines clés du fonctionnement mitochondrial et une production mitochondriale excessive d’espèces réactives de l’ O2. Méthodes: Des ratons Sprague-Dawley sont exposés à 80% d’O2 (H) ou 21% O2 (Ctrl) du 3e au 10e jr de vie. En considérant que plusieurs organes des rats sont encore en développement actif à la naissance, ces rongeurs sont un modèle reconnu pour étudier les complications d’une hyperoxie néonatale, comme celles liées à une naissance prématurée chez l’homme. À 4 et à 16 semaines, les reins sont prélevés et les mitochondries sont extraites suivant une méthode d’extraction standard, avec un tampon contenant du sucrose 0.32 M et différentes centrifugations. L’expression des protéines mitochondriales a été mesurée par Western blot, tandis que la production d’ H202 et les activités des enzymes clés du cycle de Krebs ont été évaluées par spectrophotométrie. Les résultats sont exprimés par la moyenne ± SD. Résultats: Les rats mâles H de 16 semaines (n=6) présentent une activité de citrate synthase (considéré standard interne de l’expression protéique et de l’abondance mitochondriales) augmentée (12.4 ± 8.4 vs 4.1 ± 0.5 μmole/mL/min), une diminution de l’activité d’aconitase (enzyme sensible au redox mitochondrial) (0.11 ± 0.05 vs 0.20 ± 0.04 μmoles/min/mg mitochondrie), ainsi qu’une augmentation dans la production de H202 (7.0 ± 1.3 vs 5.4 ± 0.8 ρmoles/mg protéines mitochondriales) comparativement au groupe Ctrl (n=6 mâles et 4 femelles). Le groupe H (vs Ctrl) présente également une diminution dans l’expression de peroxiredoxin-3 (Prx3) (H 0.61±0.06 vs. Ctrl 0.78±0.02 unité relative, -23%; p<0.05), une protéine impliquée dans l’élimination d’ H202, de l’expression du cytochrome C oxidase (Complexe IV) (H 1.02±0.04 vs. Ctrl 1.20±0.02 unité relative, -15%; p<0.05), une protéine de la chaine de respiration mitochondriale, tandis que l’expression de la protéine de découplage (uncoupling protein)-2 (UCP2), impliquée dans la dispersion du gradient proton, est significativement augmentée (H 1.05±0.02 vs. Ctrl 0.90±0.03 unité relative, +17%; p<0.05). Les femelles H (n=6) (vs Ctrl, n=6) de 16 semaines démontrent une augmentation significative de l’activité de l’aconitase (0.33±0.03 vs 0.17±0.02 μmoles/min/mg mitochondrie), de l’expression de l’ATP synthase sous unité β (H 0.73±0.02 vs. Ctrl 0.59±0.02 unité relative, +25%; p<0.05) et de l’expression de MnSOD (H 0.89±0.02 vs. Ctrl 0.74±0.03 unité relative, +20%; p<0.05) (superoxide dismutase mitochondriale, important antioxidant), tandis que l’expression de Prx3 est significativement réduite (H 1.1±0.07 vs. Ctrl 0.85±0.01 unité relative, -24%; p<0.05). À 4 semaines, les mâles H (vs Ctrl) présentent une augmentation significative de l’expression de Prx3 (H 0.72±0.03 vs. Ctrl 0.56±0.04 unité relative, +31%; p<0.05) et les femelles présentent une augmentation significative de l’expression d’UCP2 (H 1.22±0.05 vs. Ctrl 1.03±0.04 unité relative, +18%; p<0.05) et de l’expression de MnSOD (H 1.36±0.01 vs. 1.19±0.06 unité relative, +14%; p<0.05). Conclusions: Une exposition néonatale à l’O2 chez le rat adulte mène à des indices de dysfonction mitochondriale dans les reins adultes, associée à une augmentation dans la production d’espèces réactives de l’oxygène, suggérant que ces modifications mitochondriales pourraient jouer un rôle dans l’hypertension artérielle et d’un stress oxydant, et par conséquent, être un facteur possible dans la progression vers des maladies cardiovasculaires. Mots-clés: Mitochondries, Reins, Hypertension, Oxygène, Stress Oxydant, Programmation

La fragmentation du droit international:vers un changement de paradigme ?

Le droit international prend de plus en plus d’expansion au sein de la société internationale. En fait, grâce à plusieurs acteurs, le droit international s’étend maintenant à de nombreux domaines tels que l’environnement, le droit humanitaire, l’énergie, etc. Or, parallèlement à cette expansion du droit international, on craint maintenant sa fragmentation. Face à ce nouveau phénomène, il y a lieu de se poser la question suivante : s’il y existe un phénomène de fragmentation du droit international, cela signifie-t-il qu’une unité, qui semblait exister a priori dans ce droit, est en train de disparaître, ou bien assistons-nous plutôt à un changement de paradigme? Pour répondre, à cette interrogation, l’auteur analyse tout d’abord les différents facteurs de fragmentation du droit international et observe que ce droit devient de plus en plus complexe, voire même désordonné. Le tout, à l’opposé de la vision traditionnelle d’unité que l’on a du droit. Quels éléments de solution peuvent alors être apportés pour réduire cette fragmentation? Pour le savoir, l’auteur analyse l’unité du droit en fonction de deux paradigmes : le normativisme et le pluralisme juridique. Dans le premier, c'est la hiérarchie des normes qui va donner lieu à un ordre et à une unité du droit. Dans le second, le droit est perçu comme une institution qui apporte la cohésion et il existe autant d’ordres juridiques qu’il y existe d’institutions. C'est dans ce contexte que naît une certaine unité générale grâce à divers types de rapports entre les différents ordres juridiques. Mais en droit international, l’idée d’organisation hiérarchique des normes ne pourrait englober toute la complexité grandissante de la société pluraliste internationale. C'est pourquoi, l’auteur conclu que la fragmentation du droit international signifie un changement de paradigme : ce n’est plus la théorie normativiste qui permet d’englober la toute la complexité naissante du droit international mais bien la théorie du pluralisme juridique.

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.