


Relations de Récurrence en Algorithmes |
A- Récurrences linéaires homogènes à coefficients constantsUne formule de récurrence est dite linéaire homogène a coefficients constants si a0 tn + a1 tn−1 + . . . + ai tn−i + . . . + ak tn−k = 0. Exemple 1 : La suite de Fibonnacci se définit comme suit : Celle-ci est une récurrence linéaire homogène a coefficients constants. Pour le voir, Formule connue sous le nom de formule de de Moivre. Exemple 2 : Réécrivons la récurrence sous la forme : tn − 5tn−1 + 8tn−2 − 4tn−3 = 0 Ses racines sont donc r1 = 1 de multiplicité m1 = 1 et r2 = 2 de multiplicité m2 = 2.
B- Récurrences linéaires non homogènes à coefficients constantsConsidérons l'équation suivante :
Voici Une serie d'exercices PDF Relations de Récurrence Algorithmes et Complexité Partie 1 : Relations de récurrence Partie 2 : Algorithmes et complexité |