Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

Segmentation d’images intravasculaires ultrasonores

L'imagerie intravasculaire ultrasonore (IVUS) est une technologie médicale par cathéter qui produit des images de coupe des vaisseaux sanguins. Elle permet de quantifier et d'étudier la morphologie de plaques d'athérosclérose en plus de visualiser la structure des vaisseaux sanguins (lumière, intima, plaque, média et adventice) en trois dimensions. Depuis quelques années, cette méthode d'imagerie est devenue un outil de choix en recherche aussi bien qu'en clinique pour l'étude de la maladie athérosclérotique. L'imagerie IVUS est par contre affectée par des artéfacts associés aux caractéristiques des capteurs ultrasonores, par la présence de cônes d'ombre causés par les calcifications ou des artères collatérales, par des plaques dont le rendu est hétérogène ou par le chatoiement ultrasonore (speckle) sanguin. L'analyse automatisée de séquences IVUS de grande taille représente donc un défi important. Une méthode de segmentation en trois dimensions (3D) basée sur l'algorithme du fast-marching à interfaces multiples est présentée. La segmentation utilise des attributs des régions et contours des images IVUS. En effet, une nouvelle fonction de vitesse de propagation des interfaces combinant les fonctions de densité de probabilité des tons de gris des composants de la paroi vasculaire et le gradient des intensités est proposée. La segmentation est grandement automatisée puisque la lumière du vaisseau est détectée de façon entièrement automatique. Dans une procédure d'initialisation originale, un minimum d'interactions est nécessaire lorsque les contours initiaux de la paroi externe du vaisseau calculés automatiquement sont proposés à l'utilisateur pour acceptation ou correction sur un nombre limité d'images de coupe longitudinale. La segmentation a été validée à l'aide de séquences IVUS in vivo provenant d'artères fémorales provenant de différents sous-groupes d'acquisitions, c'est-à-dire pré-angioplastie par ballon, post-intervention et à un examen de contrôle 1 an suivant l'intervention. Les résultats ont été comparés avec des contours étalons tracés manuellement par différents experts en analyse d'images IVUS. Les contours de la lumière et de la paroi externe du vaisseau détectés selon la méthode du fast-marching sont en accord avec les tracés manuels des experts puisque les mesures d'aire sont similaires et les différences point-à-point entre les contours sont faibles. De plus, la segmentation par fast-marching 3D s'est effectuée en un temps grandement réduit comparativement à l'analyse manuelle. Il s'agit de la première étude rapportée dans la littérature qui évalue la performance de la segmentation sur différents types d'acquisition IVUS. En conclusion, la segmentation par fast-marching combinant les informations des distributions de tons de gris et du gradient des intensités des images est précise et efficace pour l'analyse de séquences IVUS de grandes tailles. Un outil de segmentation robuste pourrait devenir largement répandu pour la tâche ardue et fastidieuse qu'est l'analyse de ce type d'images.

Algorithmes pour la réconciliation d’un arbre de gènes avec un arbre d’espèces

Une réconciliation entre un arbre de gènes et un arbre d’espèces décrit une histoire d’évolution des gènes homologues en termes de duplications et pertes de gènes. Pour inférer une réconciliation pour un arbre de gènes et un arbre d’espèces, la parcimonie est généralement utilisée selon le nombre de duplications et/ou de pertes. Les modèles de réconciliation sont basés sur des critères probabilistes ou combinatoires. Le premier article définit un modèle combinatoire simple et général où les duplications et les pertes sont clairement identifiées et la réconciliation parcimonieuse n’est pas la seule considérée. Une architecture de toutes les réconciliations est définie et des algorithmes efficaces (soit de dénombrement, de génération aléatoire et d’exploration) sont développés pour étudier les propriétés combinatoires de l’espace de toutes les réconciliations ou seulement les plus parcimonieuses. Basée sur le processus classique nommé naissance-et-mort, un algorithme qui calcule la vraisemblance d’une réconciliation a récemment été proposé. Le deuxième article utilise cet algorithme avec les outils combinatoires décrits ci-haut pour calculer efficacement (soit approximativement ou exactement) les probabilités postérieures des réconciliations localisées dans le sous-espace considéré. Basé sur des taux réalistes (selon un modèle probabiliste) de duplication et de perte et sur des données réelles/simulées de familles de champignons, nos résultats suggèrent que la masse probabiliste de toute l’espace des réconciliations est principalement localisée autour des réconciliations parcimonieuses. Dans un contexte d’approximation de la probabilité d’une réconciliation, notre approche est une alternative intéressante face aux méthodes MCMC et peut être meilleure qu’une approche sophistiquée, efficace et exacte pour calculer la probabilité d’une réconciliation donnée. Le problème nommé Gene Tree Parsimony (GTP) est d’inférer un arbre d’espèces qui minimise le nombre de duplications et/ou de pertes pour un ensemble d’arbres de gènes. Basé sur une approche qui explore tout l’espace des arbres d’espèces pour les génomes considérés et un calcul efficace des coûts de réconciliation, le troisième article décrit un algorithme de Branch-and-Bound pour résoudre de façon exacte le problème GTP. Lorsque le nombre de taxa est trop grand, notre algorithme peut facilement considérer des relations prédéfinies entre ensembles de taxa. Nous avons testé notre algorithme sur des familles de gènes de 29 eucaryotes.

Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future.

