Représentation d'un polynôme par un circuit arithmétique et chaînes additives

Un circuit arithmétique dont les entrées sont des entiers ou une variable x et dont les portes calculent la somme ou le produit représente un polynôme univarié. On assimile la complexité de représentation d'un polynôme par un circuit arithmétique au nombre de portes multiplicatives minimal requis pour cette modélisation. Et l'on cherche à obtenir une borne inférieure à cette complexité, et cela en fonction du degré d du polynôme. A une chaîne additive pour d, correspond un circuit arithmétique pour le monôme de degré d. La conjecture de Strassen prétend que le nombre minimal de portes multiplicatives requis pour représenter un polynôme de degré d est au moins la longueur minimale d'une chaîne additive pour d. La conjecture de Strassen généralisée correspondrait à la même proposition lorsque les portes du circuit arithmétique ont degré entrant g au lieu de 2. Le mémoire consiste d'une part en une généralisation du concept de chaînes additives, et une étude approfondie de leur construction. On s'y intéresse d'autre part aux polynômes qui peuvent être représentés avec très peu de portes multiplicatives (les d-gems). On combine enfin les deux études en lien avec la conjecture de Strassen. On obtient en particulier de nouveaux cas de circuits vérifiant la conjecture.

Affine and generalized affine models : Theory and applications

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Conception et synthèse d’aminoglycosides semi-synthétiques

