Computation and Analysis of Multiple Structural-Change Models

In a recent paper, Bai and Perron (1998) considered theoretical issues related to the limiting distribution of estimators and test statistics in the linear model with multiple structural changes. In this companion paper, we consider practical issues for the empirical applications of the procedures. We first address the problem of estimation of the break dates and present an efficient algorithm to obtain global minimizers of the sum of squared residuals. This algorithm is based on the principle of dynamic programming and requires at most least-squares operations of order O(T 2) for any number of breaks. Our method can be applied to both pure and partial structural-change models. Secondly, we consider the problem of forming confidence intervals for the break dates under various hypotheses about the structure of the data and the errors across segments. Third, we address the issue of testing for structural changes under very general conditions on the data and the errors. Fourth, we address the issue of estimating the number of breaks. We present simulation results pertaining to the behavior of the estimators and tests in finite samples. Finally, a few empirical applications are presented to illustrate the usefulness of the procedures. All methods discussed are implemented in a GAUSS program available upon request for non-profit academic use.

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

Practical and Foundational Aspects of Secure Computation

Il y a des problemes qui semblent impossible a resoudre sans l'utilisation d'un tiers parti honnete. Comment est-ce que deux millionnaires peuvent savoir qui est le plus riche sans dire a l'autre la valeur de ses biens ? Que peut-on faire pour prevenir les collisions de satellites quand les trajectoires sont secretes ? Comment est-ce que les chercheurs peuvent apprendre les liens entre des medicaments et des maladies sans compromettre les droits prives du patient ? Comment est-ce qu'une organisation peut ecmpecher le gouvernement d'abuser de l'information dont il dispose en sachant que l'organisation doit n'avoir aucun acces a cette information ? Le Calcul multiparti, une branche de la cryptographie, etudie comment creer des protocoles pour realiser de telles taches sans l'utilisation d'un tiers parti honnete. Les protocoles doivent etre prives, corrects, efficaces et robustes. Un protocole est prive si un adversaire n'apprend rien de plus que ce que lui donnerait un tiers parti honnete. Un protocole est correct si un joueur honnete recoit ce que lui donnerait un tiers parti honnete. Un protocole devrait bien sur etre efficace. Etre robuste correspond au fait qu'un protocole marche meme si un petit ensemble des joueurs triche. On demontre que sous l'hypothese d'un canal de diusion simultane on peut echanger la robustesse pour la validite et le fait d'etre prive contre certains ensembles d'adversaires. Le calcul multiparti a quatre outils de base : le transfert inconscient, la mise en gage, le partage de secret et le brouillage de circuit. Les protocoles du calcul multiparti peuvent etre construits avec uniquements ces outils. On peut aussi construire les protocoles a partir d'hypoth eses calculatoires. Les protocoles construits a partir de ces outils sont souples et peuvent resister aux changements technologiques et a des ameliorations algorithmiques. Nous nous demandons si l'efficacite necessite des hypotheses de calcul. Nous demontrons que ce n'est pas le cas en construisant des protocoles efficaces a partir de ces outils de base. Cette these est constitue de quatre articles rediges en collaboration avec d'autres chercheurs. Ceci constitue la partie mature de ma recherche et sont mes contributions principales au cours de cette periode de temps. Dans le premier ouvrage presente dans cette these, nous etudions la capacite de mise en gage des canaux bruites. Nous demontrons tout d'abord une limite inferieure stricte qui implique que contrairement au transfert inconscient, il n'existe aucun protocole de taux constant pour les mises en gage de bit. Nous demontrons ensuite que, en limitant la facon dont les engagements peuvent etre ouverts, nous pouvons faire mieux et meme un taux constant dans certains cas. Ceci est fait en exploitant la notion de cover-free families . Dans le second article, nous demontrons que pour certains problemes, il existe un echange entre robustesse, la validite et le prive. Il s'effectue en utilisant le partage de secret veriable, une preuve a divulgation nulle, le concept de fantomes et une technique que nous appelons les balles et les bacs. Dans notre troisieme contribution, nous demontrons qu'un grand nombre de protocoles dans la litterature basee sur des hypotheses de calcul peuvent etre instancies a partir d'une primitive appelee Transfert Inconscient Veriable, via le concept de Transfert Inconscient Generalise. Le protocole utilise le partage de secret comme outils de base. Dans la derniere publication, nous counstruisons un protocole efficace avec un nombre constant de rondes pour le calcul a deux parties. L'efficacite du protocole derive du fait qu'on remplace le coeur d'un protocole standard par une primitive qui fonctionne plus ou moins bien mais qui est tres peu couteux. On protege le protocole contre les defauts en utilisant le concept de privacy amplication .

