Licence informatique - L2 Année 2013/2014

Conceptions algorithmiques (L2)

TD Algorithmes diviser pour régner
Séances 2,3,4

Rappel du théorème maı̂tre

Théorème 1. (Résolution de récurrences diviser pour régner). Soient a ≥ 1 et b > 1 deux
constantes, soient f une fonction à valeurs dans R+ et T une fonction de N∗ dans R+ vérifiant,
pour tout n suffisamment grand, l’encadrement suivant : aT (⌊n/b⌋)+f (n) ≤ T (n) ≤ aT (⌈n/b⌉)+
f (n). Alors T peut être bornée asymptotiquement comme suit :
1. Si f (n) = O(n(logb 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) = Ω(n(logb a)+ε ) pour une certaine constante ε > 0, et si on a asymptotiquement
pour une constante c < 1, af (n/b) < cf (n), alors T (n) = Θ(f (n)).

1 Notations Asymptotiques
Exercice 1.1. Rappeler les définitions des notations O, Ω, Θ pour les fonctions à valeur dans
R∗+ .

Solution:
 
il existe des constantes stt positives c et n0  f (n) 
f (n) = O(g(n)) ⇔ ⇔ lim sup  <∞
telles que 0 ≤ f (n) < c.g(n) pour tout n ≥ n0 n→∞ g(n)

 
il existe des constantes stt positives c et n0  f (n) 
f (n) = Ω(g(n)) ⇔ ⇔ lim inf  >0
telles que 0 ≤ c.g(n) ≤ f (n) pour tout n ≥ n0 n→∞ g(n) 

il existe des constantes stt positives c1 , c2 et un n0

f (n) = Θ(g(n)) ⇔
tels que 0 ≤ c1 .g(n) ≤ f (n) ≤ c2 .g(n) pour tout n ≥ n0

Exercice 1.2. Le but de cet exercice est de tester votre compréhension de la notion de com-
plexité dans le pire des cas.
1. Si je prouve que la complexité dans le pire des cas d’un algorithme est en O(n2 ), est-il
possible qu’il soit en O(n) sur certaines données ?
2. Si je prouve que la complexité dans le pire des cas d’un algorithme est en O(n2 ), est-il
possible qu’il soit en O(n) sur toutes les données ?
3. Si je prouve que la complexité dans le pire des cas d’un algorithme est en Θ(n2 ), est-il possible
qu’il soit en O(n) sur certaines données ?
4. Si je prouve que la complexité dans le pire des cas d’un algorithme est en Θ(n2 ), est-il possible
qu’il soit en O(n) sur toutes les données ?

1
 Solution:
1. OUI
2. OUI
3. OUI
4. NON

Exercice 1.3. Sur une échelle croissante, classer les fonctions suivantes selon leur comportement
asymptotique : c’est-à-dire g(n) suit f (n) si f (n) = O(g(n)).
n3
f1 (n) := 2 n f2 (n) := 2n f3 (n) := log(n) f4 (n) := 3
f5 (n) := n! f6 (n) := log(n)2 f7 (n) := nn f8 (n) := n2
√
f9 (n) := n + log(n) f10 (n) := n f11 (n) := log(n ) f12 (n) := en
2

f14 (n) := log(n) f15 (n) := 2log2 (n) f16 (n) := n log(n)
p
f13 (n) := n

Solution: On classe d’abord les fonctions en trois catégories : les fonctions polylogarith-
miques (logk n), les fonctions polynomiales (nk ) et les fonctions exponentielles (an ). Pour les
autres fonctions, on essaie quand même de les faire rentrer dans une de ces trois catégories.
Par exemple pour n ≥ 2, on a 2n ≤ n! ≤ nn donc n! est plus qu’exponentielle.

f14 < f3 ≡ f11 < f6 < f10 < f13 = f15 ≡ f9 ≡ f1 < f16 < f8 < f4 < f2 < f12 < f5 < f7

√
log(n) < log(n) ≡ log(n2 ) < log(n)2 < n < n = 2log2 (n) ≡ n + log(n) ≡ 2 n
p

n3
< n log(n) < n2 < < 2n < en < n! < nn
3

Remarque :

logb n
loga n =
logb a
√  n n
n ! ∼ 2πn
e

2 Fonctions définies par récurrence

Exercice 2.1. Soit un algorithme dont la complexité T (n) est donnée par la relation de récur-
rence :

T (1) = 1,
j n k
T (n) = 3 T + n2 .
2
a. Calculer T (n) en résolvant la récurrence.

2
b. Déterminer T (n) à l’aide du théorème maı̂tre.

Remarque :
On a
k
X xk+1 − 1
alogx b = blogx a et xi = .
x−1
i=0

Solution:
a.
n
T (n) = 3 T + n2
2
  n  n2 
= 3 3T + + n2
4 4
   n  n2  n2 
= 3 3 3T + + + n2
8 16 4
..
.
log2 n log2 n  i
X n2 X 3
i 2
= 3 i =n
4 4
i=0 i=0
 log2 n+1
3
= −4n2 + 4n2
4
= −3nlog2 3 + 4n2

Remarque :
Des fois, on s’en sort mieux en posant n = 2N pour avoir T (N − 1) (pas dans cet
exemple).

b. a = 3, b = 2, f (n) = n2 = Ω(n2 ), cas 3, ε = 2 − log2 3, c = 3/4 + 0.1 par ex. ⇒ T (n) =

Θ(n2 ).

Exercice 2.2. Le but de cet exercice est d’utiliser le théorème maı̂tre pour donner des ordres
de grandeur asymptotique pour des fonctions définies par récurrence.
1. En utilisant le théorème maı̂tre, donner un ordre de grandeur asymptotique pour T (n) :
a. n
T (1) = 1, T (n) = 2 T + n2 ;
2
b. n
T (1) = 0, T (n) = 2 T + n;
2
c. n √
T (1) = 1, T (n) = 2 T + n;
2

3
 d. n
T (1) = 0, T (n) = T
+ Θ(1).
2
2. Essayer de donner des exemples d’algorithmes dont le coût est calculé par l’une de ces
récurrences.

Solution:
1. a. a = b = 2, f (n) = n2 = Ω(n2 ), cas 3, ε = 1, c = 3/4 par exemple. ⇒ T (n) = Θ(n2 ).
b. a = b = 2, f (n) = n = Θ(n), cas 2. ⇒ T (n) = Θ(n log(n)).
√ 1
c. a = b = 2, f (n) = n = O(n 2 ), cas 1, ε = 21 . ⇒ T (n) = Θ(n).
d. a = 1, b = 2, f (n) = 1 = Θ(n0 ), cas 2. ⇒ T (n) = Θ(log(n)).
2. a. Les point rapprochés, méthode naı̈ve.
b. Tri fusion, Quicksort, ...
c. ...
d. Recherche dichotomique.

Exercice 2.3. Le but de cet exercice est de choisir l’algorithme de type diviser pour régner
le plus rapide pour un même problème.
1. Pour résoudre un problème manipulant un nombre important de données, on propose deux
algorithmes :
a. un algorithme qui résout un problème de taille n en le divisant en 2 sous-problèmes de
taille n/2 et qui combine les solutions en temps quadratique,
b. un algorithme qui résout un problème de taille n en le divisant en 4 sous-problèmes de
√
taille n/2 et qui combine les solutions en temps O( n).
Lequel faut-il choisir ?
2. Même question avec les algorithmes suivants :
a. un algorithme qui résout un problème de taille n en le réduisant à un sous-problème de
√
taille n/2 et qui combine les solutions en temps Ω( n),
b. un algorithme qui résout un problème de taille n en le divisant en 2 sous-problèmes de
taille n/2 et qui combine les solutions en temps constant.

Solution:
n
+ n2 ⇒ T (n) = Θ(n2 ).


1. a. T (n) = 2 T 2
√
b. a = 4, b = 2, f (n) = O( n), cas 1. ε = 23 , ⇒ T (n) = Θ(n2 ).
Les 2 algos sont équivalents.
1 √ √
2. a. a = 1, b = 2, f (n) = Ω(n 2 ), cas 3. ε = 12 , c = 1/ 2 par exemple. ⇒ T (n) = Θ( n).
b. a = b = 2, f (n) = Θ(1), cas 1. ε = 1, ⇒ T (n) = Θ(n).
Le premier algo est meilleur.

Exercice 2.4. Considérons maintenant un algorithme dont le nombre d’opérations sur une
entrée de taille n est donné par la relation de récurrence :
n  
2n
T (1) = 0 et T (n) = T +T + n.
3 3

4
1. Construire un arbre représentant les appels récursifs de l’algorithme. En déduire la complexité
de T (n).
2. Vérifier le résultat par récurrence (méthode par substitution).
3. Cette récurrence peut-elle être résolue en utilisant le théorème maı̂tre ?

Solution:
1. On déduit une complexité O(n log3 n).
2. On veut montrer la proprièté P (n) : T (n) = O(n log3 n), c-a-d, ∃c, T (n) ≤ c.n log3 n.
On suppose que P (k) est vraie pour tout k < n. On a donc :
n n 2n 2n
T (n) ≤ c · log3 + c · log3 +n
3 3 3 3
n 2n n 2n 2n
= c · log3 n + c · log3 n − c · + c · log3 2 − c · +n
3 3 3 3 3
2n
= c · n · log3 n − c · n + c · log3 2 + n
3
2n
= c · n · log3 n + c · ( log3 2 − n) + n
3

Pour que P (n) soit vraie, il faut que c · ( 2n

3 log3 2 − n) + n < 0, c-a-d :

−1
c≥ 2 ∼ 1, 7.
3 log3 2 − 1

On peut par exemple choisir c = 3 et on vérifie que

n n 2n 2n
3· log3 + 3 · log3 + n = 3n log3 n + 2n(log3 2 − 1) ≤ 3n log3 n.
3 3 3 3
3. Le théorème maı̂tre ne permet pas de résoudre cette récurrence.

3 Recherche d’éléments, de suite d’éléments

Exercice 3.1. Donnez un algorithme de recherche d’un élément dans un tableau trié (dans
l’ordre croissant) :
a. en utilisant une recherche séquentielle,
b. en utilisant le principe diviser pour régner .
Donnez la complexité (en nombre de comparaisons) dans le pire cas de chacun de ces deux
algorithmes en fonction de la taille n du tableau.

Solution:
1. R e c h e r c h e 1(t , e )
i <- 1;
tantque i≤l o n g u e u r( t ) et t [ i ]<e f a i r e
i <- i +1;

5
 fint a nt que
s i i = l o n g u e u r( t )+1 OU t [ i ]6= e a l o r s
retourne FAUX
finsi
retourne i ;
fin
Complexité : O(n)
2. R e c h e r c h e 2(t , g , d ,e )
s i g=d a lors
s i t [ g ]= e a l o r s retourne g ;
sinon retourne FAUX
finsi ;
finsi ;
s i e≤t [⌊ g+d 2 ⌋] a l o r s
retourne R e c h e r c h e 2(t , g , ⌊ g+d2 ⌋, e );
sinon
retourne R e c h e r c h e 2(t , ⌊ g+d2 ⌋ + 1, d , e );
finsi
fin
n
Complexité : T (n) = T + O(1) cf. exo ??.
2

Exercice 3.2. On cherche le k-ième plus petit élément dans un tableau non trié.
a. Proposer un algorithme utilisant le principe diviser pour régner en s’inspirant de celui
du tri rapide.
b. Faire la trace de l’algorithme sur le tableau
2 4 1 6 3 5
pour k = 4.
c. Donnez la complexité (en nombre de comparaisons) dans le pire cas de cet algorithme en
fonction de la taille n du tableau.
d. Que se passe-t-il si, à chaque étape, le tableau considéré est coupé en 2 sous-tableaux de
tailles équivalentes ?

Solution:
a. R e c h e r c h e K i è m e(t , g , d , k )
s i g = d a l o r s retourne t [ g ] f i n s i ;

p <- t [ g ]; # on choisit le 1 er élément comme pivot .

j <- g; # d e r n i è r e entrée <=p .
pour i de g +1 à d f a i r e
si t [ i ]≤p a l o r s
swap ( t [ i ] , t [ j +1]);

6
 j <- j +1;
finsi ;
f i n pour;
swap ( t [ g ] , t [ j ]);

s i k=j a lors
retourne t [ j ];
sinon
s i k<j a lors
retourne R e c h e r c h e K i è m e(t , g , j , e )
sinon
retourne R e c h e r c h e K i è m e(t , j +1 , d , e )
finsi
finsi
fin

i
b. 2 4 1 6 3 5 p=2,
j=1
i
2 4 1 6 3 5 p=2,
j
i i i
2 1 4 6 3 5 −→ swap −→ 1 2 | 4 6 3 5
j=2
i
4 6 3 5 p=4,
j=3
i i i
4 6 3 5 −→ swap −→ 3 4 6 5 −→ j=k −→ fin.
j=4 j=4
c. Pire cas : tableau trié et k = lg(tableau) : T (n) = T (n − 1) + O(n).
La complexité est O(n2 ).
n
d. T (n) = T + O(n).
2
a = 1, b = 2, f (n) = n = Ω(n), cas 3 du [Link]ı̂tre, ε = 1, c = 3/4 par exemple.
⇒ T (n) = Θ(n).

Exercice 3.3. On dispose d’un tableau d’entiers relatifs de taille n. On cherche à déterminer
la suite d’entrées consécutives du tableau dont la somme est maximale. Par exemple, pour le ta-
bleau T = [−1, 9, −3, 12, −5, 4], la solution est 18 (somme des éléments de T [2..4] = [9, −3, 12]).
a. Proposer un algorithme élémentaire pour résoudre ce problème. Donner sa complexité.
b. Donner un (meilleur) algorithme de type diviser pour régner . Quelle est sa complexité ?

Solution:

7
a. 1. MaxSum1 ( t )
max <- 0;
pour i de 1 à l o n g u e u r( t ) f a i r e
pour j de i +1 à l o n g u e u r( t ) f a i r e
S <- 0;
pour k de i à j f a i r e
S <- S + t [ k ];
s i S > max a l o r s
max <- S ;
finsi
f i n pour
f i n pour
f i n pour
retourne max ;
fin
Complexité : O(n3 )
2. MaxSum2 ( t )
max <- 0;
pour i de 1 à l o n g u e u r( t ) f a i r e
S <- 0;
pour j de i +1 à l o n g u e u r( t ) f a i r e
S <- S + t [ j ];
s i S > max a l o r s
max <- S ;
finsi
f i n pour
f i n pour
retourne max ;
fin
Complexité : O(n2 )
b. M a x A c h e v a l(t , g , d )
int max <- 0;
int S <- 0;
pour i de ⌊ g+d 2 ⌋ + 1 à d f a i r e
S < - S + t [ i ];
s i S > max a l o r s
max <- S ;
finsi
f i n pour
S <- max ;
pour i de ⌊ g+d 2 ⌋ à g pas de -1 f a i r e
S <- S + t [ i ];
s i S > max a l o r s
max <- S ;
fin si

8
 f i n pour
retourne max ;
fin

MaxSum3 (t , g , d ) {
s i g > d a l o r s retourne 0 f i n s i ;
s i g=d a lors
s i t [ g ] <0 a l o r s
retourne 0;
sinon
retourne t [ g ];
finsi
finsi
m1 <- MaxSum3 (t ,g , ⌊ g+d 2 ⌋);
g+d
m2 <- MaxSum3 (t ,⌊ 2 ⌋ + 1,d );
m3 <- M a x A c h e v a l(t ,g , d );

retourne max ( m1 , m2 , m3 );
fin
n
Complexité : T (n) = 2 T + O(n).
2
a = b = 2, f (n) = n = Θ(n), cas 2. du th. maı̂tre. ⇒ T (n) = Θ(n log(n)).

Exercice 3.4. Un élément x est majoritaire dans un ensemble E de n éléments si E contient

strictement plus de n/2 occurrences de x. La seule opération dont nous disposons est la com-
paraison (égalité ou non) de deux éléments.
Le but de l’exercice est d’étudier le problème suivant : étant donné un ensemble E, représenté
par un tableau, existe-t-il un élément majoritaire, et si oui quel est-il ?
1. Algorithme naı̈f
a. Écrivez un algorithme NombreOccurrences qui, étant donné un élément x et deux
indices i et j, calcule le nombre d’occurrences de x entre E[i] et E[j]. Quelle est sa
complexité (en nombre de comparaisons) ?
b. Écrivez un algorithme Majoritaire qui vérifie si un tableau E contient un élément
majoritaire, et si oui le retourne. Quelle est sa complexité ?
2. Algorithme de type diviser pour régner
Pour calculer l’élément majoritaire de l’ensemble E (s’il existe), on découpe l’ensemble E
en deux sous-ensembles E1 et E2 de même taille, et on calcule récursivement dans chaque
sous-ensemble l’élément majoritaire. Pour qu’un élément x soit majoritaire dans E, il suffit
que l’une des conditions suivantes soit vérifiée :
– x est majoritaire dans E1 et dans E2 ,
– x est majoritaire dans E1 et non dans E2 , mais suffisamment présent dans E2 ,
– x est majoritaire dans E2 et non dans E1 , mais suffisamment présent dans E1 .
Écrivez un algorithme utilisant cette approche diviser pour régner . Analysez sa complexité.
3. Pour améliorer l’algorithme précédent, on propose de construire un algorithme PseudoMa-
joritaire tel que :
– soit l’algorithme garantit que E ne possède pas d’élément majoritaire,

9
 – soit il rend un couple (x, p) tel que p > n/2, x est un élément apparaissant au plus p fois
dans E, et tout élément y 6= x de E apparaı̂t au plus n − p fois dans E.
Donnez un algorithme récursif vérifiant ces conditions. Donnez sa complexité. Déduisez-en
un algorithme de recherche d’un élément majoritaire, et donnez sa complexité.

Solution:
Rmq. 1 pour simplifier, on peut supposer que n = 2k .
Rmq. 2 pour la question 2, comme indice : renvoyer un couple (booléen, élément).

4 Tris
Exercice 4.1 (Tri fusion). Le but de l’exercice est de trier un tableau en utilisant l’approche
diviser pour régner : on commence par couper le tableau en deux, on trie chaque moitié avec
notre algorithme, puis on fusionne les deux moitiés.
1. Écrire un algorithme Fusion(A, B) permettant de fusionner deux tableaux A et B déjà triés
de tailles nA et nB en un seul tableau trié T . Quelle est sa complexité ?
2. À l’aide de l’algorithme décrit ci-dessus, écrire l’algorithme du tri fusion.
3. Quelle est la complexité du tri fusion ?

Solution:
1. F U S I O N N E R( A : tableau de nombres , B : tableau de nombres )

i_A := 0
i_B := 0
i_R := 0

n_A := l o n g u e u r de A
n_B := l o n g u e u r de B

I n i t i a l i s e r un tableau R de taille n_A + n_B

TANT QUE i_A < n_A ou i_B < n_B

FAIRE
SI i_B >= n_B A [ i_A ] <B [ i_B ]
ALORS
R [ i_R ] = A [ i_A ]
i_A ++
SINON
R [ i_R ] = B [ i_B ]
i_B ++
FIN SI
i_R ++

10
 FIN

TANT QUE i_A < n_A

FAIRE
R [ i_R ] = A [ i_A ]
i_A ++
i_R ++
FIN

TANT QUE i_B < n_B

FAIRE
R [ i_R ] = B [ i_B ]
i_B ++
i_R ++
FIN

RENVOYER R
La complexité est linéaire, O(n)
2. T R I F U S I O N( T )

A = T R I F U S I O N (1 ere moitie de T )
B = T R I F U S I O N (2 eme moitie de T )
R E N V O Y E R( F U S I O N N E R(A , B ))

3. C(n) = n + 2C(n/2)
Une application immediate du theoreme maitre (2eme cas) donne C(n) = O(n log n)

5 Algèbre et arithmétique
Exercice 5.1 (Multiplication de deux polynômes). On représente un polynôme p(x) = m−1 i
P
i=0 ai x
par la liste de ses coefficients [a0 , a1 , . . . , am−1 ]. Nous nous intéressons au problème de la multi-
plication de deux polynômes P : étant donnés deux polynômes p(x) et q(x) de degré au plus n − 1,
2n−2
calculer pq(x) = p(x)q(x) = i=0 ci xi .
1. Préliminaires : énumérez les opérations basiques (de coût 1) qui serviront à calculer la com-
plexité de vos algorithmes. Vérifiez que l’addition de deux polynômes de degré n − 1 se fait
en Θ(n).
2. Méthode directe.
Donnez un algorithme calculant directement chaque coefficient ci . Quelle est sa complexité ?
3. On découpe chaque polynôme en deux parties de tailles égales :

p(x) = p1 (x) + xn/2 p2 (x),

q(x) = q1 (x) + xn/2 q2 (x),

et on utilise l’identité

pq = p1 q1 + xn/2 (p1 q2 + p2 q1 ) + xn p2 q2 .

11
 Donnez un algorithme récursif, utilisant le principe diviser pour régner, qui calcule le produit
de deux polynômes à l’aide de l’identité précédente. Si T (n) est le coût de la multiplication
de deux polynômes de taille n, quelle est la relation de récurrence vérifiée par T (n) ? Quelle
est la complexité de votre algorithme ? Comparez-la à la complexité de la méthode directe.
4. On utilise maintenant la relation
p1 q2 + p2 q1 = (p1 + p2 )(q1 + q2 ) − p1 q1 − p2 q2 .
Donnez un algorithme calculant le produit pq à l’aide de cette relation, et explicitez le nombre
de multiplications et d’additions de polynômes de degré n/2 utilisées. Quelle est la complexité
de votre algorithme ?
5. Pensez-vous que cet algorithme a une complexité optimale ?

Solution:
1. Nous comptons comme opération élémentaire (de coût 1) les additions et les multiplica-
tions entre
Pn−1les coefficients P(scalaires).
i n−1 Pn−1
Si p = i=0 ai x et q = i=0 bi xi alors p + q = i=0 (ai + bi )xi . On effectue donc n
additions ai + bi pour 0 ≤ i ≤ n − 1. L’addition de deux polynômes de degré n − 1 se
fait donc en Θ(n).
Pn−1 Pn−1 P2n−2
ai xi et q = i=0 bi xi alors pq = i=0 ci xi avec ci = ij=0 aj bi−j .
P
2. Toujours si p = i=0
L’algorithme consiste donc à calculer les 2n − 1 coefficients ci .
Entrées : 2 p o l y n ^ o m e s p et q
Sortie : 1 p o l y n ^ o m e pq
Mult (p , q )
ci = 0 pour i allant de 0 à 2n − 1
pour i de 0 à n − 1
pour j de 0 à n − 1
ci+j = ci+j + ai ∗ bj
f i n pour
f i n pour
fin
Par conséquent T (n) = Θ(n2 ).
3. Entrées : 2 p o l y n ^ o m e s p et q
Sortie : 1 p o l y n ^ o m e pq
Mult (p , q )
k := max(deg(p), deg(q))
si k ≤ 1 alors
retourne pq
sinon
m := n/2
p1 := p mod xm
p2 := p/xm
q1 := q mod xm
q2 := q/xm
r1 := Mult(p1 , q1 )
r2 := Mult(p2 , q2 )

12
 r3 := Mult(p1 , q2 )
r4 := Mult(p2 , q1 )
retourne r1 + (r3 + r4 )xm + r2 xn
Soit T (n) le nombre d’opérations élémentaires nécessaires pour calculer le produit de
2 polynômes de taille n. Dans l’algorithme, on fait 4 multiplications de polynômes de
taille n/2. La reconstruction nécessite d’additionner des polynômes donc est en O(n).
Par conséquent
T (n) = 4T (n/2) + O(n).
Le théorème maı̂tre donne T (n) = Θ(n2 ) avec a = 4, b = 2 et logb a = 2 et ε = 1. On
n’a rien gagné par rapport à l’approche directe.
4. Entrées : 2 p o l y n ^ o m e s p et q
Sortie : 1 p o l y n ^ o m e pq
M u l t K a r a t s u b a(p , q )
k := max(deg(p), deg(q))
si k ≤ 1 alors
retourne pq
sinon
m := n/2
p1 := p mod xm
p2 := p/xm
q1 := q mod xm
q2 := q/xm
r1 := MultKaratsuba(p1 , q1 )
r2 := MultKaratsuba(p2 , q2 )
r3 := MultKaratsuba(p1 + p2 , q1 + q2 )
retourne r1 + (r3 − r1 − r2 )xm + r2 xn
On ne fait maintenant plus que 3 multiplications de polynômes de taille n/2. Là encore
la division et la reconstruction se font en O(n). Par conséquent T (n) = 3T (n/2) + O(n).
Pour a = 3, b = 2, logb a = log2 3 ≈ 1.585 et ε = 1/2, le théorème maı̂tre donne
T (n) = Θ(nlog2 3 ).
5. Non, l’algorithme n’est pas optimal. On peut multiplier deux polynômes en O(n log n)
grâce à la FFT (voir le cours AAA).

Exercice 5.2 (Algorithme de Strassen pour la multiplication de deux matrices). La multipli-

cation de matrices est très fréquente dans les codes numériques. Le but de cet exercice est de
proposer un algorithme rapide pour cette multiplication.
1. Donnez un algorithme direct qui multiplie deux matrices A et B de taille n × n. Donnez sa
complexité en nombre de multiplications élémentaires.
2. Notons C = A B. Dans le but d’utiliser le principe diviser pour régner , on divise les matrices
A, B et C en quatre sous-matrices n/2 × n/2
    
c11 c12 a11 a12 b11 b12
C= = = A B.
c21 c22 a21 a22 b21 b22

Les sous-matrices de C peuvent être obtenues en effectuant les produits et additions de

13
 matrices n/2 × n/2 suivants :
c11 = a11 b11 + a12 b21 , c12 = a11 b12 + a12 b22 ,
c21 = a21 b11 + a22 b21 , c22 = a21 b12 + a22 b22 .
Notons T (n) le coût de la multiplication de deux matrices de taille n, quelle est la relation de
récurrence vérifiée par T (n) dans ce cas ? Donnez la solution de cette relation de récurrence,
comparez-la à la complexité de la méthode directe.
3. Strassen (en 1969) a suggéré de calculer les produits intermédiaires suivants :
m1 = (a12 − a22 ) (b21 + b22 ), m4 = (a11 + a12 ) b22 ,
m2 = (a11 + a22 ) (b11 + b22 ), m5 = a11 (b12 − b22 ),
m3 = (a11 − a21 ) (b11 + b12 ), m6 = a22 (b21 − b11 ),
m7 = (a21 + a22 ) b11 ,
puis de calculer C comme suit :
c11 = m1 + m2 − m4 + m6 , c12 = m4 + m5 ,
c21 = m6 + m7 , c22 = m2 − m3 + m5 − m7 .
a. Montrez que C est bien le produit de A par B (attention, la multiplication de deux
matrices n’est pas commutative !).
b. Donnez la relation de récurrence vérifiée par T (n). Déduisez-en la complexité de l’algo-
rithme de Strassen.
c. Pensez-vous que cet algorithme a une complexité optimale ?

Solution:
1. Soit C = AB où A et B sont des matrices carrées de taille n. On a cij = nk=1 aik bkj . Par
P
conséquent, le calcul de cij nécessite n multiplications et (n − 1) additions soit au total
2n − 1 opérations élémentaires. Comme il y a n2 coefficients à calculer, la complexité est
en Θ(n3 ).
2. Soit T (n) le coût de la multiplication de deux matrices de taille n. Pour calculer le
produit de deux matrices de taille n, on calcule le produit de 8 matrices de taille n/2
puis on les recombine (on somme des matrices de taille n/2 ce qui se fait en O(n2 ). Par
conséquent T (n) = 8T (n/2) + O(n2 ). Avec b = 2, a = 8, logb a = log2 8 = 3, ε = 1, le
théorème implique que T (n) = Θ(n3 ). Cela n’améliore pas la complexité par rapport à
la méthode directe.
3. a. Pour montrer que l’on a bien C = AB, il suffit de développer et de simplifier ensuite.
b. La séparation se fait en O(n2 ) puisque l’on doit sommer des matrices de taille n/2. On
fait ensuite 7 multiplications de matrices de taille n/2 puis on reconstruit en faisant
des additions de matrices de taille n/2 ce qui est aussi en O(n2 ). Par conséquent
T (n) = 7T (n/2) + O(n2 ). Avec b = 2, a = 7, logb a = log2 7 ≈ 2.807 et ε = 1/2, le
théorème maı̂tre donne T (n) = Θ(nlog2 7 ).
c. Non on peut faire mieux avec l’algorithme de Coppersmith-Winograd qui permet de
calculer un produit matriciel en O(n2.376 ). C’est l’algorithme le plus rapide connu à
l’heure actuelle même si on conjecture que l’on doit pouvoir multiplier des matrices
en O(n2 ). Il est trop compliqué pour le cours car il utilise de la théorie des groupes
assez avancée. Malgré sa complexité avantageuse, il n’est jamais utilisé en pratique
car la constante dans le O est très grande.

14
Exercice 5.3 (Matrices Toeplitz). Une matrice Toeplitz est une matrice de taille n × n (aij )
telle que ai,j = ai−1,j−1 pour 2 ≤ i, j ≤ n.
1. La somme de deux matrices Toeplitz est-elle une matrice Toeplitz ? Et le produit ?
2. Trouver un moyen d’additionner deux matrices Toeplitz en O(n).
3. Comment calculer le produit d’une matrice Toeplitz n × n par une vecteur de longueur n ?
Quelle est la complexité de l’algorithme ?

Solution:
n−1
1. Les matrices Toeplitz sont les matrices dont les diagonales sont constantes (ti−j )i,j=0 .
 
t0 t−1 · · · t1−n
 .. .. 
 t1 t0 . . 
 ..
 
.. ..
. . t−1 

 .
tn−1 · · · t1 t0

Il devrait clair que la somme de deux matrices Toeplitz reste Toeplitz. Par contre, c’est
faux pour le produit. En effet
     
1 0 1 1 1 1
× = .
1 1 0 1 1 2

2. On remarque d’après la définition qu’une matrice Toeplitz est caractérisé par sa première
ligne et sa première colonnes, c’est-à-dire par 2n − 1 éléments. Pour additionner deux
matrices Toeplitz, il suffit d’additionner les premières lignes et les premières colonnes ce
qui se fait en O(n).
3. On va considérer des matrices de taille n avec n une puissance de 2. On va décomposer
la matrice en blocs de taille n/2 ainsi que le vecteur Z
   
A B X
TZ = × .
C A Y

On pose alors

U = (C + A)X,
V = A(Y − X),
W = (B + A)Y.

On a alors  
W −V
TZ = .
U +V
Soit T (n) le coût de la multiplication d’une matrice Toeplitz de taille n par un vecteur
de taille n. On fait 3 multiplication de matrices Toeplitz de taille n/2 par des vecteurs
de taille n/2. Lors de la division et de la reconstruction, on additionne des matrices
Toeplitz de taille n/2 et des vecteurs de taille n/2 ce qui se fait en O(n). Par conséquent
T (n) = 3T (n/2) + O(n). Avec b = 2, a = 3, logb a = log2 3 ≈ 1.585 et ε = 1/2, le
théorème maı̂tre donne T (n) = Θ(nlog2 3 ).
Remarque : On peut même multiplier une matrice Toeplitz par un vecteur en O(n log n)
via la FFT et multiplier deux matrices Toeplitz en O(n2 ).

15
6 Géométrie algorithmique
Exercice 6.1 (Recherche des deux points les plus rapprochés). Le problème consiste à trou-
ver les deux points les plus rapprochés (au sens de la distance euclidienne classique) dans un
ensemble P de n points. Deux points peuvent coı̈ncider, auquel cas leur distance vaut 0. Ce pro-
blème a notamment des applications dans les systèmes de contrôle de trafic : un contrôleur du
trafic aérien ou maritime peut avoir besoin de savoir quels sont les appareils les plus rapprochés
pour détecter des collisions potentielles.
1. Donnez un algorithme naı̈f qui calcule directement les deux points les plus rapprochés, et
analysez sa complexité (on représentera P sous forme de tableau et on analysera la complexité
de l’algorithme en nombre de comparaisons).
Nous allons construire un algorithme plus efficace basé sur le principe diviser pour régner .
Le principe est le suivant :
a. Si |P | ≤ 3, on détermine les deux points les plus rapprochés par l’algorithme naı̈f.
b. Si |P | > 3, on utilise une droite verticale ∆, d’abscisse l, séparant l’ensemble P en deux
sous ensembles (P gauche et P droit) tels que l’ensemble P gauche contienne la moitié des
éléments de P et l’ensemble P droit l’autre moitié, tous les points de P gauche étant situés
à gauche de ou sur ∆, et tous les points de P droit étant situés à droite de ou sur ∆.
c. On résout le problème sur chacun des deux sous-ensembles P gauche et P droit, les deux
points les plus rapprochés sont alors :
– soit les deux points les plus rapprochés de P gauche,
– soit les deux points les plus rapprochés de P droit,
– soit un point de P gauche et un point de P droit.
On supposera qu’initialement l’ensemble P est trié selon des abscisses et ordonnées crois-
santes ; en d’autres termes l’algorithme prend la forme : PlusProche(PX, PY), où PX est
un tableau correspondant à l’ensemble P trié selon les abscisses (et selon les ordonnées pour
les points d’abscisses égales) et PY à l’ensemble P trié selon les ordonnées. Les ensembles
P , PX et PY contiennent les mêmes points P [i] (seul l’ordre change).
2. Écrivez un algorithme DiviserPoints qui calcule à partir de P les tableaux P gaucheX
(resp. P gaucheY) correspondant aux points de l’ensemble P gauche triés selon les abscisses
(resp. les ordonnées), de même pour les tableaux P droitX et P droitY. Montrez que cette
division peut être effectuée en O(n) comparaisons.
3. Notons δg (resp. δd ) la plus petite distance entre deux points de P gauche (resp. P droit), et
δ = min(δg , δd ). Il faut déterminer s’il existe une paire de points dont l’un est dans P gauche
et l’autre dans P droit, et dont la distance est strictement inférieure à δ.
a. Si une telle paire existe, alors les deux points se trouvent dans le tableau PY’, trié selon
les ordonnées, et obtenu à partir de PY en ne gardant que les points d’abscisse x vérifiant
l − δ ≤ x ≤ l + δ. Donnez un algorithme qui calcule PY’ en O(n) comparaisons.
b. Montrez que si 5 points sont situés à l’intérieur ou sur le bord d’un carré de coté a > 0,
alors la distance minimale entre 2 quelconques d’entre eux est strictement inférieure à a.
c. Montrez que s’il existe un point pg = (xg , yg ) de P gauche et un point pd = (xd , yd ) de
P droit tels que dist(pg , pd ) < δ et yg < yd , alors pd se trouve parmi les 7 points qui suivent
pg dans le tableau PY’.
d. Donnez un algorithme, en O(n) comparaisons, qui vérifie s’il existe une paire de points
dans P gauche et P droit dont la distance est strictement inférieurs à δ, et si oui la retourne.

16
4. En déduire un algorithme recherchant 2 points à distance minimale dans un ensemble de n
points.
5. Donnez la relation de récurrence satisfaite par le nombre de comparaisons effectuées par cet
algorithme. En déduire sa complexité.

Solution:
1. On supppose que l’on dispose d’une p fonction dist qui calcule la distance euclidienne entre
deux points (rappel : dist(p0 , p1 ) = (x1 − x0 )2 + (y1 − y0 )2 ).
P l u s P r o c h e s N a i f( P )
Entrée : tableau de points P
Sortie : ( P 0 , P 1 )
n ← l o n g u e u r( P );
( min , P 0 ,P 1 ) ← (∞ ,0 ,0);
pour i de 1 \ ‘a n -1}
pour j de i +1 \ ‘ a n }
s i dist ( P[i],P[j] <min ) a l o r s
( min , P 0 ,P 1 ) ← ( dist ( P[i],P[j],i , j );
finsi
f i n pour
f i n pour
retourne ( P 0 , P 1 )
fin
Cet algorithme utilise 2 boucles imbriquées sur P, donc sa complexité est O(n2 ).
2. On suppose que, pour les points (couples abscisse, ordonnée), on dispose des relations
d’ordre <x et <y sur les abscisses et les ordonnees. On suppose également, pour cette
question, qu’il n’y a pas de points confondus.
D i v i s e r P o i n t s( PX , PY )
Entrée : t a b l e a u x de points PX , PY
Sortie :( l , PGX , PDX , PGY , PDY )
n ← l o n g u e u r( PX );
PGX ← PX[1..⌊ n2 ⌋];
PDX ← PX[⌊ n2 ⌋ + 1..n];
PGY ← C r e e r T a b l e a u [1..⌊ n2 ⌋];
PDY ← C r e e r T a b l e a u [⌊ n2 ⌋ + 1..n];
g , d ← 1;
med ← PGX[⌊ n2 ⌋];
pour i de 1 à n f a i r e
s i PY[i] <x med ou ( PY[i] =x med et PY[i] <y med ) a l o r s
PGY[g] ← PY[i];
g ← g +1;
sinon
PDY[d] ← PY[i];
d ← d +1;
finsi
f i n pour

17
 retourne ( med .x , PGX , PDX , PGY , PDY );
fin
On fait un seul passage sur PY, on a donc O(n) comparaisons.
3. a. B a n d e V e r t i c a l e( PY ,δ ,l )
Entrée : tableau de points PY , d i s t a n c e δ , a b s c i s s e
Sortie : PY ’
j ← 1;
pour i de 1 à n
s i PY[i] ≥x (l − δ, 0) et PY[i] ≤x (l + δ, 0) a l o r s
PY ’[j] ← PY[i];
j ← j +1;
finsi
f i n pour
retourne PY ’
fin
On parcourt PY une fois et on fait deux comparaisons à chaque fois, on a bien O(n)
comparaisons.

b. Supposons qu’il existe 5 points à l’interieur d’un carré C de côté a et que la distance
minimale entre 2 de ces points soit supérieure ou égale à a. Découpons ce carré en 4
cases comme le montre la figure qui suit. On obtient des petits carrés de côté a2 . La
diagonale d’un petit carré est de longueur √a2 . 2 points situés dans le même petit carré
sont donc à une distance strictement inférieure à a. Pour que la distance minimale
entre 2 points du carré C soit supérieure ou égale à a, il faut donc que ces points se
trouvent dans des petits carrés différents. On ne peut placer ainsi que quatre points,
l’hypothèse de départ est donc absurde. 

c. Soit P0 un point de PY’. Supposons qu’il existe un point P1 dans PY’ tel dist(P0 ,P1 )
< δ et y0 < y1 . P1 se trouve obligatoirement dans le rectangle R compris entre les
ordonnées y0 et y0 + δ (voir figure suivante). Combien peut-il y avoir de points, au
maximum, dans ce rectangle ? D’après la question précédente, dans le carré qui se
trouve à gauche de ∆, il y en a au maximum 4. Il en va de même pour le carré à
droite de ∆ (voir figure suivante). Il peut donc y avoir au plus 8 points dans R, P0
compris, donc si P1 existe, il se trouve parmis les 7 points qui le suivent dans PY’. 

d. D e P a r t E t D a u t r e( PY ’ ,δ )}
Entrée : tableau de points PY ’ , d i s t a n c e δ
Sortie : ( booléen , P 0 , P 1 )
δmin ← δ; r e s u l t a t ← ( FAUX ,0 ,0);
pour i de 1 à l o n g u e u r( PY ’)
j ← i +1;
tantque j ≤ l o n g u e u r( PY ’) et j ≤ i +7
s i dist ( PY ’[i],PY ’[j])< δmin a l o r s
δmin ← dist ( PY ’[i],PY ’[j]);
r e s u l t a t ← ( VRAI ,i , j );

18
 finsi
j ← j +1;
fint a nt que
f i n pour
retourne r e s u l t a t;
fin
On parcourt PY’ une fois, etr pour chaque point, on fait 7 comparaisons. DePar-
tEtDautre est bien O(n) en nombre de comparaisons.
4. P l u s P r o c h e s( PX , PY )}
Entrée : t a b l e a u x de points PX , PY
Sortie : ( P 0 , P 1 )
s i l o n g u e u r( PX )≤3 a l o r s
retourne P l u s P r o c h e N a i f( PX );
finsi
( PGX , PDX , PGY , PDY ) ← D i v i s e r P o i n t s( PX , PY );
( PG 0 , PG 1 ) ← P l u s P r o c h e s( PGX , PGY );
( PD 0 , PD 1 ) ← P l u s P r o c h e s( PDX , PDY );
δg ← dist ( PG 0 , PG 1 ); δd ← dist ( PD 0 , PD 1 );
s i δg < δd a l o r s
δ ← δg ; ( P 0 ,P 1 ) ← ( PG 0 , PG 1 );
sinon
δ ← δd ; ( P 0 ,P 1 ) ← ( PD 0 , PD 1 );
finsi
PY ’ ← B a n d e V e r t i c a l e( PY );
(b , P ′0 ,P ′1 ) ← D e P a r t E t D a u t r e( PY ’ ,δ );
s i b = VRAI a l o r s
( P 0 ,P 1 ) ← ( P ′0 ,P ′1 );
finsi
retourne ( P 0 ,P 1 );

5. La relation satisfaite par le nombre de comparaisons effectuées est :

n
T n(n) = 2T ( ) + O(n)
2
La complexité de cet algorithme est donc O(n log n)

19