Quadtree representation and compression of spatial data

Spatial data representation and compression has become a focus issue in computer graphics and image processing applications. Quadtrees, as one of hierarchical data structures, basing on the principle of recursive decomposition of space, always offer a compact and efficient representation of an image. For a given image, the choice of quadtree root node plays an important role in its quadtree representation and final data compression. The goal of this thesis is to present a heuristic algorithm for finding a root node of a region quadtree, which is able to reduce the number of leaf nodes when compared with the standard quadtree decomposition. The empirical results indicate that, this proposed algorithm has quadtree representation and data compression improvement when in comparison with the traditional method.

Teachers' professional learning within communities of mathematics-for-teaching practice

Ontario bansho is an emergent mathematics instructional strategy used by teachers working within communities of practice that has been deemed to have a transformational effect on teachers' professional learning of mathematics. This study sought to answer the following question: How does teachers' implementation of Ontario bansho within their communities of practice inform their professional learning process concerning mathematics-for-teaching? Two other key questions also guided the study: What processes support teachers' professional learning of content-for-teaching? What conditions support teachers' professional learning of content-for-teaching? The study followed an interpretive phenomenological approach to collect data using a purposive sampling of teachers as participants. The researcher conducted interviews and followed an interpretive approach to data analysis to investigate how teachers construct meaning and create interpretations through their social interactions. The study developed a model of professional learning made up of 3 processes, informing with resources, engaging with students, and visualizing and schematizing in which the participants engaged and 2 conditions, ownership and community that supported the 3 processes. The 3 processes occur in ways that are complex, recursive, nonpredictable, and contextual. This model provides a framework for facilitators and leaders to plan for effective, content-relevant professional learning by placing teachers, students, and their learning at the heart of professional learning.

A Narrative Study of Patient Encounter Accounts of Physicians, Nurses, and Medical Receptionists after Two Decades of a Paradigm of Patient-Centered Care

Despite recent well-known advancements in patient care in the medical fields, such as patient-centeredness and evidence-based medicine and practice, there is rather less known about their effects on the particulars of clinician-patient encounters. The emphasis in clinical encounters remains mostly on treatment and diagnosis and less on communicative competency or engagement for medical professionals. The purpose of this narrative study was to explore interactive competencies in diagnostic and therapeutic encounters and intake protocols within the context of the physicians’, nurses’, and medical receptionists’ perspectives and experiences. Literature on narrative medicine, phenomenology and medicine, therapeutic relationships, cultural and communication competency, and non-Western perspectives on human communication provided the guiding theoretical frameworks for the study. Three data sets including 13 participant interviews (5 physicians, 4 nurses, and 4 medical receptionists), policy documents (physicians, nurses, and medical receptionists) and a website (Communication and Cultural Competency) were used. The researcher then engaged in triangulated analyses, including N-Vivo, manifest and latent, Mishler’s (1984, 1995) narrative elements and Charon’s (2005, 2006a, 2006b, 2013) narrative themes, in recursive, overlapping, comparative and intersected analysis strategies. A common factor affecting physicians’ relationships with their clients was limitation of time, including limited time (a) to listen, (b) to come up with a proper diagnosis, and (c) to engage in decision making in critical conditions and limited time for patients’ visits. For almost all nurse participants in the study establishing therapeutic relationships meant being compassionate and empathetic. The goals of intake protocols for the medical receptionists were about being empathetic to patients, being an attentive listener, developing rapport, and being conventionally polite to patients. Participants with the least iv amount of training and preparation (medical receptionists) appeared to be more committed to working narratively in connecting with patients and establishing human relationships as well as in listening to patients’ stories and providing support to narrow down the reason for their visit. The diagnostic and intake “success stories” regarding patient clinical encounters for other study participants were focused on a timely securing of patient information, with some acknowledgement of rapport and emapathy. Patient-centeredness emerged as a discourse practice, with ambiguous or nebulous enactment of its premises in most clinical settings.

The Fast Regulation of Photosynthesis in Diatoms: an inquiry into the physiological and physical origins of non-photochemical chlorophyll fluorescence quenching.

