TD2EEA .pdf
Nom original: TD2EEA.pdf
Ce document au format PDF 1.4 a été généré par TeX / pdfTeX-1.40.10, et a été envoyé sur fichier-pdf.fr le 09/02/2011 à 18:05, depuis l'adresse IP 134.59.x.x.
La présente page de téléchargement du fichier a été vue 1300 fois.
Taille du document: 173 Ko (3 pages).
Confidentialité: fichier public
Aperçu du document
Exercice 1
Donnés : T[1....n]
1|
2|
f o r i ∈ [ 1 . . . n−1]
k ←− i
(C)
3|
f o r j ∈ [ i +1 . . . n ]
4|
5|
i f T[ j ] < T[ k ]
k←− j
6|
(C’ )
(C’ ’ )
T[ i ↔ k ]
On à utiliser jusqu’a aujourd’hui toute les regles du cours a part celle de la recursion pour calculer la compléxité
(Voir Analysis of Algorithms : Running time dans le cours)
W(1) est une boucle , même si c’est un for il s’agit d’une boucle tout comme while , on se refere donc à la regle
№3 du cour
P#.of.iterations
(W(while (C) S = i
(W (C) + W (S))
W (P r) =PW (1)
W (1) = n−1
i=1 (W (C) + W (2) + W (3) + W (6))
W (C) = 0 car on fait 0 comparaison entre les elements 6= comparaison entre indices
W (2) = 0 comparaison
W (6) = 0 comparaison
W (C 0 ) =P0
W (3) = nj=i+1 [W (C 0 ) + W (4)]
W (4) = W(C”) + W(5) = 1
W (C 00 ) = 1 car on fait une seule comparaison T[j]<T[k]
W (5) = P
0
Pn
W (1) = n−1
j=i+1 1
i=1 ·
On
Pn Calcule de
Pnla somme
Pila plus imbriquée vers l’exterieur
j=i+1 1 =
j=1 1 −
j=1 1 = n − i
Donc :
Pn−1
Pn−1
Pn−1
W(1) = i=1 (n − i) = i=1 n − i=1 i = n(n − 1) − n(n−1)
2
= n(n−1)
⇒ O(n2 )
2
(en comptant la comparaison en temps constant)
ATTENTION : Si on ne considère pas les affectation comme prenant un temps constant on à que
T[i ↔ k] necessite 3 affections , affectation utilisé avec des variable tampon pour faire la permutation.
Pn−1
Notes pour le calcul : i=1 n = n(n − 1)
Pn−1
n(n−1)
i=1 =
2
1
Pour chercher un element dans un tableau l’algo minimal :
T[ i ]
i ←− 1
w h i l e i ≤ n et T [ i ] 6= x
i ++
return ( i ≤ n)
−→ Complexite en O( n )
−→ Algo MASTER
i ←− 1 , T [ n+1] ←− x
w h i l e T [ i ] 6= x
i++
return ( i ≤ n)
−→ Algo Super MASTER
Exercice 2
L ’ a l g o de c e t exemple c a l c u l l e pgcd
x
y
1|
←− q u e l c o n q u e dans N
←− q u e l c o n q u e dans N
w h i l e ( x != y )
2|
−→ C
if x > y
−→ C’
3|
x ←− x − y
4|
e l s e y ←− y − x
5|
return x
W (P r) =PW (1) + W (2)
W (1) = x−1
i=1 [W (C) + W (2)]
W (C) = O(n)
W (2) = W (C 0 ) + max(W (3), W (4))
W (C 0 ) = O(n)
W (3) = O(n)
W (4) = O(n)
Donc
Px−1
i=1
[W (C) + W (2)] =
Px−1
i=1
O(n) = O(x ∗ n)
n = log x ⇒ 2n = x
La compléxité au final est en O(2n n) temps exponentiel
2
Le p i r e c a s : quand y
Exos hors TD en SuperUltraMegaMasterDeLaMort
1|
w h i l e ( y != 0 )
2|
3|
4|
r ←− x
x ←− y
y ←− r mod y
5|
return r
W (P r) = W (1)
Le nombre exact d’opérations en fonction de n est n3
(ici pas de de O(...) car le resultat est exact , on utilise O(n) si on parle de compléxité)
Preuve (hors partiel):
∀ x ∀ y ∃ q ∃ r ( x = y q + r
V
x>y
x mod y
x = d i f f (x
cas 1
:
y >
, y) ∗ y
x
2
⇔ 2 >
V
x
y
r < y)
⇔ ≤ < 2 div (x , y) = 1
x = y + x mod y ⇔ x mod y = x − y <
cas 2
Plogy
i=1
:
y ≤
x
2
x
2
x mod y < y ≤
(W (C) + W (2) + W (3) + W (4)) −→ O(n2 )
n = max( log x log y) =⇒ O(n3 )
3
x
2



Sur le même sujet..
utilise
return
boucle
complexite
while
exercice
affectation
cours
chercher
constant
master
comparaison
exact
notes
temps