Sleep spindle activity in children with ADHD

Le trouble du déficit de l’attention/hyperactivité (TDA/H) est le désordre du comportement le plus commun chez les enfants. Les études suggèrent qu'un pourcentage élevé d'enfants atteints de TDA/H souffre de problèmes de sommeil et de somnolence diurne. Le mécanisme sous-jacent à ces difficultés demeure inconnu. Plusieurs études ont suggéré que les fuseaux de sommeil jouent un rôle dans les mécanismes de protection du sommeil. L'objectif de cette étude est de comparer les fuseaux lents (11-13 Hz) et rapides (14-15 Hz) chez des enfants atteints du TDA/H et des sujets contrôles. Nous prévoyons que comparativement aux enfants contrôles, les enfants atteints du TDA/H montreront une plus faible densité des fuseaux lents et rapides, et auront des fuseaux plus courts (sec), moins amples (uV) et plus rapides (cycle/sec). Enfin, nous prévoyons que ces effets seront plus prononcés dans les dérivations cérébrales antérieures que dans les dérivations plus postérieures du cerveau. Les enregistrements polysomnographiques (PSG) du sommeil de nuit ont été menés chez 18 enfants diagnostiqués avec le TDA/H et chez 26 sujets témoins âgés entre 7 et 11 ans. Un algorithme automatique a permis de détecter les fuseaux lents et rapides sur les dérivations frontales, centrales, pariétales et occipitales. Les résultats ont montré que, les caractéristiques PSG du sommeil ne différaient pas significativement entre les deux groupes. On ne note aucune différence significative entre les groupes sur nombre/densité des fuseaux lents et rapides ainsi que sur leurs caractéristiques respectives. Cette étude suggère que les mécanismes de synchronisation du l'EEG en sommeil lent, tel que mesuré par la densité et les caractéristiques des fuseaux lents et rapides en sommeil lent ne différent pas chez les enfants atteints du TDA/H.

Génération et reconnaissance de rythmes au moyen de réseaux de neurones à réservoir

Les fichiers sons qui accompagne mon document sont au format midi. Le programme que nous avons développés pour ce travail est en language Python.

Modèle de mélange de lois multinormales appliqué à l'analyse de comportements et d'habiletés cognitives d'enfants.

Cette étude aborde le thème de l’utilisation des modèles de mélange de lois pour analyser des données de comportements et d’habiletés cognitives mesurées à plusieurs moments au cours du développement des enfants. L’estimation des mélanges de lois multinormales en utilisant l’algorithme EM est expliquée en détail. Cet algorithme simplifie beaucoup les calculs, car il permet d’estimer les paramètres de chaque groupe séparément, permettant ainsi de modéliser plus facilement la covariance des observations à travers le temps. Ce dernier point est souvent mis de côté dans les analyses de mélanges. Cette étude porte sur les conséquences d’une mauvaise spécification de la covariance sur l’estimation du nombre de groupes formant un mélange. La conséquence principale est la surestimation du nombre de groupes, c’est-à-dire qu’on estime des groupes qui n’existent pas. En particulier, l’hypothèse d’indépendance des observations à travers le temps lorsque ces dernières étaient corrélées résultait en l’estimation de plusieurs groupes qui n’existaient pas. Cette surestimation du nombre de groupes entraîne aussi une surparamétrisation, c’est-à-dire qu’on utilise plus de paramètres qu’il n’est nécessaire pour modéliser les données. Finalement, des modèles de mélanges ont été estimés sur des données de comportements et d’habiletés cognitives. Nous avons estimé les mélanges en supposant d’abord une structure de covariance puis l’indépendance. On se rend compte que dans la plupart des cas l’ajout d’une structure de covariance a pour conséquence d’estimer moins de groupes et les résultats sont plus simples et plus clairs à interpréter.

