TD d’algorithmique avanc´ee
Corrig´e du TD 2 : r´ecursivit´e
Jean-Michel Dischler et Fr´ed´eric Vivien
Suite de Fibonacci
La suite de Fibonacci est d´efinie comme suit :
Fib(n) =
1
1
Fib(n − 1) + Fib(n − 2)
si n = 0
si n = 1
sinon.
1. ´Ecrivez un algorithme r´ecursif calculant Fib(n).
Fibonacci(n)
si n = 0 ou n = 1 alors renvoyer 1
sinon renvoyer Fibonacci(n − 1) + Fibonacci(n − 2)
2. Montrez que la complexit´e (en nombre d’additions) de cet algorithme est en Ω(2 n
2 ).
On proc`ede par r´ecurrence. On veut montrer qu’il existe une constante c strictement positive telle que
T (n) ≥ c.2 n
2 , pour des valeurs de n sup´erieures a une certaine borne n0 (a d´eterminer). Supposons le
r´esultat d´emontr´e jusqu’au rang n − 1. Alors :
T (n) = T (n − 1) + T (n − 2) + 1 ≥ c.2
n−1
2 + c2
n−2
2 + 1 ≥ c.2
n−2
2 + c.2
n−2
2 + 1 ≥ 2 × c.2
n−2
2 = c.2
n
2
Il nous reste juste `a montrer que cette ´equation est vraie « au d´epart ». Nous ne pouvons bien
´evidemment pas partir des cas n = 0 et n = 1, puisque pour ces valeurs T (n) = 0. Nous partons
donc des cas n = 2 et n = 3 (la r´ecurrence n´ecessite deux valeurs de d´epart) :
– Cas n = 2 : Fibonacci(2) = Fibonacci(1) + Fibonacci(0), et T (2) = 1. Pour que la propri´et´e
d´esir´ee soit vraie, c doit donc v´erifier :
1 ≥ c.2
2
2 = 2c ⇔ c ≤ 1
2
– Cas n = 3 : Fibonacci(3) = Fibonacci(2) + Fibonacci(1), et T (3) = 2. Pour que la propri´et´e
d´esir´ee soit vraie, c doit donc v´erifier :
Donc si c = 1
Advertisement
2 , pour n ≥ 2, on a T (n) ≥ c2 n
2 ≥ c.2
√
√
3
2 = 2
2c ⇔ c ≤
2
2
2 et donc T (n) = Ω(2 n
2 ).
3. ´Ecrire un algorithme r´ecursif qui calcule, pour n > 0, le couple (Fibonacci(n), Fibonacci(n − 1)).
Fib-Paire(n)
si n = 1 alors renvoyer (1, 1)
sinon (x, y) = Fib-Paire(n − 1)
renvoyer (x + y, x)
4. Utilisez l’algorithme pr´ec´edent pour ´ecrire un nouvel algorithme calculant Fibonacci(n).
1
Fibonacci(n)
si n = 0 alors renvoyer 1
sinon (x, y) = Fib-Paire(n)
renvoyer x
5. Qu’elle est la complexit´e (en nombre d’additions) de cet algorithme ?
La complexit´e de l’algorithme Fib-Paire, en nombre d’additions, est donn´ee par la r´ecurrence T (n) =
1 + T (n − 1). On a donc T (n) = n − 1 pour Fib-Paire, et par extension pour la nouvelle version de
Fibonacci.
Op´erations ensemblistes
Dans cette partie on consid`ere des ensembles repr´esent´es par des tableaux, certains ensembles seront tri´es
et d’autres pas. Toutes les solutions propos´ees doivent ˆetre r´ecursives.
1. Nous voulons un algorithme Appartenance(A, x) qui recherche si un ´el´ement x appartient `a l’en-
semble A. Si x appartient effectivement `a A, l’algorithme renverra Vrai, et Faux sinon.
(a) Cas des ensembles non tri´es :
i. ´Ecrivez un tel algorithme.
Recherche(A, rang, x)
si rang > longueur (A) alors renvoyer Faux
si A[rang] = x alors renvoyer Vrai
sinon renvoyer Recherche(A, rang + 1, x)
L’appel initial de l’algorithme est alors Recherche(A, 1, x).
ii. Quelle est sa complexit´e en nombre de comparaisons ?
Dans le pire cas, l’´el´ement n’appartient pas `a l’ensemble et tout le tableau est parcouru. La
complexit´e au pire est donc en Θ(n), o`u n est la longueur du tableau (et donc la taille de
l’ensemble).
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
Recherche(A, rang, x)
si rang > longueur (A) ou A[rang] > x
alors renvoyer Faux
sinon si A[rang] = x
alors renvoyer Vrai
Advertisement
sinon renvoyer Recherche(A, rang + 1, x)
L’appel initial de l’algorithme est alors Recherche(A, 1, x).
ii. Quelle est sa complexit´e en nombre de comparaisons ?
Le pire cas est aussi en Θ(n) : il intervient quand l’´el´ement recherch´e n’appartient pas `a
l’ensemble mais est plus grand que tous les ´el´ements de l’ensemble.
iii. Utilisez une recherche dichotomique pour am´eliorer votre algorithme.
Recherche(A, x, inf, sup)
inf +sup
milieu ←
2
si A[milieu] = x
(cid:106)
(cid:107)
alors renvoyer Vrai
sinon si A[milieu] > x alors renvoyer Recherche(A, x, inf, milieu - 1)
sinon renvoyer Recherche(A, x, milieu + 1, sup)
2
iv. Quelle est la complexit´e de votre nouvel algorithme ?
Posons n = sup −inf +1 le nombre d’´el´ements dans la partie du tableau `a ´etudier. Consid´erons
la taille du tableau lors de l’´eventuel appel r´ecursif. Nous avons deux cas `a consid´erer :
– L’appel effectu´e est : Recherche(A, x, inf, milieu - 1). Le nombre d’´el´ements concern´es
(cid:107) =
– L’appel effectu´e est : Recherche(A, x, milieu + 1, sup). Le nombre d’´el´ements concern´es
est alors : milieu − 1 − inf + 1 = (cid:106)
sup−inf
2
n−1
2 (cid:5)
≤ n
2 .
(cid:4)
est alors : sup − (milieu + 1) + 1 = (cid:108)
sup−inf
2
(cid:109) =
n−1
2 (cid:7)
(cid:6)
≤ n
2 .
On passe donc d’un ensemble de taille n `a un ensemble de taille au plus n
2 × T ( n
cons´equent : T (n) ≤ 2 × log2(n)T (
2 . D’o`u T (n) ≤
2 ) (la fonction T (n) ´etant croissante, on peut se permettre l’approximation). Par
2log2 n ) et T (n) = O(log2 n).
n
2. Nous voulons maintenant un algorithme Union(A, B) qui nous renvoie l’union des deux ensembles qui
lui sont pass´es en argument.
Advertisement
(a) Cas des ensembles non tri´es :
i. ´Ecrivez un tel algorithme.
Union(A, B, rang, C)
si Recherche(A, B[rang]) = Faux
alors longueur(C) ← longueur(C) + 1
C[longueur (C)] ← B[rang]
Union(A, B, rang + 1, C)
L’appel initial est alors Union(A, B, 1, C) o`u C est un tableau de taille longueur (A) +
longueur (B), et dont les longueur (A) premi`eres cases contiennent les ´el´ements de A.
ii. Quelle est sa complexit´e ?
La recopie de A dans C est de coˆut longueur(A).
L’algorithme Union est appel´e longueur (B) fois, chacun de ces appels effectuant un appel `a
Recherche sur A, dont le coˆut au pire est en longueur(A). La complexit´e au pire de Union
est donc en Θ(longueur (A) × longueur (B)) ou Θ(nm), n et m d´enotant la taille des deux
tableaux. Ce pire cas apparaˆıt quand les tableaux A et B sont disjoints.
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
Union(A, a, B, b, C)
si a > longueur (A) et b > longueur (B) alors renvoyer C
si b > longueur (B) ou B[b] > A[a]
alors longueur (C) ← longueur (C) + 1
C[longueur (C)] ← A[a]
Union(A, a + 1, B, b, C)
sinon longueur (C) ← longueur (C) + 1
C[longueur (C)] ← B[b]
si a ≤ longueur (A) et A[a] = B[b] alors Union(A, a + 1, B, b + 1, C)
sinon Union(A, a, B, b + 1, C)
L’appel initial est Union(A, 1, B, 1, C).
ii. Quelle est sa complexit´e ?
La complexit´e de cet algorithme est au pire en Θ(longueur (A) + longueur (B)) ou Θ(n + m) :
a chaque appel on d´ecr´emente au moins de un l’ensemble des valeurs a consid´erer.
3. Nous voulons maintenant un algorithme Intersection(A, B) qui nous renvoie l’intersection des deux
ensembles qui lui sont pass´es en argument.
(a) Cas des ensembles non tri´es :
i. ´Ecrivez un tel algorithme.
3
Intersection(A, B, rang, C)
si Recherche(A, B[rang]) = Vrai
alors longueur(C) ← longueur(C) + 1
C[longueur (C)] ← B[rang]
Intersection(A, B, rang + 1, C)
L’appel initial est alors Intersection(A, B, 1, C) o`u C est un nouveau tableau, de taille
min(longueur (A), longueur (B)), et ne contenant initialement aucun ´el´ement (longueur (C) =
0).
ii. Quelle est sa complexit´e ?
L’algorithme Intersection est appel´e longueur (B) fois, chacun de ces appels effectuant un
appel `a Recherche sur A, dont le coˆut au pire est en longueur(A). La complexit´e au pire
de Intersection est donc en Θ(longueur (A) × longueur (B)) ou Θ(nm), n et m d´enotant la
taille des deux tableaux. Ce pire cas apparaˆıt quand les tableaux A et B sont disjoints.
Advertisement
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
Intersection(A, a, B, b, C)
si a > longueur (A) ou b > longueur (B) alors renvoyer C
si A[a] = B[b] alors longueur (C) ← longueur (C) + 1
C[longueur (C)] ← A[a]
renvoyer Intersection(A, a + 1, B, b + 1, C)
sinon si B[b] > A[a] alors renvoyer Intersection(A, a + 1, B, b, C)
sinon renvoyer Intersection(A, a, B, b + 1, C)
L’appel initial est Intersection(A, 1, B, 1, C, 0).
ii. Quelle est sa complexit´e ?
La complexit´e de cet algorithme est au pire en Θ(longueur (A) + longueur (B)) ou Θ(n + m) :
a chaque appel on d´ecr´emente au moins de un l’ensemble des valeurs a consid´erer.
4. Nous voulons maintenant un algorithme Diff´erence(A, B) qui nous renvoie la diff´erence des deux
ensembles qui lui sont pass´es en argument (La diff´erence de A et de B, not´ee A \ B est l’ensemble des
´el´ements de A n’appartenant pas `a B).
(a) Cas des ensembles non tri´es :
i. ´Ecrivez un tel algorithme.
Diff´erence(A, rang, B, C)
si Recherche(B, A[rang]) = Faux
alors longueur(C) ← longueur(C) + 1
C[longueur (C)] ← A[rang]
Diff´erence(A, rang + 1, B, C)
L’appel initial est alors Diff´erence(A, 1, B, C) o`u C est un tableau de taille longueur (A),
ne contenant initialement aucun ´el´ement (longueur (C) = 0).
ii. Quelle est sa complexit´e ?
L’algorithme Diff´erence est appel´e longueur (A) fois, chacun de ces appels effectuant un
appel `a Recherche sur B, dont le coˆut au pire est en longueur(B). La complexit´e au pire
de Diff´erence est donc en Θ(longueur (A) × longueur (B)) ou Θ(nm), n et m d´enotant la
taille des deux tableaux. Ce pire cas apparaˆıt quand les tableaux A et B sont disjoints.
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
4
Diff´erence(A, a, B, b, C)
si a > longueur (A) alors renvoyer C
si A[a] = B[b] alors renvoyer Diff´erence(A, a + 1, B, b + 1, C)
sinon si A[a] < B[b] alors longueur (C) ← longueur (C) + 1
C[longueur (C)] ← A[a]
renvoyer Diff´erence(A, a + 1, B, b, C)
sinon renvoyer Diff´erence(A, a, B, b + 1, C)
L’appel initial est Diff´erence(A, 1, B, 1, C, 0).
ii. Quelle est sa complexit´e ?
La complexit´e de cet algorithme est au pire en Θ(longueur (A) + longueur (B)) ou Θ(n + m) :
a chaque appel on d´ecr´emente au moins de un l’ensemble des valeurs a consid´erer.
5