TD d’algorithmique avancée

Corrigé du TD 2 : récursivité
Jean-Michel Dischler et Frédéric Vivien

Suite de Fibonacci
La suite de Fibonacci est définie comme suit :

 1 si n = 0
Fib(n) = 1 si n = 1
Fib(n − 1) + Fib(n − 2) sinon.


1. Écrivez un algorithme récursif calculant Fib(n).

Fibonacci(n)
si n = 0 ou n = 1 alors renvoyer 1
sinon renvoyer Fibonacci(n − 1) + Fibonacci(n − 2)
n
2. Montrez que la complexité (en nombre d’additions) de cet algorithme est en Ω(2 2 ).
On procède par récurrence. On veut montrer qu’il existe une constante c strictement positive telle que
n
T (n) ≥ c.2 2 , pour des valeurs de n supérieures à une certaine borne n0 (à déterminer). Supposons le
résultat démontré jusqu’au rang n − 1. Alors :
n−1 n−2 n−2 n−2 n−2 n
T (n) = T (n − 1) + T (n − 2) + 1 ≥ c.2 2 + c2 2 + 1 ≥ c.2 2 + c.2 2 + 1 ≥ 2 × c.2 2 = c.2 2

Il nous reste juste à montrer que cette équation est vraie « au départ ». Nous ne pouvons bien
évidemment 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écurrence nécessite deux valeurs de départ) :
– Cas n = 2 : Fibonacci(2) = Fibonacci(1) + Fibonacci(0), et T (2) = 1. Pour que la propriété
désirée soit vraie, c doit donc vérifier :
2 1
1 ≥ c.2 2 = 2c ⇔ c≤
2
– Cas n = 3 : Fibonacci(3) = Fibonacci(2) + Fibonacci(1), et T (3) = 2. Pour que la propriété
désirée soit vraie, c doit donc vérifier :
√
3 √ 2
2 ≥ c.2 = 2 2c ⇔ c ≤
2
2
n n
Donc si c = 12 , pour n ≥ 2, on a T (n) ≥ c2 2 et donc T (n) = Ω(2 2 ).
3. Écrire un algorithme récursif 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écédent pour écrire 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é (en nombre d’additions) de cet algorithme ?
La complexité de l’algorithme Fib-Paire, en nombre d’additions, est donnée par la récurrence 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érations ensemblistes
Dans cette partie on considère des ensembles représentés par des tableaux, certains ensembles seront triés
et d’autres pas. Toutes les solutions proposées doivent être récursives.
1. Nous voulons un algorithme Appartenance(A, x) qui recherche si un élément x appartient à l’en-
semble A. Si x appartient effectivement à A, l’algorithme renverra Vrai, et Faux sinon.
(a) Cas des ensembles non triés :
i. Écrivez 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é en nombre de comparaisons ?
Dans le pire cas, l’élément n’appartient pas à l’ensemble et tout le tableau est parcouru. La
complexité au pire est donc en Θ(n), où n est la longueur du tableau (et donc la taille de
l’ensemble).
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez 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
sinon renvoyer Recherche(A, rang + 1, x)
L’appel initial de l’algorithme est alors Recherche(A, 1, x).
ii. Quelle est sa complexité en nombre de comparaisons ?
Le pire cas est aussi en Θ(n) : il intervient quand l’élément recherché n’appartient pas à
l’ensemble mais est plus grand que tous les éléments de l’ensemble.
iii. Utilisez une recherche dichotomique pour améliorer votre algorithme.
Recherche(A, x, inf, sup)
j k
milieu ← inf +sup
2
si A[milieu] = x
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é de votre nouvel algorithme ?
Posons n = sup −inf +1 le nombre d’éléments dans la partie du tableau à étudier. Considérons
la taille du tableau lors de l’éventuel appel récursif. Nous avons deux cas à considérer :
– L’appel effectué est : Recherche(A, j x, inf, k milieu - 1). Le nombre d’éléments concernés
sup−inf
 n−1  n
est alors : milieu − 1 − inf + 1 = 2 = 2 ≤ 2.
– L’appel effectué est : Recherche(A,l x, milieu m +1, sup). Le nombre d’éléments concernés
sup−inf n−1
 n
