0 évaluation0% ont trouvé ce document utile (0 vote) 81 vues5 pagesCorrection TD Complexite Final
Copyright
© © All Rights Reserved
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
TD - Complexité des algorithmes
Module INF301 ~ IMT Lille Douai
1 Temps d’exécution et taille des problémes
On considére une machine capable d’exéeuter une instruction en 10-® secondes.
Questions
1, Dans la Table[I] indiquer, pour chaque complexité algorithmique, la taille maximale Rinax
des données que l'on peut traiter avec un algorithme de cette complexité en un temps t
donné,
Soit ala durée d'une instruction
Soit Fla fonction de compléxité
On cherche ninas tel que c .f(Minax) = t
t Ollogs(n)) O(n) O(nloge(n)) | O(n*) O(n?) | O(2")
I seconde 210% 10" 3.7 * 10° 10¢ 464 ba
1 jour 2s | s6e10'2] 20410 | 29"10%| 216108) 43
Jan gato | 31610 | 6.110% | 5.64107 | 1.5«105 S1
| Fonction | 2# t ae log,’
as log(n)
O(loga(n)) - Recherche Dichotomique (dans un tableau trig)
sieth >Oetb# 1 alors logs(:r) = y peut s*écrire sous la forme x = bY.
O(n) - Recherche Séquentielle dans une liste
loga(n) =~
n
O(n.loga(n)) - Tri par comparaisons optimaux (Tri par tas)
On utilise la méthode de Newton ou la méthode de point fixe oft ri41 = 2, — HE)
O(n?) - Tri par sélection
x’ = y donne 2 solutions ¥/¥ et — yg, b = 2, alors 2 > 0
O(n) - Multiplication matricielle naive
ax at
r= au
0(2") - Algorithme du simplexe (dans le pire des cas) a
D’aprés les propriétés du logarithme, Logo(:r) = 42 = toga)
_ int
~ In(2) 2. On considére maintenant une machine 10 fois plus rapide (qui exéeute done une instruc-
tion en 10-® secondes). Calculez la quantité de données maximum que l'on pourra traiter
en une heure avec un algorithme de complexité
{a) O(loga(n))
(b) O(n)
(©) 002”).
10 4 988108 _ 93.6610!2
Ologe(n)) en I heure =
O(n) en I heure = 10+ 3.6 « 10" = 3.6 « 10"?
O(2") en I heure = logy(10) + 38 = 41
2 Propriétés asymptotiques des fonctions
Ces propristés sont-elles vraies ou fausses? Démontrez. vos réponses.
1. Si p(n) = DE, ajni,a; € Rt, alors p(n) = O(n*). Vrai
2, Si f(n) = O(g(n)), alors g(n) = O(f(n)). Faux
Mm, 1x F(nk)< P(n) < cp x F (nk)
1 x F(nk)< dew < @ x F(nk)
LX F(II)S wotaun azn. taut < op x F(nk)
AS wtatatuta So
mo C2 no e-Da
cin)
Démonstration graphique :
Sif(n) = O(G(n)) alors :
alors f(n) < C2* G(n) vrai
flo)
et Gln) < C2*A(n) faux:impossible de
trouver une constante C2
Démonstration algébrique :
Vn>1,1 < nel
f=R>R = ROR Done vn > 1, |f(n)| < |g(n)|*1
a n->n Done f(n) = O(g(n))
Supposons qu'il existe k>0 et n, >0 tel que Yn > nO Ig(n)| < [f(nyItk
Onadonc: ¥n>n, In| <=k
mais également n>k, ce qui se contredit
En particulier, soit n = In,|+k+1, on a n>} 3. Matrices
On considére les Algorithmes[I]et [2] sur les matrices rectangulaires de Mm,n(Z).
1. Calculez les complexités en temps et en espace de Algorithme []]
Algorithme 1 + Somme de matrices,
1 fonction somme(m1 : Matrice, m2 : Matrice) : Matrice
entrée : ml : matrice de taille m x n
m2: matrice de taille m xn
sortie : m12: matrice de taille m xn, m12 = m1 + m2
2 | pour SEWN AEN) faire complesté algorthmique > O10 | 6 igyqy
3 pour GEMMA) faire complexité algorithmique -> o{n)_|O"'")
4 | 2G] GGMANGY —Affectation qui dépend des 2 boucles donc de met n
5 fin complexité mémoize -> O(en"n)
6 | fin
7 | retourner ml2
5 fin
2. Justifiez que la complexité au meilleur cas, en moyenne et au pire cas de l’Algorithme|
sont identiques,
complexité au meilleur cas = moyen cas = pire cas
Les complexités sont identiques car on doit parcourir l'ensemble des valeurs du tableau
3. Calculez les complexités en temps et en espace de l’Algorithme 2]
Algorithme 2: Produit de matrices,
1 fonction produit (mi : Matrice, m2 > Matrice) : Matrice
entrée : ml : matrice de taille m x n
m2 : matrice de taille n x p
sortie : ml2: matrice de taille m x p, m12 = ml.m2
2 | pour KOREAN faire complexité algorithmique -> O(m)
a pour GME) faire complexitéalgoithique > O10) | .q)
4 ml2{ilf] — 0
5 pour REANIM faire complexité algorithmique -> O(n)
6 | L2G) SMUG AMY YRMAMA| GY complexité mémoice-> O(m“p)
7 fin taille dela matrice
8 fin
9 fin
10 retourner m12
u fin
4. Exprimez les complexités en temps des Algorithmes[i]et [jdans le cas de matrices carrées
nxn.
Algorithme 1: sil'on considére des matrices carrées, alors m = n -> O(n‘n) - > O(n2)
Algorithme 2: m =n, p=n-> O(n‘n‘n) -> O(n3) 4 Ensembles
On dispose de I’AlgorithmefJ] permettant de calculer les parties d'un ensembles. L’opération
insere(e : Element, E : Ensemble): Ensemble instre un élément e dans un ensemble E qui
ne le contient pas déja. On considérera qu’elle a une complexité en @(1).
Questions
1. Dérouler Algorithme [i] pour les instances suivantes : E = {1,2}, B = {1,23}, B=
{1,2,3,4}
‘Algorithme 3 Cala des parios Pan osebTe
1 Fonction Pores E Tableau dléments): Tableau ensemble elements
‘Données: Ensembie elements
Résultat: P: Ensemble clments + ensemble des pats de E
tmp, : tableau densemble
tmp. falenn densemble
Petlell:
Pour (de 06 longueur de E-1) faire
tmp 6:
POUT (de 00 longueur de P-1) aire
tmp inserer EG. PD)
tmpye-insereramp,.tmp,)|
fin
PePUtmnpy
fm
ts | retourner P
4 fn
= ° wane a =r
+ 137 T T TTT
3 ter 7 , Ts
: ish ; * a
: i o : as TI
: ier a ‘a : =
i wy a in ‘ i 8
: ‘ont a ta : 3
i tie) a 2 i 5 Bh arn
Hi ten o : 3
: tom a : a ee
: torn 2 (a Ee mestmre onsets
; ‘oath a ia rr)
° io. teh cary ae 2h |
sortie si € = {1,2}
: a
; tmmacal fa rr}
: (erment! o —— oo}
: tea a on |
: (eeima ote |
; Vera a) easy a tl
; (emacs Gy tanh
: tema! |
: imaaen Gy mmm
: (mmarial dam tou)
Sta i iia see ieesesstitiem sortio si E = {12,3}
E={1,2}->P={ 0), {1}, 2), (1.2}}
E= {1,23} -> P= {{}, {1}, (2), {1.2}, (3), {1.3}, {2,3}, {12,3} }
E= {12,34} -> P= {{}, (1h, (23, €1.2), {3}, {1,3}, {2,3}, (1.2.3), (4), 1.4}, (2.4), (1.2,4}, (3,4), (1,3,4), (2,3,4}, (1.2.3.4) }
2. D'apris les résultats de la question précédente, que peut-on dire sur la complexité en
mémoire de VAlgorithmeB?
Lacomplexité en mémoire est de O(2") otin est le nombre d'éléments de l'ensemble E (si ensemble =
ensemble des parties d'un ensemble E a n élément a pour cardinalité 2”.
unité).
3. En supposant que lopérateur d’union U a une complexité en @(1), calculer la complexité
de Algorithme B}
Chaque itération de P est deux fois plus longue que la précédente. On a donc le nombre d'opérations qui vaut :
142444. #27 = 29 F1-1 (suite géométrique) dont la compléxité en temps est de O(2"), 4, Ecrire un algorithme calculant union de deux ensembles.
‘Algorithme Union de deux eases
Table demons): Tabled
nf ET: Tableau dlémens
‘elements
‘Données: El : Ensemble slements
2: Ensemble d’ements
Résultat tes: Ensemble ements + union des ensembles Et et E2
| pour dea longuewr de ED) fae
4) [es inser Eire)
| fn
| por (de 0 longue de B21) fa
+ |] apparent FAUX
8 | pour (de 0. longueur de BI) fare
, si (EI[j] = EZ) alors
snpartient = VRAL
" fin
| | an
|| silappartent = FAUX) alors
4 res incere( EDI rs)
| | fa
te | fn
| retoumer es
5. Calculer la complexité de cet algorithme,
La complexité de cet algorithme est de O(n2), olin est la taille des ensembles E1 et E2.
6. En utilisant le résultat précédent, calculer la complexité effective de l’Algorithme|
Notons na a taille de E et nb la taille de P.
La complexité de l'algorithme 3 était de O(2") quand la fonction insérer était estimée 4 une complexité de O(1).
‘Or, on sait que la complexité de la fonction insérer est égale 4 O(nb’).
Etant donné que nb = 22, on a alors la complexité totale de l'algorithme 3 qui est égale a:
O{nb?) = O( (2"7)") = O14")
joints, modifier
7. En remarquant qu’a la ligne 8 de Algorithme] P et tmp-p sont
VAlgorithme fi] pour qu’il ait une complexité en @(2") (avec n la taille de Pensemble
entrée).
“Algorithme: Calcul des partes un ensemble optimise
1 Fonetion Parties(E: Tableau d'eléments): Tableau ensemble ements
Données : E: Ensemble 'élements
[Résultat : P Ensemble d'éléments ~> ensemble des panies de E
2 | tmp, : tableau d'enserable
| Ptloll
4 | pour (ide 0 a longuewrde E-1) faire
: pour (j de 0d longueur de P -1) faire
‘ timp. inserer(Eli}, PUD
P+ inserertmp., P)
fin
fin
w | retourner P
fn
Vous aimerez peut-être aussi