Diatoms are renowned for their robust ability to perform NPQ (Non-Photochemical Quenching of chlorophyll fluorescence) as a dissipative response to heightened light stress on photosystem II, plausibly explaining their dominance over other algal groups in turbulent light environs. Their NPQ mechanism has been principally attributed to a xanthophyll cycle involving the lumenal pH regulated reversible de-epoxidation of diadinoxanthin. The principal goal of this dissertation is to reveal the physiological and physical origins and consequences of the NPQ response in diatoms during short-term transitions to excessive irradiation. The investigation involves diatom species from different originating light environs to highlight the diversity of diatom NPQ and to facilitate the detection of core mechanisms common among the diatoms as a group. A chiefly spectroscopic approach was used to investigate NPQ in diatom cells. Prime methodologies include: the real time monitoring of PSII excitation and de-excitation pathways via PAM fluorometry and pigment interconversion via transient absorbance measurements, the collection of cryogenic absorbance spectra to measure pigment energy levels, and the collection of cryogenic fluorescence spectra and room temperature picosecond time resolved fluorescence decay spectra to study excitation energy transfer and dissipation. Chemical inhibitors that target the trans-thylakoid pH gradient, the enzyme responsible for diadinoxanthin de-epoxidation, and photosynthetic electron flow were additionally used to experimentally manipulate the NPQ response. Multifaceted analyses of the NPQ responses from two previously un-photosynthetically characterised species, Nitzschia curvilineata and Navicula sp., were used to identify an excitation pressure relief ‘strategy’ for each species. Three key areas of NPQ were examined: (i) the NPQ activation/deactivation processes, (ii) how NPQ affects the collection, dissipation, and usage of absorbed light energy, and (iii) the interdependence of NPQ and photosynthetic electron flow. It was found that Nitzschia cells regulate excitation pressure via performing a high amplitude, reversible antenna based quenching which is dependent on the de-epoxidation of diadinoxanthin. In Navicula cells excitation pressure could be effectively regulated solely within the PSII reaction centre, whilst antenna based, diadinoxanthin de-epoxidation dependent quenching was implicated to be used as a supplemental, long-lasting source of excitation energy dissipation. These strategies for excitation balance were discussed in the context of resource partitioning under these species’ originating light climates. A more detailed investigation of the NPQ response in Nitzschia was used to develop a comprehensive model describing the mechanism for antenna centred non-photochemical quenching in this species. The experimental evidence was strongly supportive of a mechanism whereby: an acidic lumen triggers the diadinoxanthin de-epoxidation and protonation mediated aggregation of light harvesting complexes leading to the formation of quencher chlorophyll a-chlorophyll a dimers with short-lived excited states; quenching relaxes when a rise in lumen pH triggers the dispersal of light harvesting complex aggregates via deprotonation events and the input of diadinoxanthin. This model may also be applicable for describing antenna based NPQ in other diatom species.

Empirical Assessment of an Intertemporal Option Pricing Model with Latent variables

This paper assesses the empirical performance of an intertemporal option pricing model with latent variables which generalizes the Hull-White stochastic volatility formula. Using this generalized formula in an ad-hoc fashion to extract two implicit parameters and forecast next day S&P 500 option prices, we obtain similar pricing errors than with implied volatility alone as in the Hull-White case. When we specialize this model to an equilibrium recursive utility model, we show through simulations that option prices are more informative than stock prices about the structural parameters of the model. We also show that a simple method of moments with a panel of option prices provides good estimates of the parameters of the model. This lays the ground for an empirical assessment of this equilibrium model with S&P 500 option prices in terms of pricing errors.

Risk Aversion, Intertemporal Substitution, and Option Pricing

This paper develops a general stochastic framework and an equilibrium asset pricing model that make clear how attitudes towards intertemporal substitution and risk matter for option pricing. In particular, we show under which statistical conditions option pricing formulas are not preference-free, in other words, when preferences are not hidden in the stock and bond prices as they are in the standard Black and Scholes (BS) or Hull and White (HW) pricing formulas. The dependence of option prices on preference parameters comes from several instantaneous causality effects such as the so-called leverage effect. We also emphasize that the most standard asset pricing models (CAPM for the stock and BS or HW preference-free option pricing) are valid under the same stochastic setting (typically the absence of leverage effect), regardless of preference parameter values. Even though we propose a general non-preference-free option pricing formula, we always keep in mind that the BS formula is dominant both as a theoretical reference model and as a tool for practitioners. Another contribution of the paper is to characterize why the BS formula is such a benchmark. We show that, as soon as we are ready to accept a basic property of option prices, namely their homogeneity of degree one with respect to the pair formed by the underlying stock price and the strike price, the necessary statistical hypotheses for homogeneity provide BS-shaped option prices in equilibrium. This BS-shaped option-pricing formula allows us to derive interesting characterizations of the volatility smile, that is, the pattern of BS implicit volatilities as a function of the option moneyness. First, the asymmetry of the smile is shown to be equivalent to a particular form of asymmetry of the equivalent martingale measure. Second, this asymmetry appears precisely when there is either a premium on an instantaneous interest rate risk or on a generalized leverage effect or both, in other words, whenever the option pricing formula is not preference-free. Therefore, the main conclusion of our analysis for practitioners should be that an asymmetric smile is indicative of the relevance of preference parameters to price options.