est alors : sup − (milieu + 1) + 1 = 2 = 2 ≤ 2.
On passe donc d’un ensemble de taille n à un ensemble de taille au plus n2 . D’où T (n) ≤
2 × T ( n2 ) (la fonction T (n) étant croissante, on peut se permettre l’approximation). Par
conséquent : T (n) ≤ 2 × log2 (n)T ( 2logn2 n ) et T (n) = O(log2 n).
2. Nous voulons maintenant un algorithme Union(A, B) qui nous renvoie l’union des deux ensembles qui
lui sont passés en argument.
(a) Cas des ensembles non triés :
i. Écrivez 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ù C est un tableau de taille longueur (A) +
longueur (B), et dont les longueur (A) premières cases contiennent les éléments de A.
ii. Quelle est sa complexité ?
La recopie de A dans C est de coût longueur(A).
L’algorithme Union est appelé longueur (B) fois, chacun de ces appels effectuant un appel à
Recherche sur A, dont le coût au pire est en longueur(A). La complexité au pire de Union
est donc en Θ(longueur (A) × longueur (B)) ou Θ(nm), n et m dénotant la taille des deux
tableaux. Ce pire cas apparaı̂t quand les tableaux A et B sont disjoints.
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez 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é ?
La complexité de cet algorithme est au pire en Θ(longueur (A) + longueur (B)) ou Θ(n + m) :
à chaque appel on décrémente au moins de un l’ensemble des valeurs à considérer.
3. Nous voulons maintenant un algorithme Intersection(A, B) qui nous renvoie l’intersection des deux
ensembles qui lui sont passés en argument.
(a) Cas des ensembles non triés :
i. Écrivez 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ù C est un nouveau tableau, de taille
min(longueur (A), longueur (B)), et ne contenant initialement aucun élément (longueur (C) =
0).
ii. Quelle est sa complexité ?
L’algorithme Intersection est appelé longueur (B) fois, chacun de ces appels effectuant un
appel à Recherche sur A, dont le coût au pire est en longueur(A). La complexité au pire
de Intersection est donc en Θ(longueur (A) × longueur (B)) ou Θ(nm), n et m dénotant la
taille des deux tableaux. Ce pire cas apparaı̂t quand les tableaux A et B sont disjoints.
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez 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é ?
La complexité de cet algorithme est au pire en Θ(longueur (A) + longueur (B)) ou Θ(n + m) :
à chaque appel on décrémente au moins de un l’ensemble des valeurs à considérer.
4. Nous voulons maintenant un algorithme Différence(A, B) qui nous renvoie la différence des deux
ensembles qui lui sont passés en argument (La différence de A et de B, notée A \ B est l’ensemble des
éléments de A n’appartenant pas à B).
(a) Cas des ensembles non triés :
i. Écrivez un tel algorithme.
Différence(A, rang, B, C)
si Recherche(B, A[rang]) = Faux
alors longueur(C) ← longueur(C) + 1
C[longueur (C)] ← A[rang]
Différence(A, rang + 1, B, C)
L’appel initial est alors Différence(A, 1, B, C) où C est un tableau de taille longueur (A),
ne contenant initialement aucun élément (longueur (C) = 0).
ii. Quelle est sa complexité ?
L’algorithme Différence est appelé longueur (A) fois, chacun de ces appels effectuant un
appel à Recherche sur B, dont le coût au pire est en longueur(B). La complexité au pire
de Différence est donc en Θ(longueur (A) × longueur (B)) ou Θ(nm), n et m dénotant la
taille des deux tableaux. Ce pire cas apparaı̂t quand les tableaux A et B sont disjoints.
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez un tel algorithme.

4
 Différence(A, a, B, b, C)
si a > longueur (A) alors renvoyer C
si A[a] = B[b] alors renvoyer Différence(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érence(A, a + 1, B, b, C)
sinon renvoyer Différence(A, a, B, b + 1, C)
L’appel initial est Différence(A, 1, B, 1, C, 0).
ii. Quelle est sa complexité ?
La complexité de cet algorithme est au pire en Θ(longueur (A) + longueur (B)) ou Θ(n + m) :
à chaque appel on décrémente au moins de un l’ensemble des valeurs à considérer.