Mathématiques discrètes : Suites récurrentes
9 pages
Français

Mathématiques discrètes : Suites récurrentes

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

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 ...

Sujets

Informations

Publié par
Nombre de lectures 137
Langue Français

Exrait

Math´ematiques discre`tes: Suitesre´currentes
De´nitions Re´currence lin´eaire ´ Equation de partition Remarques
V0 (09-01-2009)
Math´ematiquesdiscre`tes: Suitesre´currentes
LicenceUniversite´Lille1 Pour toutes remarques : Alexandre.Sedoglavic@univ-lille1.fr
Semestre 3 — 2010-2011
Math´ematiques discr`etes: Suitesre´currentes
D´enitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Relationsetsuitesre´currentes
Unesuiteest un ensembleEemden´el´dex´tsinlrseseap entiersnaturels.Ellepeuteˆtreassimile´e`auneapplication deNdansE.
Lesnsior´deurecncreerleta suitesd´el´ements:chaque despre´c´edents.
sontdesre`glesdede´nitionde e´le´ment´etantd´enienfonction
Ces relations interviennent souvent dans l’estimation de la complexite´der´esolutiondeprobl`emesseramenant`acellede cas de taille plus petite — du typeividserpourr´egner commelesstrat´egiesa`basededichotomie.
Cecourstraiteraprincipalementdesrelationsdere´currence line´aires.
Math´ematiques discr`etes: Suitesre´currentes
De´nitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Classicationdesrelationsder´ecurrence
Notation Classiquement, on note une suite(un)nN. Ainsi, une relationfder´ecurrencesepre´sentesouslaforme:
un=f(un1, . . . ,unk).
Lesrelationsder´ecurrencepeuventseclassersuivant3 crit`eres: lespropri´ete´sdelafonctionftc).i´ne,´eear(ilt I l’ordrek.ceenucrrrae´dle I abscenceounondeparame`tredanslafonctionf I (relationhomoge`neounon).
Mathe´matiques discre`tes: Suitesre´currentes
De´nitions Re´currence lin´eaire ´ Equation de partition Remarques
V19 (09-01-2009)
Exemples
La suite (un)nNdes puissances deu0ed´epnilaarets relationder´ecurrencelin´eaire,homoge`ne d’ordre 1 :un=u0un1. La suite (un)nNnieparlaests´decaotirlesedfserbmon relationder´ecurrencenonlin´eaire,nonhomoge`ne d’ordre 1 :un=nun1. m s (C’ordrem Les suiten)nNdes coefficients binomiaux d sontd´eniesparlesrelationsder´ecurrenceline´aires m m m1 homoge`nesC=C+C. n n1n1
Lalge`brelin´eairenouspermetder´esoudretoutesles re´currencesline´aires.Nousneconsid´eronsdanslasuiteque descasparticuliersdelathe´orieg´en´erale.
Mathe´matiques discre`tes: Suitesre´currentes
D´enitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Casline´airedordre1 constants
`acoecients
Lecashomog`eneestleplussimple:
un=cun1
n On obtient une forme closeun=c u0. Lecasinhomoge`necorrespond`alarelation:
un=cun1+r(n)
On obtient une forme close : n X n ni un=c u0+r(n)c, i=0
(si le second membrer(n) se simplifie).
Mathe´matiques discr`etes: Suitesre´currentes
De´nitions R´ecurrence lin´eaire ´ Equation de partition Remarques
V19 (09-01-2009)
Casline´airehomog`enea`coecients constants ´ Etantdonne´eunerelationlin´eairehomoge`nedordrek:
un=c1un1+∙ ∙ ∙+ckunk.
et sonnˆomecaract´erisuqiteopyl P k k ki associ´ep(x) =xcix. i=1 Proposition L’ensemble des suites solutions de (1) forment un espace vectoriel V de dimension k. Si p(x)a k racines distinctes{r1, . . . ,rk}, alors les k n suites(r)nNpour i= 1. . .k forment une base de V . i Si p(x)a p racines distinctes{r1, . . . ,rp}de j n multiplicite´{m1, . . . ,mp}, alors les k suites(n r)nN i pour i= 1. . .p et j= 1. . .mi.forment une base de V
(1)
Mathe´matiques discre`tes: Suitesre´currentes
D´enitions Re´currence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Casline´airenonhomoge`nea`coecients constants
´ Etantdonn´eeunerelationlin´eairehomog`enedordrek:
un=c1un1+∙ ∙ ∙+ckunk+r(n).
Proposition L’ensemble des solutions de (2) est un espace affine de dimensionkdontlespacevectorielassocie´estlensemble dessolutionsdele´quationhomoge`necorrespondante.
(2)
Enconse´quence,ilfautd´ej`ar´esoudrele´quationhomoge`ne ettrouverunesolutionparticuli`erede(2).
Mathe´matiques discr`etes: Suitesr´ecurrentes
D´enitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
D´enition Unerelationder´ecurrencedelaformeun=f(un/a)avec a constantestunee´quationdepartition.Elled´enieunesuite re´currente(u)idme.reeueinanu`qi n n∈{a|iN}
Le´tudedel´equationdepartitionun=cun/a+d(n) se k+1 ram`ene`acelledelare´currencevk+1=cvk+d(a) par le changement de variablevn=u. k a
Mathe´matiques discre`tes: Suitesr´ecurrentes
De´nitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Ilnyapasdeme´thodeg´ene´ralepourtraiterlesr´ecurrences lin´eaires´acoecientsvariables. Cetteremarqueestvalablepourlesr´ecurrencesnonline´aires