Cuestionario: Principes et Applications du Diviser pour Régner — 8 preguntas

1. Comment doit-on appliquer la méthode diviser pour régner pour résoudre un problème complexe ?

A. Découper le problème en sous-problèmes indépendants, puis résoudre chaque sous-problème séparément et enfin fusionner leurs résultats.

B. Fusionner plusieurs petits problèmes pour créer un problème plus grand, puis le résoudre directement.

C. Résoudre directement le problème initial sans le diviser, puis optimiser la solution.

D. Diviser le problème en sous-problèmes, puis résoudre chaque sous-problème en utilisant une approche différente.

Answer: (A)

Explicación

L'application de la méthode diviser pour régner consiste à d'abord découper le problème en sous-problèmes plus petits, puis à les résoudre séparément, et enfin à fusionner leurs résultats pour obtenir la solution du problème initial.

2. Quelle est la étape principale de la stratégie 'diviser pour régner' ?

A. Diviser, régner, combiner

B. Analyser, décider, exécuter

C. Partitionner, conquerir, remanier

D. Diviser, résoudre, optimiser

Answer: (A)

Explicación

La méthode diviser pour régner se compose de trois étapes clés : diviser le problème, résoudre les sous-problèmes, puis combiner les résultats. Ces mots clés illustrent le processus global.

3. Quelle est la caractéristique principale de la phase de descente dans la méthode d’exponentiation rapide ?

A. Elle construit la solution en remontant à partir des résultats intermédiaires.

B. Elle utilise la décomposition en facteurs premiers de n.

C. Elle consiste à diviser récursivement n par 2 jusqu’à atteindre 1.

D. Elle divise l’exposant n par 2 jusqu’à atteindre la base, en construisant la solution en descendant dans l’arbre.

Answer: (D)

Explicación

La phase de descente dans l’exponentiation rapide consiste à diviser récursivement n par 2 jusqu’à atteindre la base (n=0 ou n=1), construisant ainsi la solution en descendant dans l’arbre de calcul, conformément à la description dans la source.

4. Qui est l'auteur associé à une méthode spécifique ou une date clé mentionnée dans la fiche ?

A. Les auteurs de la méthode n sont pas spécifiés dans le document

B. Maxwell en 1865

C. Turing en 1936

D. Knuth en 1973

Answer: (A)

Explicación

Le document ne mentionne aucun auteur spécifique comme Maxwell, Turing ou Knuth, il souligne plutôt des concepts et méthodes sans attribution précise.

5. Quelle est la différence principale entre 'diviser pour régner' et la programmation dynamique ?

A. Diviser pour régner est utilisé pour des sous-problèmes indépendants, la programmation dynamique pour dépendants

B. Les deux utilisent la mémorisation à la même étape

C. La programmation dynamique divise en deux, alors que diviser pour régner en trois étapes

D. Il n'y a aucune différence notable

Answer: (A)

Explicación

La différence clé est que 'diviser pour régner' suppose généralement des sous-problèmes indépendants, alors que la programmation dynamique gère des sous-problèmes dépendants en mémorisant leurs solutions.

6. Quelle méthode d'optimisation est utilisée lorsque les sous-problèmes sont dépendants ?

A. Programmation dynamique

B. Tri fusion

C. Recherche dichotomique

D. Exponentiation rapide

Answer: (A)

Explicación

La programmation dynamique est une méthode d'optimisation pour traiter des sous-problèmes dépendants en mémorisant leurs résultats afin d'éviter de les recalculer.

7. Quelle technique permet de calculer efficacement a^n en réduisant le nombre d’opérations ?

A. Exponentiation rapide

B. Tri fusion

C. Recherche dichotomique

D. Programmation dynamique

Answer: (A)

Explicación

L'exponentiation rapide utilise la décomposition binaire de l'exposant pour réduire considérablement le nombre d'opérations, en divisant par 2 à chaque étape.

8. Quelle est la complexité améliorée grâce à la méthode 'diviser pour régner' par rapport à une approche naïve ?

A. De O(n) à O(log n)

B. De O(n^2) à O(n)

C. De O(n log n) à O(n)

D. De O(n) à O(n^2)

Answer: (A)

Explicación

La méthode diviser pour régner peut transformer une complexité linéaire O(n) en une complexité logarithmique O(log n) en divisant le problème en deux à chaque étape.