Algorithmique et complexité des systèmes à compteurs

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

A survey of graph and subgraph isomorphism problems

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

A survey of graph and subgraph isomorphism problems

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

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.

Interactive quantum information theory

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.

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)"

Preuves interactives quantiques

Cette thèse est consacrée à la complexité basée sur le paradigme des preuves interactives. Les classes ainsi définies ont toutes en commun qu’un ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un vérificateur, de puissance bornée, de l’appartenance d’un mot à un langage. Nous abordons ici le modèle classique, où les participants sont des machines de Turing, et le modèle quantique, où ceux-ci sont des circuits quantiques. La revue de littérature que comprend cette thèse s’adresse à un lecteur déjà familier avec la complexité et l’informatique quantique. Cette thèse présente comme résultat la caractérisation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les différentes classes sont présentées dans un ordre permettant d’aborder aussi facilement que possible les classes interactives. Le premier chapitre est consacré aux classes de base de la complexité ; celles-ci seront utiles pour situer les classes subséquemment présentées. Les chapitres deux et trois présentent respectivement les classes à un et à plusieurs prouveurs. La présentation du résultat ci-haut mentionné est l’objet du chapitre quatre.

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.

Urban Detection From Hyperspectral Images Using Dimension-Reduction Model and Fusion of Multiple Segmentations Based on Stuctural and Textural Features

Ce mémoire de maîtrise présente une nouvelle approche non supervisée pour détecter et segmenter les régions urbaines dans les images hyperspectrales. La méthode proposée n ́ecessite trois étapes. Tout d’abord, afin de réduire le coût calculatoire de notre algorithme, une image couleur du contenu spectral est estimée. A cette fin, une étape de réduction de dimensionalité non-linéaire, basée sur deux critères complémentaires mais contradictoires de bonne visualisation; à savoir la précision et le contraste, est réalisée pour l’affichage couleur de chaque image hyperspectrale. Ensuite, pour discriminer les régions urbaines des régions non urbaines, la seconde étape consiste à extraire quelques caractéristiques discriminantes (et complémentaires) sur cette image hyperspectrale couleur. A cette fin, nous avons extrait une série de paramètres discriminants pour décrire les caractéristiques d’une zone urbaine, principalement composée d’objets manufacturés de formes simples g ́eométriques et régulières. Nous avons utilisé des caractéristiques texturales basées sur les niveaux de gris, la magnitude du gradient ou des paramètres issus de la matrice de co-occurrence combinés avec des caractéristiques structurelles basées sur l’orientation locale du gradient de l’image et la détection locale de segments de droites. Afin de réduire encore la complexité de calcul de notre approche et éviter le problème de la ”malédiction de la dimensionnalité” quand on décide de regrouper des données de dimensions élevées, nous avons décidé de classifier individuellement, dans la dernière étape, chaque caractéristique texturale ou structurelle avec une simple procédure de K-moyennes et ensuite de combiner ces segmentations grossières, obtenues à faible coût, avec un modèle efficace de fusion de cartes de segmentations. Les expérimentations données dans ce rapport montrent que cette stratégie est efficace visuellement et se compare favorablement aux autres méthodes de détection et segmentation de zones urbaines à partir d’images hyperspectrales.

Le drame social du travail d'escorte indépendante à Montréal

