TD : Complexité

Exercice 1. On considère les algorithmes suivants. while j ≤ i 2 do

k := 0
Algorithme 1. function(n) Algorithme 3. while k ≤ j do
function(n) S←0 function(n) s := s + 1
S←0 for i = 1 to n do S←0 k := k + 1
for i = 1 to n do for j = 1 to i P ←1 end while
S ← S +3× i do while P < n do j := j + 1
end for S ← S+ P ← 5×P end while
S 12(i + j) S ← S +3×P i := i + 1
end for end while end while
end for S
S Exercice 3. Écrire un algorithme simple qui permet de déterminer si
Algorithme 2. un nombre est premier. Quelle est sa complexité exprimée en fonction
de la taille de l’entrée supposée donnée en binaire.
1. Pour chaque algorithme déterminer la fonction complexité.
Exercice 4. On rappelle l’algorithme suivant vu au TD1.
2. À quelle classe de complexité appartiennent ces algorithmes ? Algorithme 7. Calcul de a n
function puiss(a, n)
Exercice 2. Même exercice.
A := a;
N := n;
Algorithme 4. function(n) Algorithme 5. function(n)
R := 1
s := 0 s := 0
while N > 0 do
i := 0 i := 0
if N pair then
while i ≤ n do while i ≤ n do
A := A × A
j := 0 j := 0
N := N/2
while j ≤ n2 do while j ≤ i do
else
s := s + 1 s := s + 1
R := R ∗ A
j := j + 1 j := j + 1
N := N − 1
end while end while
end if
i := i + 1 i := i + 1
end while
end while end while
return R
Algorithme 6. function(n)
Déterminer la complexité de l’algorithme.
s := 0
i := 0 Exercice 5. Reprendre l’échelle des comparaisons des classes de
while i ≤ n do complexité donnée dans le cours. En considérant une machine effectuant
j := 0 109 opérations seconde (GigaHertz) donner les temps machine pour

1MITH2129: Fondements théoriques de l’informatique UL-UTBM-UTT-EMA

TD : Complexité

traiter des données de taille n = 10, 100, 1000, 1000 ? Pour chaque end while
classe quelles sont les tailles des données qui peuvent être traité en Prouver que l’algorithme calcule q = a div b et r = a mod b. Quelle
un jour ? un an ? est sa complexité ?

Exercice 6. On considère deux algorithmes A1 et A2 qui fournissent Exercice 8. On considère l’algorithme de tri, dit de tri sélection,
le même résultat. On suppose que l’analyse de chacun a permis composé des deux algorithmes suivants:
d’établir les fonction complexités temporelles, notées f 1 et f 2 vérfient Algorithme 9. function M inimum(T, j)
f 1 ∈ Θ(n2 ) et f 2 ∈ Θ(n ln(n)). i← j
1. On suppose que A1 et A2 nécessitent t = 100 pour traiter des m ← T[ j]
données de taille n = 100. En déduire le temps nécessaire pour for k = j + 1 to n do
traiter des données de taille n0 = 10000 pour chaque algorithme. if T[k] < m then
i←k
2. Une étude expérimentale des deux algorithmes A1 et A2 montre m ← T[k]
qu’en première approximation on a end if
end for
f 1 (n) ≈ 3n2 et f 2 (n) ≈ 2500n ln(n) (1)
Return i
(a) Quel est le meiller algorithme pour n grand ?
Algorithme 10. function T ri_sel ection(T)
(b) En étudiant des fonctions à choisir, montrer qu’il existe for j = 1 to n − 1 do
une valeur de seuil n 0 en dessous de laquelle le réputé i ← M inimum(T, j)
moins bon est en fait le meilleur. if i 6= j then
Échanger T[i] et T[ j]
Exercice 7. On considère l’algorithme suivant
end if
Algorithme 8. function(a, b) end for
r := a
q := 0 Étudier la complexité de cet algorithme et comparé avec l’algorithme
x := b de tri-fusion vu en cours.
while x ≤ a do
x := 2x Exercice 9. [d’après final] Dans cet exercice on étudie un algorithme
end while extrèmement important en ingénierie et en sciences en général connu
while x 6= b do sous le nom d’algorithme FFT (Fast Fourier Transform).
q := 2q
x := x div 2 Mathématiquement faire la transformée de Fourier d’un vecteur
x0
 
if x ≤ r then
 . 
r := r − x x revient à transformer ce vecteur x =  ..  en un vecteur y =
q := q + 1 x N −1
end if

1MITH2129: Fondements théoriques de l’informatique UL-UTBM-UTT-EMA

TD : Complexité

y0
 
4. Quel type d’algorithme peut-on envisager pour calculer la transformée
.. de Fourier de x en se basant sur ce principe ? (on ne demande
 tel que y = Ax avec
 
 .
yN −1 pas d’écrire un tel algorithme mais d’expliquer la stratégie qui
peut être mise en jeu).
1 1 1 ... 1
 
1
 ω ω2 ... ω N −1   La complexité
1
 ω2 ω4 ... ω2( N −1)  Les questions précédentes montrent que le calcul de la transformée
A=
1 ω3 ω6 ... ω 3( N −1) 
 (2) de Fourier d’un vecteur x de taille N peut s’obtenir en calculant
.. .. .. .. la transformée de Fourier de deux vecteurs de tailles N/2 (xpair et
 
.
 
1 . . .
ximpair ). On admet que le nombre d’opérations élémentaires (coût)

