Complexité raffinée du problème d'intersection d'automates

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

La représentation numérique à l'épreuve de la complexité du projet de territoire

Le projet de territoire n’aura jamais suscité autant de débats et de passions. Son devenir mobilise à bien des égards la construction collective d’un dessein se matérialisant par des formes qui informent des forces tout autant que par des forces qui investissent des formes lesquelles traduisent les valeurs du moment. Par conséquent, cette projection dans un avenir partagé amène des exigences sociales en matière d’édification du projet de territoire mettant à l’ordre du jour la complexité d’une telle entreprise. L’enchevêtrement d’actions et de logiques qui s’y opèrent et qui s’y expriment pour en élaborer, dans la plus grande incertitude, les contours d’un futur souhaité nous presse de s’y prononcer : la construction complexe d’un dessein territorial s’exhibant nous interpelle quant à son évaluation voire quant à sa reformulation. Parmi les modalités d’expression qui permettent une telle délibération, il y a l’énoncé visuel. Médiation discursive privilégiée, elle autorise l’élaboration et la mise en scène collective d’un devenir territorial possible. Or depuis quelques années, au couple projet / représentation, vient se superposer une autre médiation, celle du numérique. Portée par le développement des technologies de l’information, celle-ci s’invite dans le champ de l’édification du projet de territoire. En s’alliant avec la puissance de l’image, elle recompose les représentations d’un dessein territorial collectivement formulé, ouvrant un nouvel espace d’actions à l’occasion d’une démarche de planification. Démarche de plus en plus complexe. De surcroit, la présente recherche tient cette complexité non comme un mot «fourre-tout» ou une tare dont il faudrait se débarrasser, mais se résout à l’affronter en s’inscrivant dans un paradigme en pleine gestation, celui de la «pensée complexe». La fécondité autant conceptuelle qu’opératoire d’une telle inscription permettra de jeter un regard renouvelé sur une pratique à travers une de ses modalités discursives à la fois la plus manifeste et la moins questionnée, à savoir l’énoncé visuel. En fin de compte, les représentations notamment celles construites et véhiculées par le numérique sauront-elles rendre compte et relever le défi de l’édification collective d’un projet de territoire qui se pose dans toute sa complexité ? Telle est en substance le questionnement dont cette recherche s’attellera à apporter des éléments de réponse et à esquisser de nouvelles perspectives.

Approximation du calcul de la taille échantillonnale pour les tests à hypothèses multiples lorsque r parmis m hypothèses doivent être significatives

Généralement, dans les situations d’hypothèses multiples on cherche à rejeter toutes les hypothèses ou bien une seule d’entre d’elles. Depuis quelques temps on voit apparaître le besoin de répondre à la question : « Peut-on rejeter au moins r hypothèses ? ». Toutefois, les outils statisques pour répondre à cette question sont rares dans la littérature. Nous avons donc entrepris de développer les formules générales de puissance pour les procédures les plus utilisées, soit celles de Bonferroni, de Hochberg et de Holm. Nous avons développé un package R pour le calcul de la taille échantilonnalle pour les tests à hypothèses multiples (multiple endpoints), où l’on désire qu’au moins r des m hypothèses soient significatives. Nous nous limitons au cas où toutes les variables sont continues et nous présentons quatre situations différentes qui dépendent de la structure de la matrice de variance-covariance des données.

Activation cérébrale en fonction de l'âge et de la complexité du traitement sémantique des mots par imagerie par résonance magnétique fonctionnelle

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay

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

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

A survey of graph and subgraph isomorphism problems

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

De computatione quantica

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Arbitrage en ligne et les litiges du commerce électronique

"Mémoire présenté à la Faculté des études supérieures en vue de l'obtention du grade de Maîtrise en droit (LLM)"

Caractérisation de la migration du virus Herpès simplex de type 1 (HSV-1) par protéomique

