Le télescopage créatif est un principe algorithmique développé depuis les années 1990 en combinatoire et en calcul formel, notamment depuis les travaux de Doron Zeilberger, pour calculer avec des sommes et intégrales paramétrées, que ce soit pour trouver des formes explicites ou pour justifier des identités intégrales ou sommatoires. Le procédé est particulièrement adapté à une grande famille de fonctions et suites données par des équations linéaires différentielles et de récurrences, que ce soient des fonctions spéciales de l'analyse, des suites de la combinatoire, ou des familles de polynômes orthogonaux. Dans ce mémoire, je retrace l'évolution des algorithmes et de mes contributions pour adapter le procédé à des classes de fonctions de plus en plus générales, du cadre initial des suites hypergéométriques, données par des récurrences d'ordre 1, aux cas de fonctions données par des équations d'ordre supérieur, ceci jusqu'aux fonctions données par des idéaux non zéro-dimensionnels. La difficulté d'obtenir des implantations rapides dans tous ces cas repose sur le calcul d'un certificat justifiant l'application du télescopage créatif, ce certificat étant par nature de grande taille. Ceci m'a motivé dans l'étude de la complexité du procédé. Plusieurs pistes d'amélioration ont été explorées, d'abord en essayant de maintenir compact ce certificat, puis en obtenant des algorithmes validés sans passer par son calcul. Comme souvent, l'estimation des tailles arithmétiques des objets intervenant dans le telescopage créatif a à la fois guidé le développement de nouveaux algorithmes plus efficaces et permis leur estimation théorique de complexité. Pour finir, j'indique brièvement la direction qu'a prise mes travaux récents sur le sujet, vers la preuve formelle, et qui font ressortir des pistes pour une meilleure justification de l'application du télescopage créatif.

Cette thèse montre comment le calcul formel permet la manipulation d'une grande classe de suites et fonctions solutions d'opérateurs linéaires, la classe des fonctions holonomes. Celle-ci contient de nombreuses fonctions spéciales, en une ou plusieurs variables, et de nom- breuses suites de la combinatoire. Un cadre théorique est tout d'abord introduit pour algorith- miser les propriétés de clôture de la classe holonome, pour y permettre un test à zéro et pour unifier les calculs différentiels sur les fonctions et les calculs de récurrences sur les suites. Ces méthodes s'appuient sur des calculs par une extension de la théorie des bases de Gröbner dans un cadre de polynômes non commutatifs, les polynômes de Ore. Deux types d'algorithmes de sommation et d'intégration symboliques définies et indéfinies sont ensuite développés, dont la justification théorique fait appel à la théorie des D-modules holonomes. Les premiers ont recours à une élimination polynomiale non commutative par bases de Gröbner ; les seconds à des algo- rithmes de résolution de systèmes fonctionnels linéaires en leurs solutions fractions rationnelles. Bien plus que la recherche de formes closes, l'objectif est de pouvoir continuer à calculer avec la représentation implicite des objets holonomes même en l'absence de formes explicites. Ce type de calculs permet en particulier la preuve automatique d'identités sommatoires et intégrales. Une implantation de ces algorithmes dans le système de calcul formel Maple a permis de donner la première preuve automatique d'identités jusqu'à présent inaccessibles par le calcul formel.

Computations with polynomials are at the heart of any computer algebra system and also have many applications in engineering, coding theory, and cryptography. Generally speaking, the low-level polynomial computations of interest can be classified as arithmetic operations, algebraic computations, and inverse symbolic problems. New algorithms are presented in all these areas which improve on the state of the art in both theoretical and practical performance. Traditionally, polynomials may be represented in a computer in one of two ways: as a "dense" array of all possible coefficients up to the polynomial's degree, or as a "sparse" list of coefficient-exponent tuples. In the latter case, zero terms are not explicitly written, giving a potentially more compact representation. In the area of arithmetic operations, new algorithms are presented for the multiplication of dense polynomials. These have the same asymptotic time cost of the fastest existing approaches, but reduce the intermediate storage required from linear in the size of the input to a constant amount. Two different algorithms for so-called "adaptive" multiplication are also presented which effectively provide a gradient between existing sparse and dense algorithms, giving a large improvement in many cases while never performing significantly worse than the best existing approaches. Algebraic computations on sparse polynomials are considered as well. The first known polynomial-time algorithm to detect when a sparse polynomial is a perfect power is presented, along with two different approaches to computing the perfect power factorization. Inverse symbolic problems are those for which the challenge is to compute a symbolic mathematical representation of a program or "black box". First, new algorithms are presented which improve the complexity of interpolation for sparse polynomials with coefficients in finite fields or approximate complex numbers. Second, the first polynomial-time algorithm for the more general problem of sparsest-shift interpolation is presented. The practical performance of all these algorithms is demonstrated with implementations in a high-performance library and compared to existing software and previous techniques.

