Upload
yahya-elamrani
View
225
Download
0
Embed Size (px)
DESCRIPTION
comp
Citation preview
TD3:ComplexitExercice 1:Calculer la complexit temporelle de l'algorithme 'Recherche dichotomique' dans le pire et dans le meilleur des cas. Comparer avec l'algorithme de recherche squentielle.
Exercice 2:1. Ecrire l'algorithme de la procedure Tri-insertion2(A) qui trie rcursivement le tableau A.
2. Est ce que la dfinition par rcurrence est vraiment utile dans cet exemple?
Exercice 3:Soient T1[n] et T2[n] deux tableaux tris par ordre croissant.(on suppose que n est une puissance
de2)
Ecrire l'algorithme qui permet de trouver llment central de ces deux tableaux (lment qui a autant dlments suprieurs stricts que dlments infrieurs ou gaux).
Exercice 4: Appliquer lalgorithme du tri fusion la suite de nombres suivante :
16 - 11 - 9 - 10 - 5 - 6 - 8 - 1 - 2 - 4
Exercice 5:Soit le tableau[10] suivant :
200 100 300 30 50 40 75 20 35 10
Appliquer lalgorithme du tri rapide
Exercice 6: Soit T un tableau dj tri
Soit a un entier (pas ncessairement dans T), crire un algorithme efficace pour vrifier sil existe deux lments x et y dans T tels que x + y = a.
Exercice 7: Soit T un tableau de taille n. Trouver le kime lement le plus petit.(Proposer un algorithme qui partitionne le tableau la faon du tri rapide).