Remerciez-le!

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

CORRECTION FICHE TD ALGORITHMIQUE IN_3 Exercice 1 1) Expliquez la différence en

CORRECTION FICHE TD ALGORITHMIQUE IN_3 Exercice 1 1) Expliquez la différence entre les notations O() et Ω(), sans donner leur définition formelle. O() exprime une borne supérieure sur la consommation de ressources. Ω() exprime une borne inférieure sur la consommation de ressources. 2) Les algorithmes diviser-pour-régner et de programmation dynamique sont tous deux basés sur une relation de récurrence. Expliquez cependant la différence fondamentale entre les deux techniques de conception. Diviser-pour-régner procède de haut en bas, alors que la programmation dynamique procède de bas en haut. 3) Qu’est-ce qu’un algorithme vorace ? Un algorithme vorace est un algorithme qui fait toujours le choix qui lui semble le meilleur sur le moment. Autrement dit, il fait le choix localement optimal, dans l’espoir que ce choix conduira à une solution globalement optimale. Exercice 2 1) Complexité Le «if» s’exécute en O(1) et le «return» effectue 3 T(n-1) appels récursifs; la complexité du code précédent sera donc sous la forme T(n) = 3*T(n-1) + 1 avec T(0) = 1. on aura donc: T(n) = 3 * T(n-1) + 1 = 3( 3T(n-2) + 1) +1 = 32 T(n-2) + 3 + 1 = 33 T(n-3) + 3² + 3 + 1 … = 3n T(0) + 3^(n-1) + 3^(n-2) + … + 3 + 1 or T(0) = 1 = 3n + 3^(n-1) + 3^(n-2) + … + 3 + 1 = [ 3^(n+1) – 1] / 2 ~ 3^n → T(n) = O(3n) 2) Algorithme int T(int n ) { int T[] = new int(); if (n ≤ 0 ){ return 1; else return T[n-1] * 3; // juste T(n-1) appels récursifs } return T[n]; } Complexité: O(n) Exercice 3 1) T(n) = 2 T(n/2 + 17) + n il faut utiliser la substitution pour prouver que T(n) = O(n log n) car T(n) a la même complexité qu’un T’(n) = 2 T’(n/2) + n dont la complexité ( O(n log n ) )est facile à obtenir car classique. Supposons donc que T(n/2) ϵ O(n/2 log n/2) et montrons que T(n) ϵ O(n log n); il existe alors c ϵ R tq T(n/2 + 17) ≤ c n/2 log n/2 → 2 T(n/2 + 17) ≤ c n log n/2 = c n (log n – log 2) → 2 T(n/2 +17) + n ≤ c n (log n – log 2) + n pour c > 1 / log 2 on aura → T(n) < c n log n d’où T(n) = O(n log n) 2) On a T(n) = 3 T(n/2) + n 0 n T(n) = 3 T(n/2) + n / | \ 1 n/2 n/2 n/2 T(n/2) = 3 T(n/ 2²) + n/2 / | \ 2 n/2² … n/2² T(n/2²) = 3 T(n/2³) + n/2² … k 1 … 1 T(n/2^k) = 3 T(2^k+1) + n/2^k on a n/2^k = 1 → k = log2 n c0 = 3 n ⁰ c1 = 3(n/2) = 3/2 n c2 = 3² (n/2²) = (3/2)² n … ck = 3^k (n/2^k) = (3/2)^k n T(n) = c0 + c1 + … + ck = n( 1 + 3/2 + (3/2)² + … + (3/2)^k) = n ( (3/2)^k+1 – 1 ) / 3/2 – 1 = 2n ( (3/2)^log2 n – 1) or (3/2)^log2 n = elog 2 n . ln 3/2 = e ln n / ln 2 (ln 3 – ln 2) = e ln n (log 3 2 – 1 ) ~ e ln n = n T(n) = 2 n . n → T(n) = O(n²) 3) T(n) = 2 T( n1/2) + log n (on doit effectuer un changement de variable ici) Pour se faciliter la tâche, on ne se préoccupera pas d’arrondir les valeurs comme √n à l’entier le plus proche. Si l’on fait le changement de variable m = lg n, on obtient T(2m) = 2T(2m/2) + m . Si l’on pose maintenant S(m) = T(2m) , on obtient la nouvelle récurrence S(m) = 2S(m/2) + m , Effectivement, la nouvelle récurrence a la même solution : S(m) = O(m lg m). En repassant de S(m) à T(n), on obtient T(n) = T(2m) = S(m) = O(m lg m) = O(lg n lg lg n). pour les questions 4 et 5, procédez comme précédemment 6) Méthode générale T(n) = 2T(n/2) + n lg n , bien qu’elle ait la forme correcte : a = 2, b = 2, f (n) = n lg n et nlogb a = n. On pourrait penser que le cas 3 de la méthode générale s’applique, puisque f (n) = n lg n est plus grande asymptotiquement que nlogb a = n. Le problème est qu’elle n’est pas polynomialement plus grande. Le rapport f (n)/nlogb a = (n lg n)/n = lg n est asymptotiquement plus petit que n´ pour toute constante positive ´. En conséquence, la récurrence tombe dans le fossé situé entre le cas 2 et le cas 3 Exercice 4: Soit la suite T (n) définie par T (2) = T (1) = T (0) = 1 et: T (n) = T (n − 1) + 2 T ∗ (n − 2) + T (n − 3); n > 2 On considère le problème de calculer T (n) pour l’entrée n. Soit l’algorithme naïf récursif associé: int T(int n){ if (n<=2) return 1; else return T(n-1)+2*T(n-2)+T(n-3);} Q 1. Soit A(n) le nombre d’appels récursifs à T effectués lors de l’exécution de la function T (n). Exprimez A(n) en fonction de A(n − 1); A(n − 2); A(n − 3). Qu’en déduire sur la complexité de l’algorithme naïf ? on suppose qu’on compte dans A(n) l’appel principal. On a donc: A(n) = 1 si n ≤ 2 A(n) = 1 + A(n − 1) + A(n − 2) + A(n − 3) si n > 2 Donc on peut par exemple en déduire que: A(n) > 3A(n − 3) si n > 2. Et donc A(n) > 3n÷3. Q 2. Proposez un algorithme en O(n) (en supposant qu’on est dans le cadre du coût uniforme, i.e. en ne prenant pas en compte la taille des opérandes). int T(int n){ if (n<=2) return 1; int[] T=new int[n]; T[0]=1; T[1]=1; T[2]=1; for (int i=3; i <=n; i++) T[i]=T[i-3]+T[i-2]+T[i-1]; return T[i]; } int T(int n){ if (n<=2) return 1; int A=1, B=1, C=1, D; for (int i=3; i <=n; i++){ D=A+2*B+C; A=B; B=C; C=D;} return C; } Exercice 5 1) Le cas le plus défavorable intervient pour le tri rapide quand la routine de partitionnement produit un sous-problème à n − 1 éléments et une autre avec 0 élément. Sa complexité est O(n²) 2) Dans le partitionnement le plus équilibré possible, PARTITION produit deux sousproblèmes de taille non supérieure à n/2, vu que l’un est de taille n/2 et l’autre de taille récurrence du temps d’exécution est alors T(n) 2T(n/2) + Q(n) , D’après le cas 2 du théorème général (théorème 4.1), la solution en est T(n) = O(n lg n) 3) Supposons, par exemple, que l’algorithme de partitionnement produise systématiquement un découpage dans une proportion de 9 contre 1, ce qui paraît à première vue assez déséquilibré. On obtient dans ce cas la récurrence T(n) T(9n/10) + T(n/10) + cn pour le temps d’exécution du tri rapide ; nous avons explicitement inclus la constante c implicitement contenue dans le terme Q(n). La suivante montre l’arbre récursif de cette récurrence. Remarquez que chaque niveau de l’arbre a un coût cn, jusqu’à ce qu’une condition aux limites soit atteinte à la profondeur log10/9 n = Q(lg n), après Arbre récursif de TRI-RAPIDE dans lequel PARTITION produit toujours une décomposition 9-1, donnant ainsi un temps d’exécution O(nlgn). Exercice 6 1) Étant donné que T(n) = 2T( n/4 ) + 3 log n ⌊ ⌋ trouvons le comportement asymptotique de T(n). Justifiez votre réponse. On utilisera le Master Theorem avec les coefficients a = 2, b = 4 et la perturbation f(n) = log n. On trouve d’abord l’exposant : k = log4 2 = 1/2. On voit que la perturbation est petite log n = o(nk−ε), en choisissant, par exemple ε = 0, 1. Effectivement log n = o(n0.4) puisque le logarithme croit moins vite que n’importe quelle puissance positive. Par Master Theorem on obtient donc : T(n) = Θ(n1/2) = Θ(√n). 2) L’algo diviser-pour-régner de cours calcule xn comme suit : –si n = 0, 1, 2 on renvoie 1, x, x x respectivement ; ∗ –sinon si n est pair alors on calcule d’abord y = xn/2, et ensuite xn = y y ; ∗ –sinon (si n est impair) alors on calcule d’abord y = x n/2 , et ensuite xn = y y x ; ⌊ ⌋ ∗ ∗ Pour n = 13 ça donne : x13 = y y x avec y = x6. A son tour y = z z avec z = x3. Finalement ∗ ∗ ∗ z = x x x. En tout on a 5 multiplications. ∗ ∗ On a trouvé uploads/s3/ correction-td-algo-in3-2020.pdf