Тест: Paradigmes algorithmiques et stratégies efficaces — 24 въпроса

1. Quelles propriétés rendent la programmation dynamique applicable ?

A. Des sous-problèmes qui se chevauchent et une sous-structure optimale

B. Des sous-problèmes indépendants et une absence de solution optimale

C. Une énumération exhaustive et une complexité exponentielle

D. Un choix local unique et irréversible

Answer: (A)

Обяснение

La programmation dynamique convient quand les sous-problèmes se recouvrent et que la solution optimale globale se construit à partir de solutions optimales locales. C’est ce qui justifie la réutilisation des résultats.

2. Quelle différence fondamentale sépare la mémoïsation de la tabulation ?

A. La tabulation repose sur le retour en arrière

B. La mémoïsation est ascendante, la tabulation est récursive

C. Les deux calculent les sous-problèmes dans le même ordre

D. La mémoïsation est descendante, la tabulation est ascendante

Answer: (D)

Обяснение

La mémoïsation suit une logique top-down en calculant à la demande, tandis que la tabulation suit une logique bottom-up en remplissant un tableau. Les deux réutilisent des résultats déjà obtenus.

3. Quel énoncé décrit correctement le paradigme diviser pour mieux régner ?

A. Il choisit à chaque étape la meilleure option locale

B. Il mémorise les résultats d’états déjà vus pour éviter les recalculs

C. Il teste toutes les solutions possibles jusqu’à trouver la bonne

D. Il découpe le problème en sous-problèmes plus petits, les résout, puis combine leurs solutions

Answer: (D)

Обяснение

Diviser pour mieux régner consiste à décomposer un problème en sous-problèmes, les résoudre récursivement, puis combiner les réponses. Ce n’est pas une exploration exhaustive ni une logique gloutonne.

4. Quel mécanisme est au cœur de l’algorithme de Dijkstra ?

A. Explorer exhaustivement tous les chemins possibles

B. Fusionner deux moitiés de graphe triées

C. Mémoriser les sous-problèmes de chemins comme en programmation dynamique

D. Choisir à chaque étape le sommet non visité de distance minimale puis relâcher ses arêtes

Answer: (D)

Обяснение

Dijkstra fixe progressivement les sommets en sélectionnant celui dont la distance estimée est minimale, puis met à jour les distances voisines. C’est une logique gloutonne sur les distances.

5. Dans la validation des pistes pour DaariNova, quand un glouton peut-il être optimal ?

A. Quand il existe beaucoup de permutations à tester

B. Quand le problème possède la propriété du choix glouton et une sous-structure optimale

C. Quand la solution finale dépend d’un retour arrière

D. Quand les sous-problèmes se chevauchent fortement

Answer: (B)

Обяснение

Un glouton peut être optimal si chaque choix local optimal peut appartenir à une solution globale optimale et si le problème admet une sous-structure optimale. Sans ces conditions, l’efficacité locale ne suffit pas.

6. Quel ordre de complexité est typiquement associé à une exploration exhaustive du type force brute ?

A. O(n)

B. O(n!) ou exponentiel

C. O(1)

D. O(n log n)

Answer: (B)

Обяснение

La force brute s’accompagne souvent d’une complexité factorielle ou exponentielle parce qu’elle essaie toutes les possibilités. C’est précisément ce qui la rend vite impraticable.

7. Quelle affirmation distingue le retour sur trace d’une approche gloutonne ?

A. Il explore des branches et revient en arrière en cas d’échec

B. Il remplit un tableau de bas en haut

C. Il ignore les contraintes de validité

D. Il choisit toujours l’option localement la plus rentable

Answer: (A)

Обяснение

Le retour sur trace explore plusieurs choix puis revient en arrière lorsqu’une branche ne mène pas à une solution. À l’inverse, le glouton ne revient pas sur ses décisions.

8. Qu’apporte principalement l’élagage dans un algorithme de retour sur trace ?

A. Il garantit un temps constant

B. Il supprime des branches qui ne peuvent plus mener à une solution valide

C. Il remplace la récursion par une boucle

D. Il transforme un problème en sous-problèmes indépendants

Answer: (B)

Обяснение

L’élagage coupe des branches de l’arbre de recherche dès qu’elles ne peuvent plus aboutir à une solution acceptable. Cela réduit l’espace exploré sans changer la logique du backtracking.

9. Quel paradigme garantit en général l’optimalité sur de petites instances en examinant toutes les possibilités ?

