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

Ce mémoire de thèse est consacré à l'étude de quelques problèmes de probabilités provenant de l'informatique théorique. Dans une première partie, nous étudions un algorithme probabiliste qui compte le nombre de mots différents dans une liste. Nous montrons que l'étude peut se ramener à un problème d'estimation, et qu'en modifiant légèrement cet algorithme, il est d'une certaine manière optimal. La deuxième partie est consacrée à l'étude de plusieurs problèmes de convergences pour des systèmes finis de particules, nous envisageons différents types de passage à une limite infinie. La première famille de systèmes considérés est une classe particulière d'automates cellulaires. En dimension 1, il apparaît des marches aléatoires dont nous caractérisons de façon complète les comportements limites. En dimension 2, sur une grille carrée, nous étudions quelques-un des cas les plus représentatifs. Nous en déterminons le temps moyen de convergence vers une configuration fixe. Enfin, nous étudions un modèle d'urnes avec des boules à deux états. Dans la troisième partie, nous étudions deux problèmes particuliers de marches aléatoires. Ces deux questions sont initialement motivées par l'étude de certains automates cellulaires, mais nous les présentons de façon indépendante. Le premier de ces deux problèmes est l'étude de marches aléatoires sur un tore discret, réfléchies les unes sur les autres. On montre la convergence de ce processus vers une limite brownienne. Nous étudions enfin de façon entièrement combinatoire une famille de marches aléatoires sur un intervalle, biaisées vers le bas. Nous déterminons le temps moyen de sortie vers le haut de la marche. / This thesis deals with several problems in probability, mostly motivated by theoretical computer science. In the first part, we study of a probabilistic algorithm that counts the number of different words in a given sequence, by boiling it down to a statistical problem. We show that slightly improved, it achieves an optimal bound. The second and main part is devoted to different asymptotic problems concerning finite particle systems, for which we consider different kinds of infinite limits. We first deal with cellular automata. In dimension one, it appears random walks for which we entirely describe the asymptotic behaviors. In dimension two, on a square grid, we study some caracteristic rules for which we estimate the converge time. Lastly, we study a family of urn models. The third part focuses on two random walks problems. These questions where motivated by the study of cellular automata, but presented here in a self-contained way. The first problem is the study of a family of self-reflected random walks on a circle, for which we show a ``brownian limit''. The latter is a combinatorial description of a family of biased random walks on an interval.

La théorie supersymmetrique N = 2 de Yang-Mills est considérée pour tous les groupes de jauge classiques (SU(N), SO(N) et Sp(N)). Les expressions formelles pour l'action Wilsonienne effective pour (presque) tous les modèles compatible avec la condition de la liberté asymptotique sont obtenues. Les équations qui déterminent les courbes de Seiberg et Witten sont proposées. Dans quelque cas elles sont résolues. Il est montre que pour tous les modèles considères les corrections à l' instant on qui viennent de ces équations sont en accord avec les calculs directs. Ainsi elles sont en accord avec les calculs bases sur les courbes de Seiberg et Witten qui viennent de la théorie M. Il est montre donc que pour une grande classe de modèles les prédictions de la théorie M coïncident avec les calculs directs. Ceci est fait pour toutes les modèles considères au niveau des calculs à l' instant on. Pour quelques modèles ceci est fait au niveau des courbes algébriques.

