Exercices d'intro à l'algorithmique
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:
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.
