QCM Algorithmes, structures de données et complexité – Partie 16

juillet 7, 2024juillet 7, 2024 Thomas Aucun commentaire

Questions pratiques pour testez vos connaissances sur la complexité en espace et en temps des algorithmes et des structures de données courants. Testez votre connaissance et travaillez sur les questions que vous trompez le plus souvent.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

1. Qu’est-ce que la mémorisation dans le contexte de la programmation dynamique ?

A Stocker les résultats d’appels de fonctions coûteux et renvoyer le résultat mis en cache lorsque les mêmes entrées se produisent à nouveau.

B La sélection aléatoire de sous-problèmes à résoudre

C Optimiser l’utilisation de la mémoire en supprimant les données inutiles

D Technique permettant d’améliorer le temps d’exécution des algorithmes gourmands.

La mémoïsation est une technique utilisée en programmation dynamique pour accélérer les programmes informatiques en stockant les résultats des appels de fonctions coûteux et en renvoyant le résultat mis en cache lorsque les mêmes entrées se produisent à nouveau, évitant ainsi le calcul des mêmes résultats à plusieurs reprises.

2. Quel problème est un exemple classique qui peut être résolu efficacement à l’aide de la programmation dynamique ?

A Le problème du voyageur de commerce

B Les algorithmes de tri

C Le problème du sac à dos

D Recherche binaire

Le problème du sac à dos est un problème d’optimisation classique qui peut être résolu efficacement à l’aide de la programmation dynamique. Il s’agit de sélectionner un ensemble d’éléments avec des poids et des valeurs donnés afin de maximiser la valeur totale dans un sac à dos de capacité limitée, en tenant compte des sous-problèmes qui se chevauchent et de la propriété de sous-structure optimale.

3. Comment calculer efficacement la suite de Fibonacci à l’aide de la programmation dynamique ?

A En utilisant une boucle pour calculer itérativement chaque nombre

B En stockant chaque nombre de Fibonacci calculé dans un tableau et en l’utilisant pour des calculs ultérieurs

C Par récursion sans mémorisation

D En devinant et en vérifiant

La séquence de Fibonacci peut être calculée efficacement à l’aide de la programmation dynamique en stockant chaque nombre de Fibonacci dans un tableau (ou une structure de données similaire) au fur et à mesure qu’il est calculé, puis en utilisant ces valeurs stockées pour le calcul des futurs nombres de la séquence, plutôt que de les recalculer, ce qui réduit considérablement le nombre de calculs.

4. Quel est l’avantage principal de l’utilisation de la programmation dynamique par rapport à la récursion naïve pour des problèmes tels que le calcul du nième nombre de Fibonacci ?

A Elle réduit la complexité de calcul

B Elle élimine le besoin de calcul

C Il utilise moins de mémoire

D Il repose sur des concepts mathématiques plus simples

L’utilisation de la programmation dynamique plutôt que de la récursion naïve pour des problèmes tels que le calcul du nième nombre de Fibonacci réduit considérablement la complexité des calculs. La récursivité naïve peut entraîner une complexité temporelle exponentielle en raison du recalcul des mêmes valeurs, alors que la programmation dynamique résout chaque sous-problème une seule fois, ce qui permet d’obtenir une complexité temporelle polynomiale ou linéaire beaucoup plus efficace.

5. Une solution de programmation dynamique fonctionne plus lentement que prévu. Quelle pourrait en être la raison ?

A Le problème ne comporte pas de sous-problèmes qui se chevauchent.

B Les sous-problèmes ne sont pas correctement mémorisés

C Il y a trop de sous-problèmes

D Les cas de base sont mal définis

Si une solution de programmation dynamique s’exécute plus lentement que prévu, cela peut s’expliquer par le fait que les sous-problèmes ne sont pas correctement mémorisés, ce qui entraîne des recalculs inutiles. S’assurer que la solution de chaque sous-problème est stockée et récupérée efficacement peut améliorer considérablement les performances.

6. Quel est l’objectif principal de l’algorithme de Dijkstra dans la théorie des graphes ?

A Trouver le chemin le plus court entre toutes les paires de nœuds.

B Détecter les cycles dans le graphe

C Trouver le chemin le plus court entre une source unique et tous les autres nœuds du graphe

D Créer un arbre minimal couvrant

L’algorithme de Dijkstra est conçu pour trouver le chemin le plus court entre un nœud source unique et tous les autres nœuds d’un graphe dont les poids des arêtes ne sont pas négatifs. Il calcule efficacement les distances minimales à l’aide d’une approche gourmande, en mettant à jour les chemins les plus courts vers chaque sommet au fur et à mesure qu’il progresse.