Distributed conditional computation

L'objectif de cette thèse est de présenter différentes applications du programme de recherche de calcul conditionnel distribué. On espère que ces applications, ainsi que la théorie présentée ici, mènera à une solution générale du problème d'intelligence artificielle, en particulier en ce qui a trait à la nécessité d'efficience. La vision du calcul conditionnel distribué consiste à accélérer l'évaluation et l'entraînement de modèles profonds, ce qui est très différent de l'objectif usuel d'améliorer sa capacité de généralisation et d'optimisation. Le travail présenté ici a des liens étroits avec les modèles de type mélange d'experts. Dans le chapitre 2, nous présentons un nouvel algorithme d'apprentissage profond qui utilise une forme simple d'apprentissage par renforcement sur un modèle d'arbre de décisions à base de réseau de neurones. Nous démontrons la nécessité d'une contrainte d'équilibre pour maintenir la distribution d'exemples aux experts uniforme et empêcher les monopoles. Pour rendre le calcul efficient, l'entrainement et l'évaluation sont contraints à être éparse en utilisant un routeur échantillonnant des experts d'une distribution multinomiale étant donné un exemple. Dans le chapitre 3, nous présentons un nouveau modèle profond constitué d'une représentation éparse divisée en segments d'experts. Un modèle de langue à base de réseau de neurones est construit à partir des transformations éparses entre ces segments. L'opération éparse par bloc est implémentée pour utilisation sur des cartes graphiques. Sa vitesse est comparée à deux opérations denses du même calibre pour démontrer le gain réel de calcul qui peut être obtenu. Un modèle profond utilisant des opérations éparses contrôlées par un routeur distinct des experts est entraîné sur un ensemble de données d'un milliard de mots. Un nouvel algorithme de partitionnement de données est appliqué sur un ensemble de mots pour hiérarchiser la couche de sortie d'un modèle de langage, la rendant ainsi beaucoup plus efficiente. Le travail présenté dans cette thèse est au centre de la vision de calcul conditionnel distribué émis par Yoshua Bengio. Elle tente d'appliquer la recherche dans le domaine des mélanges d'experts aux modèles profonds pour améliorer leur vitesse ainsi que leur capacité d'optimisation. Nous croyons que la théorie et les expériences de cette thèse sont une étape importante sur la voie du calcul conditionnel distribué car elle cadre bien le problème, surtout en ce qui concerne la compétitivité des systèmes d'experts.

Macroclosures in Open Economy Cge Models: a Numerical Reappraisal

It Has Been Argued That in the Construction and Simulation Process of Computable General Equilibrium (Cge) Models, the Choice of the Proper Macroclosure Remains a Fundamental Problem. in This Study, with a Standard Cge Model, We Simulate Disturbances Stemming From the Supply Or Demand Side of the Economy, Under Alternative Macroclosures. According to Our Results, the Choice of a Particular Closure Rule, for a Given Disturbance, May Have Different Quantitative and Qualitative Impacts. This Seems to Confirm the Imiportance of Simulating Cge Models Under Alternative Closure Rules and Eventually Choosing the Closure Which Best Applies to the Economy Under Study.

Les recours collectifs contre plusieurs défendeurs