A. Le diviser pour mieux régner

B. La programmation dynamique

C. La stratégie gloutonne

D. La force brute

Answer: (D)

Обяснение

La force brute teste toutes les possibilités et garantit donc l’optimalité, mais seulement au prix d’un coût de calcul élevé. C’est pourquoi elle convient surtout aux petites instances.

10. De quoi dépend fortement la complexité de Dijkstra sur un graphe ?

A. Du nombre de couleurs des sommets

B. Du nombre de composantes connexes seulement

C. Du fait que les arêtes soient orientées ou non uniquement

D. De la structure de données utilisée pour choisir le prochain sommet

Answer: (D)

Обяснение

La structure de données, notamment la file de priorité, influence fortement le coût de sélection du prochain sommet. C’est un facteur central de la complexité de Dijkstra.

11. Pour l’exemple des N-reines, quelle stratégie décrit le mieux le retour sur trace ?

A. Remplir un tableau de distances minimales

B. Tester uniquement la première colonne puis s’arrêter

C. Placer toutes les reines au hasard puis trier les conflits

D. Placer une reine colonne par colonne et revenir en arrière en cas de conflit

Answer: (D)

Обяснение

Le backtracking sur les N-reines construit une affectation partielle colonne par colonne et revient en arrière dès qu’un conflit apparaît. Cette exploration guidée est différente d’une force brute sans retour.

12. Quel paradigme construit une solution en choisissant à chaque étape l’option localement la plus avantageuse sans revenir en arrière ?

A. La programmation dynamique

B. Le diviser pour mieux régner

C. La stratégie gloutonne

D. La force brute

Answer: (C)

Обяснение

La stratégie gloutonne effectue un choix local à chaque étape sans retour en arrière. La programmation dynamique, elle, réutilise des sous-problèmes mémorisés au lieu de décider seulement sur le moment.

13. Quelle affirmation décrit le mieux une heuristique ?

A. Une technique de mémorisation de sous-problèmes

B. Une méthode qui garantit l’optimalité sur tous les problèmes

C. Un algorithme qui explore toutes les solutions possibles

D. Une règle pratique qui vise une bonne solution rapidement sans garantie d’optimalité

Answer: (D)

Обяснение

Une heuristique cherche une solution satisfaisante en un temps raisonnable, sans promettre le meilleur résultat. Elle est utile quand une résolution exacte serait trop coûteuse.

14. Quelle est la principale limite de la force brute sur les problèmes de grande taille ?

A. Elle ne peut traiter que les problèmes de graphe

B. Elle devient trop coûteuse en temps à cause de l’explosion du nombre de possibilités

C. Elle exige une structure de sous-problèmes chevauchants

D. Elle perd toujours l’optimalité

Answer: (B)

Обяснение

La force brute examine toutes les possibilités, ce qui fait exploser le temps de calcul lorsque l’espace de recherche grandit. Elle garantit l’optimalité, mais souvent au prix d’un coût impraticable.

15. Pourquoi la récursion naïve de Fibonacci est-elle coûteuse ?

A. Parce qu’elle trie les termes avant de les additionner

B. Parce qu’elle ne dépend que d’un seul terme précédent

C. Parce qu’elle calcule des sous-problèmes qui se répètent massivement

D. Parce qu’elle utilise un tableau trop grand

Answer: (C)

Обяснение

La récursion naïve recalcule les mêmes valeurs de Fibonacci plusieurs fois, ce qui provoque une explosion du nombre d’appels. C’est un cas classique de sous-problèmes qui se chevauchent.

16. Pourquoi la programmation dynamique se distingue-t-elle de diviser pour mieux régner ?

A. Parce qu’elle ne combine jamais les résultats

B. Parce qu’elle impose une énumération exhaustive

C. Parce qu’elle refuse toute récursion

D. Parce qu’elle utilise des sous-problèmes qui se chevauchent

Answer: (D)

Обяснение

En programmation dynamique, les sous-problèmes se chevauchent et leurs résultats sont mémorisés. Dans diviser pour mieux régner, les sous-problèmes sont plutôt indépendants.

17. Quel gain principal apporte la programmation dynamique pour Fibonacci ?

A. Elle rend le calcul exponentiel en O(n!)

B. Elle supprime les recalculs grâce au stockage des résultats intermédiaires

C. Elle impose un retour sur trace