Bootstrapping Autoregressions with Conditional Heteroskedasticity of Unknown Form

Conditional heteroskedasticity is an important feature of many macroeconomic and financial time series. Standard residual-based bootstrap procedures for dynamic regression models treat the regression error as i.i.d. These procedures are invalid in the presence of conditional heteroskedasticity. We establish the asymptotic validity of three easy-to-implement alternative bootstrap proposals for stationary autoregressive processes with m.d.s. errors subject to possible conditional heteroskedasticity of unknown form. These proposals are the fixed-design wild bootstrap, the recursive-design wild bootstrap and the pairwise bootstrap. In a simulation study all three procedures tend to be more accurate in small samples than the conventional large-sample approximation based on robust standard errors. In contrast, standard residual-based bootstrap methods for models with i.i.d. errors may be very inaccurate if the i.i.d. assumption is violated. We conclude that in many empirical applications the proposed robust bootstrap procedures should routinely replace conventional bootstrap procedures for autoregressions based on the i.i.d. error assumption.

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.

Annotation syntaxico-sémantique des actants en corpus spécialisé

L’annotation en rôles sémantiques est une tâche qui permet d’attribuer des étiquettes de rôles telles que Agent, Patient, Instrument, Lieu, Destination etc. aux différents participants actants ou circonstants (arguments ou adjoints) d’une lexie prédicative. Cette tâche nécessite des ressources lexicales riches ou des corpus importants contenant des phrases annotées manuellement par des linguistes sur lesquels peuvent s’appuyer certaines approches d’automatisation (statistiques ou apprentissage machine). Les travaux antérieurs dans ce domaine ont porté essentiellement sur la langue anglaise qui dispose de ressources riches, telles que PropBank, VerbNet et FrameNet, qui ont servi à alimenter les systèmes d’annotation automatisés. L’annotation dans d’autres langues, pour lesquelles on ne dispose pas d’un corpus annoté manuellement, repose souvent sur le FrameNet anglais. Une ressource telle que FrameNet de l’anglais est plus que nécessaire pour les systèmes d’annotation automatisé et l’annotation manuelle de milliers de phrases par des linguistes est une tâche fastidieuse et exigeante en temps. Nous avons proposé dans cette thèse un système automatique pour aider les linguistes dans cette tâche qui pourraient alors se limiter à la validation des annotations proposées par le système. Dans notre travail, nous ne considérons que les verbes qui sont plus susceptibles que les noms d’être accompagnés par des actants réalisés dans les phrases. Ces verbes concernent les termes de spécialité d’informatique et d’Internet (ex. accéder, configurer, naviguer, télécharger) dont la structure actancielle est enrichie manuellement par des rôles sémantiques. La structure actancielle des lexies verbales est décrite selon les principes de la Lexicologie Explicative et Combinatoire, LEC de Mel’čuk et fait appel partiellement (en ce qui concerne les rôles sémantiques) à la notion de Frame Element tel que décrit dans la théorie Frame Semantics (FS) de Fillmore. Ces deux théories ont ceci de commun qu’elles mènent toutes les deux à la construction de dictionnaires différents de ceux issus des approches traditionnelles. Les lexies verbales d’informatique et d’Internet qui ont été annotées manuellement dans plusieurs contextes constituent notre corpus spécialisé. Notre système qui attribue automatiquement des rôles sémantiques aux actants est basé sur des règles ou classificateurs entraînés sur plus de 2300 contextes. Nous sommes limités à une liste de rôles restreinte car certains rôles dans notre corpus n’ont pas assez d’exemples annotés manuellement. Dans notre système, nous n’avons traité que les rôles Patient, Agent et Destination dont le nombre d’exemple est supérieur à 300. Nous avons crée une classe que nous avons nommé Autre où nous avons rassemblé les autres rôles dont le nombre d’exemples annotés est inférieur à 100. Nous avons subdivisé la tâche d’annotation en sous-tâches : identifier les participants actants et circonstants et attribuer des rôles sémantiques uniquement aux actants qui contribuent au sens de la lexie verbale. Nous avons soumis les phrases de notre corpus à l’analyseur syntaxique Syntex afin d’extraire les informations syntaxiques qui décrivent les différents participants d’une lexie verbale dans une phrase. Ces informations ont servi de traits (features) dans notre modèle d’apprentissage. Nous avons proposé deux techniques pour l’identification des participants : une technique à base de règles où nous avons extrait une trentaine de règles et une autre technique basée sur l’apprentissage machine. Ces mêmes techniques ont été utilisées pour la tâche de distinguer les actants des circonstants. Nous avons proposé pour la tâche d’attribuer des rôles sémantiques aux actants, une méthode de partitionnement (clustering) semi supervisé des instances que nous avons comparée à la méthode de classification de rôles sémantiques. Nous avons utilisé CHAMÉLÉON, un algorithme hiérarchique ascendant.

Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