Le recours collectif est un moyen de procédure qui permet à une personne d'agir en demande pour le compte des membres d'un groupe dont elle fait partie. Cette procédure peut être introduite contre plus qu'un seul défendeur. On distingue deux types de recours collectifs contre plusieurs défendeurs. Il y a d'abord les recours collectifs où tous les membres du groupe ont un recours personnel contre tous les défendeurs. Il y a aussi les recours collectifs où les membres du groupe font valoir une même cause d'action à l'encontre de plusieurs défendeurs qui auraient eu un comportement fautif similaire à l'égard de l'un ou l'autre des membres du groupe. La recevabilité de ce dernier type de recours collectifs a été remise en question. Le requérant n'aurait pas l'intérêt suffisant pour ester en justice contre les défendeurs qui ne lui ont pas causé préjudice. Il ne saurait non plus satisfaire aux exigences du Code de procédure civile concernant l'autorisation du recours collectif. Or, il appert des règles mises en place en matière de recours collectif que le requérant fait valoir non seulement ses propres droits personnels, mais aussi tous ceux des membres du groupe. Ainsi, on ne peut lui reprocher l'absence d'intérêt juridique ou de cause d'action dans la mesure où il y a, pour chacun des défendeurs, au moins un membre du groupe avec un intérêt suffisant ou une cause d'action à son encontre. Les autres exigences du Code de procédure civile ne font pas, en soi, obstacle à l'autorisation d'un recours collectif contre plusieurs défendeurs.

Modes de représentation pour l'éclairage en synthèse d'images

Réalisé en cotutelle avec l'Université Bordeaux 1 (France)

Paramétrisation de la rétrodiffusion ultrasonore érythrocytaire haute fréquence et pertinence comme facteur de risque de la thrombose veineuse

L’agrégation érythrocytaire est le principal facteur responsable des propriétés non newtoniennes sanguines pour des conditions d’écoulement à faible cisaillement. Lorsque les globules rouges s’agrègent, ils forment des rouleaux et des structures tridimensionnelles enchevêtrées qui font passer la viscosité sanguine de quelques mPa.s à une centaine de mPa.s. Cette organisation microstructurale érythrocytaire est maintenue par des liens inter-globulaires de faible énergie, lesquels sont brisés par une augmentation du cisaillement. Ces propriétés macroscopiques sont bien connues. Toutefois, les liens étiologiques entre ces propriétés rhéologiques générales et leurs effets pathophysiologiques demeurent difficiles à évaluer in vivo puisque les propriétés sanguines sont dynamiques et fortement tributaires des conditions d’écoulement. Ainsi, à partir de propriétés rhéologiques mesurées in vitro dans des conditions contrôlées, il devient difficile d’extrapoler leurs valeurs dans un environnement physiologique. Or, les thrombophlébites se développent systématiquement en des loci particuliers du système cardiovasculaire. D’autre part, plusieurs études cliniques ont établi que des conditions hémorhéologiques perturbées constituent des facteurs de risque de thrombose veineuse mais leurs contributions étiologiques demeurent hypothétiques ou corrélatives. En conséquence, un outil de caractérisation hémorhéologique applicable in vivo et in situ devrait permettre de mieux cerner et comprendre ces implications. Les ultrasons, qui se propagent dans les tissus biologiques, sont sensibles à l’agrégation érythrocytaire. De nature non invasive, l’imagerie ultrasonore permet de caractériser in vivo et in situ la microstructure sanguine dans des conditions d’écoulements physiologiques. Les signaux ultrasonores rétrodiffusés portent une information sur la microstructure sanguine reflétant directement les perturbations hémorhéologiques locales. Une cartographie in vivo de l’agrégation érythrocytaire, unique aux ultrasons, devrait permettre d’investiguer les implications étiologiques de l’hémorhéologie dans la maladie thrombotique vasculaire. Cette thèse complète une série de travaux effectués au Laboratoire de Biorhéologie et d’Ultrasonographie Médicale (LBUM) du centre de recherche du Centre hospitalier de l’Université de Montréal portant sur la rétrodiffusion ultrasonore érythrocytaire et menant à une application in vivo de la méthode. Elle se situe à la suite de travaux de modélisation qui ont mis en évidence la pertinence d’un modèle particulaire tenant compte de la densité des globules rouges, de la section de rétrodiffusion unitaire d’un globule et du facteur de structure. Ce modèle permet d’établir le lien entre la microstructure sanguine et le spectre fréquentiel du coefficient de rétrodiffusion ultrasonore. Une approximation au second ordre en fréquence du facteur de structure est proposée dans ces travaux pour décrire la microstructure sanguine. Cette approche est tout d’abord présentée et validée dans un champ d’écoulement cisaillé homogène. Une extension de la méthode en 2D permet ensuite la cartographie des propriétés structurelles sanguines en écoulement tubulaire par des images paramétriques qui mettent en évidence le caractère temporel de l’agrégation et la sensibilité ultrasonore à ces phénomènes. Une extrapolation menant à une relation entre la taille des agrégats érythrocytaires et la viscosité sanguine permet l’établissement de cartes de viscosité locales. Enfin, il est démontré, à l’aide d’un modèle animal, qu’une augmentation subite de l’agrégation érythrocytaire provoque la formation d’un thrombus veineux. Le niveau d’agrégation, la présence du thrombus et les variations du débit ont été caractérisés, dans cette étude, par imagerie ultrasonore. Nos résultats suggèrent que des paramètres hémorhéologiques, préférablement mesurés in vivo et in situ, devraient faire partie du profil de risque thrombotique.

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.