Plusieurs aminoglycosides font partie d’une famille d’antibiotiques à large spectre d’action. Les aminoglycosides ayant une activité antibiotique viennent interférer dans la synthèse protéique effectuée par les bactéries. Les protéines mal codées entraineront la mort cellulaire. Au fil des années, de nombreux cas de résistance ont émergé après une utilisation soutenue des aminoglycosides. De nombreux aminoglycosides semi-synthétiques ont été synthétisés avec comme objectif de restaurer leur activité antimicrobienne. Parmi les modifications ayant connu du succès, notons la didésoxygénation d’un diol et l’introduction de la chaine latérale HABA. Des études précédentes ont montré l’efficacité de ces modifications sur les aminoglycosides. Les présents travaux portent sur l’installation de la chaine latérale HABA et la didésoxygénation d’un diol sur la paromomycine et la néomycine. La didésoxygénation sélective des diols a été effectuée en utilisant la méthodologie développée par Garegg et Samuelsson, une variation de la réaction de Tipson-Cohen. Cette méthode a permis l’obtention du motif didésoxygéné sur les cycles A et D dans des rendements jamais égalés pour ce motif synthétique. La chaîne latérale a été introduite en tirant profit de la réactivité et de la sélectivité d’un carbamate cyclique. Ces méthodes combinées ont permis la synthèse efficace de nombreux analogues semi-synthétiques nouveaux. La 3',4'-didéhydro-N-1-HABA-néomycine et la 3',4',3''',4'''-tétradésoxy-N-1-HABA-néomycine montrent une activité impressionnante contre des souches de bactéries résistantes aux aminoglycosides. Des tests de toxicité effectués en collaboration avec Achaogen Inc. ont démontré que ces composés sont relativement toxiques sur les cellules rénales de type H2K, ce qui réduit de façon importante leur index thérapeutique. Afin d’abaisser la toxicité des composés, la relation entre toxicité et basicité a été explorée. Des substitutions de l’amine en 6''' ont été effectuées afin d’abaisser la basicité de l’amine. Les résultats de toxicité et d’activité antimicrobienne démontrent une corrélation importante entre la basicité des amines et la toxicité/activité des aminoglycosides antibiotiques. L’effet d’une modulation du pKa a aussi été exploré en installant des chaines fluorées sur l’amine en 6''' de la paromomycine et de la néomycine. Une séquence synthtétique pour isoler l’amine en 6''' de la néomycine a aussi été développée.

Bases moléculaires et cellulaires d’un trouble neurodéveloppemental causé par l’haploinsuffisance de SYNGAP1.

La déficience intellectuelle est la cause d’handicap la plus fréquente chez l’enfant. De nombreuses évidences convergent vers l’idée selon laquelle des altérations dans les gènes synaptiques puissent expliquer une fraction significative des affections neurodéveloppementales telles que la déficience intellectuelle ou encore l’autisme. Jusqu’à récemment, la majorité des mutations associées à la déficience intellectuelle a été liée au chromosome X ou à la transmission autosomique récessive. D’un autre côté, plusieurs études récentes suggèrent que des mutations de novo dans des gènes à transmission autosomique dominante, requis dans les processus de la plasticité synaptique peuvent être à la source d’une importante fraction des cas de déficience intellectuelle non syndromique. Par des techniques permettant la capture de l’exome et le séquençage de l’ADN génomique, notre laboratoire a précédemment reporté les premières mutations pathogéniques dans le gène à transmission autosomique dominante SYNGAP1. Ces dernières ont été associées à des troubles comportementaux tels que la déficience intellectuelle, l’inattention, des problèmes d’humeur, d’impulsivité et d’agressions physiques. D’autres patients sont diagnostiqués avec des troubles autistiques et/ou des formes particulières d’épilepsie généralisée. Chez la souris, le knock-out constitutif de Syngap1 (souris Syngap1+/-) résulte en des déficits comme l’hyperactivité locomotrice, une réduction du comportement associée à l’anxiété, une augmentation du réflexe de sursaut, une propension à l’isolation, des problèmes dans le conditionnement à la peur, des troubles dans les mémoires de travail, de référence et social. Ainsi, la souris Syngap1+/- représente un modèle approprié pour l’étude des effets délétères causés par l’haploinsuffisance de SYNGAP1 sur le développement de circuits neuronaux. D’autre part, il est de première importance de statuer si les mutations humaines aboutissent à l’haploinsuffisance de la protéine. SYNGAP1 encode pour une protéine à activité GTPase pour Ras. Son haploinsuffisance entraîne l’augmentation des niveaux d’activité de Ras, de phosphorylation de ERK, cause une morphogenèse anormale des épines dendritiques et un excès dans la concentration des récepteurs AMPA à la membrane postsynaptique des neurones excitateurs. Plusieurs études suggèrent que l’augmentation précoce de l’insertion des récepteurs AMPA au sein des synapses glutamatergiques contribue à certains phénotypes observés chez la souris Syngap1+/-. En revanche, les conséquences de l’haploinsuffisance de SYNGAP1 sur les circuits neuronaux GABAergiques restent inconnues. Les enjeux de mon projet de PhD sont: 1) d’identifier l’impact de mutations humaines dans la fonction de SYNGAP1; 2) de déterminer si SYNGAP1 contribue au développement et à la fonction des circuits GABAergiques; 3) de révéler comment l’haploinsuffisance de Syngap1 restreinte aux circuits GABAergiques affecte le comportement et la cognition. Nous avons publié les premières mutations humaines de type faux-sens dans le gène SYNGAP1 (c.1084T>C [p.W362R]; c.1685C>T [p.P562L]) ainsi que deux nouvelles mutations tronquantes (c.2212_2213del [p.S738X]; c.283dupC [p.H95PfsX5]). Ces dernières sont toutes de novo à l’exception de c.283dupC, héritée d’un père mosaïque pour la même mutation. Dans cette étude, nous avons confirmé que les patients pourvus de mutations dans SYNGAP1 présentent, entre autre, des phénotypes associés à des troubles comportementaux relatifs à la déficience intellectuelle. En culture organotypique, la transfection biolistique de l’ADNc de Syngap1 wild-type dans des cellules pyramidales corticales réduit significativement les niveaux de pERK, en fonction de l’activité neuronale. Au contraire les constructions plasmidiques exprimant les mutations W362R, P562L, ou celle précédemment répertoriée R579X, n’engendre aucun effet significatif sur les niveaux de pERK. Ces résultats suggèrent que ces mutations faux-sens et tronquante résultent en la perte de la fonction de SYNGAP1 ayant fort probablement pour conséquences d’affecter la régulation du développement cérébral. Plusieurs études publiées suggèrent que les déficits cognitifs associés à l’haploinsuffisance de SYNGAP1 peuvent émerger d’altérations dans le développement des neurones excitateurs glutamatergiques. Toutefois, si, et auquel cas, de quelle manière ces mutations affectent le développement des interneurones GABAergiques résultant en un déséquilibre entre l’excitation et l’inhibition et aux déficits cognitifs restent sujet de controverses. Par conséquent, nous avons examiné la contribution de Syngap1 dans le développement des circuits GABAergiques. A cette fin, nous avons généré une souris mutante knockout conditionnelle dans laquelle un allèle de Syngap1 est spécifiquement excisé dans les interneurones GABAergiques issus de l’éminence ganglionnaire médiale (souris Tg(Nkx2.1-Cre);Syngap1flox/+). En culture organotypique, nous avons démontré que la réduction de Syngap1 restreinte aux interneurones inhibiteurs résulte en des altérations au niveau de leur arborisation axonale et dans leur densité synaptique. De plus, réalisés sur des coupes de cerveau de souris Tg(Nkx2.1-Cre);Syngap1flox/+, les enregistrements des courants inhibiteurs postsynaptiques miniatures (mIPSC) ou encore de ceux évoqués au moyen de l’optogénétique (oIPSC) dévoilent une réduction significative de la neurotransmission inhibitrice corticale. Enfin, nous avons comparé les performances de souris jeunes adultes Syngap1+/-, Tg(Nkx2.1-Cre);Syngap1flox/+ à celles de leurs congénères contrôles dans une batterie de tests comportementaux. À l’inverse des souris Syngap1+/-, les souris Tg(Nkx2.1-Cre);Syngap1flox/+ ne présentent pas d’hyperactivité locomotrice, ni de comportement associé à l’anxiété. Cependant, elles démontrent des déficits similaires dans la mémoire de travail et de reconnaissance sociale, suggérant que l’haploinsuffisance de Syngap1 restreinte aux interneurones GABAergiques dérivés de l’éminence ganglionnaire médiale récapitule en partie certains des phénotypes cognitifs observés chez la souris Syngap1+/-. Mes travaux de PhD établissent pour la première fois que les mutations humaines dans le gène SYNGAP1 associés à la déficience intellectuelle causent la perte de fonction de la protéine. Mes études dévoilent, également pour la première fois, l’influence significative de ce gène dans la régulation du développement et de la fonction des interneurones. D’admettre l’atteinte des cellules GABAergiques illustre plus réalistement la complexité de la déficience intellectuelle non syndromique causée par l’haploinsuffisance de SYNGAP1. Ainsi, seule une compréhension raffinée de cette condition neurodéveloppementale pourra mener à une approche thérapeutique adéquate.

Analysis and Design of an Adaptive Polynomial Predistorter with the Loop Delay Estimator

Most adaptive linearization circuits for the nonlinear amplifier have a feedback loop that returns the output signal oj'tne eunplifier to the lineurizer. The loop delay of the linearizer most be controlled precisely so that the convergence of the linearizer should be assured lot this Letter a delay control circuit is presented. It is a delay lock loop (ULL) with it modified early-lute gate and can he easily applied to a DSP implementation. The proposed DLL circuit is applied to an adaptive linearizer with the use of a polynomial predistorter, and the simulalion for a 16-QAM signal is performed. The simulation results show that the proposed DLL eliminates the delay between the reference input signal and the delayed feedback signal of the linearizing circuit perfectly, so that the predistorter polynomial coefficients converge into the optimum value and a high degree of linearization is achieved

Hysteresis in a system driven by either generalized force or displacement variables: martensitic phase transition in single-crystalline Cu-Zn-Al

We report on experiments aimed at comparing the hysteretic response of a Cu-Zn-Al single crystal undergoing a martensitic transition under strain-driven and stress-driven conditions. Strain-driven experiments were performed using a conventional tensile machine while a special device was designed to perform stress-driven experiments. Significant differences in the hysteresis loops were found. The strain-driven curves show reentrant behavior yield point which is not observed in the stress-driven case. The dissipated energy in the stress-driven curves is larger than in the strain-driven ones. Results from recently proposed models qualitatively agree with experiments.

Algebraic Geometric Codes and their relation to Cryptography using Elliptic Curves

Communication is the process of transmitting data across channel. Whenever data is transmitted across a channel, errors are likely to occur. Coding theory is a stream of science that deals with finding efficient ways to encode and decode data, so that any likely errors can be detected and corrected. There are many methods to achieve coding and decoding. One among them is Algebraic Geometric Codes that can be constructed from curves. Cryptography is the science ol‘ security of transmitting messages from a sender to a receiver. The objective is to encrypt message in such a way that an eavesdropper would not be able to read it. A eryptosystem is a set of algorithms for encrypting and decrypting for the purpose of the process of encryption and decryption. Public key eryptosystem such as RSA and DSS are traditionally being prel‘en‘ec| for the purpose of secure communication through the channel. llowever Elliptic Curve eryptosystem have become a viable altemative since they provide greater security and also because of their usage of key of smaller length compared to other existing crypto systems. Elliptic curve cryptography is based on group of points on an elliptic curve over a finite field. This thesis deals with Algebraic Geometric codes and their relation to Cryptography using elliptic curves. Here Goppa codes are used and the curves used are elliptic curve over a finite field. We are relating Algebraic Geometric code to Cryptography by developing a cryptographic algorithm, which includes the process of encryption and decryption of messages. We are making use of fundamental properties of Elliptic curve cryptography for generating the algorithm and is used here to relate both.

Some Dynamic Generalized Information Measures In The Context Of Weighted Models

In this paper, we study some dynamic generalized information measures between a true distribution and an observed (weighted) distribution, useful in life length studies. Further, some bounds and inequalities related to these measures are also studied

A generic polynomial solution for the differential equation of hypergeometric type and six sequences of orthogonal polynomials related to it

In this work, we present a generic formula for the polynomial solution families of the well-known differential equation of hypergeometric type s(x)y"n(x) + t(x)y'n(x) - lnyn(x) = 0 and show that all the three classical orthogonal polynomial families as well as three finite orthogonal polynomial families, extracted from this equation, can be identified as special cases of this derived polynomial sequence. Some general properties of this sequence are also given.

Algorithmen für q-holonome Funktionen und q-hypergeometrische Reihen

Die q-Analysis ist eine spezielle Diskretisierung der Analysis auf einem Gitter, welches eine geometrische Folge darstellt, und findet insbesondere in der Quantenphysik eine breite Anwendung, ist aber auch in der Theorie der q-orthogonalen Polynome und speziellen Funktionen von großer Bedeutung. Die betrachteten mathematischen Objekte aus der q-Welt weisen meist eine recht komplizierte Struktur auf und es liegt daher nahe, sie mit Computeralgebrasystemen zu behandeln. In der vorliegenden Dissertation werden Algorithmen für q-holonome Funktionen und q-hypergeometrische Reihen vorgestellt. Alle Algorithmen sind in dem Maple-Package qFPS, welches integraler Bestandteil der Arbeit ist, implementiert. Nachdem in den ersten beiden Kapiteln Grundlagen geschaffen werden, werden im dritten Kapitel Algorithmen präsentiert, mit denen man zu einer q-holonomen Funktion q-holonome Rekursionsgleichungen durch Kenntnis derer q-Shifts aufstellen kann. Operationen mit q-holonomen Rekursionen werden ebenfalls behandelt. Im vierten Kapitel werden effiziente Methoden zur Bestimmung polynomialer, rationaler und q-hypergeometrischer Lösungen von q-holonomen Rekursionen beschrieben. Das fünfte Kapitel beschäftigt sich mit q-hypergeometrischen Potenzreihen bzgl. spezieller Polynombasen. Wir formulieren einen neuen Algorithmus, der zu einer q-holonomen Rekursionsgleichung einer q-hypergeometrischen Reihe mit nichttrivialem Entwicklungspunkt die entsprechende q-holonome Rekursionsgleichung für die Koeffizienten ermittelt. Ferner können wir einen neuen Algorithmus angeben, der umgekehrt zu einer q-holonomen Rekursionsgleichung für die Koeffizienten eine q-holonome Rekursionsgleichung der Reihe bestimmt und der nützlich ist, um q-holonome Rekursionen für bestimmte verallgemeinerte q-hypergeometrische Funktionen aufzustellen. Mit Formulierung des q-Taylorsatzes haben wir schließlich alle Zutaten zusammen, um das Hauptergebnis dieser Arbeit, das q-Analogon des FPS-Algorithmus zu erhalten. Wolfram Koepfs FPS-Algorithmus aus dem Jahre 1992 bestimmt zu einer gegebenen holonomen Funktion die entsprechende hypergeometrische Reihe. Wir erweitern den Algorithmus dahingehend, dass sogar Linearkombinationen q-hypergeometrischer Potenzreihen bestimmt werden können. ________________________________________________________________________________________________________________

Development and applications of density matrix functional theory of generalized Hubbard Models

In dieser Doktorarbeit wird eine akkurate Methode zur Bestimmung von Grundzustandseigenschaften stark korrelierter Elektronen im Rahmen von Gittermodellen entwickelt und angewandt. In der Dichtematrix-Funktional-Theorie (LDFT, vom englischen lattice density functional theory) ist die Ein-Teilchen-Dichtematrix γ die fundamentale Variable. Auf der Basis eines verallgemeinerten Hohenberg-Kohn-Theorems ergibt sich die Grundzustandsenergie Egs[γgs] = min° E[γ] durch die Minimierung des Energiefunktionals E[γ] bezüglich aller physikalischer bzw. repräsentativer γ. Das Energiefunktional kann in zwei Beiträge aufgeteilt werden: Das Funktional der kinetischen Energie T[γ], dessen lineare Abhängigkeit von γ genau bekannt ist, und das Funktional der Korrelationsenergie W[γ], dessen Abhängigkeit von γ nicht explizit bekannt ist. Das Auffinden präziser Näherungen für W[γ] stellt die tatsächliche Herausforderung dieser These dar. Einem Teil dieser Arbeit liegen vorausgegangene Studien zu Grunde, in denen eine Näherung des Funktionals W[γ] für das Hubbardmodell, basierend auf Skalierungshypothesen und exakten analytischen Ergebnissen für das Dimer, hergeleitet wird. Jedoch ist dieser Ansatz begrenzt auf spin-unabhängige und homogene Systeme. Um den Anwendungsbereich von LDFT zu erweitern, entwickeln wir drei verschiedene Ansätze zur Herleitung von W[γ], die das Studium von Systemen mit gebrochener Symmetrie ermöglichen. Zuerst wird das bisherige Skalierungsfunktional erweitert auf Systeme mit Ladungstransfer. Eine systematische Untersuchung der Abhängigkeit des Funktionals W[γ] von der Ladungsverteilung ergibt ähnliche Skalierungseigenschaften wie für den homogenen Fall. Daraufhin wird eine Erweiterung auf das Hubbardmodell auf bipartiten Gittern hergeleitet und an sowohl endlichen als auch unendlichen Systemen mit repulsiver und attraktiver Wechselwirkung angewandt. Die hohe Genauigkeit dieses Funktionals wird aufgezeigt. Es erweist sich jedoch als schwierig, diesen Ansatz auf komplexere Systeme zu übertragen, da bei der Berechnung von W[γ] das System als ganzes betrachtet wird. Um dieses Problem zu bewältigen, leiten wir eine weitere Näherung basierend auf lokalen Skalierungseigenschaften her. Dieses Funktional ist lokal bezüglich der Gitterplätze formuliert und ist daher anwendbar auf jede Art von geordneten oder ungeordneten Hamiltonoperatoren mit lokalen Wechselwirkungen. Als Anwendungen untersuchen wir den Metall-Isolator-Übergang sowohl im ionischen Hubbardmodell in einer und zwei Dimensionen als auch in eindimensionalen Hubbardketten mit nächsten und übernächsten Nachbarn. Schließlich entwickeln wir ein numerisches Verfahren zur Berechnung von W[γ], basierend auf exakten Diagonalisierungen eines effektiven Vielteilchen-Hamilton-Operators, welcher einen von einem effektiven Medium umgebenen Cluster beschreibt. Dieser effektive Hamiltonoperator hängt von der Dichtematrix γ ab und erlaubt die Herleitung von Näherungen an W[γ], dessen Qualität sich systematisch mit steigender Clustergröße verbessert. Die Formulierung ist spinabhängig und ermöglicht eine direkte Verallgemeinerung auf korrelierte Systeme mit mehreren Orbitalen, wie zum Beispiel auf den spd-Hamilton-Operator. Darüber hinaus berücksichtigt sie die Effekte kurzreichweitiger Ladungs- und Spinfluktuationen in dem Funktional. Für das Hubbardmodell wird die Genauigkeit der Methode durch Vergleich mit Bethe-Ansatz-Resultaten (1D) und Quanten-Monte-Carlo-Simulationen (2D) veranschaulicht. Zum Abschluss wird ein Ausblick auf relevante zukünftige Entwicklungen dieser Theorie gegeben.

Time Discretization of the SST-generalized Navier-Stokes Equations: Positive and Negative Results

In the theory of the Navier-Stokes equations, the proofs of some basic known results, like for example the uniqueness of solutions to the stationary Navier-Stokes equations under smallness assumptions on the data or the stability of certain time discretization schemes, actually only use a small range of properties and are therefore valid in a more general context. This observation leads us to introduce the concept of SST spaces, a generalization of the functional setting for the Navier-Stokes equations. It allows us to prove (by means of counterexamples) that several uniqueness and stability conjectures that are still open in the case of the Navier-Stokes equations have a negative answer in the larger class of SST spaces, thereby showing that proof strategies used for a number of classical results are not sufficient to affirmatively answer these open questions. More precisely, in the larger class of SST spaces, non-uniqueness phenomena can be observed for the implicit Euler scheme, for two nonlinear versions of the Crank-Nicolson scheme, for the fractional step theta scheme, and for the SST-generalized stationary Navier-Stokes equations. As far as stability is concerned, a linear version of the Euler scheme, a nonlinear version of the Crank-Nicolson scheme, and the fractional step theta scheme turn out to be non-stable in the class of SST spaces. The positive results established in this thesis include the generalization of classical uniqueness and stability results to SST spaces, the uniqueness of solutions (under smallness assumptions) to two nonlinear versions of the Euler scheme, two nonlinear versions of the Crank-Nicolson scheme, and the fractional step theta scheme for general SST spaces, the second order convergence of a version of the Crank-Nicolson scheme, and a new proof of the first order convergence of the implicit Euler scheme for the Navier-Stokes equations. For each convergence result, we provide conditions on the data that guarantee the existence of nonstationary solutions satisfying the regularity assumptions needed for the corresponding convergence theorem. In the case of the Crank-Nicolson scheme, this involves a compatibility condition at the corner of the space-time cylinder, which can be satisfied via a suitable prescription of the initial acceleration.

Parallel Methods for Synthesizing Whole-Hand Grasps from Generalized Prototypes

This report addresses the problem of acquiring objects using articulated robotic hands. Standard grasps are used to make the problem tractable, and a technique is developed for generalizing these standard grasps to increase their flexibility to variations in the problem geometry. A generalized grasp description is applied to a new problem situation using a parallel search through hand configuration space, and the result of this operation is a global overview of the space of good solutions. The techniques presented in this report have been implemented, and the results are verified using the Salisbury three-finger robotic hand.