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

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. Quel algorithme est utilisé pour trouver les composantes fortement connectées dans un graphe orienté ?

A L’algorithme de Dijkstra

B Algorithme de Bellman-Ford

C Algorithme de Kosaraju

D Algorithme de Floyd-Warshall

L’algorithme de Kosaraju est spécifiquement conçu pour trouver des composantes fortement connectées dans un graphe orienté. Il implique deux passages de recherche en profondeur (DFS): l’un sur le graphe et l’autre sur la transposition du graphe, afin d’identifier efficacement toutes les composantes fortement connectées.

2. Comment le problème du plus court chemin entre toute paire de sommets (x,y) est-il résolu dans un graphe sans cycles négatifs ?

A En utilisant l’algorithme de Dijkstra de manière répétée pour chaque sommet

B En utilisant l’algorithme de Bellman-Ford de façon répétée pour chaque sommet

C Utilisation de l’algorithme de Floyd-Warshall

D Utilisation de l’algorithme de Prim

L’algorithme de Floyd-Warshall est idéal pour résoudre le problème du plus court chemin entre toutes les paires dans les graphes, y compris ceux qui ont des poids négatifs mais pas de cycles négatifs. Il compare systématiquement tous les chemins à travers le graphe pour trouver les chemins les plus courts entre toutes les paires de sommets, en utilisant une approche de programmation dynamique.

3. Dans un graphe, comment déterminer si l’ajout d’une arête crée un cycle ?

A En effectuant un tri topologique

B En vérifiant si l’arête relie les sommets d’une même composante fortement connectée

C En utilisant une structure de données appelée union-find

D En calculant le diamètre du graphe

Pour déterminer si l’ajout d’une arête risque de créer un cycle dans un graphe, il est possible d’utiliser une structure de données appelée union-find (également connue sous le nom d’ensemble disjoint). Avant d’ajouter l’arête, vous vérifiez si les deux sommets qu’elle relierait se trouvent déjà dans le même ensemble (ce qui indique qu’ils sont connectés). Si c’est le cas, l’ajout de l’arête créera un cycle ; si ce n’est pas le cas, il n’en créera pas.

4. L’implémentation de l’algorithme de Dijkstra d’un graphe renvoie des valeurs de plus court chemin incorrectes. Quelle pourrait en être la raison ?

A Le graphe contient des poids d’arête négatifs

B La file d’attente des priorités n’est pas mise à jour correctement

C L’algorithme s’arrête trop tôt

D Le graphe n’est pas fortement connecté

L’algorithme de Dijkstra suppose que tous les poids des arêtes sont non négatifs. Si le graphe contient des poids d’arête négatifs, l’algorithme de Dijkstra peut renvoyer des valeurs de plus court chemin incorrectes parce qu’il ne peut pas gérer correctement la possibilité qu’un chemin devienne plus court en traversant une arête de poids négatif. Bellman-Ford ou Floyd-Warshall peuvent être des alternatives pour les graphes avec des poids négatifs.

5. Qu’est-ce qui peut amener l’algorithme de Floyd-Warshall à donner des résultats incorrects pour les plus courts chemins ?

A L’initialisation de la matrice des distances n’est pas correcte

B Ne pas itérer sur toutes les paires de sommets

C Traitement incorrect des cycles négatifs

D Toutes les réponses ci-dessus

Une initialisation incorrecte de la matrice de distance dans l’algorithme de Floyd-Warshall peut conduire à des résultats erronés. La matrice doit représenter correctement les distances entre toutes les paires de sommets au départ, notamment en fixant à zéro la distance d’un sommet à lui-même et en tenant compte des poids directs des arêtes entre les sommets. Toute erreur dans cette configuration peut affecter l’ensemble du calcul.

6. Quelle est la caractéristique d’un tas binaire ?

A Un arbre binaire entièrement rempli, à l’exception éventuellement du niveau inférieur, qui est rempli de gauche à droite.

B Un arbre binaire dans lequel chaque nœud a une valeur supérieure ou égale à celle de ses enfants

C Un arbre binaire où chaque nœud a une valeur inférieure ou égale à ses enfants

D Les deux A et B

Un tas binaire est un arbre binaire complet où chaque nœud a une valeur supérieure ou égale à ses enfants (tas max) ou inférieure ou égale à ses enfants (tas min). Cette structure permet d’extraire et d’insérer efficacement des éléments, la racine étant toujours la valeur minimale ou maximale.

7. Quel est l’avantage principal de l’utilisation d’un tas de Fibonacci par rapport à un tas binaire ?

A Une opération de fusion plus rapide

B Meilleure complexité de l’espace

C Insertion à temps fixe

D Les deux A et C