2
N −1
1 ω ω2( N −1) ... ω( N −1)
pour reconstituer y à partir des transformées y1 (transformée de xpair )
Dans l’écriture de A, ω est une racine N-ème de l’unité, c’est à et de y2 (transformée de ximpair ) est proportionel à N. On notera ce
dire un nombre complexe tel que ω N = 1. On choisit ω = e−2 iπ/ N . Pour coût aN où a est une constante réelle.
simplifier les calculs on supposera dans tout ce qui suit que N = 2n .
1. On note f 2 la fonction complexité du calcul de y basée sur le
Le principe principe précédent. Montrer que
Afin de calculer rapidement y, on remarque que le coefficient yk
f 2 (N) = 2 f 2 (N/2) + aN. (4)
est donné par:
NX
−1 ln(N)
yk = x0 + x1 ωk + x2 ω2k + x3 ω3k + · · · + x N −1 ω( N −1)k = x j ω jk (3) 2. Vérifier que f 2 (N) = N + aN est bien solution de (4).
ln(2)
j =0
3. Quelle est la complexité d’un algorithme basé sur ce principe ?
On considère les deux polynômes suivants,
4. Estimer rapidement la complexité du calcul permettant d’obtenir
p pair (t) = x0 + x2 t + x4 t2 + x6 t3 · · · + x N −2 t( N −2)/2 y sans l’algorithme FFT.

Exercice 10. Dans cet exercice on s’intéresse à la multiplication

p impair (t) = x1 + x3 t + x5 t2 + x7 t3 · · · + x N −1 t( N −2)/2 .
de deux matrices. La complexité d’un algorithme réalisant cette
1. Montrer que yk = p pair (ω2k ) + ωk p impair (ω2k ). opération est mesurée en comptant le nombre de multiplications
effectuées (la multiplication est plus coûteuse que l’addition). L’algorithme
2. Soit ω̃ = e−2 iπ/( N /2) est une racine N/2-ème de l’unité. Vérifier
de Strassen est un algorithme pour le calcul du produit de deux
que ω2 = ω̃.
matrices dont la complexité est meilleure que l’algorithme naïf.
3. À l’aide des deux questions précédentes, montrer que si on
1. Cas des matrices 2 × 2. Soit le produit de deux matrices de taille
connaît la transformée de Fourier des vecteurs xpair = (x0 , x2 , . . . , x N −2 )
2 × 2,
et ximpair = (x1 , x3 , . . . , x N −1 ) on peut reconstruire la transformée
de Fourier de x (on remarquera que xpair et ximpair sont des
µ ¶ µ ¶ µ ¶
a 11 a 12 b 11 b 12 c 11 c 12
A×B = × = =C
vecteurs de taille N/2). a 21 a 22 b 21 b 22 c 21 c 22

1MITH2129: Fondements théoriques de l’informatique UL-UTBM-UTT-EMA

TD : Complexité

(a) Combien de multiplications sont nécessaires pour calculer (b) Soit u k le nombre de multiplications nécessaires pour
tous les coefficients c i j par la définition du produit matriciel calculer le produit de deux matrices A et B de tailles 2k ×2k .
vue en cours ? Montrer que si on applique les formules de Strassen on a
(b) Considérons les produits suivants : u k = 7u k−1 .
(c) Toujours en utilisant la méthode de Strassen, que vaut u 1
?.
 (d) En déduire qu’il faut u k = 7k multiplications pour réaliser
q 1 = (a 11 − a 12 )b 22 q 2 = (a 21 − a 22 )b 11
le produit de deux matrices de taille 2k × 2k .



 q = a (b + b )
3 22 11 21 q 4 = a 11 (b 12 + b 22 )
ln(7)

 q 5 = (a 11 + a 22 )(b 22 − b 11 ) q 6 = (a 11 + a 21 )(b 11 + b 12 ) (e) Posons n = 2k et montrer que u k = n ln(2) ' n2.81 (on pourra
poser u k = nα et chercher à déterminer α).

 q = (a + a )(b + b )
7 12 22 21 22

(f) Si on applique la méthode classique vue en cours pour

Vérifier qu’on retrouve la matrice C en effectuant les opérations
calculer le produit de deux matrices A × B de taille n × n
suivantes :
combien de multiplications en fonction de n sont nécessaires
?
c 11 = q 1 − q 3 − q 5 + q 7
c 12 = q 4 − q 1 (g) Application numérique : pour multiplier deux matrices de
c 21 = q 2 + q 3 taille 128 × 128 combien de multiplications économise-t-on
c 22 = − q 2 − q 4 + q 5 + q 6 en utilisant les formules de Strassen à la place du calcul
classique ?
(c) Conclure que les formules de Strassen permettent de calculer
le produit A × B en effectuant 7 multiplications. Qu’a-t-on Remarque : Le cas général où A et B sont des matrices de tailles
gagné ? n × n avec 2k−1 < n < 2k se résout en complétant les matrices par des
zéros de sorte à obtenir deux matrices de tailles 2k × 2k .
2. Cas des matrices n × n avec n = 2k :

(a) Soient A et B deux matrices de tailles n × n = 2k × 2k . On

découpe ces matrices en blocs (les sous-matrices sont de
taille 2k−1 × 2k−1 ) :
µ ¶ µ ¶
A 11 A 12 B11 B12
A= et B =
A 21 A 22 B21 B22
µ ¶
C 11 C 12
et on note C = le produit A × B.
C 21 C 22
Écrire les formules de Strassen par blocs et vérifier qu’elles
permettent de calculer C.

1MITH2129: Fondements théoriques de l’informatique UL-UTBM-UTT-EMA