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.

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.

Impacts potentiels d’un changement climatique sur le pergélisol dans le nord canadien

Les fichiers video (d'animation) sont dans un format Windows Media (.wmv)

Représentation et détection des images et des surfaces déformables

La représentation d'une surface, son lissage et son utilisation pour l'identification, la comparaison, la classification, et l'étude des variations de volume, de courbure ou de topologie sont omniprésentes dans l'aire de la numérisation. Parmi les méthodes mathématiques, nous avons retenu les transformations difféomorphiques d'un pattern de référence. Il y a un grand intérêt théorique et numérique à approcher un difféomorphisme arbitraire par des difféomorphismes engendrés par des champs de vitesses. Sur le plan théorique la question est : "est-ce que le sous-groupe de difféomorphismes engendrés par des champs de vitesses est dense dans le groupe plus large de Micheletti pour la métrique de Courant ?" Malgré quelques progrès réalisés ici, cette question demeure ouverte. Les pistes empruntées ont alors convergé vers le sous-groupe de Azencott et de Trouvé et sa métrique dans le cadre de l'imagerie. Elle correspond à une notion de géodésique entre deux difféomorphismes dans leur sous-groupe. L'optimisation est utilisée pour obtenir un système d'équations état adjoint caractérisant la solution optimale du problème d'identification à partir des observations. Cette approche est adaptée à l'identification de surfaces obtenues par un numériseur tel que, par exemple, le scan d'un visage. Ce problème est beaucoup plus difficile que celui d'imagerie. On doit alors introduire un système de référence courbe et une surface à facettes pour les calculs. On donne la formulation du problème d'identification et du calcul du changement de volume par rapport à un scan de référence.

Approche efficace pour la conception des architectures multiprocesseurs sur puce électronique

Les systèmes multiprocesseurs sur puce électronique (On-Chip Multiprocessor [OCM]) sont considérés comme les meilleures structures pour occuper l'espace disponible sur les circuits intégrés actuels. Dans nos travaux, nous nous intéressons à un modèle architectural, appelé architecture isométrique de systèmes multiprocesseurs sur puce, qui permet d'évaluer, de prédire et d'optimiser les systèmes OCM en misant sur une organisation efficace des nœuds (processeurs et mémoires), et à des méthodologies qui permettent d'utiliser efficacement ces architectures. Dans la première partie de la thèse, nous nous intéressons à la topologie du modèle et nous proposons une architecture qui permet d'utiliser efficacement et massivement les mémoires sur la puce. Les processeurs et les mémoires sont organisés selon une approche isométrique qui consiste à rapprocher les données des processus plutôt que d'optimiser les transferts entre les processeurs et les mémoires disposés de manière conventionnelle. L'architecture est un modèle maillé en trois dimensions. La disposition des unités sur ce modèle est inspirée de la structure cristalline du chlorure de sodium (NaCl), où chaque processeur peut accéder à six mémoires à la fois et où chaque mémoire peut communiquer avec autant de processeurs à la fois. Dans la deuxième partie de notre travail, nous nous intéressons à une méthodologie de décomposition où le nombre de nœuds du modèle est idéal et peut être déterminé à partir d'une spécification matricielle de l'application qui est traitée par le modèle proposé. Sachant que la performance d'un modèle dépend de la quantité de flot de données échangées entre ses unités, en l'occurrence leur nombre, et notre but étant de garantir une bonne performance de calcul en fonction de l'application traitée, nous proposons de trouver le nombre idéal de processeurs et de mémoires du système à construire. Aussi, considérons-nous la décomposition de la spécification du modèle à construire ou de l'application à traiter en fonction de l'équilibre de charge des unités. Nous proposons ainsi une approche de décomposition sur trois points : la transformation de la spécification ou de l'application en une matrice d'incidence dont les éléments sont les flots de données entre les processus et les données, une nouvelle méthodologie basée sur le problème de la formation des cellules (Cell Formation Problem [CFP]), et un équilibre de charge de processus dans les processeurs et de données dans les mémoires. Dans la troisième partie, toujours dans le souci de concevoir un système efficace et performant, nous nous intéressons à l'affectation des processeurs et des mémoires par une méthodologie en deux étapes. Dans un premier temps, nous affectons des unités aux nœuds du système, considéré ici comme un graphe non orienté, et dans un deuxième temps, nous affectons des valeurs aux arcs de ce graphe. Pour l'affectation, nous proposons une modélisation des applications décomposées en utilisant une approche matricielle et l'utilisation du problème d'affectation quadratique (Quadratic Assignment Problem [QAP]). Pour l'affectation de valeurs aux arcs, nous proposons une approche de perturbation graduelle, afin de chercher la meilleure combinaison du coût de l'affectation, ceci en respectant certains paramètres comme la température, la dissipation de chaleur, la consommation d'énergie et la surface occupée par la puce. Le but ultime de ce travail est de proposer aux architectes de systèmes multiprocesseurs sur puce une méthodologie non traditionnelle et un outil systématique et efficace d'aide à la conception dès la phase de la spécification fonctionnelle du système.

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.

Quantum nonlocality, cryptography and complexity

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.

Reconstruction des structures magnéto-convectives solaires sous une région active, par l’utilisation conjointe d’un modèle de convection anélastique et d’une méthode d’assimilation de données.

L’utilisation d’une méthode d’assimilation de données, associée à un modèle de convection anélastique, nous permet la reconstruction des structures physiques d’une partie de la zone convective située en dessous d’une région solaire active. Les résultats obtenus nous informent sur les processus d’émergence des tubes de champ magnétique au travers de la zone convective ainsi que sur les mécanismes de formation des régions actives. Les données solaires utilisées proviennent de l’instrument MDI à bord de l’observatoire spatial SOHO et concernent principalement la région active AR9077 lors de l’ ́évènement du “jour de la Bastille”, le 14 juillet 2000. Cet évènement a conduit à l’avènement d’une éruption solaire, suivie par une importante éjection de masse coronale. Les données assimilées (magnétogrammes, cartes de températures et de vitesses verticales) couvrent une surface de 175 méga-mètres de coté acquises au niveau photosphérique. La méthode d’assimilation de données employée est le “coup de coude direct et rétrograde”, une méthode de relaxation Newtonienne similaire à la méthode “quasi-linéaire inverse 3D”. Elle présente l’originalité de ne pas nécessiter le calcul des équations adjointes au modèle physique. Aussi, la simplicité de la méthode est un avantage numérique conséquent. Notre étude montre au travers d’un test simple l’applicabilité de cette méthode à un modèle de convection utilisé dans le cadre de l’approximation anélastique. Nous montrons ainsi l’efficacité de cette méthode et révélons son potentiel pour l’assimilation de données solaires. Afin d’assurer l’unicité mathématique de la solution obtenue nous imposons une régularisation dans tout le domaine simulé. Nous montrons enfin que l’intérêt de la méthode employée ne se limite pas à la reconstruction des structures convectives, mais qu’elle permet également l’interpolation optimale des magnétogrammes photosphériques, voir même la prédiction de leur évolution temporelle.

Brisure de symétrie par la réduction des groupes de Lie simples à leurs sous-groupes de Lie réductifs maximaux

Dans ce travail, nous exploitons des propriétés déjà connues pour les systèmes de poids des représentations afin de les définir pour les orbites des groupes de Weyl des algèbres de Lie simples, traitées individuellement, et nous étendons certaines de ces propriétés aux orbites des groupes de Coxeter non cristallographiques. D'abord, nous considérons les points d'une orbite d'un groupe de Coxeter fini G comme les sommets d'un polytope (G-polytope) centré à l'origine d'un espace euclidien réel à n dimensions. Nous introduisons les produits et les puissances symétrisées de G-polytopes et nous en décrivons la décomposition en des sommes de G-polytopes. Plusieurs invariants des G-polytopes sont présentés. Ensuite, les orbites des groupes de Weyl des algèbres de Lie simples de tous types sont réduites en l'union d'orbites des groupes de Weyl des sous-algèbres réductives maximales de l'algèbre. Nous listons les matrices qui transforment les points des orbites de l'algèbre en des points des orbites des sous-algèbres pour tous les cas n<=8 ainsi que pour plusieurs séries infinies des paires d'algèbre-sous-algèbre. De nombreux exemples de règles de branchement sont présentés. Finalement, nous fournissons une nouvelle description, uniforme et complète, des centralisateurs des sous-groupes réguliers maximaux des groupes de Lie simples de tous types et de tous rangs. Nous présentons des formules explicites pour l'action de tels centralisateurs sur les représentations irréductibles des algèbres de Lie simples et montrons qu'elles peuvent être utilisées dans le calcul des règles de branchement impliquant ces sous-algèbres.

Sécurité polynomiale en cryptographie

Dans ce mémoire, nous proposons des protocoles cryptographiques d'échange de clef, de mise en gage, et de transfert équivoque. Un premier protocole de transfert équivoque, primitive cryptographique universelle pour le calcul multi-parties, s'inspire du protocole d'échange de clef par puzzle de Merkle, et améliore les résultats existants. Puis, nous montrons qu'il est possible de construire ces mêmes primitives cryptographiques sans l'hypothèse des fonctions à sens unique, mais avec le problème 3SUM. Ce problème simple ---dans une liste de n entiers, en trouver trois dont la somme a une certaine valeur--- a une borne inférieure conjecturée de Omega(n^2).

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.

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.