Chapitre 3 informatique commune Corrigé des exercices Tris par comparaison  

Chapitre 3 informatique commune Corrigé des exercices Tris par comparaison  
Exercice 1 def minimum(t, j): if j == len(t)−1: return j i = minimum(t, j+1) if t[j] < t[i]: return j else: return i def select_sort(t, j=0): if j < len(t)−1: i = minimum(t, j) if i > j: t[i], t[j] = t[j], t[i] select_sort(t, j+1) def insere(t, j): if j > 0 and t[j] < t[j−1]: t[j−1], t[j] = t[j], t[j−1] insere(t, j−1) def insertion_sort(t, j=1): if j < len(t): insere(t, j) insertion_sort(t, j+1)  
Exercice 2 Observons la situation après avoir déjà trouvé les j plus petits éléments et déterminé l’endroit où se trouve l’élément j + 1 : 1 2 ··· j j + 1 non trié La partie non triée correspond à une permutation de S(⟦j + 1,n⟧). Si on les suppose toutes équiprobables, la probabilité pour que j + 1 soit situé à son endroit définitif et ne nécessite donc pas de permutation est égale à (n −j −1)! (n −j)! = 1 n −j . Le nombre de permutation moyen est donc égal à : n−2 X j=0  1 − 1 n −j  = n − n X k=1 1 k = n −lnn −γ + o(1).  
Exercice 3 Lorsqu’on parcourt le tableau (de la gauche vers la droite) en permutant deux éléments consécutifs à chaque fois que l’élément le plus petit se trouve à droite du plus grand, on est assuré en fin de parcours d’avoir placé le plus grand élément du tableau à sa place définitive, en ayant effectué n −1 comparaisons et au plus n −1 permutations. Il reste à réitérer le procédé sur le tableau privé de sa dernière case pour obtenir l’algorithme de tri bulle, ainsi nommé car les éléments les plus grands du tableau se dirigent vers leur place définitive à l’image des bulles d’air qui remontent à la surface d’un liquide. On rédige une fonction de « remontée » des bulles (jusqu’au niveau k) : def remonte(t, k): for j in range(k−1): if t[j] > t[j+1]: t[j], t[j+1] = t[j+1], t[j] puis la fonction de tri proprement dit : Jean-Pierre Becirspahic 3.2 informatique commune def bubble_sort(t): for k in range(len(t), 0, −1): remonte(t, k) Notons cn le nombre de comparaisons effectuées, et pn le nombre de permutations de deux éléments. Nous avons cn = n −1 + cn−1 et pn−1 ⩽pn ⩽pn−1 + n −1, donc cn = n(n −1) 2 et 0 ⩽pn ⩽n(n −1) 2 . Il s’agit donc d’un algorithme de coût quadratique, le pire des cas ayant lieu lorsque le tableau est trié à l’envers, car alors cn = pn = n(n −1) 2 . Remarque. Il est possible d’améliorer légèrement cet algorithme en observant que si lors d’une étape de remontée aucune permutation n’est effectuée, c’est que le tableau est trié, et qu’on peut donc s’arrêter là. Pour exploiter cette remarque on peut par exemple faire en sorte que la fonction remonte renvoie une valeur booléenne indiquant si aucune permutation n’a été réalisée. Ceci conduit à cette seconde version : def remonte(t, k): b = False for j in range(k−1): if t[j] > t[j+1]: t[j], t[j+1] = t[j+1], t[j] b = True return b def bubble_sort(t): b, k = True, len(t) while b and k > 0: b = remonte(t, k) k −= 1 Avec cette nouvelle version, le nombre d’échanges est inchangé mais le nombre de comparaisons n’est plus systématiquement quadratique. Dans le cas d’un tableau déjà trié, par exemple, cet algorithme n’effectue que n −1 comparaisons et aucune permutation. On peut aussi observer que le nombre de permutations effectuées reste identique dans chacune des deux versions, très précisément égal au nombre d’inversions de la permutation initiale (c’est à dire le nombre de couples (i,j) tel que i < j et t[j] < t[i]), au moins dans les cas où toutes les valeurs du tableau sont distinctes. Il n’est pas difficile de prouver que le nombre moyens d’inversions est égal à n(n −1) 4 , ce qui assure un coût quadratique en moyenne.  
Exercice 4 La version itérative de l’algorithme de tri fusion consiste à fusionner les cases deux par deux, puis quatre par quatre, huit par huit, etc. On peut utiliser la fonction fusion du cours, et la fonction de tri à proprement parler devient : def merge_sort(t): n = len(t) aux = [None] * n p = 1 while p < n: q = n // p for k in range(0, q−1, 2): fusion(t, k*p, (k+1)*p, (k+2)*p, aux) t[k*p:(k+2)*p] = aux[k*p:(k+2)*p] if q % 2 == 1: k = q −1 fusion(t, k*p, (k+1)*p, n, aux) t[k*p:n] = aux[k*p:n] p *= 2 Prouvons la validité de cet algorithme en supposant qu’après p −1 étapes on ait n = pq + r avec 0 ⩽r < p et que le tableau t soit la concaténation de q tableaux triés de longueur p et d’un tableau de longueur r. Deux cas sont à envisager : Corrigé des exercices 3.3 – si q = 2q′ est pair, les tableaux sont fusionnés deux par deux pour former des tableaux triés de longueur 2p et le dernier de longueur r n’est pas fusionné ; – si q = 2q′ −1 est impair, les tableaux sont fusionnés deux par deux pour former des tableaux triés de longueur 2p et le dernier de longueur p est fusionné avec celui de longueur r pour former un tableau trié de longueur p + r. En posant p′ = 2p et r′ = r ou t′ = p + r suivant la parité de q nous pouvons affirmer que n = p′q′ + r′ avec 0 ⩽r′ < p′ et le tableau t est maintenant constitué de q′ tableaux triés de longueur 2p et d’un tableau trié de longueur r′. L’algorithme se termine lorsque p > n car alors q = 0 et r = n.  
Exercice 5 a) Lors du tri par insertion d’un tableau déjà 2-trié, le nombre maximal d’échanges est obtenu lorsque les termes d’indices impairs sont tous inférieurs aux termes d’indices pairs. Dans cette situation, le nombre d’échanges effectués est égal à 1 + 2 + ··· + ln 2 m = p(p + 1) 2 avec p = ln 2 m . Le tableau trié prend alors la forme : (a1,a3,a5,...,a0,a2,a4,...). b) Partons d’un tableau trié, par exemple (1,2,3,4). Pour que le nombre d’échanges par le 1-tri soit maximal, il faut qu’à l’étape précédente on soit en présence du tableau (3,1,4,2). De même, pour que le nombre d’échanges par le 2-tri soit maximal, il faut qu’à l’étape précédente on soit en présence du tableau (4,2,3,1). Ce dernier tableau nécessite donc 5 échanges pour être trié par le tri de Shell : à la première étape (le 2-tri), 2 échanges le transforment en (3,1,4,2), à la seconde étape (le 1-tri), 3 échanges en transforment en (1,2,3,4). C’est la même chose pour n = 8 en partant de (1,2,3,4,5,6,7,8). Avant le 1-tri, il faut avoir (5,1,6,2,7,3,8,4), avant le 2-tri, (7,3,5,1,8,4,6,2), et avant le 4-tri, (8,4,6,2,7,3,5,1). Avec ce dernier tableau, le tri de Shell effectue 20 échanges. c) Le tri de Shell étudié ici revient à trier récursivement les termes pairs et impairs séparément puis à appliquer le 1-tri (le tri par insertion) au tableau obtenu. D’après la première question, le nombre maximal d’échanges effectués vérifie la relation : C(2p) = 2C(2p−1) + 2p−1(2p−1 + 1) 2 , soit : up = 2up−1 + 2p−2(2p−1 + 1). Écrivons : up 2p = up−1 2p−1 + 2p−1 + 1 4 de manière à réaliser un télescopage. Sachant que u0 = 0 on obtient : up = 2p p−1 X k=0 2k + 1 4 = 2p−2(2p −1 + p) = 2p(2p −1) 4 + p2p−2. Lorsque n = 2p, le nombre d’échanges effectués est égal dans le pire des cas à n(n −1) 4 + nlogn 4 . Le coût reste quadratique, mais asymptotiquement le nombre d’échanges est deux fois moindre que pour le tri par insertion. Cela n’en reste pas moins mauvais, et d’autres choix pour la suite hp conduisent à de meilleurs résultats. Par exemple, la suite définie par hp = 2p −1 conduit à un coût dans la pire des cas en Θ(n3/2) (Hibbard, 1963). Mieux, la suite des nombres de la forme 2a3b conduit à un coût en Θ(nlog2 n) (Pratt, 1971). Mais la recherche de la meilleure suite de valeurs pour hp reste à l’heure actuelle un problème ouvert. d) On écrit tout d’abord une fonction insertion qui réalise le h-tri d’un tableau. def insertion(t, h): for j in range(h, len(t)): k = j while k >= h and t[k] < t[k−h]: t[k−h], t[k] = t[k], t[k−h] k −= 1 Le tri proprement dit consiste essentiellement à calculer la plus grande valeur hp de la suite qui vérifie hp ⩽n < hp+1 puis à appliquer la fonction précédente avec hp,hp−1,...,h1 = 1. Jean-Pierre Becirspahic 3.4 informatique commune uploads/Finance/ algorithmes-de-tri-corrige-des-exercices 1 .pdf

Documents similaires

PLAN PLAN 1/2 1/2  Introduction Introduction  Les risques nés des opérations 0 0

La PME-PMI Algérienne : Passé, Présent et Perspectives Meliani Hakim & Bouadam 0 0

Calcul Outils pour apprendre à calculer 2007 P. Dupré Documents SLECC : http:// 0 0

II. Etude financière : A. Tableau des charges d’exploitation Désignation Année 0 0

LYCEE NELSON MANDELA ANNEE SCOLAIRE 2007-2008 OUAGADOUGOU CLASSES : Toutes les 0 0

Corrections Luc Lasne, 29/10/2008 Partie 1 : Régime alternatif sinusoïdal monop 0 0

Concours National Commun – Session 2019 – Filière MP • On veillera à une présen 0 0

Soleil de Lumière > Lettres hébraïques > 10 - Yod, la Main de Dieu 19 janvier 2 0 0

• Détails
• Publié le Sep 06, 2022
• Catégorie Business / Finance
• Langue French
• Taille du fichier 0.1823MB