Cette thèse est consacrée à l'étude des opérateurs de composition sur les espaces modèles. Soit [Phi] une fonction analytique du disque unité dans lui-même et soit [Théta] une fonction intérieure, c'est à  dire une fonction holomorphe et bornée par 1 dont les limites radiales sur le cercle sont de module 1 presque partout par rapport à la mesure de Lebesgue. A cette fonction [Théta], on associe l'espace modèle K[Théta], défini comme l'ensemble des fonctions f ∈ H² qui sont orthogonales au sous-espace [Théta]H². Ici H² est l'espace de Hardy du disque unité. Ces sous-espaces sont importants en théorie des opérateurs car ils servent à modéliser une large classe de contractions sur un espace de Hilbert. Le premier problème auquel nous nous intéressons concerne la compacité d'un opérateur de composition C[Phi] vu comme opérateur de K[Théta], dans H². Récemment, Lyubarskii et Malinnikova ont obtenu un joli critère de compacité pour ces opérateurs qui fait intervenir la fonction de comptage de Nevanlinna du symbole [Phi]. Ce critère généralise le critère classique de Shapiro. Dans une première partie de la thèse, nous généralisons ce résultat de Lyubarskii-Malinnikova à une classe plus générale de sous-espaces, à savoir les espaces de de Branges-Rovnyak ou certains de leurs sous-espaces. Les techniques utilisées sont en particulier des inégalités  fines de type Bernstein pour ces espaces. Le deuxième problème auquel nous nous intéressons dans cette thèse concerne l'invariance de K[Théta] sous l'action de C [Phi]. Ce problème nous amène à considérer une structure de groupe sur le disque  unité du plan complexe via les automorphismes qui fixent le point 1. A travers cette action de groupe, chaque point du disque produit une classe d'équivalence qui se trouve être une suite de Blaschke. On montre alors que les produits de Blaschke correspondant sont des solutions "minimales" d'une équation fonctionnelle [Psi]°[Phi]=[Lambda][Psi], où [Lambda] est une constante unimodulaire et [Phi] un automorphisme du disque unité. Ces résultats sont ensuite appliqués au problème d'invariance d'un espace modèle par un opérateur de composition. / This thesis concerns the study of composition operators on model spaces. Let [Phi] be an analytic function on the unit disk into itself and let [Théta] be an inner function, that is a holomorphic function bounded by 1 such that the radial limits on the unit circle are of modulus 1 almost everywhere with respect to Lebesgue measure. With this function [Théta], we associate the model space K[Théta], defined as the set of functions f ∈ H², which are orthogonal to the subspace [Théta]H². Here H² is the Hardy space on the unit disc. These subspaces are important in operator theory because they are used to model a large class of contractions on Hilbert space. The first problem which we are interested in concerns the compactness of the composition operator C[Phi] as an operator on H² into H². Recently, Lyubarskii and Malinnikova have obtained a nice criterion for the compactness of these operators which is related to the Nevanlinna counting function. This criterion generalizes the classical criterion of Shapiro. In the first part of the thesis, we generalize this result of Lyubarskii-Malinnikova to a more general class of subspaces, known as de Branges-Rovnyak spaces or some subspaces of them. The techniques that are used are particular Bernstein type inequalities of these spaces.The second problem in which we are interested in this thesis concerns the invariance of K[Théta] under C[Phi]. We present a group structure on the unit disc via the automorphisms which fix the point 1. Then, through theinduced group action, each point of the unit disc produces an equivalence class which turns out to be a Blaschke sequence. Moreover, the corresponding Blaschke products are minimal solutions of the functional equation [Psi]°[Phi]=[Lambda][Psi] where [Lambda] is a unimodular constant and is an automorphism of the unit disc. These results are applied in the invariance problem of the model spaces by the composition operator.

