Тест: Maîtrise des algorithmes gloutons et dichotomie — 7 въпроса

1. Quelle est la cause principale de la rapidité de convergence de la recherche dichotomique ?

A. Le théorème des valeurs intermédiaires

B. L’utilisation de la continuité de la fonction

C. La monotonie de la fonction

D. La division en deux de l’intervalle à chaque étape

Answer: (D)

Обяснение

La division en deux de l’intervalle à chaque étape réduit rapidement la zone de recherche, ce qui explique la complexité logarithmique et la convergence rapide de la recherche dichotomique.

2. Selon le texte, à quel moment la stratégie de sélection du plus tôt dans le planning d’occupation a été démontrée comme optimale ?

A. Avant la présentation de l’algorithme glouton

B. Après avoir testé plusieurs exemples concrets

C. Au début de l’étude du problème, lors de sa formulation

D. Lors de la conclusion de la preuve par échange et contradiction

Answer: (D)

Обяснение

Le texte indique que la preuve d’optimalité de la stratégie du plus tôt repose sur un raisonnement par échange et contradiction, ce qui a été réalisé lors de cette étape précise, c’est-à-dire lors de la démonstration formelle.

3. Quelle propriété du système monétaire garantit que l’algorithme glouton donne toujours la solution optimale pour le rendu de monnaie ?

A. Le système doit contenir au moins une pièce de 1 unité

B. Les pièces doivent être en nombre pair

C. Le système monétaire doit être canonique

D. Les pièces doivent être toutes de la même valeur

Answer: (C)

Обяснение

Le système monétaire est dit canonique si l’algorithme glouton donne toujours la solution optimale. La source précise que dans un système canonique, l’algorithme glouton fonctionne parfaitement, ce qui n’est pas le cas dans les systèmes non canoniques.

4. Qu'est-ce qu'un planning d’occupation ?

A. La gestion des tâches dans un projet pour respecter les délais

B. Le calendrier annuel d'une organisation pour répartir les événements

C. La planification des ressources pour réduire les coûts d'une entreprise

D. L'organisation des plages horaires pour maximiser le nombre d'activités sans chevauchement

Answer: (D)

Обяснение

Le planning d’occupation désigne l’organisation des intervalles de temps réservés pour des conférences ou activités, dans le but de maximiser leur nombre sans chevauchement, conformément à la définition présente dans la source.

5. Selon le texte, quel théorème garantit l'existence d'une racine dans un intervalle si la fonction est continue et change de signe aux extrémités ?

A. Le théorème des valeurs intermédiaires

B. Le théorème de Rolle

C. Le théorème de Cauchy

D. Le théorème de Bolzano

Answer: (A)

Обяснение

Le texte mentionne explicitement que le théorème des valeurs intermédiaires garantit qu'une fonction continue qui change de signe entre deux points possède une racine dans l'intervalle.

6. Quelle est la principale caractéristique de la recherche dichotomique telle que décrite dans le contenu ?

A. Elle se limite à une recherche linéaire dans un tableau non trié.

B. Elle utilise un algorithme non itératif basé sur une seule vérification.

C. Elle divise constamment l’intervalle en deux pour localiser une solution ou une racine.

D. Elle consiste à explorer toutes les solutions possibles de manière exhaustive.

Answer: (C)

Обяснение

La recherche dichotomique est caractérisée par la division répétée de l’intervalle en deux pour localiser une solution ou une racine, jusqu’à atteindre la précision désirée.

7. Quel est le rôle principal de la recherche dans tableau trié exploitant la dichotomie ?

A. Calculer la somme de tous les éléments du tableau

B. Identifier la position de l’élément le plus grand

C. Localiser efficacement une valeur dans le tableau

D. Classer les éléments du tableau par ordre croissant

Answer: (C)

Обяснение

La recherche dans tableau trié exploitant la dichotomie a pour rôle principal de localiser efficacement une valeur dans le tableau en divisant l’espace de recherche par moitié à chaque étape, ce qui optimise la vitesse de recherche.