Mathématiques discrètes : Suites récurrentes

Math´ematiques
discr`etes :
Suites r´ecurrentes
D´efinitions
R´ecurrence
lin´eaire
Math´ematiques discr`etes :´Equation de
partition
Suites r´ecurrentes
Remarques
Licence — Universit´e Lille 1
Pour toutes remarques : Alexandre.Sedoglavic@univ-lille1.fr
Semestre 3 — 2010-2011
V0 (09-01-2009)Math´ematiques Relations et suites r´ecurrentesdiscr`etes :
Suites r´ecurrentes
D´efinitions Une suite est un ensemble E d’´el´ements index´es par les
R´ecurrence entiers naturels. Elle peut ˆetre assimil´ee `a une application
lin´eaire
deN dans E.
´Equation de
partition
Les relations de r´ecurrence sont des r`egles de d´efinition de
Remarques
suites d’´el´ements : chaque ´el´ement ´etant d´efini en fonction
des pr´ec´edents.
Ces relations interviennent souvent dans l’estimation de la
complexit´e de r´esolution de probl`emes se ramenant `a celle de
cas de taille plus petite — du type diviser pour r´egner
comme les strat´egies `a base de dichotomie.
Ce cours traitera principalement des relations de r´ecurrence
lin´eaires.
V19 (09-01-2009)Math´ematiques Classification des relations de r´ecurrencediscr`etes :
Suites r´ecurrentes
D´efinitions
NotationR´ecurrence
lin´eaire Classiquement, on note une suite (u ) . Ainsi, unen n∈N
´Equation de
relation f de r´ecurrence se pr´esente sous la forme :partition
Remarques
u = f(u , . . . ,u ).n n−1 n−k
Les relations de r´ecurrence peuvent se classer suivant 3
crit`eres :
I les propri´et´es de la fonction f (lin´earit´e, etc).
I l’ordre k de la ...