Université Paris 13 L2
Institut Galilée Année 2016-2017
Licence 2 Info - 2ème semestre
Conception d'algorithmes
Travaux dirigés 2 : Diviser pour régner
Exercice 1 : Encore Fibonnacci !
Dans le TD précédent, nous avons analysé le nombre de comparaisons d'un algorithme
récursif pour calculer le n-ième nombre de la séquence de Fibonacci Fn dé nie comme :
F0 = 0, F1 = 1 et ∀n ≥ 2, Fn = Fn−1 + Fn−2 . On a obtenu un nombre exponentielle de
comparaisons.
a. Proposez un algorithme linéaire pour ce problème.
b. Notez que, pour n ≥ 2, Fibonnaci peut se récrire comme :
Fn 1 1 Fn−1
=
Fn−1 1 0 Fn−2
Utilisez cette information pour proposer un nouvel algorithme pour le calcul du n-ième
nombre de la séquence de Fibonacci. Analysez la complexité de votre algorithme (c-à-d,
nombre totale d'opérations eectuées).
Exercice 2 : MaxMin d'un tableau
Soit A un tableau d'entiers de taille n. On désire calculer simultanément les valeurs maxi-
mum et minimum contenus dans A.
a. Proposez un algorithme naïf qui exécute au plus 2n − 2 comparaisons entre éléments
du tableau.
b. En utilisant la technique de diviser par régner, proposez un algorithme qui exécute au
plus 32 n − 2 comparaisons entre éléments du tableau.
Exercice 3 : Recherche de pics
Soit A un tableau d'entiers de taille n. On dit que A[i] est un "pic" s'il n'est pas plus petit
que ses voisins : A[i − 1] ≤ A[i] ≥ A[i + 1]. On supposera que A[−1] = A[n] = −∞. Donc,
un pic A[i] est un maximum local. Par exemple, si A = [1, 2, 6, 5, 3, 7, 4], on a que A[2] = 6
et A[5] = 7 sont des pics. Notez que si l'on permute les valeurs dans les positions 0 et 1 du
tableau précédent A, on aura que A[0] = 2 est aussi un pic, car −∞ ≤ 2 ≥ 1. Le but de cet
exercice est de trouver un pic dans un tableau (n'importe lequel).
a. En remarquant qu'il existe toujours un pic, proposez un algorithme naïf utilisant O(n)
comparaisons des éléments du tableau.
b. Supposez que A[q + 1] > A[q] et pourtant A[q] n'est pas un pic, avec 0 < q < n − 1.
Prouvez qu'il existe un pic dans l'intervalle A[q + 1..n − 1].
c. En utilisant l'exercice précédent (3.b), proposez un algorithme diviser pour régner qui
résoudre le problème de pic en temps O(log n).
Exercice 4
Soit S un ensemble de n entiers et soit x un entier donné. Développez un algorithme de
complexité Θ(n log n) qui détermine s'il existent a, b ∈ S tels que a + b = x.
1
Exercice 5 : Évaluation d'un polynôme
Soit P (Z) = an−1 Z n−1 + an−2 Z n−2 + . . . + a1 Z + a0 un polynôme, où les ai ´s sont des
coe cients réels. Soit x un nombre réel. On désire évaluer P dans le point x.
a. Concevoir un algorithme itératif pour ce problème qui utilise Θ(n2 ) multiplications.
b. Concevoir un algorithme récursif pour ce problème qui utilise Θ(n) multiplications.
Justi er formellement votre réponse.
Exercice 6
Soit a ≥ 1 et b > 1 deux constantes, et soit f (n) une fonction positive dé nie sur des
puissances exactes de b. On dé nit T (n) pour des puissances exactes de b par la récurrence :
si n = 1
(
Θ(1)
T (n) =
aT (n/b) + f (n) si n = bi ,
où i est un entier positif. Prouver que :
(logb n)−1
X
logb a
T (n) = Θ(n )+ aj f (n/bj ).
j=0
Exercice 7 : Il ne faut pas oublier les récurrences linéaires
Soit p > 0 une constante et soit tn = ni=0 ipi , pour n ∈ N. Exprimez tn comme une
P
récurrence linéaire (non-homogène) et trouvez une solution à cette équation de récurrence en
utilisant la méthode du polynôme caractéristique vu en cours. (Indice : la solution à l'équation
n −1)
de récurrence est : tn = npp−1 − p(p ).
n+1
(p−1)2
