Fiche d’exercices de Algorithmes et complexité avec corrigé

Fiche d’exercices de Algorithmes et complexité gratuite et imprimable : 8 exercices, du niveau facile au niveau examen, avec corrigé. Imprimez-la ou enregistrez-la en PDF.

Nouvelle ficheS’entraîner en ligne avec indices

Pour les enseignants : gratuite à imprimer, copier et utiliser en classe. Chaque nouvelle fiche a de nouvelles valeurs et son propre corrigé. Un lien vers ExamProblems sur la page de votre cours est apprécié.

Nom: ____________________   Date: ____________

1.Facile

Qu'est-ce que le cas de base d'une fonction récursive ?

  1. ALe cas avec l'entrée la plus grande, traité avant tout appel récursif
  2. BUn cas traité directement, sans nouvel appel récursif
  3. CL'appel qui utilise le plus de mémoire
  4. DLa première ligne de la fonction
2.Facile

Un algorithme en O(n) prend 3 secondes pour n = 1 million. Combien de temps prend-il environ pour n = 2 millions ?

  1. A3 secondes
  2. B12 secondes
  3. C9 secondes
  4. D6 secondes
3.Facile

Qu'est-ce que la mémoïsation ?

  1. AÉcrire des commentaires à côté de chaque ligne de code
  2. BConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
  3. CLibérer la mémoire après le retour d'une fonction
  4. DStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
4.Moyen

Avec des pièces de 1, 3 et 4 et un montant de 6, combien de pièces utilise la méthode gloutonne « la plus grosse pièce d'abord », comparée à l'optimum ?

  1. ALe glouton utilise 3 pièces ; l'optimum est 3
  2. BLe glouton utilise 3 pièces ; l'optimum est 2
  3. CLe glouton utilise 2 pièces ; l'optimum est 2
  4. DLe glouton utilise 4 pièces ; l'optimum est 3
5.Moyen

Que signifie qu'un problème possède une sous-structure optimale ?

  1. ATous les sous-problèmes ont la même taille
  2. BLe problème a exactement une solution optimale, que partagent tous les sous-problèmes
  3. CUne solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
  4. DLe problème peut être résolu en temps constant
6.Moyen

La récurrence T(n) = 2T(n/2) + O(n) a pour solution :

  1. AO(log n)
  2. BO(n log n)
  3. CO(n)
  4. DO(n²)
7.Difficile

Pourquoi toute recherche par comparaisons dans un tableau trié nécessite-t-elle Ω(log n) comparaisons dans le pire cas ?

  1. ALa recherche dichotomique est le seul algorithme possible, et elle nécessite log₂ n comparaisons
  2. BUn arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n
  3. CChaque élément doit être comparé au moins une fois
  4. DChaque comparaison prend un temps logarithmique
8.Difficile

L'algorithme de programmation dynamique de Held-Karp résout exactement le problème du voyageur de commerce. Quel est son temps d'exécution pour n villes ?

  1. AO(n!)
  2. BO(2n²)
  3. CO(n² 2ⁿ)
  4. DO(n³)

Corrigé

  1. 1. B · Un cas traité directement, sans nouvel appel récursif
  2. 2. D · 6 secondes
  3. 3. D · Stocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  4. 4. B · Le glouton utilise 3 pièces ; l'optimum est 2
  5. 5. C · Une solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
  6. 6. B · O(n log n)
  7. 7. B · Un arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n
  8. 8. C · O(n² 2ⁿ)

Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.