نبذة مختصرة : Master ; 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. ; Les récurrences diviser pour régner, qui fréquemment relient les valeurs d’une suite en un entier et sa moitié, tirent leur nom de la stratégie diviser pour régner communément employée en algorithmique. Mais elles apparaissent aussi dans des problèmes de dénombrement liés à la combinatoire des mots ou à la combinatoire des partitions, ou encore en lien avec les séries algébriques à coefficients dans un corps fini, voire de manière inattendue dans des questions d’optimisation. Leur aspect exotique et les différentes formes qu’elles peuvent prendre leurs confèrent un aspect déroutant.Cette introduction élémentaire au domaine comporte deux parties. La première est algébrique et vise à donner une définition de ces récurrences à travers leurs différentes formes et à montrer que ces formes ont toutes la même capacité d’expression. La seconde partie traite de l'asymptotique de ces suites d'abord par des méthodes élémentaires, puis par une méthode d'algèbre linéaire. Le texte est décoré de nombreux exemples et d'exercices.
Processing Request
No Comments.