Le principal avantage de l’utilisation d’un tas de Fibonacci par rapport à un tas binaire est la rapidité de l’opération de fusion. Les tas de Fibonacci sont particulièrement adaptés aux algorithmes tels que le chemin le plus court de Dijkstra, où de nombreuses opérations de fusion sont effectuées, car ils peuvent fusionner deux tas en un temps constant amorti, contrairement aux tas binaires qui nécessitent un temps linéaire en fonction de la taille des tas.

8. Quelle structure de données est la plus efficace pour implémenter une file d’attente prioritaire ?

A L’arbre de recherche binaire

B Table de hachage

C Tas binaire

D Liste chaînée

Un tas binaire est le plus efficace pour implémenter une file d’attente prioritaire en raison de sa capacité à insérer rapidement des éléments et à retirer l’élément ayant la priorité la plus élevée (ou la plus faible). Sa structure garantit que ces opérations peuvent être effectuées en temps logarithmique, ce qui le rend idéal pour l’implémentation d’une file d’attente prioritaire.

9. À quoi sert principalement la technique « diviser pour régner » ?

A Simplifier un problème en le divisant en parties plus petites et plus faciles à gérer

B Accroître l’efficacité des algorithmes de tri

C Optimiser les fonctions récursives

D Équilibrer les arbres de recherche binaires

La technique « diviser pour régner » est utilisée pour simplifier un problème en le divisant en parties plus petites et plus faciles à gérer. Cette approche consiste à résoudre chaque partie indépendamment, puis à combiner les solutions pour résoudre le problème d’origine. Elle est largement utilisée dans des algorithmes tels que le tri par fusion et le tri rapide.

10. Dans le contexte de la conception d’algorithmes, qu’est-ce que le retour sur trace ou backtracking?

A Une technique pour trouver le chemin le plus court dans un graphe

B Un moyen d’économiser de la mémoire en supprimant les données inutiles

C Une méthode récursive pour résoudre des problèmes combinatoires en essayant de construire une solution de manière incrémentale

D Une méthode de compression des données

Le retour en arrière est une méthode récursive et systématique pour résoudre des problèmes en essayant de construire une solution de manière incrémentale et en éliminant les solutions qui ne satisfont pas les contraintes du problème à un moment donné. Cette méthode est souvent utilisée dans les énigmes, comme la résolution de labyrinthes ou de problèmes à n reines.

11. Qu’est-ce qui distingue la programmation dynamique de l’approche « diviser pour régner » ?

A La programmation dynamique exige que le problème comporte des sous-problèmes qui se chevauchent, ce qui n’est pas le cas de l’approche « diviser pour régner ».

B La programmation dynamique n’utilise que la récursivité, contrairement à l’approche « diviser pour régner ».

C La programmation dynamique n’est utilisée que pour les problèmes d’optimisation

D Les algorithmes « diviser pour régner » ne sont pas applicables aux problèmes ayant une sous-structure optimale.

La principale différence entre la programmation dynamique et la méthode « diviser pour régner » est que la programmation dynamique est utilisée lorsque le problème comporte des sous-problèmes qui se chevauchent, qu’elle ne résout qu’une seule fois et dont elle stocke les solutions en vue d’une utilisation ultérieure, ce qui réduit considérablement le temps de calcul par rapport à une nouvelle résolution des sous-problèmes.

12. Quelle est l’idée principale des algorithmes d’approximation ?

A Fournir la solution exacte à des problèmes NP-difficiles

B Fournir des solutions proches de la meilleure réponse possible pour les problèmes NP-difficiles

C Réduire la complexité temporelle des algorithmes à un temps polynomial

D Convertir les problèmes NP-difficiles en problèmes P

Les algorithmes d’approximation sont conçus pour fournir des solutions proches de la meilleure réponse possible à des problèmes NP difficiles pour lesquels la recherche d’une solution exacte n’est pas réalisable en raison de la complexité du temps. Ces algorithmes sont essentiels pour traiter les problèmes complexes pour lesquels une solution approximative est suffisante.

13. Pourquoi les algorithmes randomisés sont-ils utilisés en informatique ?

A Pour garantir la meilleure solution aux problèmes

B Pour fournir une complexité temporelle déterministe pour un problème donné

C Améliorer la performance moyenne des algorithmes en introduisant des éléments aléatoires

D Simplifier la mise en œuvre des algorithmes

Les algorithmes randomisés utilisent l’aléatoire dans leur logique pour améliorer la performance moyenne, offrant une meilleure performance pour certains problèmes par rapport aux algorithmes déterministes. Ils sont particulièrement utiles dans les scénarios où l’entrée peut être le pire des cas pour les algorithmes déterministes ou lorsque le comportement de l’algorithme ne doit pas être facilement prévisible.