L’arbre de régression multivariable et les modèles linéaires généralisés revisités : applications à l’étude de la diversité bêta et à l’estimation de la biomasse d’arbres tropicaux

En écologie, dans le cadre par exemple d’études des services fournis par les écosystèmes, les modélisations descriptive, explicative et prédictive ont toutes trois leur place distincte. Certaines situations bien précises requièrent soit l’un soit l’autre de ces types de modélisation ; le bon choix s’impose afin de pouvoir faire du modèle un usage conforme aux objectifs de l’étude. Dans le cadre de ce travail, nous explorons dans un premier temps le pouvoir explicatif de l’arbre de régression multivariable (ARM). Cette méthode de modélisation est basée sur un algorithme récursif de bipartition et une méthode de rééchantillonage permettant l’élagage du modèle final, qui est un arbre, afin d’obtenir le modèle produisant les meilleures prédictions. Cette analyse asymétrique à deux tableaux permet l’obtention de groupes homogènes d’objets du tableau réponse, les divisions entre les groupes correspondant à des points de coupure des variables du tableau explicatif marquant les changements les plus abrupts de la réponse. Nous démontrons qu’afin de calculer le pouvoir explicatif de l’ARM, on doit définir un coefficient de détermination ajusté dans lequel les degrés de liberté du modèle sont estimés à l’aide d’un algorithme. Cette estimation du coefficient de détermination de la population est pratiquement non biaisée. Puisque l’ARM sous-tend des prémisses de discontinuité alors que l’analyse canonique de redondance (ACR) modélise des gradients linéaires continus, la comparaison de leur pouvoir explicatif respectif permet entre autres de distinguer quel type de patron la réponse suit en fonction des variables explicatives. La comparaison du pouvoir explicatif entre l’ACR et l’ARM a été motivée par l’utilisation extensive de l’ACR afin d’étudier la diversité bêta. Toujours dans une optique explicative, nous définissons une nouvelle procédure appelée l’arbre de régression multivariable en cascade (ARMC) qui permet de construire un modèle tout en imposant un ordre hiérarchique aux hypothèses à l’étude. Cette nouvelle procédure permet d’entreprendre l’étude de l’effet hiérarchisé de deux jeux de variables explicatives, principal et subordonné, puis de calculer leur pouvoir explicatif. L’interprétation du modèle final se fait comme dans une MANOVA hiérarchique. On peut trouver dans les résultats de cette analyse des informations supplémentaires quant aux liens qui existent entre la réponse et les variables explicatives, par exemple des interactions entres les deux jeux explicatifs qui n’étaient pas mises en évidence par l’analyse ARM usuelle. D’autre part, on étudie le pouvoir prédictif des modèles linéaires généralisés en modélisant la biomasse de différentes espèces d’arbre tropicaux en fonction de certaines de leurs mesures allométriques. Plus particulièrement, nous examinons la capacité des structures d’erreur gaussienne et gamma à fournir les prédictions les plus précises. Nous montrons que pour une espèce en particulier, le pouvoir prédictif d’un modèle faisant usage de la structure d’erreur gamma est supérieur. Cette étude s’insère dans un cadre pratique et se veut un exemple pour les gestionnaires voulant estimer précisément la capture du carbone par des plantations d’arbres tropicaux. Nos conclusions pourraient faire partie intégrante d’un programme de réduction des émissions de carbone par les changements d’utilisation des terres.

Modélisation procédurale par composants

Le réalisme des images en infographie exige de créer des objets (ou des scènes) de plus en plus complexes, ce qui entraîne des coûts considérables. La modélisation procédurale peut aider à automatiser le processus de création, à simplifier le processus de modification ou à générer de multiples variantes d'une instance d'objet. Cependant même si plusieurs méthodes procédurales existent, aucune méthode unique permet de créer tous les types d'objets complexes, dont en particulier un édifice complet. Les travaux réalisés dans le cadre de cette thèse proposent deux solutions au problème de la modélisation procédurale: une solution au niveau de la géométrie de base, et l’autre sous forme d'un système général adapté à la modélisation des objets complexes. Premièrement, nous présentons le bloc, une nouvelle primitive de modélisation simple et générale, basée sur une forme cubique généralisée. Les blocs sont disposés et connectés entre eux pour constituer la forme de base des objets, à partir de laquelle est extrait un maillage de contrôle pouvant produire des arêtes lisses et vives. La nature volumétrique des blocs permet une spécification simple de la topologie, ainsi que le support des opérations de CSG entre les blocs. La paramétrisation de la surface, héritée des faces des blocs, fournit un soutien pour les textures et les fonctions de déplacements afin d'appliquer des détails de surface. Une variété d'exemples illustrent la généralité des blocs dans des contextes de modélisation à la fois interactive et procédurale. Deuxièmement, nous présentons un nouveau système de modélisation procédurale qui unifie diverses techniques dans un cadre commun. Notre système repose sur le concept de composants pour définir spatialement et sémantiquement divers éléments. À travers une série de déclarations successives exécutées sur un sous-ensemble de composants obtenus à l'aide de requêtes, nous créons un arbre de composants définissant ultimement un objet dont la géométrie est générée à l'aide des blocs. Nous avons appliqué notre concept de modélisation par composants à la génération d'édifices complets, avec intérieurs et extérieurs cohérents. Ce nouveau système s'avère général et bien adapté pour le partionnement des espaces, l'insertion d'ouvertures (portes et fenêtres), l'intégration d'escaliers, la décoration de façades et de murs, l'agencement de meubles, et diverses autres opérations nécessaires lors de la construction d'un édifice complet.

Patrons de distribution des crustacés planctoniques dans le fleuve Saint-Laurent

La recherche porte sur les patrons de distribution longitudinale (amont-aval) et transversale (rive nord - rive sud) des communautés de crustacés planctoniques qui ont été analysés le long du fleuve Saint-Laurent entre le lac Saint-François et la zone de transition estuarienne, à deux hydropériodes en mai (crue) et en août (étiage). Les données zooplanctoniques et environnementales ont été récoltées à 52 stations réparties sur 16 transects transversaux en 2006. Au chapitre 1, nous présentons les principaux modèles écosystémiques en rivière, une synthèse des facteurs influençant le zooplancton en rivières et les objectifs et hypothèses de recherche. Au chapitre 2, nous décrivons la structure des communautés de zooplancton dans trois zones biogéographiques du fleuve et 6 habitats longitudinaux, ainsi que les relations entre la structure du zooplancton et la distribution spatiale des masses d’eau et les variables environnementales. Au chapitre 3, nous réalisons une partition de la variation des variables spatiales AEM (basées sur la distribution des masses d’eau) et des variables environnementales pour évaluer quelle part de la variation du zooplancton est expliquée par les processus hydrologiques (variables AEM) et les conditions locales (facteurs environnementaux). Le gradient salinité-conductivité relié à la discontinuité fleuve-estuaire a déterminé la distribution à grande échelle du zooplancton. Dans les zones fluviales, la distribution du zooplancton est davantage influencée par la distribution des masses d’eau que par les facteurs environnementaux locaux. La distribution des masses d’eau explique une plus grande partie de la variation dans la distribution du zooplancton en août qu’en mai.

Heuristiques efficaces pour l'optimisation de la performance des systèmes séries-parallèles

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

Impact des perturbations anthropiques sur la végétation du complexe de milieux humides des Tourbières-de-Lanoraie

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