Categorical quantum computation

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

Reliable computation for geometric models

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

Développement d’une méthode de simulation multi-échelle pour l’étude des grandes transformations dans les protéines

Les films de simulations qui accompagnent le document ont été réalisés avec Pymol.

Reliable Solid Modelling Using Subdivision Surfaces

Les surfaces de subdivision fournissent une méthode alternative prometteuse dans la modélisation géométrique, et ont des avantages sur la représentation classique de trimmed-NURBS, en particulier dans la modélisation de surfaces lisses par morceaux. Dans ce mémoire, nous considérons le problème des opérations géométriques sur les surfaces de subdivision, avec l'exigence stricte de forme topologique correcte. Puisque ce problème peut être mal conditionné, nous proposons une approche pour la gestion de l'incertitude qui existe dans le calcul géométrique. Nous exigeons l'exactitude des informations topologiques lorsque l'on considère la nature de robustesse du problème des opérations géométriques sur les modèles de solides, et il devient clair que le problème peut être mal conditionné en présence de l'incertitude qui est omniprésente dans les données. Nous proposons donc une approche interactive de gestion de l'incertitude des opérations géométriques, dans le cadre d'un calcul basé sur la norme IEEE arithmétique et la modélisation en surfaces de subdivision. Un algorithme pour le problème planar-cut est alors présenté qui a comme but de satisfaire à l'exigence topologique mentionnée ci-dessus.

Une nouvelle méthode smoothed particle hydrodynamics : simulation des interfaces immergées et de la dynamique Brownienne des molécules avec des interactions hydrodynamiques

Dans cette thèse, nous présentons une nouvelle méthode smoothed particle hydrodynamics (SPH) pour la résolution des équations de Navier-Stokes incompressibles, même en présence des forces singulières. Les termes de sources singulières sont traités d'une manière similaire à celle que l'on retrouve dans la méthode Immersed Boundary (IB) de Peskin (2002) ou de la méthode régularisée de Stokeslets (Cortez, 2001). Dans notre schéma numérique, nous mettons en oeuvre une méthode de projection sans pression de second ordre inspirée de Kim et Moin (1985). Ce schéma évite complètement les difficultés qui peuvent être rencontrées avec la prescription des conditions aux frontières de Neumann sur la pression. Nous présentons deux variantes de cette approche: l'une, Lagrangienne, qui est communément utilisée et l'autre, Eulerienne, car nous considérons simplement que les particules SPH sont des points de quadrature où les propriétés du fluide sont calculées, donc, ces points peuvent être laissés fixes dans le temps. Notre méthode SPH est d'abord testée à la résolution du problème de Poiseuille bidimensionnel entre deux plaques infinies et nous effectuons une analyse détaillée de l'erreur des calculs. Pour ce problème, les résultats sont similaires autant lorsque les particules SPH sont libres de se déplacer que lorsqu'elles sont fixes. Nous traitons, par ailleurs, du problème de la dynamique d'une membrane immergée dans un fluide visqueux et incompressible avec notre méthode SPH. La membrane est représentée par une spline cubique le long de laquelle la tension présente dans la membrane est calculée et transmise au fluide environnant. Les équations de Navier-Stokes, avec une force singulière issue de la membrane sont ensuite résolues pour déterminer la vitesse du fluide dans lequel est immergée la membrane. La vitesse du fluide, ainsi obtenue, est interpolée sur l'interface, afin de déterminer son déplacement. Nous discutons des avantages à maintenir les particules SPH fixes au lieu de les laisser libres de se déplacer. Nous appliquons ensuite notre méthode SPH à la simulation des écoulements confinés des solutions de polymères non dilués avec une interaction hydrodynamique et des forces d'exclusion de volume. Le point de départ de l'algorithme est le système couplé des équations de Langevin pour les polymères et le solvant (CLEPS) (voir par exemple Oono et Freed (1981) et Öttinger et Rabin (1989)) décrivant, dans le cas présent, les dynamiques microscopiques d'une solution de polymère en écoulement avec une représentation bille-ressort des macromolécules. Des tests numériques de certains écoulements dans des canaux bidimensionnels révèlent que l'utilisation de la méthode de projection d'ordre deux couplée à des points de quadrature SPH fixes conduit à un ordre de convergence de la vitesse qui est de deux et à une convergence d'ordre sensiblement égale à deux pour la pression, pourvu que la solution soit suffisamment lisse. Dans le cas des calculs à grandes échelles pour les altères et pour les chaînes de bille-ressort, un choix approprié du nombre de particules SPH en fonction du nombre des billes N permet, en l'absence des forces d'exclusion de volume, de montrer que le coût de notre algorithme est d'ordre O(N). Enfin, nous amorçons des calculs tridimensionnels avec notre modèle SPH. Dans cette optique, nous résolvons le problème de l'écoulement de Poiseuille tridimensionnel entre deux plaques parallèles infinies et le problème de l'écoulement de Poiseuille dans une conduite rectangulaire infiniment longue. De plus, nous simulons en dimension trois des écoulements confinés entre deux plaques infinies des solutions de polymères non diluées avec une interaction hydrodynamique et des forces d'exclusion de volume.

