Diviser pour régner Algèbre et analyse : Cours donné aux Journées ALÉA 2016

Abstract : The divide-and-conquer recurrences, which frequently relate the values of a sequence at an integer and at one half of this integer, have the divide-and-conquer strategy, commonly used in algorithmic, as its origin. However, they also come to light in combinatorics of words or in combinatorics of integer partitions. Even, they are related to algebraic series with coefficients in a finite field, or in a surprising way to some optimization problems. Their exotic appearance and the various shapes they can take make them disconcerting. This elementary introduction is made from two parts. The first one is algebraic and its aim is to provide a definition of these recurrences through their various shapes and to show that all these shapes have the same expressiveness. The second part deals with the asymptotic behavior of these sequences, first by elementary methods, next by linear algebra. The text is decorated with numerous examples and exercises.
Document type :
Lectures
Complete list of metadatas

Cited literature [61 references]  Display  Hide  Download

https://hal.inria.fr/cel-01388741
Contributor : Philippe Dumas <>
Submitted on : Thursday, October 27, 2016 - 2:54:00 PM
Last modification on : Monday, September 23, 2019 - 2:16:03 PM

Identifiers

  • HAL Id : cel-01388741, version 1

Collections

Citation

Philippe Dumas. Diviser pour régner Algèbre et analyse : Cours donné aux Journées ALÉA 2016. Master. Centre International de Rencontres Mathématiques, Marseille, France. 2016, pp.80. ⟨cel-01388741⟩

Share

Metrics

Record views

323

Files downloads

337