Corrigé du questionnaire - Centre d`histoire de la Résistance et de

Algorithmique DU1 MI2E
Année 2012-2013
Corrigé TD 1
Exercice 1
Montrer que les assertions suivantes sont exactes :
(a) n(n − 1) est en O(n2 ) :
Définition : ∃c1 ∈ N∗ , n0 ∈ N∗ tels que ∀n ≥ n0 on a n(n − 1) ≤ c1 n2 .
Posons c1 = 1 et remarquons que n(n − 1) ≤ n2 , ∀ n ≥ 1 = n0 .
(b) max(n3 , 10n2 ) est en O(n3 ) :
Définition : ∃c1 ∈ N∗ , n0 ∈ N∗ tels que ∀n ≥ n0 on a max(n3 , 10n2 ) ≤ c1 n3 .
Posons c1 = 1 et remarquons que max(n3 , 10n2 ) = n3 , ∀n ≥ 10 = n0 .
(c) Si p(x) est un polynôme quelconque de degré k, à coefficients entiers positifs, alors p(n)
est en Θ(nk ) :
Définition : ∃c1 , c2 ∈ N∗ , n0 ∈ N∗ tels que
∀n ≥ n0 on a c1 nk ≤ p(n) ≤ c2 nk . P
P
k
Posons c1 = 1 et remarquons que nk ≤ i=0 ai ni , ∀n ≥ 1 ; de plus posons c2 = ki=0 ai
P
P
et remarquons que ki=0 ai ni ≤ ki=0 ai nk , ∀n ≥ 1 = n0 .
Exercice 2
Soient f (x) et g(x) des fonctions positives asymptotiquement. En s’aidant de la définition de
base de la notion Θ, montrer que : f (n) + g(n) = Θ(max(f (n), g(n))).
Définition : ∃c1 , c2 ∈ N∗ , n0 ∈ N∗ tels que ∀n ≥ n0 on a c1 max(f (n), g(n)) ≤ f (n) + g(n) ≤
c2 max(f (n), g(n)).
Posons c1 = 1, c2 = 2 et remarquons que max(f (n), g(n)) ≤ f (n) + g(n) ≤ max(f (n), g(n)),
∀n ≥ n0 , où n0 est tel que f (n), g(n) ≥ 0 pour tout n ≥ n0 (par hypothèse n0 existe).
Exercice 3
Soient f (x) et g(x) des fonctions positives asymptotiquement. On suppose que S(n) ∈ O(f (n))
et T (n) ∈ O(g(n)). Montrer que :
(a) si f (n) ∈ O(g(n)) alors S(n) + T (n) ∈ O(g(n)) :
On sait que ∃c1 ∈ N∗ , n0 ∈ N∗ tels que ∀n ≥ n0 on a f (n) ≤ c1 g(n). A montrer que ∃c2 ∈ N∗ , n1 ∈ N∗ tels que ∀n ≥ n1 on a S(n) + T (n) ≤ c2 g(n). Comme
Corrigé TD 1
Algorithmique
S(n) ∈ O(f (n)), ∃c3 ∈ N∗ , n2 ∈ N∗ tels que ∀n ≥ n2 on a S(n) ≤ c3 f (n). De même
comme T (n) ∈ O(g(n)), ∃c4 ∈ N∗ , n3 ∈ N∗ tels que ∀n ≥ n3 on a T (n) ≤ c4 g(n).
Donc S(n) + T (n) ≤ c3 f (n) + c4 g(n) ≤ c3 c1 g(n) + c4 g(n) = (c3 c1 + c4 )g(n), ∀n ≥
max(n0 , n2 , n3 ). En posant n1 = max(n0 , n2 , n3 ) et c2 = c3 c1 + c4 , on obtient le résulat
voulu.
(b) S(n)T (n) ∈ O(f (n)g(n)) :
A montrer que ∃c2 ∈ N∗ , n1 ∈ N∗ tels que ∀n ≥ n1 on a S(n) + T (n) ≤ c2 g(n). Comme
S(n) ∈ O(f (n)), ∃c3 ∈ N∗ , n2 ∈ N∗ tels que ∀n ≥ n2 on a S(n) ≤ c3 f (n). De même
comme T (n) ∈ O(g(n)), ∃c4 ∈ N∗ , n3 ∈ N∗ tels que ∀n ≥ n3 on a T (n) ≤ c4 g(n).
Donc S(n)T (n) ≤ c3 f (n)c4 g(n) ≤ c3 c4 f (n)g(n), ∀n ≥ max(n2 , n3 ). En posant n1 =
max(n2 , n3 ) et c2 = c3 c4 , on obtient le résulat voulu.
Exercice 4
Peut-on écrire :
(a) 2n+1 ∈ O(2n ) ?
Oui, car ∃c1 ∈ N∗ , n0 ∈ N∗ tels que ∀n ≥ n0 on a 2n+1 ≤ c1 2n . Il suffit de poser c1 = 2
et n0 = 1.
(b) 22n ∈ O(2n ) ?
Non, car pour n arbitrairement grand, 6 ∃c1 ∈ N∗ tel que 22n ≤ c2n . Autrement dit : si
c’était vrai, alors ∃c1 ∈ N∗ , n0 ∈ N∗ tels que ∀n ≥ n0 on a 22n ≤ c1 2n . Divisons alors
par 2n : ∀n ≥ n0 on a 2n ≤ c1 , ce qui est impossible car c1 est une constante !
Exercice 5
Soient f (x) et g(x) des fonctions asymptotiquement strictement positives, prouver ou démentir
les affirmations suivantes :
(a) f (n) = O(g(n)) implique que g(n) = O(f (n)) :
Faux car n2 ∈ O(n3 ) mais n3 6∈ O(n2 ).
(b) f (n) + g(n) = Θ(min(f (n), g(n))) :
Faux car n2 + n3 6∈ O(n2 ).
DU1 MI2E - Année 2012-2013
2
Corrigé TD 1
Algorithmique
(c) f (n) = O(g(n)) implique que 2f (n) = O(2g(n) ) :
Faux car 2n ∈ O(n), mais 22n 6∈ O(2n ).
Exercice 6
En utilisant la notation O, donner, en fonction de n, la complexité dans le pire des cas des
fonctions suivantes :
(a) Fonction prodmat :
pour i = 1 à n faire
pour j = 1 à n faire
C[i, j] ← 0 ;
pour k = 1 à n faire
C[i, j] ← C[i, j] + A[i, k] ∗ B[k, j] ;
fin pour
fin pour
fin pour
Complexité : O(n3 )
(b) Fonction mystere :
pour i = 1 à n − 1 faire
pour j = i + 1 à n faire
pour k = 1 à j faire
opération en O(1) ;
fin pour
fin pour
fin pour
Pour i = 1, on aura 2+3+4+. . .+n opérations en O(1) ; pour i = 2, on aura 3+4+. . .+n
opérations en O(1) ; . . . ; pour i = n − 1, on aura n opérations en
Ainsi on aura au
PO(1).
n−1
total : 1 × 2 + 2 × 3 + . . . + (n − 1) × n opérations en O(1), i.e., i=1 i(i + 1) opérations
P
Pn−1 2 Pn−1
n(n−1)(2n−1)
en O(1). Or n−1
+ n(n−1)
. On obtient donc
i=1 i(i + 1) =
i=1 i +
i=1 i =
6
2
une complexité en O(n3 ).
(c) Fonction oddidonc :
pour i = 1 à n faire
si i impair
pour j = 1 à n faire
x ← x + 1;
fin pour
pour j = 1 à n faire
y ← y + 1;
fin pour
DU1 MI2E - Année 2012-2013
3
Corrigé TD 1
Algorithmique
fin si
fin pour
Complexité : O(n2 )
(d) Fonction recursive :
si n = 0
alors retourner(2)
fin si
sinon retourner(recursive(n − 1) + recursive(n − 1))
La fonction recursive(n) est appelée 1 fois ; recursive(n−1) est appelée 2 fois ; recursive(n−
2) est appelée 4 fois ; . . . ; recursive(1) estPappelée 2n−1 fois et finalement recursive(0)
est appelée 2n fois. On aura donc en tout ni=0 2i = 2n+1 − 1 appels. Comme chacun se
fait en O(1), la complexité est en O(2n ).
(e) Si on remplace l’instruction "(recursive(n − 1) + recursive(n − 1))" par "retourner(2 ∗
recursive(n − 1))", la complexité de la fonction recursive est-elle modifiée ?
Oui, à ce moment chaque fonction recursive(i), pour i = n, . . . , 0 est appelée une seule
fois. On aura donc une complexité en O(n).
Exercice 7
(a) Ecrire un algorithme itératif qui prenne en entrée un entier n et retourne le factoriel de
cet entier et prouver cet algorithme.
Fonction f actoriel :
f act ← 1
pour i = 2 à n faire
f act ← f act ∗ i
fin pour
retourner f act
fin Fonction
Preuve :
(i) Terminaison : Triviale car la boucle est exécutée n − 1 fois et le contenu de la boucle
s’effectue en temps constant.
(ii) Validité : Nous allons montrer qu’à la fin de l’itération i, la variable f act a pour
valeur i!. Pour cela, on effectue un raisonnement par récurrence : pour i = 2, f act2 =
f act1 ∗ 2 = 2!QX ; on suppose la propriété vraie pour i itérations, i.e., on suppose
que f acti = ij=1 j X ; considérons l’itération i + 1 : f acti+1 = f acti ∗ (i + 1)=
DU1 MI2E - Année 2012-2013
4
Corrigé TD 1
Qi
j=1 j
Algorithmique
∗ (i + 1)=
Qi+1
j=1 j
= (i + 1)! X.
(b) Déterminer la complexité de cet algorithme.
Complexité : O(n).
(c) Ecrire un algorithme récursif qui calcule n! puis prouver cet algorithme.
Fonction f actorielbis :
si n ≤ 1
alors retourner 1
sinon
retourner (f actorielbis(n − 1) ∗ n)
fin Fonction
Preuve :
(i) Terminaison : Par récurrence sur n : pour f actorielbis(1) X (fin immédiate) ; supposons f actorielbis(n) se termine et considérons f actorielbis(n + 1) : cette fonction
appelle f actorielbis(n) (qui par hypothèse se termine) et multiplie le résultat par n+1
puis renvoie le résultat final X.
(ii) Validité : Par récurrence : f actorielbis(1)
Q = 1! X ; on suppose la propriété vraie pour
n, i.e., on suppose que f actorielbis(n) = nj=1 j X ; considérons n+1 : f actorielbisn + 1 =
Q
Q
f actorielbis(n) ∗ (n + 1)= nj=1 j ∗ (n + 1)= n+1
j=1 j = (n + 1)! X.
(d) Déterminer la complexité de cet algorithme récursif.
Complexité : O(n).
Exercice 8
Donner une fonction M in qui, étant donné un tableau T de n valeurs entières, retourne la
plus petite de ces valeurs. Donner la complexité, en fonction de n, de cette fonction.
Fonction M in
min ← Tab[1]
pour i = 2 à n faire
si T ab[i] < min alors
min ← T ab[i]
fin si
fin pour
retourner min
DU1 MI2E - Année 2012-2013
5
Corrigé TD 1
Algorithmique
fin Fonction
Complexité : O(n)
DU1 MI2E - Année 2012-2013
6

Download Report