Le virus Herpès simplex de type 1 (HSV-1), agent étiologique des feux sauvages, possède une structure multicouche comprenant une capside icosaédrale qui protège le génome viral d’ADN, une couche protéique très structurée appelée tégument et une enveloppe lipidique dérivant de la cellule hôte et parsemée de glycoprotéines virales. Tous ces constituants sont acquis séquentiellement à partir du noyau, du cytoplasme et du réseau trans-golgien. Cette structure multicouche confère à HSV-1 un potentiel considérable pour incorporer des protéines virales et cellulaires. Toutefois, l’ensemble des protéines qui composent ce virus n’a pas encore été élucidé. De plus, malgré son rôle critique à différentes étapes de l’infection, le tégument demeure encore mal défini et ce, tant dans sa composition que dans la séquence d’addition des protéines qui le composent. Toutes ces incertitudes quant aux mécanismes impliqués dans la morphogenèse du virus nous amènent à l’objectif de ce projet, soit la caractérisation du processus de maturation d’HSV-1. Le premier article présenté dans cette thèse et publié dans Journal of Virology s’attarde à la caractérisation protéique des virus extracellulaires matures. Grâce à l’élaboration d’un protocole d’isolation et de purification de ces virions, une étude protéomique a pu être effectuée. Celle-ci nous a permis de réaliser une cartographie de la composition globale en protéines virales des virus matures (8 protéines de la capside, 23 protéines du tégument et 13 glycoprotéines) qui a fait la page couverture de Journal of Virology. De plus, l’incorporation potentielle de 49 protéines cellulaires différentes a été révélée. Lors de cette étude protéomique, nous avons aussi relevé la présence de nouveaux composants du virion dont UL7, UL23, ICP0 et ICP4. Le deuxième article publié dans Journal of General Virology focalise sur ces protéines via une analyse biochimique afin de mieux comprendre les interactions et la dynamique du tégument. Ces résultats nous révèlent que, contrairement aux protéines ICP0 et ICP4, UL7 et UL23 peuvent être relâchées de la capside en présence de sels et que les cystéines libres jouent un rôle dans cette relâche. De plus, cet article met en évidence la présence d’ICP0 et d’ICP4 sur les capsides nucléaires suggérant une acquisition possible du tégument au noyau. La complexité du processus de morphogenèse du virus ainsi que la mise en évidence d’acquisition de protéines du tégument au noyau nous ont incités à poursuivre nos recherches sur la composition du virus à un stade précoce de son cycle viral. Les capsides C matures, prémisses des virus extracellulaires, ont donc été isolées et purifiées grâce à un protocole innovateur basé sur le tri par cytométrie en flux. L’analyse préliminaire de ces capsides par protéomique a permis d’identifier 28 protéines virales et 39 protéines cellulaires. Les données recueilles, comparées à celles obtenues avec les virus extracellulaires, suggèrent clairement un processus séquentiel d’acquisition des protéines du tégument débutant dans le noyau, site d’assemblage des capsides. Finalement, tous ces résultats contribuent à une meilleure compréhension du processus complexe de maturation d’HSV-1 via l’utilisation de techniques variées et innovatrices, telles que la protéomique et la cytométrie en flux, pouvant être appliquées à d’autres virus mais aussi permettre le développement de meilleurs traitements pour vaincre l’HSV-1.

Habitudes de vie et contrôle glycémique chez des adultes atteints de diabète de type 1 : des barrières envers l’activité physique au calcul des glucides.

