Université Paris 13 L2
Institut Galilée
Licence 2 Math-Info - 2ème semestre
Conception d'Algorithmes
Conception d'algorithmes
DTL n° 1 (DpR : Diviser pour Régner)
Durée : 4 heures.
ATTENTION : Toute réponse NON justi ée sera considère NON valide.
Rappel du théorème maître.
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction à valeurs dans R+ , et soit T (n) une
fonction dé nie pour les entiers positifs par la récurrence T (n) = aT (n/b) + f (n), où l'on interprète
n/b soit comme bn/bc, soit comme dn/be. Alors, T (n) peut être bornée asymptotiquement comme
suit :
1. Si f (n) = O(nlogb a− ) pour une certaine constante > 0, alors T (n) = Θ(nlogb a ) .
2. Si f (n) = Θ(nlogb a ), alors T (n) = Θ(nlogb a log n).
3. Si f (n) = Ω(nlogb a+ ) pour une certaine constante > 0, et si l'on a asymptotiquement
af (n/b) ≤ cf (n) pour une constante 0 < c < 1, alors T (n) = Θ(f (n)).
Exercice 1 : (3 points)
Donner des bornes asymptotiques pour T (n) dans chacune des récurrences suivantes. On
suppose que T (n) est constante pour n ≤ 2. Justi ez vos réponses.
a. T (n) = T (9n/10) + n
b. T (n) = √
16T (n/4) + n2
√
c. T (n) = nT ( n) + n
Exercice 2 : (6 points)
Considérez, pour tout n ≥ 0, la séquence Fn = aFn−3 +bFn−2 +cFn−1 où F0 = 0, F1 = F2 = 1,
et où a, b, c sont des constantes réelles.
a. Notez que, pour n ≥ 3, Fn peut se récrire comme :
Fn−2 0 1 0 Fn−3
Fn−1 = 0 0 1 Fn−2
Fn a b c Fn−1
Utilisez cette information pour proposer un algorithme DpR en temps O(log n) pour
calculer la valeur de Fn .
b. Soient a = −1 et b = c = 1. Utilisez la méthode du polynôme caractéristique pour
donner une forme close de la récurrence Fn .
Exercice 3 : (4 points)
Considérons un tableau T de taille n (T [1 . . . n]) contenant tous les entiers de l'intervalle
1 . . . n+1, sauf un. On veut déterminer quel est l'entier absent de T . Les calculs de complexité
se feront sur la base du nombre d'accès aux éléments du tableau. Par exemple, si n = 8 et
T = [9, 7, 4, 6, 5, 2, 8, 1] alors l'entier absent est 3.
a. Le tableau T n'est pas trié. Construire un algorithme qui résout le problème en temps
linéaire, sans utiliser de tableau auxiliaire. Justi ez la complexité de votre algorithme.
1
b. Le tableau T est supposé trié en ordre croissant. Construire une solution DpR basée sur
la recherche dichotomique en temps O(log n). Justi ez la complexité de votre algorithme.
Exercice 4 : (8 points)
On considère un tableau à deux dimensions (une matrice) de valeurs entières positives telles
que les valeurs d'une même ligne et celles d'une même colonne sont ordonnées. Un tel tableau
est appelé bâtière. La gure ci-dessous est un exemple d'une bâtière à quatre lignes et quatre
colonnes. Il est à noter que tout sous-tableau d'une bâtière est lui-même une bâtière, et cette
2 14 25 30
3 15 28 30
7 15 32 43
20 28 36 58
propriété est utilisée implicitement dans la suite. On étudie la recherche d'une valeur v xée
dans une bâtière B . Plus précisément, si v est présent, on souhaite connaître les coordonnées
d'une de ses occurrences, sinon on délivre (−1, −1). Dans cet exercice, on supposera que la
bâtière est un carré de côté n = 2k (k ≥ 1), et on distingue les deux valeurs : x = B[n/2, n/2],
y = B[n/2 + 1, n/2 + 1].
a. Montrer que si la valeur recherchée v est telle que v > x, on peut éliminer une partie
(à préciser) de la bâtière pour poursuivre la recherche. Préciser ce qu'il est possible de
faire quand v < y .
b. En déduire un algorithme récursif de type DpR pour résoudre ce problème.
c. Établir une récurrence en termes de nombre de comparaisons eectuées pour votre so-
lution.
d. Résoudre la récurrence proposée dans le point (c).
