TD d’algorithmique avanc´ee
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
Publicité
si n = 1
sinon.
1. ´Ecrivez un algorithme r´ecursif calculant Fib(n).
2. Montrez que la complexit´e (en nombre d’additions) de cet algorithme est en Ω(2 n
3. ´Ecrire un algorithme r´ecursif qui calcule, pour n > 0, le couple (Fibonacci(n), Fibonacci(n − 1)).
4. Utilisez l’algorithme pr´ec´edent pour ´ecrire un nouvel algorithme calculant Fibonacci(n).
5. Qu’elle est la complexit´e (en nombre d’additions) de cet algorithme ?
2 ).
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-
Publicité
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.
ii. Quelle est sa complexit´e en nombre de comparaisons ?
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
ii. Quelle est sa complexit´e en nombre de comparaisons ?
iii. Utilisez une recherche dichotomique pour am´eliorer votre algorithme.
iv. Quelle est la complexit´e 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´es en argument.
(a) Cas des ensembles non tri´es :
Publicité
i. ´Ecrivez un tel algorithme.
ii. Quelle est sa complexit´e ?
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
ii. Quelle est sa complexit´e ?
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.
ii. Quelle est sa complexit´e ?
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
Publicité
ii. Quelle est sa complexit´e ?
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.
ii. Quelle est sa complexit´e ?
(b) Cas des ensembles tri´es (dans l’ordre croissant) :
i. ´Ecrivez un tel algorithme.
ii. Quelle est sa complexit´e ?