Ce mémoire vise à retracer les carrières des escortes indépendantes montréalaises et les tensions qui les traversent, afin de rendre compte de la complexité du « drame social » que constitue cette activité. Nos résultats montrent que cette profession présente de nombreuses similarités avec d’autres professions, en même temps que sa position particulière dans une matrice sociale stigmatisante et dans une relation de service intime lui confère toute sa singularité. Partie de la question « Comment commence-t-on et poursuit-on dans l’activité d’escorte, alors que celle-ci est stigmatisée ? », nous avons réalisé une enquête de terrain auprès d’escortes indépendantes, composée essentiellement de sept entrevues approfondies et de l’observation de leur environnement professionnel informatisé. Nous avons décidé de nous écarter du débat actuel, tant scientifique que militant, qui divise sur le sujet du travail du sexe. Notre cadre conceptuel est, dans un perspective interactionniste, à la croisée des sociologies des professions, de la déviance et du stigmate. Nous rendons compte de nos résultats sous la forme de quatre actes, afin de poursuivre la métaphore théâtrale engagée par Hughes, qui suivent les étapes d’une carrière d’escorte et qui mettent l’accent sur leur complexité intrinsèque. Ces étapes sont ancrées dans une ambivalence entre un effort de professionnalisation de leur pratique et une tentative de rester dans la norme en se distanciant de cette activité. Cette ambivalence, causée par la matrice sociale dans laquelle évoluent ces escortes et à l’intimité des relations de service, contribue à la pérennité de la stigmatisation de cette activité.

Étude de dispositifs électroniques moléculaires à l'aide de modèles simples

Cette thèse en électronique moléculaire porte essentiellement sur le développement d’une méthode pour le calcul de la transmission de dispositifs électroniques moléculaires (DEMs), c’est-à-dire des molécules branchées à des contacts qui forment un dispositif électronique de taille moléculaire. D’une part, la méthode développée vise à apporter un point de vue différent de celui provenant des méthodes déjà existantes pour ce type de calculs. D’autre part, elle permet d’intégrer de manière rigoureuse des outils théoriques déjà développés dans le but d’augmenter la qualité des calculs. Les exemples simples présentés dans ce travail permettent de mettre en lumière certains phénomènes, tel que l’interférence destructive dans les dispositifs électroniques moléculaires. Les chapitres proviennent d’articles publiés dans la littérature. Au chapitre 2, nous étudions à l’aide d’un modèle fini avec la méthode de la théorie de la fonctionnelle de la densité de Kohn-Sham un point quantique moléculaire. De plus, nous calculons la conductance du point quantique moléculaire avec une implémentation de la formule de Landauer. Nous trouvons que la structure électronique et la conductance moléculaire dépendent fortement de la fonctionnelle d’échange et de corrélation employée. Au chapitre 3, nous discutons de l’effet de l’ajout d’une chaîne ramifiée à des molécules conductrices sur la probabilité de transmission de dispositifs électroniques moléculaires. Nous trouvons que des interférences destructives apparaissent aux valeurs propres de l’énergie des chaînes ramifiées isolées, si ces valeurs ne correspondent pas à des états localisés éloignés du conducteur moléculaire. Au chapitre 4, nous montrons que les dispositifs électroniques moléculaires contenant une molécule aromatique présentent généralement des courants circulaires qui sont associés aux phénomènes d’interférence destructive dans ces systèmes. Au chapitre 5, nous employons l’approche « source-sink potential » (SSP) pour étudier la transmission de dispositifs électroniques moléculaires. Au lieu de considérer les potentiels de sources et de drains exactement, nous utilisons la théorie des perturbations pour trouver une expression de la probabilité de transmission, T(E) = 1 − |r(E)|2, où r(E) est le coefficient de réflexion qui dépend de l’énergie. Cette expression dépend des propriétés de la molécule isolée, en effet nous montrons que c’est la densité orbitalaire sur les atomes de la molécule qui sont connectés aux contacts qui détermine principalement la transmission du dispositif à une énergie de l’électron incident donnée. Au chapitre 6, nous présentons une extension de l’approche SSP à un canal pour des dispositifs électroniques moléculaires à plusieurs canaux. La méthode à multiples canaux proposée repose sur une description des canaux propres des états conducteurs du dispositif électronique moléculaire (DEM) qui sont obtenus par un algorithme auto-cohérent. Finalement, nous utilisons le modèle développé afin d’étudier la transmission du 1-phényl-1,3-butadiène branché à deux rangées d’atomes couplées agissant comme contacts à gauche et à la droite.