Le diabète de type 1 (DT1) est une maladie complexe qui requiert une implication importante des patients pour contrôler leur glycémie et ainsi prévenir les complications et comorbidités. L’activité physique (AP) régulière et une attention constante pour les glucides ingérés sont des adjuvants essentiels au traitement insulinique. Nous avons démontré que le questionnaire BAPAD-1, spécifiquement développé pour des adultes atteints de DT1, est un outil valide (validité prédictive, fiabilité interne et reproductibilité) pour définir des barrières associées à l’AP. Bien que le niveau de barrières envers l’AP soit faible, la crainte de l’hypoglycémie est la barrière la plus importante chez cette population. L’adoption d’un mode de vie actif est associée à un profil corporel favorable. Les adultes, avec un DT1 et non diabétique, qui maintiennent un bon niveau d’AP, soit un ratio entre la dépense énergétique totale et celle au repos ≥ 1.7, ont une masse grasse, un indice de masse corporelle et un tour de taille significativement inférieurs à ceux d’adultes moins actifs. Le niveau d’AP peut être estimé au moyen d’un moniteur d’AP comme le SenseWear Armband™. Afin de compléter les études de validation de cet outil, nous avons évalué et démontré la reproductibilité des mesures. Toutefois, la dépense énergétique est sous-estimée durant les 10 premières minutes d’une AP d’intensité modérée sur ergocycle. L’utilisation de cet appareil est donc justifiée pour une évaluation de la dépense énergétique sur de longues périodes. Le calcul des glucides est une méthode largement utilisée pour évaluer la quantité d’insuline à injecter lors des repas. Nous avons évalué dans un contexte de vie courante, sans révision de la technique, la précision des patients pour ce calcul. L’erreur moyenne est de 15,4 ± 7,8 g par repas, soit 20,9 ± 9,7 % du contenu glucidique. L’erreur moyenne est positivement associée à de plus grandes fluctuations glycémiques mesurées via un lecteur de glucose en continu. Une révision régulière du calcul des glucides est probablement nécessaire pour permettre un meilleur contrôle glycémique. Nous avons développé et testé lors d’un essai clinique randomisé contrôlé un programme de promotion de l’AP (PEP-1). Ce programme de 12 semaines inclut une séance hebdomadaire en groupe ayant pour but d’initier l’AP, d’établir des objectifs et d’outiller les adultes atteints de DT1 quant à la gestion de la glycémie à l’AP. Bien que n’ayant pas permis d’augmenter la dépense énergétique, le programme a permis un maintien du niveau d’AP et une amélioration de la condition cardio-respiratoire et de la pression artérielle. À la fin du programme, une plus grande proportion de patients connaissait la pharmacocinétique de l’insuline et une plus grande variété de méthodes pour contrer l’hypoglycémie associée à l’AP était utilisée. En conclusion, le diabète de type 1 engendre des défis quotidiens particuliers. D’une part, le calcul des glucides est une tâche complexe et son imprécision est associée aux fluctuations glycémiques quotidiennes. D’autre part, l’adoption d’un mode de vie actif, qui est associée à un meilleur profil de composition corporelle, est limitée par la crainte des hypoglycémies. Le programme PEP-1 offre un support pour intégrer l’AP dans les habitudes de vie des adultes avec un DT1 et ainsi améliorer certains facteurs de risque cardio-vasculaire.

Effet d'une approche par le jeu sur l'apprentissage du répertoire mémorisé chez des élèves de deuxième année primaire

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

Suivi des changements des utilisations/occupations du sol en milieu urbain par imagerie satellitale de résolution spatiale moyenne : le cas de la région métropolitaine de Montréal