Made available in DSpace on 2014-06-11T19:35:41Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-01Bitstream added on 2014-06-13T18:48:27Z : No. of bitstreams: 1 correa_va_dr_guara.pdf: 949805 bytes, checksum: 5d0ebae9cf9395efc83588da395f5ab9 (MD5) / Universidade Estadual Paulista (UNESP) / Com a evolução dos sistemas de computação simbólica ampliou-se a capacidade de modelagem e análise de problemas provenientes de equações diferenciais. Propõe-se a resolução da equação da condução de calor em regimes permanente e transiente para uma geometria cilíndrica com condições de contorno convectivas de forma analítica e numérica utilizando o software de computação simbólica Maple. Para este propósito serão empregados para a resolução analítica, o método de separação de variáveis e para a resolução numérica, o método das diferenças finitas com o esquema Crank- Nicolson e explícito. Os resultados obtidos das resoluções analíticas e numéricas, para algumas situações avaliadas são comparadas. As vantagens computacionais da utilização do software Maple são apresentadas. / The evolution of symbolic computation systems enlarges the capacity of modeling and analysis of problems by differential equations. The aim is the resolution of the conduction heat equation in unsteady and steady state for the cylindrical geometry with convective boundary conditions with analytical and numerical solutions using the Maple software. To this results will be used the separated variables method and finite differences to numerical solutions with Crank-Nicolson and explicit schemes. The results obtained for numerical and analytical solutions for some situations it will available and compared. The computational advantages of the Maple software are showed too.

In this thesis, we explore the interface between symbolic and dynamical system computation, with particular regard to dynamical system models of neuronal networks. In doing so, we adhere to a definition of computation as the physical realization of a formal system, where we say that a dynamical system performs a computation if a correspondence can be found between its dynamics on a vectorial space and the formal system’s dynamics on a symbolic space. Guided by this definition, we characterize computation in a range of neuronal network models. We first present a constructive mapping between a range of formal systems and Recurrent Neural Networks (RNNs), through the introduction of a Versatile Shift and a modular network architecture supporting its real-time simulation. We then move on to more detailed models of neural dynamics, characterizing the computation performed by networks of delay-pulse-coupled oscillators supporting the emergence of heteroclinic dynamics. We show that a correspondence can be found between these networks and Finite-State Transducers, and use the derived abstraction to investigate how noise affects computation in this class of systems, unveiling a surprising facilitatory effect on information transmission. Finally, we present a new dynamical framework for computation in neuronal networks based on the slow-fast dynamics paradigm, and discuss the consequences of our results for future work, specifically for what concerns the fields of interactive computation and Artificial Intelligence.

Resumo: Com a evolução dos sistemas de computação simbólica ampliou-se a capacidade de modelagem e análise de problemas provenientes de equações diferenciais. Propõe-se a resolução da equação da condução de calor em regimes permanente e transiente para uma geometria cilíndrica com condições de contorno convectivas de forma analítica e numérica utilizando o software de computação simbólica Maple. Para este propósito serão empregados para a resolução analítica, o método de separação de variáveis e para a resolução numérica, o método das diferenças finitas com o esquema Crank- Nicolson e explícito. Os resultados obtidos das resoluções analíticas e numéricas, para algumas situações avaliadas são comparadas. As vantagens computacionais da utilização do software Maple são apresentadas. / Abstract: The evolution of symbolic computation systems enlarges the capacity of modeling and analysis of problems by differential equations. The aim is the resolution of the conduction heat equation in unsteady and steady state for the cylindrical geometry with convective boundary conditions with analytical and numerical solutions using the Maple software. To this results will be used the separated variables method and finite differences to numerical solutions with Crank-Nicolson and explicit schemes. The results obtained for numerical and analytical solutions for some situations it will available and compared. The computational advantages of the Maple software are showed too. / Orientador: Luiz Roberto Carrocci / Coorientador: Marcio Abud Marcelino / Banca: Petronio Masanobu Tanisho / Banca: Rubens Alves Dias / Banca: Carlos Alberto Chaves / Banca: José Rui Camargo / Doutor