Le comptage des points rationnels est un problème classique en géométrie diophantienne. On s’intéresse à des majorations du nombre des points rationnels de hauteur bornée qui sont valables pour toute hypersurface arithmétique de degré fixé d’un espace projectif. Dans ce but, on construit une famille d’hypersurfaces auxiliaires qui contiennent tous les points rationnels de hauteur bornée mais ne contiennent pas le point générique de l’hypersurface initiale. Plusieurs outils géométriques sont développés ou adaptés dans le cadre de la géométrie d’Arakelov et de la géométrie diophantienne afin d’appliquer la méthode des déterminants par la langage de la géométrie d’Arakelov, notamment une majoration et une minoration explicite uniforme de la fonction de Hilbert-Samuel arithmétrique d’une hypersurface. Pour un schéma projectif réduit de dimension pure sur un anneau d’entiers algébriques, on donne une majoration du nombre des places sur lesquelles la fibre ne soit pas réduite. Cette majoration est utile pour la construction des hypersurfaces auxiliaires mentionnées au-dessus. De plus, la géométrie sur un corps fini joue un rôle important dans ce problème. Dans ce travail, l’un des ingrédients clé dans ce travail est une majoration effective liée à une fonction de comptage des multiplicités des points rationnels dans une hypersurface projective réduite définie sur un corps fini, qui donne une description de la complexité de son lieu singulier. Pour ce problème de comptage de multiplicités, l’outil principal est la théorie d’intersection sur un espace projectif. / Counting rational points is a classical problem in Diophantine geometry. We are interested inupper bounds for the number of rational points of bounded height of an arithmetic hypersurface with bounded degree in a projective space. For this propose, we construct a family of auxiliary hypersurfaces which contain all these rational points of bounded height but don’t contain the generic point of this hypersurface. Several tools of Arakelov geometry and Diophantine geometry are developed or adapted in this work in order to apply the determinant method by the approach of Arakelov geometry, especially a uniform explicit upper bound and a uniform explicit lower bound of the arithmetic Hilbert-Samuel function of a hypersurface. For a reduced pure dimensional projective scheme over a ring of algebraic integers, we give an upper bound of the number of places over which the fiber is not reduced any longer. This upper bound is useful for the construction of these auxilary hypersurfaces mentioned above. In addition, the geometry over a finite field plays an important role in this problem. One of the key ingredients in this work is an e_ective upper bound for a counting function of multiplicities of rational points in a reduced projective hypersurface defined over a finite field, which gives a description of the complexity of its singular locus. For this problem of counting multiplicities, the major tool is intersection theory on a projective space

L'un des objectifs centraux de la biologie est de comprendre comment l'ADN, la séquence primaire, donne lieu à des traits observables. À cette fin, nous examinons ici des méthodes pour identifier les composants génétiques qui influencent les traits microbiens. Par « identifier », nous entendons l'élucidation à la fois l'état allélique et de la position physique de chaque variante causale d'un phénotype d'intérêt à la résolution des nucléotides de paires de bases. Nous nous sommes concentrés sur les études d'association génomique (genome-wide association studies; GWAS) en tant qu'approche générale d’étudier l'architecture génétique des traits. L'objectif global de cette thèse était d'examiner de manière critique les méthodologies GWAS et de les considérer en pratique dans des populations microbiennes fortement clonales et non- clonales (i.e. avec recombinaison fréquent). Le domaine de la GWAS microbienne est relativement nouveau par rapport aux quinze dernières années de la GWAS humaine, et en tant que tel, nous avons commencé par un examen de l'état de la GWAS microbienne. Nous avons posé deux questions principales : 1) Les méthodes GWAS humaines fonctionnent-elles facilement et sans modification pour les populations microbiennes ? 2) Et sinon, quels sont les problèmes méthodologiques centraux et les modifications nécessaires pour la GWAS microbienne? À partir de ces résultats, nous avons ensuite détaillé le déséquilibre de liaison (linkage disequilibrium; LD) comme principal obstacle dans la GWAS microbien, et nous avons présenté une nouvelle méthode, POUTINE, pour relever ce défi en exploitant les mutations homoplasiques pour briser implicitement la structure LD. Le reste de la thèse présente à la fois les méthodes traditionnelles GWAS (comptage des allèles) et POUTINE (comptage d’homoplasies) appliquées à une population hautement recombinogène de génomes de vibrions marins. Malgré une taille d'échantillon modeste, nous donnons un premier aperçu de l'architecture génétique de la résistance aux bactériophages dans une population naturelle, tout en montrant que les récepteurs des bactériophages jouent un rôle primordial. Ce résultat est en pleine cohérence avec des expériences en laboratoire de coévolution phage-bactérie. Il est important de noter que cette architecture met en évidence à quel point la sélection positive peut sculpter certains traits microbiens différemment de nombreux traits complexes humains, qui sont généralement soumis à une faible sélection purificatrice. Plus précisément, nous avons identifié des mutations à effet important à haute fréquence qui sont rarement observées dans les phénotypes complexes humains où de nombreuses mutations à faible effet contribuent à l'héritabilité. La thèse se termine par des perspectives sur les voies à suivre pour la GWAS microbienne. / One of the central goals of biology is to understand how DNA, the primary sequence, gives rise to observable traits. To this aim, we herein examine methods to identify the genetic components that influence microbial traits. By "identify" we mean the elucidation of both the allelic state and physical position of each causal variant of a phenotype of interest down to the base-pair nucleotide resolution. Our focus has been on genome-wide association studies (GWAS) as a general approach to dissecting the genetic architecture of traits. The overarching aim of this thesis was to critically examine GWAS methodologies and to consider them in practice in both strongly clonal and highly recombining microbial populations. The field of microbial GWAS is relatively new compared to the over fifteen years of human GWAS, and as such, we began this work with an examination of the state of microbial GWAS. We asked and attempted to answer two main questions: 1) Do human GWAS methods readily work without modification for microbial populations? 2) And if not, what are the central methodological problems and changes that are required for a successful microbial GWAS? Building from these findings, we then detailed linkage disequilibrium (LD) as the primary obstacle in microbial GWAS, and we presented a new method, POUTINE, to address this challenge by harnessing homoplasic mutations to implicitly break LD structure. The remainder of the thesis showcases both traditional GWAS methods (allele counting) and POUTINE applied to a highly recombining population of marine vibrio genomes. Despite a small sample size, we provide a first glimpse into the genetic architecture of bacteriophage resistance in a natural population and show that bacteriophage receptors play a primary role consistent with experimental populations of phage-bacteria coevolution. Importantly, this architecture highlights how strong positive selection can sculpt some microbial traits differently than many human complex traits, which are generally under weak purifying selection. Specifically, we identified common frequency, large-effect mutations that are rarely observed in human complex phenotypes where many low-effect mutations are thought to contribute to the bulk of heritability. The thesis concludes with perspectives on ways forward for microbial GWAS.