14. Comment implémenter un algorithme de backtracking de base pour résoudre le probléme de N-reines ?

A En plaçant les reines une par une dans des rangées différentes et en vérifiant les conflits à chaque étape.

B En plaçant des reines au hasard sur le plateau et en les réarrangeant pour résoudre les conflits

C En utilisant un algorithme gourmand pour placer toutes les reines simultanément

D En calculant les positions exactes de toutes les reines avant de les placer

L’implémentation d’un algorithme de backtracking de base pour le problème des N-reines implique de placer les reines une par une dans différentes rangées et d’utiliser une approche systématique pour vérifier l’absence de conflits (par exemple, si les reines s’attaquent les unes les autres) à chaque étape. Si un conflit est détecté, l’algorithme revient en arrière et essaie une autre position, en continuant ce processus jusqu’à ce que toutes les reines soient placées en toute sécurité.

15. Quelle technique est couramment utilisée en programmation dynamique pour optimiser les algorithmes récursifs ?

A Mémorisation

B La randomisation

C Backtracking

D Recherche linéaire

La Mémorisation est une technique utilisée en programmation dynamique pour optimiser les algorithmes récursifs en stockant les résultats des appels de fonction coûteux et en réutilisant ces résultats lorsque les mêmes entrées se reproduisent, ce qui évite de répéter les mêmes calculs et réduit considérablement la complexité temporelle.

16. Pourquoi une solution de programmation dynamique peut-elle donner de mauvais résultats sur un problème dont l’espace d’états est large ?

A Les appels récursifs sont trop profonds

B La table de mémorisation consomme trop de mémoire

C Il n’y a pas assez de sous-problèmes

D Le problème ne présente pas de sous-problèmes qui se chevauchent

Une solution de programmation dynamique peut donner de mauvais résultats sur des problèmes ayant un grand espace d’états, principalement parce que la table de mémorisation (utilisée pour stocker les solutions aux sous-problèmes) consomme trop de mémoire. Ce problème peut nécessiter l’optimisation de l’approche de stockage, par exemple en utilisant des structures de données moins encombrantes ou en supprimant les états inutiles.

17. En optimisant un algorithme récursif à l’aide de la mémorisation, un programmeur constate que le programme manque de mémoire. Quelle est la solution possible ?

A Augmenter la mémoire disponible

B Convertir la récursion en forme itérative pour utiliser moins de mémoire

C Réduire la taille du problème

D Utiliser une stratégie de mémorisation plus efficace

La conversion d’un algorithme récursif en une forme itérative peut permettre d’utiliser moins de mémoire, en particulier lorsqu’il s’agit d’une récursion profonde qui entraîne une utilisation élevée de la mémoire. Cette approche, souvent combinée à une technique de programmation dynamique ascendante, peut réduire de manière significative l’empreinte mémoire en évitant la surcharge associée aux appels récursifs et aux piles d’appels potentiellement importantes.

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

QCMs qui pourraient vous intéresser :

1. Quel algorithme est utilisé pour trouver les composantes fortement connectées dans un graphe orienté ?

2. Comment le problème du plus court chemin entre toute paire de sommets (x,y) est-il résolu dans un graphe sans cycles négatifs ?

3. Dans un graphe, comment déterminer si l’ajout d’une arête crée un cycle ?

4. L’implémentation de l’algorithme de Dijkstra d’un graphe renvoie des valeurs de plus court chemin incorrectes. Quelle pourrait en être la raison ?

5. Qu’est-ce qui peut amener l’algorithme de Floyd-Warshall à donner des résultats incorrects pour les plus courts chemins ?

6. Quelle est la caractéristique d’un tas binaire ?

7. Quel est l’avantage principal de l’utilisation d’un tas de Fibonacci par rapport à un tas binaire ?

8. Quelle structure de données est la plus efficace pour implémenter une file d’attente prioritaire ?

9. À quoi sert principalement la technique « diviser pour régner » ?

10. Dans le contexte de la conception d’algorithmes, qu’est-ce que le retour sur trace ou backtracking?

11. Qu’est-ce qui distingue la programmation dynamique de l’approche « diviser pour régner » ?

12. Quelle est l’idée principale des algorithmes d’approximation ?

13. Pourquoi les algorithmes randomisés sont-ils utilisés en informatique ?

14. Comment implémenter un algorithme de backtracking de base pour résoudre le probléme de N-reines ?

15. Quelle technique est couramment utilisée en programmation dynamique pour optimiser les algorithmes récursifs ?

16. Pourquoi une solution de programmation dynamique peut-elle donner de mauvais résultats sur un problème dont l’espace d’états est large ?

17. En optimisant un algorithme récursif à l’aide de la mémorisation, un programmeur constate que le programme manque de mémoire. Quelle est la solution possible ?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse