Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Analyse d’Algorithmes 2000 EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER 1 EXE

Analyse d’Algorithmes 2000 EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER 1 EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER Chapitre 7 ÉNONCÉS Exercice 1 (a) Présentez l’approche Diviser pour régner. (b) Donnez deux conditions fort souhaitables pour que l’approche Diviser pour régner soit efficace. (c) Donnez deux domaines d’application de l’approche Diviser pour régner. Exercice 2 Vous décidez d’utiliser la technique diviser pour régner pour résoudre un certain type de problème. Pour n ≥4, vous savez que vous pouvez obtenir la solution à un exemplaire de taille n en résolvant a sous-exemplaires de taille n/4. Le temps requis pour la décomposition de l’exemplaire original en a sous-exemplaires est dans Θ( n2 logn) et le temps requis pour la recombinaison des sous-solutions est dans Θ(n2). Supposez pour simplifier que n est une puissance de 4. a) Donnez l’équation de récurrence asymptotique exprimant le temps d’exécution t(n) de cet algorithme en fonction de la taille n de l’exemplaire. b) Donnez l’ordre exact de t(n), sous la forme la plus simple possible, (i) lorsque a = 8; (ii) lorsque a = 16; (iii) lorsque a = 32. Aucune preuve n’est requise. Prière de ne pas réinventer la roue! c) Les réponses obtenues en b) s’appliquent-elles toujours si n n’est pas une puissance de 4? Justifiez brièvement votre réponse. Exercice 3 Un algorithme A est conçu en appliquant le principe général de la technique “diviser pour régner”. Pour résoudre de petits exemplaires de taille n ≤ n0, il utilise un algorithme Adhoc qui est dans O(n3). Autrement, il décompose l’exemplaire de taille n en k sous-exemplaires de taille n k, et les étapes de décomposition en sous-exemplaires et de combinaison des solutions intermédiaires demandent un temps dans O(n). Analysez cet algorithme et donnez son efficacité en notation O, de façon aussi simple que possible. Explicitez vos calculs (vous pouvez supposer que n = km et que n0 = km0). Exercice 4 Soit un tableau T [1..n] de n entiers distincts, décrivez de manière précise un algorithme retournant l’indice du minimum des éléments de T, basé sur la technique “diviser pour régner”. 2 EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER R. Lelouche ©2000 Exercice 5 (ancien problème 4.11.3) Soit T[1..n] un tableau de n éléments. Il est facile de déterminer le plus grand élément de T en faisant exactement n–1 comparaisons entre éléments: Max ← T[1] ; Ind ← 1 POUR i ← 2 JUSQU'À n faire SI Max < T[i] ALORS Max ← T[i] ; Ind ← i FINSI FIN POUR. Seules les comparaisons entre éléments sont comptées ici, ce qui exclut les comparaisons implicites dans le contrôle de la boucle POUR. On pourrait subséquemment déterminer le plus petit élément de T en n–2 comparaisons supplémentaires: T[Ind] ← T[1] {T[Ind] est le maximum, donc peut être remplacé par T[1]} Min ← T[2] POUR i ← 3 JUSQU'À n faire SI Min > T[i] ALORS Min ← T[i] FINSI FIN POUR. Cela donne au total 2n–3 comparaisons. 1º Trouvez un algorithme A basé sur la technique DPR capable de déterminer le plus petit et le plus grand éléments d'un tableau de n éléments en faisant moins de 2n–3 comparaisons entre éléments. Vous pouvez supposer que n est une puissance de deux (cependant votre algorithme doit fonctionner pour tout n ≥ 1). Quel est le nombre exact de comparaisons que votre algorithme requiert? 2º Dans votre algorithme A, beaucoup de temps est perdu dans la gestion des appels récursifs. Pouvez-vous imaginer un algorithme itératif B faisant le même nombre de comparaisons? Exercice 6 (problème 7.12 p.252) Soit T[1..n] un tableau d’entiers distincts triés par valeurs croissantes; certains peuvent être négatifs. 1º Donnez un algorithme qui retourne un indice i de T tel que T[i] = i, en supposant qu’un tel indice existe. Votre algorithme devrait mettre en pire cas un temps dans O(logn). 2º Justifiez très brièvement le temps mis par votre algorithme (quelques lignes). Exercice 7 L’algorithme linéaire pour trouver la médiane (section 7.5) permet de faire fonctionner le tri de Hoare (quicksort) en un temps dans O (n logn) en pire cas. a) La phrase précédente est-elle vraie ou fausse ? Justifiez brièvement. Vous pouvez supposer, pour simplifier, que tous les éléments du tableau sont distincts. b) Est-ce une bonne idée ? Pourquoi ou pourquoi pas ? Analyse d’Algorithmes 2000 EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER 3 Exercice 8 Cet exercice vise à déterminer le seuil n0 à partir duquel le tri par fusion (section 4.4) devrait cesser de s’appeler récursivement. Notez que les chiffres ci-dessous sont fictifs et qu’ils ont été choisis dans le but de faciliter les calculs (pas de fraction, etc.). Considérez l’algorithme suivant: PROCEDURE TriFusion (T[1..n]) SI n ≤ n0 ALORS TriQuad (T) SINON U ← les n/2 premiers éléments de T V ← les n/2 autres éléments de T TriFusion (U); TriFusion (V) Fusion (T, U, V) FIN TriFusion. où : • TriQuad (T) est un tri quadratique prenant un temps moyen an2 + bn + c pour trier n éléments, • Fusion (T, U, V) fusionne deux séquences triées dont la somme des longueurs est n en un temps moyen dn + e. Pour simplifier, on suppose que les temps moyens pris par TriQuad et Fusion dépendent uniquement de n et ne dépendent pas de l’ordre relatif des éléments dans les tableaux. Grâce à votre horloge (dont la précision est supposée parfaite !), vous avez déterminé que TriQuad prend en moyenne 25, 109 et 469 microsecondes pour trier 4, 8 et 16 éléments respectivement. De même, la partie non récursive de TriFusion (c'est-à-dire tout sauf les appels récursifs, lorsque n > n0) prend en moyenne 131 et 251 microsecondes pour traiter 8 et 16 éléments respectivement. a) Déterminez un seuil n0 à peu près optimal (minimisant approximativement le temps moyen) pour cette implantation du tri par fusion. Pour simplifier, approximez n/2 et n/2 par n/2. b) Sachant que la solution générale de l’équation de récurrence T (n) ∈ { t(n) si n ≤ n 0 T(n 2) + T(n 2) + β n + γ si n > n 0 est T(n) = βn lg n n0 + t(n0) + γ n0 n – γ pour n ≥ n0 lorsque n n0 est une puissance de 2 lequel des trois paramètres suivants a le plus d’influence sur le temps requis par le tri par fusion lorsque le nombre d’éléments à trier est très très grand: - le seuil bien choisi, - l’efficacité de l’algorithme ad hoc (TriQuad), ou - l’efficacité de la partie non récursive de l’algorithme ? Justifiez votre réponse. 4 EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER R. Lelouche ©2000 Exercice 9 Un polynôme de degré n, tel que an xn + an–1 xn–1 + ... + a1 x + a0, est représenté par le tableau P[0..n] de ses coefficients, c’est-à-dire que P[i] = ai. Supposez que vous disposiez déjà d’un algorithme capable de multiplier symboliquement deux polynômes de degré au plus m en un temps dans O(m logm). Soient x1, x2, ..., xn des entiers quelconques. Esquissez un algorithme efficace, basé sur la technique diviser pour régner, capable de calculer les coefficients du polynôme produit (x – x1) (x – x2) ... (x – xn). Par exemple, si n = 3, x1 = 2, x2 = –1, et x3 = 1, il faut retourner le tableau [2, –1, –2, 1] correspondant au polynôme (x – 2) (x + 1) (x – 1) = x3 – 2x2 – x + 2. En fonction de n, exprimez le temps pris par votre algorithme sous la forme d’une équation de récur- rence asymptotique. Résolvez cette récurrence en notation O lorsque n est une puissance de 2. Exercice 10 Supposons que vous ayez un problème à résoudre et que vous décidiez d’utiliser une méthode diviser pour régner telle que la solution d’un problème de taille 3n demande la solution de 9 sous-problèmes du même type, mais de taille n. Supposons de plus que le temps requis pour la séparation du problème original en sous-problèmes et pour la combinaison des sous-solutions ainsi obtenues soit de Θ(n2) opérations. Supposez pour simplifier que cet algorithme ne sera utilisé que sur des problèmes dont la taille est une puissance exacte de 3. i) Donnez l’équation de récurrence exprimant le temps d’exécution de cet algorithme en fonction de la taille du problème à traiter. ii) Exprimez en notation Θ le temps requis par cet algorithme sur un problème de taille n. (Preuves non requises. Ne ré-inventez pas la roue!) iii) Quelle aurait été la réponse à (ii) s’il avait fallu résoudre 10 sous-problèmes plutôt que 9 ? iv) Idem avec 8 sous-problèmes. Exercice 11 (ancien problème 4.8.5) Démontrez que h(A) = lgA + le nombre de “1” dans la représentation binaire de A. Exercice 12 Considérez la matrice F = ( ) 0 1 1 1 . Soient i et j deux entiers quelconques. Que vaut le produit du vecteur (i j) par la matrice F? Que se passe-t-il si i et j sont uploads/Management/ exercices-ch07-pdf.pdf