Implantation et validation d’un modèle Monte Carlo du Cyberknife dans un outil de calcul de dose clinique

Le travail de modélisation a été réalisé à travers EGSnrc, un logiciel développé par le Conseil National de Recherche Canada.

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

Optimisation des horaires des agents et du routage des appels dans les centres d’appels

Nous étudions la gestion de centres d'appels multi-compétences, ayant plusieurs types d'appels et groupes d'agents. Un centre d'appels est un système de files d'attente très complexe, où il faut généralement utiliser un simulateur pour évaluer ses performances. Tout d'abord, nous développons un simulateur de centres d'appels basé sur la simulation d'une chaîne de Markov en temps continu (CMTC), qui est plus rapide que la simulation conventionnelle par événements discrets. À l'aide d'une méthode d'uniformisation de la CMTC, le simulateur simule la chaîne de Markov en temps discret imbriquée de la CMTC. Nous proposons des stratégies pour utiliser efficacement ce simulateur dans l'optimisation de l'affectation des agents. En particulier, nous étudions l'utilisation des variables aléatoires communes. Deuxièmement, nous optimisons les horaires des agents sur plusieurs périodes en proposant un algorithme basé sur des coupes de sous-gradients et la simulation. Ce problème est généralement trop grand pour être optimisé par la programmation en nombres entiers. Alors, nous relaxons l'intégralité des variables et nous proposons des méthodes pour arrondir les solutions. Nous présentons une recherche locale pour améliorer la solution finale. Ensuite, nous étudions l'optimisation du routage des appels aux agents. Nous proposons une nouvelle politique de routage basé sur des poids, les temps d'attente des appels, et les temps d'inoccupation des agents ou le nombre d'agents libres. Nous développons un algorithme génétique modifié pour optimiser les paramètres de routage. Au lieu d'effectuer des mutations ou des croisements, cet algorithme optimise les paramètres des lois de probabilité qui génèrent la population de solutions. Par la suite, nous développons un algorithme d'affectation des agents basé sur l'agrégation, la théorie des files d'attente et la probabilité de délai. Cet algorithme heuristique est rapide, car il n'emploie pas la simulation. La contrainte sur le niveau de service est convertie en une contrainte sur la probabilité de délai. Par après, nous proposons une variante d'un modèle de CMTC basé sur le temps d'attente du client à la tête de la file. Et finalement, nous présentons une extension d'un algorithme de coupe pour l'optimisation stochastique avec recours de l'affectation des agents dans un centre d'appels multi-compétences.