De nos jours les cartes d’utilisation/occupation du sol (USOS) à une échelle régionale sont habituellement générées à partir d’images satellitales de résolution modérée (entre 10 m et 30 m). Le National Land Cover Database aux États-Unis et le programme CORINE (Coordination of information on the environment) Land Cover en Europe, tous deux fondés sur les images LANDSAT, en sont des exemples représentatifs. Cependant ces cartes deviennent rapidement obsolètes, spécialement en environnement dynamique comme les megacités et les territoires métropolitains. Pour nombre d’applications, une mise à jour de ces cartes sur une base annuelle est requise. Depuis 2007, le USGS donne accès gratuitement à des images LANDSAT ortho-rectifiées. Des images archivées (depuis 1984) et des images acquises récemment sont disponibles. Sans aucun doute, une telle disponibilité d’images stimulera la recherche sur des méthodes et techniques rapides et efficaces pour un monitoring continue des changements des USOS à partir d’images à résolution moyenne. Cette recherche visait à évaluer le potentiel de telles images satellitales de résolution moyenne pour obtenir de l’information sur les changements des USOS à une échelle régionale dans le cas de la Communauté Métropolitaine de Montréal (CMM), une métropole nord-américaine typique. Les études précédentes ont démontré que les résultats de détection automatique des changements dépendent de plusieurs facteurs tels : 1) les caractéristiques des images (résolution spatiale, bandes spectrales, etc.); 2) la méthode même utilisée pour la détection automatique des changements; et 3) la complexité du milieu étudié. Dans le cas du milieu étudié, à l’exception du centre-ville et des artères commerciales, les utilisations du sol (industriel, commercial, résidentiel, etc.) sont bien délimitées. Ainsi cette étude s’est concentrée aux autres facteurs pouvant affecter les résultats, nommément, les caractéristiques des images et les méthodes de détection des changements. Nous avons utilisé des images TM/ETM+ de LANDSAT à 30 m de résolution spatiale et avec six bandes spectrales ainsi que des images VNIR-ASTER à 15 m de résolution spatiale et avec trois bandes spectrales afin d’évaluer l’impact des caractéristiques des images sur les résultats de détection des changements. En ce qui a trait à la méthode de détection des changements, nous avons décidé de comparer deux types de techniques automatiques : (1) techniques fournissant des informations principalement sur la localisation des changements et (2)techniques fournissant des informations à la fois sur la localisation des changements et sur les types de changement (classes « de-à »). Les principales conclusions de cette recherche sont les suivantes : Les techniques de détection de changement telles les différences d’image ou l’analyse des vecteurs de changements appliqués aux images multi-temporelles LANDSAT fournissent une image exacte des lieux où un changement est survenu d’une façon rapide et efficace. Elles peuvent donc être intégrées dans un système de monitoring continu à des fins d’évaluation rapide du volume des changements. Les cartes des changements peuvent aussi servir de guide pour l’acquisition d’images de haute résolution spatiale si l’identification détaillée du type de changement est nécessaire. Les techniques de détection de changement telles l’analyse en composantes principales et la comparaison post-classification appliquées aux images multi-temporelles LANDSAT fournissent une image relativement exacte de classes “de-à” mais à un niveau thématique très général (par exemple, bâti à espace vert et vice-versa, boisés à sol nu et vice-versa, etc.). Les images ASTER-VNIR avec une meilleure résolution spatiale mais avec moins de bandes spectrales que LANDSAT n’offrent pas un niveau thématique plus détaillé (par exemple, boisés à espace commercial ou industriel). Les résultats indiquent que la recherche future sur la détection des changements en milieu urbain devrait se concentrer aux changements du couvert végétal puisque les images à résolution moyenne sont très sensibles aux changements de ce type de couvert. Les cartes indiquant la localisation et le type des changements du couvert végétal sont en soi très utiles pour des applications comme le monitoring environnemental ou l’hydrologie urbaine. Elles peuvent aussi servir comme des indicateurs des changements de l’utilisation du sol. De techniques telles l’analyse des vecteurs de changement ou les indices de végétation son employées à cette fin.

Complexité des homomorphismes de graphes avec listes

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2.

Key Agreement Against Quantum Adversaries

Key agreement is a cryptographic scenario between two legitimate parties, who need to establish a common secret key over a public authenticated channel, and an eavesdropper who intercepts all their messages in order to learn the secret. We consider query complexity in which we count only the number of evaluations (queries) of a given black-box function, and classical communication channels. Ralph Merkle provided the first unclassified scheme for secure communications over insecure channels. When legitimate parties are willing to ask O(N) queries for some parameter N, any classical eavesdropper needs Omega(N^2) queries before being able to learn their secret, which is is optimal. However, a quantum eavesdropper can break this scheme in O(N) queries. Furthermore, it was conjectured that any scheme, in which legitimate parties are classical, could be broken in O(N) quantum queries. In this thesis, we introduce protocols à la Merkle that fall into two categories. When legitimate parties are restricted to use classical computers, we offer the first secure classical scheme. It requires Omega(N^{13/12}) queries of a quantum eavesdropper to learn the secret. We give another protocol having security of Omega(N^{7/6}) queries. Furthermore, for any k>= 2, we introduce a classical protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1/2+k/{k+1}}) queries, approaching Theta(N^{3/2}) when k increases. When legitimate parties are provided with quantum computers, we present two quantum protocols improving on the best known scheme before this work. Furthermore, for any k>= 2, we give a quantum protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1+{k}/{k+1}})} queries, approaching Theta(N^{2}) when k increases.