Discussion :

[wiseowl4]

Bonjour,

J'ai 2 exercices à résoudre de manière rigoureuse, et pour lesquels je ne vois pas trop comment répondre. Voici les énoncés:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Exercice 1: comportement asymptotique des polynômes
Soit le polynôme p(n) = somme de i = 1...d (ai * n^i)
avec ai > 0 et de degré d.

Soit k une constante.

Utiliser les définitions des notations asymptotiques pour démontrer les propriétés suivantes:

1. Si k >= d, alors p(n) = O(n^k)
2. Si k <= d, alors p(n) = Ω(n^k)
3. Si k  = d, alors p(n) = Θ(n^k)

Pour info, O, Ω et Θ correspondent respectivement aux majorant, minorant et encadrement.

Exercice 2: Croissances asymptotiques relatives
Indiquer, pour chaque paire d'expression (A, B), si A est en O, Ω ou Θ de B. On suppose que k >= 1 et c > 1.

Par exemple, pour la paire (log(n!), log(n^n)), la première expression est en Ω de la seconde.

1. (n^k, c^n)
2. (2^n, 2^(n/2))

Pour l'exo 1, je sais qu'un polynôme p(n) de dégré d revient "asymptotiquement" à son terme de plus haut degré, soit (ad * n^d). Une fois cela montré, le reste découle facilement. Mais comment dire de manière rigoureuse qu'un polynôme "revient asymptotiquement à son terme de plus haut degré" ? Comment on justifie cette affirmation ?

Pour l'exo 2, je peux déjà dire la réponse de la paire 1. La réponse est "n^k est en Ω de c^n", puisque A est un minorant de B. Mais le problème se pose pour la paire 2. A est-elle "en O" ou "en Θ" de B ?

Je vous remercie énormément pour toute aide que vous pourriez m'apporter.

Amicalement,
W.

[pseudocode]

Pour l'exo 1, je sais qu'un polynôme p(n) de dégré d revient "asymptotiquement" à son terme de plus haut degré, soit (ad * n^d). Une fois cela montré, le reste découle facilement. Mais comment dire de manière rigoureuse qu'un polynôme "revient asymptotiquement à son terme de plus haut degré" ? Comment on justifie cette affirmation ?

En repartant de la définition de f=Θ(g).

f=Θ(g) => 0< lim|f/g| < +oo

Donc, il faut calculer la limite de |p(n)/n^d| et montrer que cette limite existe et n'est ni zero, ni infinie.

Pour l'exo 2, je peux déjà dire la réponse de la paire 1. La réponse est "n^k est en Ω de c^n", puisque A est un minorant de B. Mais le problème se pose pour la paire 2. A est-elle "en O" ou "en Θ" de B ?

Meme chose qu'au dessus. Repartir des définitions et calculer la limite de |A/B|