D. Elle remplace la récurrence par un tri

Answer: (B)

Обяснение

La programmation dynamique, par mémoïsation ou tabulation, évite de recalculer les mêmes valeurs. Cela fait passer Fibonacci d’un comportement exponentiel à une complexité linéaire.

18. Pourquoi la stratégie gloutonne par ratio échoue-t-elle en général pour le sac à dos 0-1 ?

A. Parce qu’elle ne respecte pas la capacité du sac

B. Parce qu’elle n’utilise jamais de tri

C. Parce que les objets indivisibles rendent les choix dépendants les uns des autres

D. Parce qu’elle transforme toujours le problème en force brute

Answer: (C)

Обяснение

Dans le sac à dos 0-1, le choix d’un objet influence les choix futurs, donc le meilleur ratio local ne garantit pas l’optimum global. C’est pourquoi la programmation dynamique est souvent nécessaire.

19. Quel couple paradigme-conséquence est le plus juste ?

A. Diviser pour mieux régner : décomposition en sous-problèmes indépendants avec complexité typique faible

B. Programmation dynamique : optimalité conditionnelle seulement

C. Glouton : optimalité garantie sans condition

D. Force brute : complexité typique linéaire

Answer: (A)

Обяснение

Diviser pour mieux régner repose sur des sous-problèmes généralement indépendants et conduit souvent à une complexité de type O(n log n). Le glouton, lui, n’est optimal que sous conditions.

20. Quelle condition caractérise une stratégie gloutonne correcte sur un problème d’optimisation ?

A. Les sous-problèmes doivent se chevaucher fortement

B. Chaque choix local optimal doit pouvoir mener à une solution globale optimale

C. Toutes les solutions partielles doivent être testées

D. Le problème doit être résolu par tableau itératif

Answer: (B)

Обяснение

Une stratégie gloutonne est justifiée si un choix local optimal peut appartenir à une solution globale optimale. Sans cette propriété, le résultat peut être sous-optimal.

21. Quel objectif est le plus directement associé à la programmation dynamique ?

A. Découper le problème sans combinaison finale

B. Mémoriser des sous-problèmes pour éviter les recalculs

C. Explorer exhaustivement toutes les possibilités

D. Choisir toujours la meilleure option locale

Answer: (B)

Обяснение

La programmation dynamique exploite des sous-problèmes récurrents en stockant leurs résultats pour éviter de les recalculer. L’exploration exhaustive correspond plutôt à la force brute.

22. Quelle proposition correspond le mieux à une métaheuristique ?

A. Une procédure qui mémorise les réponses déjà calculées

B. Un algorithme général d’optimisation combinatoire guidé par des mécanismes d’exploration

C. Une technique de tri récursif en deux moitiés

D. Une méthode qui choisit toujours la meilleure ville suivante

Answer: (B)

Обяснение

Une métaheuristique fournit un cadre général d’optimisation qui guide la recherche vers de bonnes solutions. Elle ne se confond ni avec le tri diviser-pour-régner ni avec la mémoïsation.

23. Quelle association est donnée entre apprentissage automatique et paradigmes de résolution ?

A. Le gradient descent relève du diviser pour mieux régner et la rétropropagation du tri rapide

B. Les deux sont des heuristiques non structurées sans lien avec l’optimisation

C. Le gradient descent est présenté comme une approche gloutonne et la rétropropagation comme une forme de programmation dynamique

D. Le gradient descent est un exemple de force brute et la rétropropagation de retour sur trace

Answer: (C)

Обяснение

Le gradient descent est rapproché d’une démarche gloutonne car il améliore localement la solution, tandis que la rétropropagation est associée à la programmation dynamique par réutilisation d’informations. Cette distinction sert à modéliser des problèmes complexes de manière structurée.

24. Quelle différence fondamentale oppose le sac à dos fractionnaire au sac à dos 0-1 ?

A. Le fractionnaire autorise des fractions d’objets, le 0-1 impose un choix entier ou nul

B. Le fractionnaire interdit de prendre un objet entier

C. Le 0-1 autorise de prendre une fraction de chaque objet

D. Les deux problèmes se résolvent toujours par la même heuristique

Answer: (A)

Обяснение

Le sac à dos fractionnaire permet de prendre une partie d’un objet, ce qui rend le tri par ratio pertinent. Dans le sac à dos 0-1, on prend l’objet en entier ou pas du tout, ce qui casse cette logique.