Les nombres p-adiques sont un analogue des nombres réels plus proche de l’arithmétique. L’avènement ces dernières décennies de la géométrie arithmétique a engendré la création de nombreux algorithmes utilisant ces nombres. Ces derniers ne peuvent être de manière générale manipulés qu’à précision finie. Nous proposons une méthode, dite de précision différentielle, pour étudier ces problèmes de précision. Elle permet de se ramener à un problème au premier ordre. Nous nous intéressons aussi à la question de savoir quelles bases de Gröbner peuvent être calculées sur les p-adiques. / P-Adic numbers are a field in arithmetic analoguous to the real numbers. The advent during the last few decades of arithmetic geometry has yielded many algorithms using those numbers. Such numbers can only by handled with finite precision. We design a method, that we call differential precision, to study the behaviour of the precision in a p-adic context. It reduces the study to a first-order problem. We also study the question of which Gröbner bases can be computed over a p-adic number field.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23324号 / 情博第760号 / 新制||情||130(附属図書館) / 京都大学大学院情報学研究科システム科学専攻 / (主査)教授 大塚 敏之, 教授 石井 信, 教授 太田 快人 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Cette thèse traite de problèmes d'intégration symbolique en calcul formel. L'objectif principal est de mettre au point des algorithmes permettant de calculer rapidement des fonctions qui sont présentées sous la forme d'intégrales de contour dépendant d'un paramètre.On commence par aborder le problème du calcul de l'intégrale d'une fraction rationnelle bivariée par rapport à l'une de ses variables. Le résultat est alors une fonction algébrique qui s'exprime comme une somme de résidus de l'intégrande. On met au point deux algorithmes qui calculent efficacement un polynôme annulateur pour chacun des résidus, et ensuite pour la somme, ce qui donne accès à un polynôme annulateur pour l'intégrale elle-même.Ces algorithmes s'appliquent presque directement au calcul d'un polynôme annulateur pour la diagonale d'une fraction rationnelle bivariée, c'est-à-dire la série univariée obtenue à partir du développement en série d'une fraction rationnelle bivariée en ne gardant que les coefficients diagonaux. En effet, ces diagonales peuvent s'écrire comme des intégrales de fractions rationnelles. Dans une autre application, on donne un nouvel algorithme pour le développement des séries génératrices de plusieurs familles de marches unidimensionnelles sur les entiers. Il repose sur une analyse fine des tailles des équations algébriques et différentielles satisfaites par ces séries.Dans un second temps, on s'intéresse au calcul de l'intégrale d'un terme mixte hypergéométrique et hyperexponentiel. Cette fois-ci le résultat est une suite polynomialement récursive. On élabore une méthode pour mettre sous forme normale les divers décalages d'un terme donné. Ceci permet d'appliquer la méthode du télescopage créatif par réductions pour calculer efficacement une récurrence à coefficients polynomiaux satisfaite par l'intégrale. / In this thesis, we provide solutions to some symbolic integration problems in computer algebra. The main objective is to effectively and efficiently compute functions that appear as contour integrals depending on one parameter.First, we consider the computation of the integral of a bivariate rational function with regard to one of the variables. The result is then an algebraic function that can be expressed as a sum of residues of the integrand. We design two algorithms that efficiently compute an annihilating polynomial for each residue, and then for their sum, which yields an annihilating polynomial for the integral itself.These algorithms apply almost directly to the computation of an annihilating polynomial for the diagonal of a rational function, that is, the univariate power series obtained from the expansion of a bivariate rational function by only keeping the diagonal coefficients. Indeed, these diagonals can be written as integrals of rational functions. In another application, we give a new algorithm for the Taylor expansion of the generating functions for several families of unidimensional lattice walks. It relies on a fine analysis of the sizes of the algebraic and differential equations satisfied by these generating functions.Secondly, we consider integrals of mixed hypergeometric and hyperexponential terms. In this case, the result is a polynomially recursive sequence. We devise a method to rewrite the various shifts of a given term under a normal form. This allows us to apply the method of reduction-based creative telescoping in order to efficiently compute a recurrence with polynomial coefficients for the integral.

No description available.