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.

A survey of graph and subgraph isomorphism problems

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

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

Algorithmique et complexité des systèmes à compteurs

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

Nouvelle arithmétique des écoles primaires : divisee en deux parties, 1º theorie ... /

Contiene: 1º Théorie et pratique du calcul. - 2º Applications.

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.

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.

É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.

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.

The decoupling approach to quantum information theory

La théorie de l'information quantique étudie les limites fondamentales qu'imposent les lois de la physique sur les tâches de traitement de données comme la compression et la transmission de données sur un canal bruité. Cette thèse présente des techniques générales permettant de résoudre plusieurs problèmes fondamentaux de la théorie de l'information quantique dans un seul et même cadre. Le théorème central de cette thèse énonce l'existence d'un protocole permettant de transmettre des données quantiques que le receveur connaît déjà partiellement à l'aide d'une seule utilisation d'un canal quantique bruité. Ce théorème a de plus comme corollaires immédiats plusieurs théorèmes centraux de la théorie de l'information quantique. Les chapitres suivants utilisent ce théorème pour prouver l'existence de nouveaux protocoles pour deux autres types de canaux quantiques, soit les canaux de diffusion quantiques et les canaux quantiques avec information supplémentaire fournie au transmetteur. Ces protocoles traitent aussi de la transmission de données quantiques partiellement connues du receveur à l'aide d'une seule utilisation du canal, et ont comme corollaires des versions asymptotiques avec et sans intrication auxiliaire. Les versions asymptotiques avec intrication auxiliaire peuvent, dans les deux cas, être considérées comme des versions quantiques des meilleurs théorèmes de codage connus pour les versions classiques de ces problèmes. Le dernier chapitre traite d'un phénomène purement quantique appelé verrouillage: il est possible d'encoder un message classique dans un état quantique de sorte qu'en lui enlevant un sous-système de taille logarithmique par rapport à sa taille totale, on puisse s'assurer qu'aucune mesure ne puisse avoir de corrélation significative avec le message. Le message se trouve donc «verrouillé» par une clé de taille logarithmique. Cette thèse présente le premier protocole de verrouillage dont le critère de succès est que la distance trace entre la distribution jointe du message et du résultat de la mesure et le produit de leur marginales soit suffisamment petite.

Les marques du diable et les signes de l'Autre : rhétorique du dire démonologique à la fin de la Renaissance

Comment le motif de la marque insensible du diable a-t-il pu se frayer un chemin au sein du discours théologique, juridique et médical de la fin de la Renaissance jusqu'à s'imposer comme une pièce essentielle du crime de sorcellerie? Selon quels mécanismes et à partir de quels systèmes de croyance cette marque corporelle en est-elle venue à connaître une si large diffusion et une aussi grande acceptation tant chez les gens du livres que parmi les couches populaires? En cette époque marquée par la grande chasse aux sorcières et le développement de l'investigation scientifique, l'intérêt que les savants portent à cette étrange sémiologie constitue une porte d'accès privilégiée pour aborder de front la dynamique du déplacement des frontières que la démonologie met en oeuvre au sein des différents champs du savoir. Cette thèse a pour objectif d'étudier le réseau des mutations épistémologiques qui conditionne l'émergence de la marque du diable dans le savoir démonologique français à la charnière des XVIe et XVIIe siècles. Nous examinerons par quels cheminements l'altérité diabolique s'est peu à peu intériorisée dans le corps et l'âme des individus sous l'influence grandissante des vertus de l'empirisme, de la méthode expérimentale et de l'observation. En analysant la construction rhétorique de la théorie des marques du diable et en la reliant aux changements qui s'opèrent sur la plateforme intellectuelle de l'Ancien Régime, nous entendons éclairer la nouvelle distribution qui s'effectue entre les faits naturels et surnaturels ainsi que les modalités d'écriture pour en rendre compte.

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.