Applicabilité de la texture couleur à la différentiation des classes d’occupation du territoire sur des images satellitales multispectrales

La texture est un élément clé pour l’interprétation des images de télédétection à fine résolution spatiale. L’intégration de l’information texturale dans un processus de classification automatisée des images se fait habituellement via des images de texture, souvent créées par le calcul de matrices de co-occurrences (MCO) des niveaux de gris. Une MCO est un histogramme des fréquences d’occurrence des paires de valeurs de pixels présentes dans les fenêtres locales, associées à tous les pixels de l’image utilisée; une paire de pixels étant définie selon un pas et une orientation donnés. Les MCO permettent le calcul de plus d’une dizaine de paramètres décrivant, de diverses manières, la distribution des fréquences, créant ainsi autant d’images texturales distinctes. L’approche de mesure des textures par MCO a été appliquée principalement sur des images de télédétection monochromes (ex. images panchromatiques, images radar monofréquence et monopolarisation). En imagerie multispectrale, une unique bande spectrale, parmi celles disponibles, est habituellement choisie pour générer des images de texture. La question que nous avons posée dans cette recherche concerne justement cette utilisation restreinte de l’information texturale dans le cas des images multispectrales. En fait, l’effet visuel d’une texture est créé, non seulement par l’agencement particulier d’objets/pixels de brillance différente, mais aussi de couleur différente. Plusieurs façons sont proposées dans la littérature pour introduire cette idée de la texture à plusieurs dimensions. Parmi celles-ci, deux en particulier nous ont intéressés dans cette recherche. La première façon fait appel aux MCO calculées bande par bande spectrale et la seconde utilise les MCO généralisées impliquant deux bandes spectrales à la fois. Dans ce dernier cas, le procédé consiste en le calcul des fréquences d’occurrence des paires de valeurs dans deux bandes spectrales différentes. Cela permet, en un seul traitement, la prise en compte dans une large mesure de la « couleur » des éléments de texture. Ces deux approches font partie des techniques dites intégratives. Pour les distinguer, nous les avons appelées dans cet ouvrage respectivement « textures grises » et « textures couleurs ». Notre recherche se présente donc comme une analyse comparative des possibilités offertes par l’application de ces deux types de signatures texturales dans le cas spécifique d’une cartographie automatisée des occupations de sol à partir d’une image multispectrale. Une signature texturale d’un objet ou d’une classe d’objets, par analogie aux signatures spectrales, est constituée d’une série de paramètres de texture mesurés sur une bande spectrale à la fois (textures grises) ou une paire de bandes spectrales à la fois (textures couleurs). Cette recherche visait non seulement à comparer les deux approches intégratives, mais aussi à identifier la composition des signatures texturales des classes d’occupation du sol favorisant leur différentiation : type de paramètres de texture / taille de la fenêtre de calcul / bandes spectrales ou combinaisons de bandes spectrales. Pour ce faire, nous avons choisi un site à l’intérieur du territoire de la Communauté Métropolitaine de Montréal (Longueuil) composé d’une mosaïque d’occupations du sol, caractéristique d’une zone semi urbaine (résidentiel, industriel/commercial, boisés, agriculture, plans d’eau…). Une image du satellite SPOT-5 (4 bandes spectrales) de 10 m de résolution spatiale a été utilisée dans cette recherche. Puisqu’une infinité d’images de texture peuvent être créées en faisant varier les paramètres de calcul des MCO et afin de mieux circonscrire notre problème nous avons décidé, en tenant compte des études publiées dans ce domaine : a) de faire varier la fenêtre de calcul de 3*3 pixels à 21*21 pixels tout en fixant le pas et l’orientation pour former les paires de pixels à (1,1), c'est-à-dire à un pas d’un pixel et une orientation de 135°; b) de limiter les analyses des MCO à huit paramètres de texture (contraste, corrélation, écart-type, énergie, entropie, homogénéité, moyenne, probabilité maximale), qui sont tous calculables par la méthode rapide de Unser, une approximation des matrices de co-occurrences, c) de former les deux signatures texturales par le même nombre d’éléments choisis d’après une analyse de la séparabilité (distance de Bhattacharya) des classes d’occupation du sol; et d) d’analyser les résultats de classification (matrices de confusion, exactitudes, coefficients Kappa) par maximum de vraisemblance pour conclure sur le potentiel des deux approches intégratives; les classes d’occupation du sol à reconnaître étaient : résidentielle basse et haute densité, commerciale/industrielle, agricole, boisés, surfaces gazonnées (incluant les golfs) et plans d’eau. Nos principales conclusions sont les suivantes a) à l’exception de la probabilité maximale, tous les autres paramètres de texture sont utiles dans la formation des signatures texturales; moyenne et écart type sont les plus utiles dans la formation des textures grises tandis que contraste et corrélation, dans le cas des textures couleurs, b) l’exactitude globale de la classification atteint un score acceptable (85%) seulement dans le cas des signatures texturales couleurs; c’est une amélioration importante par rapport aux classifications basées uniquement sur les signatures spectrales des classes d’occupation du sol dont le score est souvent situé aux alentours de 75%; ce score est atteint avec des fenêtres de calcul aux alentours de11*11 à 15*15 pixels; c) Les signatures texturales couleurs offrant des scores supérieurs à ceux obtenus avec les signatures grises de 5% à 10%; et ce avec des petites fenêtres de calcul (5*5, 7*7 et occasionnellement 9*9) d) Pour plusieurs classes d’occupation du sol prises individuellement, l’exactitude dépasse les 90% pour les deux types de signatures texturales; e) une seule classe est mieux séparable du reste par les textures grises, celle de l’agricole; f) les classes créant beaucoup de confusions, ce qui explique en grande partie le score global de la classification de 85%, sont les deux classes du résidentiel (haute et basse densité). En conclusion, nous pouvons dire que l’approche intégrative par textures couleurs d’une image multispectrale de 10 m de résolution spatiale offre un plus grand potentiel pour la cartographie des occupations du sol que l’approche intégrative par textures grises. Pour plusieurs classes d’occupations du sol un gain appréciable en temps de calcul des paramètres de texture peut être obtenu par l’utilisation des petites fenêtres de traitement. Des améliorations importantes sont escomptées pour atteindre des exactitudes de classification de 90% et plus par l’utilisation des fenêtres de calcul de taille variable adaptées à chaque type d’occupation du sol. Une méthode de classification hiérarchique pourrait être alors utilisée afin de séparer les classes recherchées une à la fois par rapport au reste au lieu d’une classification globale où l’intégration des paramètres calculés avec des fenêtres de taille variable conduirait inévitablement à des confusions entre classes.