La tomodensitométrie (TDM) est une modalité d'imagerie médicale anatomique extrêmement utile en imagerie moléculaire. Elle permet de localiser de façon précise les sources d'émissions détectées en tomographie d'émission par positrons (TEP) relativement à des repères anatomiques facilement identifiables dans les images à haute résolution de la TDM. La localisation s'effectue par superposition des images issues de la TDM et de la TEP, cette dernière étant susceptible de ne contenir que peu de repères anatomiques selon le radiotraceur utilisé. Classiquement, la TDM et la TEP se jumellent en juxtaposant axialement un scanner de chaque modalité de sorte que le sujet traverse successivement chaque appareil pour effectuer les deux acquisitions indépendamment. Cette translation diminue la qualité de la fusion des images, puisque les organes du sujet peuvent se déplacer légèrement, ce qui rend l'alignement difficile après la reconstruction. De plus, dans un grand nombre d'études en imagerie moléculaire, il s'est avéré que la dose de radiations X transmise au sujet lors de l'acquisition TDM peut influencer les résultats quantitatifs obtenus en TEP, ce qui rend ces études difficilement répétables. Les tomodensitomètres actuels mesurent exclusivement le flux de radiation traversant le sujet en intégrant la charge créée par les photons X lors de leur interaction photoélectrique dans un dispositif de conversion de lumière en électrons. Ce mode d'acquisition dit"d'intégration" filtre bien le bruit à haute fréquence mais accumule toutefois le courant de fuite du photodétecteur. Pour obtenir un rapport signal à bruit (S/B) adéquat en TDM, il est nécessaire d'augmenter la dose de radiations transmise de façon significative. Cette technique ne se prête pas bien à l'imagerie moléculaire où la dose injectée joue un rôle limitatif sur le diagnostic et d'autres solutions doivent être apportées. Un mode de mesure du flux de radiation novateur, qui compte individuellement chacun des photons à l'aide d'une électronique de traitement rapide, constitue une alternative au problème d'intégration et permet d'éliminer partiellement le bruit électronique. La bande passante du préamplificateur doit cependant être élevée pour permettre la détection de plusieurs millions de photons par secondes par canal d'acquisition, afin de réduire le temps total d'acquisition nécessaire. Une telle électronique a été développée à Sherbrooke et jumelée à de puissants processeurs de traitement numériques [i.e. numérique]. Cette chaîne d'acquisition double modalité (TEP/TDM), la chaîne LabPETTM, sert déjà à la mesure de TEP dans un scanner commercial pour petits animaux. Le développement d'algorithmes de traitement numériques adaptés au comptage de photons en tomodensitométrie permettrait à cette chaîne d'effectuer une mesure moins bruitée et nécessitant donc une dose substantiellement réduite. De plus, la technologie LabPETTM pourra, à partir d'un même anneau de détection, effectuer une acquisition bimodale TEP/TDM qui s'avérera moins coûteuse, occupera moins d'espace et facilitera la fusion des images TEP/TDM. Les travaux de ce mémoire ont permis d'obtenir une méthode de traitement numérique capable de supporter le comptage des photons à un débit de plusieurs millions d'événements par secondes par détecteur avec une chaîne LabPETTM. La méthode fonctionne par prédiction du signal et se base sur la réponse impulsionnelle de la chaîne placée en mode de préamplification TDM. Cette méthode ouvre la porte au développement du LabPET/TDM, un appareil bimodal intégré de faible dose.

