Scribd
Importer
5 vues4 pages

Analyse de la complexité des algorithmes

Le document présente des exercices sur la complexité algorithmique, couvrant divers algorithmes de tri et de recherche, ainsi que le problème des Tours de Hanoï. Chaque exercice analyse les cas de complexité (pire, meilleur et moyen) et fournit des pseudo-algorithmes pour illustrer les solutions. Les résultats incluent des formules pour le temps d'exécution et des analyses de complexité, notamment O(n log n) pour certains algorithmes.

Transféré par

eya azzabi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
5 vues4 pages

Analyse de la complexité des algorithmes

Le document présente des exercices sur la complexité algorithmique, couvrant divers algorithmes de tri et de recherche, ainsi que le problème des Tours de Hanoï. Chaque exercice analyse les cas de complexité (pire, meilleur et moyen) et fournit des pseudo-algorithmes pour illustrer les solutions. Les résultats incluent des formules pour le temps d'exécution et des analyses de complexité, notamment O(n log n) pour certains algorithmes.

Transféré par

eya azzabi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Correction TD2 complexité

Exercice 1

Le résultat correspond au pire des cas

Pire ∑𝑛𝑖=2 (𝑖 − 1) = n(n-1)/2


Meilleur cas on a 1 comparaison =>au total n-1 comp
Cas moyen ∑𝑛𝑖=2 (𝑖 − 1)/2 = n(n-1)/4
On traite également les décalages

Pire ∑𝑛𝑖=2 (𝑖 − 1) = n(n-1)/2


Meilleur cas 0 décalage
Cas moyen ∑𝑛𝑖=2 (𝑖 − 1)/2 = n(n-1)/4
Exercice 2

Pour i de 1 à n-1
Min =i
Pour j de i+1 à n
Si t[j]< t[min] alors min = j fsi
Fin pour
Si i<>min alors permuter t[i] et t[min] fsi
Fin pour

I=1 n-1 comp


I=2 n-2 comp
:
I=n-1 1 comp

∑𝑛−1
𝑖=1 𝑖 = 𝑛(𝑛 − 1)/2

De 0 (meilleur cas) à n-1 (pire des cas) permutations

Exercice 3

Pour i de 1 à max+1
Count[i]=0
Fin pour
Pour i de 1 à [Link] de T faire (taille de T)
Count[T[i]+1]= Count[T[i]+1]+1
Fin pour
K=1
Pour i de 1 à max +1 faire
Si Count[T[i]+1]<>0 alors
Pour j de 1 à count[i] faire
T[k]=i-1
k=k+1
Fin pour
Fin si
Fin pour
Cet algorithme effectue 0 comparaisons entre éléments du tableau

Le parcours du tableau se fait une seule fois , tri linéaire en O(n)

Exercice 4

Algorithme Dichotomie

procedure Recherche(T,x,d,f)
if f < d then
return Faux
else
m = (f+d)/2
if T[m] = x then
return Vrai
else if T[m] < x then
return Recherche(T,x,m + 1,f)
else
return Recherche(T,x,d,m − 1)
end if
end if
end if
end procedure

T(n)=T(n/2) + 1 car la recherche se fait soit à droite ou soit à gauche =>log 2n

T(n)=T(n/α) + (α-1) pire des cas (pour résoudre l’équation on pose n=αk)

T(n)=T(n/α) + 1 meilleur des cas

Pour le pire des cas on a T(αk)=1+k *(α-1) = > T(n)=1+ logα(n) *(α-1) ≈ (α-1)* logα(n)

Exercice 5

1_

ce qui est demandé c’est d’écrire un Pseudo-algorithme simple expliquant les étapes de résolution si
un étudiant a écrit la totalité de l’algorithme il ne sera pas pénalisé =>

Résoudre le problème de hanoï à n anneaux c'est-à-dire


déplacer les n anneaux du piquet A vers B en utilisant C revient à :

si n= 0 fin

sinon

déplacer les (n-1) plus petits anneaux de A vers C (utilisant B)

déplacer le nième anneau sur B

déplacer les (n-1) anneaux de C vers B (utilisant A)

finsi

2- Le temps de transfert global est exprimé comme suit :

T(n)=2 T(n-1) + 1 avec T(1)=1 ; T(0)=0

En développant cette expression (T(n-1) = 2 T(n-2) +1…………) on trouve que

T(n)= 1 + 2 + 2²+ ……..+ 2n-1 = 2n-1 (1+(1/2)+…….+ (1/2n-1 )) c’est une suite géométrique

= 2n-1 (1-(1/2n))/(1-(1/2))= 2n-1 (ou encore 2n si n tend vers l’infini n>>>)

3- 3-1 Le nombre total d’anneaux est n = k*m

3-2 le pseudo-algorithme associé :

déplacer les n=(m*k) anneaux du piquet A vers B en utilisant C revient à :

si n= 0 fin

sinon

déplacer les (m(k-1)) plus petits anneaux de A vers C (utilisant B)

déplacer les m anneaux du kième niveau sur B

déplacer les (m(k-1)) anneaux de C vers B

finsi

- Le temps de transfert global est exprimé comme suit :

T(n)= T(mk)= 2 T(n-m) + m= 2T(mk-m)+m =2T(m(k-1))+m avec T(m)=m ; T(1)=1 ; T(0)=0

En développant cette expression (T(n-m) = 2 T(n-2m) +m…………) on trouve que

T(n)= T(mk) = m (1 + 2 + 2²+ ……..+ 2k-1 )

= m 2k-1 (1+(1/2)+…….+ (1/2k-1 ))

= m 2k-1 (1-(1/2k))/(1-(1/2))= m(2k-1) (ou encore m2k )


Exercice 6

T(n)=2T(n/2) +fusion(n/2)

T(n)=2kT(1)+∑𝑘−1
𝑟=0 2𝑟 𝑓𝑢𝑠𝑖𝑜𝑛(2𝑘−𝑟−1 ) ; T(1)=1 fusion(m)≈O(m) => T(n)=2k+(2k /2)k ≈
O(nlogn)

Vous aimerez peut-être aussi