La démocratisation au Togo et au Bénin : l'influence des stratégies des groupes d'opposition

Le Bénin et le Togo sont deux pays partageant plusieurs similitudes : ils ont tous les deux été colonisés par la France; leur niveau de développement économique est équivalent; leur histoire postcoloniale est marquée par les coups d’états et, à la fin des années 1980, par des vagues de revendications démocratiques. Celles-ci se sont soldées dans chaque cas par une conférence nationale et l’organisation d’élections générales. Malgré cette trajectoire similaire, seul le Bénin est devenu une démocratie consolidée. Pour expliquer cette différence, ce mémoire se penche sur l’influence des stratégies de l’opposition et sur les processus de transition. Ce mémoire démontre que le degré de cohésion des groupes d’opposition et les accords de ces derniers avec les gouvernements en place ont eu une profonde influence sur le succès ou l’échec des transitions démocratiques.

Aspects géométriques et intégrables des modèles de matrices aléatoires

Travail réalisé en cotutelle avec l'université Paris-Diderot et le Commissariat à l'Energie Atomique sous la direction de John Harnad et Bertrand Eynard.

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.

Variation des biomarqueurs dans le spectre visible non résolu de la Terre

L’évolution rapide des technologies de détection et de caractérisation des exoplanètes depuis le début des années 1990 permet de croire que de nouveaux instruments du type Terrestrial Planet Finder (TPF) pourront prendre les premiers spectres d’exoplanètes semblables à la Terre d’ici une ou deux décennies. Dans ce contexte, l’étude du spectre de la seule planète habitée connue, la Terre, est essentielle pour concevoir ces instruments et analyser leurs résultats. Cette recherche présente les spectres de la Terre dans le visible (390-900 nm), acquis lors de 8 nuits d’observation étalées sur plus d’un an. Ces spectres ont été obtenus en observant la lumière cendrée de la Lune avec le télescope de 1.6 m de l’Observatoire du Mont-Mégantic (OMM). La surface de la Lune réfléchissant de manière diffuse la lumière provenant d’une portion de la Terre, ces spectres sont non résolus spatialement. L’évolution de ces spectres en fonction de la lumière réfléchie à différentes phases de Terre est analogue à celle du spectre d’une exoplanète, dont la phase change selon sa position autour de l’étoile. L'eau, l'oxygène et l'ozone de l’atmosphère, détectés dans tous nos spectres, sont des biomarqueurs dont la présence suggère l’habitabilité de la planète et/ou la présence d’une activité biologique. Le Vegetation Red Edge (VRE), une autre biosignature spectrale, dû aux organismes photosynthétiques à la surface, est caractérisé par l’augmentation de la réflectivité autour de 700 nm. Pour les spectres de 5 nuits, cette augmentation a été évaluée entre -5 et 15% ±~5%, après que les contributions de la diffusion de Rayleigh, des aérosols et d’une large bande moléculaire de l’ozone aient été enlevées. Les valeurs mesurées sont cohérentes avec la présence de végétation dans la phase de la Terre contribuant au spectre, mais s’étendent sur une plage de variations plus large que celles trouvées dans la littérature (0-10%). Cela pourrait s’expliquer par des choix faits lors de la réduction des données et du calcul du VRE, ou encore par la présence d’autres éléments de surface ou de l’atmosphère dont la contribution spectrale autour de 700 nm serait variable.