La photodétection est un sujet de recherche très actif encore de nos jours et l’industrie, particulièrement de la physique des hautes énergies et de l’imagerie médicale, est en quête de détecteurs avec une plus grande sensibilité, de meilleures résolutions temporelles et une plus grande densité d’intégration. Pour ces raisons, les photodiodes avalanche à photon unique (Single photon avalanche diode, ou SPAD) suscitent beaucoup d’intérêt depuis quelques années pour ses performances en temps et sa grande photosensibilité. Les SPAD sont des photodiodes avalanche opérées au-dessus de la tension de claquage et un photoporteur atteignant la région de multiplication peut à lui seul déclencher une avalanche soutenue de porteurs et entraîner le claquage de la jonction. Un circuit détecte le courant divergent et l’étouffe en abaissant la polarisation de la jonction sous la tension de claquage. Le circuit recharge ensuite la jonction en réappliquant la tension initiale permettant la détection d’un nouveau photon. Dans le but d’augmenter le nombre de photons simultanés détectables, les SPAD s’intègrent en matrice. Cependant, dans le cas où une matrice de SPAD et leurs circuits d’étouffement s’intègrent sur le même substrat, la surface photosensible devient limitée par l’espace qu’occupent les circuits d’étouffement. Dans le but d’augmenter leur région photosensible, les matrices de SPAD peuvent s’intégrer en trois dimensions (3D) avec leurs circuits d’étouffement. Ce projet porte sur le développement de matrices de SPAD en technologie CMOS HV 0,8 µm de Teledyne DALSA dédiées à une intégration 3D avec leurs circuits d’étouffement actifs. Les résultats de caractérisation montrent que les SPAD atteignent une résolution temporelle de 27 ps largeur à mi hauteur (LMH), possèdent un taux de comptage en obscurité (DCR, ou Dark Count Rate) de 3 s[indice supérieur -1]µm[indice supérieur -2] et ont une probabilité de photodétection (PDP) de 49 %. De plus, une méthode d’isolation utilisant un puits p a été développée. Les SPAD conçus avec cette méthode ont un facteur de remplissage pouvant atteindre 54 % et une probabilité de diaphonie de 6,6 % à une tension excédentaire à la tension de claquage (V[indice inférieur E]) de 4 V.