7. En théorie des graphes, qu’est-ce qu’une composante fortement connectée ?

A Un sous-ensemble de sommets qui sont mutuellement atteignables par tout autre sommet du sous-ensemble.

B Une composante où chaque sommet est connecté à tous les autres sommets par une arête directe

C Un ensemble de sommets sans arêtes entrantes

D Ensemble de sommets dans un graphe orienté où chaque sommet a le même degré.

Une composante fortement connectée dans un graphe orienté est un sous-ensemble de sommets où chaque sommet peut être atteint par tous les autres sommets du même sous-ensemble. L’identification de ces composantes est cruciale pour comprendre la structure des graphes orientés, car elle révèle des groupes de sommets à forte connectivité.

8. Qu’accomplit l’algorithme de Bellman-Ford ?

A Trouver le chemin le plus court dans un graphe dont les poids des arêtes sont négatifs.

B Créer un arbre minimal couvrant

C Recherche du flux maximal dans un réseau

D Détecter et rompre les cycles dans un graphe orienté

L’algorithme de Bellman-Ford trouve le chemin le plus court entre une source unique et tous les autres sommets d’un graphe pondéré, même si certains des poids des arêtes sont négatifs. Contrairement à l’algorithme de Dijkstra, l’algorithme de Bellman-Ford peut traiter des graphes avec des poids négatifs et peut également détecter des cycles négatifs.

9. Quelle est la principale différence entre les algorithmes de Prim et de Kruskal ?

A L’algorithme de Prim est utilisé pour la recherche du plus court chemin, tandis que celui de Kruskal est utilisé pour les arbres à recouvrement minimal.

B L’algorithme de Prim nécessite un sommet de départ, ce qui n’est pas le cas de l’algorithme de Kruskal.

C Prim est un algorithme gourmand; Kruskal ne l’est pas

D Prim peut gérer des poids d’arêtes négatifs; Kruskal ne le peut pas

Les algorithmes de Prim et de Kruskal permettent tous les deux de trouver un arbre minimal couvrant pour un graphe non orienté pondéré. La principale différence est que l’algorithme de Prim nécessite un sommet de départ et fait croître l’arbre minimal un sommet à la fois, tandis que l’algorithme de Kruskal ne nécessite pas de sommet de départ et ajoute les arêtes par ordre de poids croissant, en veillant à ce qu’aucun cycle ne se forme.

10. Pourquoi les tris topologiques sont-ils importants dans les algorithmes de graphes ?

A Ils sont utilisés pour détecter les cycles dans les graphes non dirigés

B Ils permettent de programmer des tâches dépendantes

C Ils permettent de trouver le chemin le plus court dans les graphes pondérés

D Ils calculent le flux maximal dans les réseaux

Les tris topologiques sont essentiels dans les graphes acycliques dirigés (DAG) car ils fournissent un ordre linéaire des sommets tel que pour chaque arête dirigée uv, le sommet u précède v dans l’ordre. Cette propriété rend le tri topologique important pour l’ordonnancement des tâches, la compilation des séquences ou tout autre scénario dans lequel les dépendances doivent être résolues dans un ordre spécifique.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

QCMs qui pourraient vous intéresser :

1. Qu’est-ce que la mémorisation dans le contexte de la programmation dynamique ?

2. Quel problème est un exemple classique qui peut être résolu efficacement à l’aide de la programmation dynamique ?

3. Comment calculer efficacement la suite de Fibonacci à l’aide de la programmation dynamique ?

4. Quel est l’avantage principal de l’utilisation de la programmation dynamique par rapport à la récursion naïve pour des problèmes tels que le calcul du nième nombre de Fibonacci ?

5. Une solution de programmation dynamique fonctionne plus lentement que prévu. Quelle pourrait en être la raison ?

6. Quel est l’objectif principal de l’algorithme de Dijkstra dans la théorie des graphes ?

7. En théorie des graphes, qu’est-ce qu’une composante fortement connectée ?

8. Qu’accomplit l’algorithme de Bellman-Ford ?

9. Quelle est la principale différence entre les algorithmes de Prim et de Kruskal ?

10. Pourquoi les tris topologiques sont-ils importants dans les algorithmes de graphes ?

Vous pourrez aussi aimer

QCM Algorithmes, structures de données et complexité – Partie 6

QCM Algorithmes – Notions de base – Partie 2

QCM Algorithmes, structures de données et complexité – Partie 11

Laisser un commentaire Annuler la réponse