TD d’algorithmique avancée
TD 2 : récursivité
Jean-Michel Dischler et Frédéric Vivien
Suite de Fibonacci
La suite de Fibonacci est définie comme suit :
Fib(n) =
1
1
Fib(n − 1) + Fib(n − 2)
si n = 0
si n = 1
sinon.
1. Écrivez un algorithme récursif calculant Fib(n).
Publicité
2. Montrez que la complexité (en nombre d’additions) de cet algorithme est en Ω(2 n
3. Écrire un algorithme récursif qui calcule, pour n > 0, le couple (Fibonacci(n), Fibonacci(n − 1)).
4. Utilisez l’algorithme précédent pour écrire un nouvel algorithme calculant Fibonacci(n).
5. Qu’elle est la complexité (en nombre d’additions) de cet algorithme ?
2 ).
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.
ii. Quelle est sa complexité en nombre de comparaisons ?
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez un tel algorithme.
Publicité
ii. Quelle est sa complexité en nombre de comparaisons ?
iii. Utilisez une recherche dichotomique pour améliorer votre algorithme.
iv. Quelle est la complexité de votre nouvel algorithme ?
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.
ii. Quelle est sa complexité ?
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez un tel algorithme.
ii. Quelle est sa complexité ?
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.
Publicité
ii. Quelle est sa complexité ?
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez un tel algorithme.
ii. Quelle est sa complexité ?
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.
ii. Quelle est sa complexité ?
(b) Cas des ensembles triés (dans l’ordre croissant) :
i. Écrivez un tel algorithme.
ii. Quelle est sa complexité ?