La mesure de temps de vol de photons et/ou de temps de propagation d’ondes RF et ultra large bande est devenue une technique essentielle et indispensable pour de nombreuses applications telles qu’en géolocalisation en intérieur, en détection LASER et en imagerie biomédicale, notamment en tomographie optique diffuse (TOD) avec des mesures dans le domaine temporel (DT). De telles mesures nécessitent des convertisseurs temps-numérique aptes à mesurer des intervalles de temps très courts avec grande précision, et ce, à des résolutions temporelles allant de quelques picosecondes à quelques dizaines de picosecondes. Les scanners TOD-DT ont généralement recours à des cartes électroniques de comptage de photons uniques intégrant essentiellement des convertisseurs temps-numérique hybrides (un mixte de circuits monolithiques et non-monolithiques). Dans le but de réduire le temps d’acquisition de ces appareils et d’augmenter leur précision, plusieurs mesures à différentes positions et longueurs d’ondes doivent pouvoir être effectuées en parallèle, ce qui exige plusieurs cartes de comptage de photons. L’implémentation de tels dispositifs en technologie CMOS apporte de multiples avantages particulièrement en termes de coût, d’intégration et de consommation de puissance. Cette thèse apporte une solution architecturale d’un convertisseur temps-numérique à 10-bits dédié aux applications de TOD-DT. Le convertisseur réalisé en technologie CMOS 0,13 μm d’IBM et occupant une surface en silicium de 1,83 x 2,23 mm[indice supérieur 2] incluant les plots de connexion, présente une résolution temporelle de 12 ps sur une fenêtre de 12 ns pour une consommation en courant de 4,8 mA. Les avantages de l’architecture proposée par rapport à d’autres réalisations rapportées dans la littérature résident dans son immunité face aux variations globales du procédé de fabrication, l’indépendance de la résolution temporelle vis-à-vis de la technologie ciblée et la faible gigue temporelle qu’il présente. Le circuit intégré réalisé trouvera plusieurs champs d’applications autres que la TOD notamment dans les tomographes d’émission par positrons, les boucles à verrouillage de phase numériques et dans les systèmes de télédétection et d’imagerie 3D.

Depuis l'avènement de la tomodensitométrie (TDM) au début des années 1970, la durée nécessaire à l'acquisition d'un jeu de données nécessaire à la reconstruction d'une image est passée de plusieurs jours à quelques centaines de millisecondes. Mis à part le progrès des composants mécaniques, électriques et électroniques, le principe de base implanté dans le tout premier prototype est toujours utilisé par les scanners d'aujourd'hui. Si le principe est resté le même, l'utilisation de l'imagerie TDM clinique a connu pour sa part une expansion fulgurante. Un nombre d'examens important, atteignant mondialement les centaines de millions par an au début des années 2000, commence alors à inquiéter la communauté scientifique et médicale. Si la dose administrée par examen reste relativement faible, les conséquences de cette exposition globale pourraient s'avérer fâcheuses. Parallèlement, les 15 dernières années ont vu l'apparition d'un nouveau type de détection. Ce détecteur, qui compte individuellement les photons X et mesure leur énergie, pourrait jouer un rôle important dans la quête de réduction de la dose. Même si ce nouveau développement n'a pas été motivé en réponse directe à l'accroissement de la dose, son avènement arrive à un moment très opportun. D'après la théorie, le seul fait d'acquérir la radiation incidente en utilisant cette approche permet une mesure moins bruitée. La nature spectrale de l'information recueillie ouvre aussi la porte à de nouvelles méthodes de traitement et d'analyse des images reconstruites. Dans la pratique, la fabrication de tels détecteurs n'est cependant pas chose facile et de nombreux impondérables ont fait leur apparition. L'influence des différentes caractéristiques de détection sur la qualité des images est aujourd'hui encore méconnue. Ce projet contient diverses contributions apportées au domaine de la TDM polyénergétique, en utilisant le concept de reconstruction d'images pour leitmotiv. Dans un premier temps, un modèle pragmatique et très différent des approches Monte Carlo existantes est proposé afin de reproduire de manière analytique une acquisition TDM spectrale. Un nouvel algorithme de reconstruction itératif adapté spécifiquement aux données polyénergétiques est ensuite présenté. Cet algorithme, unifiant les concepts éprouvés de décomposition en fonctions de base et de reconstruction statistique, permet de tirer pleinement parti de cette mesure particulière. Une approche de reconstruction différente, utilisant une représentation polaire de l'objet image, est aussi présentée. Celle-ci permet de diminuer grandement les exigences logicielles tout en réduisant les durées de reconstruction. L'influence de certaines caractéristiques de détection associées aux détecteurs spectraux est aussi étudiée, en mettant l'emphase sur les conséquences au niveau de la qualité des images reconstruites. Une méthode novatrice, permettant d'estimer le dépôt de dose à partir d'une acquisition polyénergétique, est finalement présentée.