Equation de récurence

par **thotoss** » 20 Nov 2008, 19:48

Bonjour a toutes et a tous !
Voila mon petit probleme, j'ai l'équation de recurence suivante :

T(1)=1
T(n)=3T(n/2) + n²

Je cherche a trouver l'ordre de grandeur asymptotique de T(n), et j'avou que je bloque pas mal ... Si quelqu'un pouvait venir a mon secours, ça serait vraiment gentil !
Merci d'avance

par **ffpower** » 20 Nov 2008, 20:18

T(n/2) c est pas bien défini ca si n/2 n'est pas entier..Tu prend la partie entiere?

par **Luc** » 20 Nov 2008, 20:39

Salut,

Les informaticiens se sortent souvent de cette remarque en disant que T est croissante (c'est une complexité) et qu'il suffit donc de le calculer pour

. On en pense ce qu'on veut ...

Tu obtiens une récurrence du type

, ça doit se résoudre, mais à vue de nez u_n est de l'ordre de 4^n, ce qui ferait T(n) de l'ordre de n^2. (Je peux me tromper)

Luc

par **thotoss** » 20 Nov 2008, 20:48

ok merci beaucoup de m'aider !
donc si on considere que Un est de l'ordre de 4^n, donc T(n) est de l'ordre de n².
Si je pose Uk=T(2^k), comment je peut montrer que Uk vérifie la récurrence
Uk - 7U(k-1) + 12U(k-2) pour k>=2

Et comment la résoudre ? vous avez une piste pour m'aider ?
merci d'avance
Cordialement

par **Luc** » 20 Nov 2008, 20:51

thotoss a écrit:ok merci beaucoup de m'aider !
donc si on considere que Un est de l'ordre de 4^n, donc T(n) est de l'ordre de n².
Si je pose Uk=T(2^k), comment je peut montrer que Uk vérifie la récurrence
Uk - 7U(k-1) + 12U(k-2) pour k>=2

Et comment la résoudre ? vous avez une piste pour m'aider ?
merci d'avance
Cordialement

Je ne comprends pas ta question.

Tu veux montrer que Uk - 7U(k-1) + 12U(k-2) = quelque chose?

Luc

par **fatal_error** » 20 Nov 2008, 23:25

salut,

T(n)=3T(n/2) + n²
avec

,

A partir de la, ya une astuce pour se ramener a une forme simplifiée :

ca nous donne :

Pis la, en utilisant la propriété de récurrénce jusqua k=1 , t'as une série géométrique!

par **thotoss** » 26 Nov 2008, 16:41

bonjour,
je ne vois pas trop le rapport en fait avec le fait que je dois verifier la récurence Uk - 7U(k-1) + 12U(k-2) et le fait de la résoudre ... merci si vous pouvez m'adier !
Cdt

par **yos** » 26 Nov 2008, 17:29

Luc a écrit:Tu obtiens une récurrence du type , ça doit se résoudre,

En effet puisque

, tu as

et du coup l'autre récurrence est immédiate.

Ah non j'ai travaillé avec

, il me manque un +1.

par **yos** » 26 Nov 2008, 17:34

En posant

tu as

.

par **yos** » 26 Nov 2008, 17:35

D'où

.

par **black** » 26 Nov 2008, 19:48

ok la je suis un peu perdu en fait ... l'ordre de grandeur asymptotique dans tout ça c'est quoi et comment on le trouve en fait ? merci beaucoup de m'aider

par **thotoss** » 26 Nov 2008, 23:14

personne pour me venir en aide svp ? ...

par **Luc** » 26 Nov 2008, 23:47

Si, il suffit de lire les posts précédents:

donc

Après, cela dépend si tu veux un équivalent ou un développement asymptotique plus poussé.

, je pense que c'est ce que tu cherchais.

Cordialement,

Luc

par **black** » 27 Nov 2008, 00:00

ah ok merci beaucoup j'avais pas bien compris en fait merci bien !
donc ça c'est T(n) en fonction de n lorsque n=2^k
Je voudrais aussi trouver l'odre de grandeur asymptotique de T(n) sans passer par n=2^k, juste avec l'equation de recurrence de mon premier post ... commetn je peux faire alors ? parsque c'est la aussi que je me mélange ..
merci beaucoup de m'aider je galere un peu la ...

par **black** » 27 Nov 2008, 16:21

re bonjour !
alors voila clairement ce que je cherche maintenant :
j'ai toujous mon equation de recurence suivante (1) :
T(1)=1
T(n)=3T(n/2)+n²

et je voudrais juste trouver l'ordre de grandeur asymptotique de T(n), sans utiliser n=2^k, parcque ça m'est demandé que aprés ... comment je peux faire ?
merci beaucoup de m'aider !
cdt

par **black** » 27 Nov 2008, 20:49

un ptit coup de pouce svp ?...

par **ffpower** » 27 Nov 2008, 21:02

Et bien c est toujours pas tres clair.Par ex T(3)=3T(1.5)+9
T(1.5),c est quoi?

par **black** » 27 Nov 2008, 21:14

Comment ça c'est quoi ? je ne sais pas en fait ... mon énoncé n'est pas trés claire : voila precisement ce qu'il dit :
Soit l'equation de récurence (1) :
T(1)=1
T(n)=3T(n/2)+n²

Trouvez l'ordre de grandeur asymptotique de T(n).

Et je vois pas comment faire ... surtout que le suite de l'exo est encore plus incomprehensible .... :triste:

par **black** » 27 Nov 2008, 22:37

ok donc j'ai reussi a montrer que l'ordre de grandeur de T(n) est n2 . Mais maintenant je bloque sur cette question :

On pose Uk=T(2^k) . Montrez que Uk vérifie la récurence (2) :
Uk - 7U(k-1) + 12U(k-2) pour k>=2
et reolvez l'equation.
Mais je ne trouve pas que c'est une équation !! enfin c'est egale a rien quoi ... je comprend pas ... merci si vous pouvez m'aider !!
cdt

par **Luc** » 28 Nov 2008, 00:38

black a écrit:ok donc j'ai reussi a montrer que l'ordre de grandeur de T(n) est n2 . Mais maintenant je bloque sur cette question :

On pose Uk=T(2^k) . Montrez que Uk vérifie la récurence (2) :
Uk - 7U(k-1) + 12U(k-2) pour k>=2
et reolvez l'equation.
Mais je ne trouve pas que c'est une équation !! enfin c'est egale a rien quoi ... je comprend pas ... merci si vous pouvez m'aider !!
cdt

Bonsoir,

Je ne comprends pas pourquoi tu reviens à cette question. yos t'a déja donné la réponse. Le

que l'on considérait était bien ce

. Pour mémoire, u_n=4^(n+1)- 3^(n+1).
L'équation est vraisemblablement

, qui se résoud facilement en calculant les racines du polynôme caractéristique X^2-7X+12.

Je me demandais un truc: dans quel contexte est posé ton exercice? C'est des maths ou de l'info?
Et question subsidiaire: quelle est la suite de l'exo?

Merci,

Luc

Equation de récurence

equation de récurence

Qui est en ligne