Remerciez-le!

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

Exercices ch07 pdf EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER Chapitre ÉNONCÉS Exercice a Présentez l ? approche Diviser pour régner b Donnez deux conditions fort souhaitables pour que l ? approche Diviser pour régner soit e ?cace c Donnez deux domain

EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER Chapitre ÉNONCÉS Exercice a Présentez l ? approche Diviser pour régner b Donnez deux conditions fort souhaitables pour que l ? approche Diviser pour régner soit e ?cace c Donnez deux domaines d ? application de l ? approche Diviser pour régner Exercice Vous décidez d ? utiliser la technique diviser pour régner pour résoudre un certain type de problème Pour n ? vous savez que vous pouvez obtenir la solution à un exemplaire de taille n en F EE F F résolvant a sous-exemplaires de taille n Le temps requis pour la décomposition de l ? exemplaire original en a sous-exemplaires est dans long n et le temps requis pour la recombinaison des sous-solutions est dans n Supposez pour simpli ?er que n est une puissance de 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 ii lorsque a iii lorsque a 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 Justi ?ez brièvement votre réponse Exercice 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 ? n il utilise un algorithme Adhoc qui est dans O n Autrement il F EE F F décompose l ? exemplaire de taille n en k sous-exemplaires de taille kn 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 e ?cacité en notation O de façon aussi simple que possible Explicitez vos calculs vous pouvez supposer que n km et que n km Exercice Soit un tableau T 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 ? Analyse d ? Algorithmes EXERCICES SUR LA TECHNIQUE DIVISER POUR RÉGNER CExercice ancien problème Soit T n un tableau de n éléments Il est facile de déterminer le plus grand élément de T en faisant exactement n ?? comparaisons entre éléments Max T Ind POUR i 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 ?? comparaisons supplémentaires T Ind T T Ind est le maximum donc peut être remplacé par T Min T POUR i JUSQU'À n faire SI Min T i ALORS Min T i FINSI FIN POUR Cela donne au total