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

Quelle est la complexité temporelle du tri fusion dans le pire cas ?

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

Qu'exige la recherche dichotomique de son entrée ?

  1. ALe tableau ne doit pas avoir plus de 1000 éléments
  2. BLe tableau doit être trié
  3. CLa longueur du tableau doit être une puissance de deux
  4. DLe tableau ne doit contenir que des nombres positifs
3.Facile

Quelle est la complexité temporelle du parcours en profondeur d'un graphe stocké sous forme de listes d'adjacence ?

  1. AO(V × E)
  2. BO(V²)
  3. CO(V + E)
  4. DO(E log V)
4.Moyen

La programmation dynamique est utile lorsqu'un problème présente :

  1. AAucun sous-problème, de sorte qu'il peut être résolu en une seule étape
  2. BUne seule boucle
  3. CDes sous-problèmes qui se chevauchent et une sous-structure optimale
  4. DUniquement des entrées aléatoires
5.Moyen

Quelle est la solution de la récurrence T(n) = 2T(n/2) + O(1) ?

  1. AO(n log n)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
6.Moyen

Quelle est la solution de la récurrence T(n) = T(n − 1) + O(n) ?

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

Prendre les deux extrémités de chaque arête d'un couplage maximal donne une couverture par sommets. Quelle est la qualité de cette couverture ?

  1. ADe qualité inconnue par rapport à l'optimum
  2. BAu plus deux fois la taille d'une couverture par sommets minimale
  3. CToujours une couverture par sommets minimale
  4. DAu plus log n fois le minimum
8.Difficile

La multiplication de Karatsuba vérifie T(n) = 3T(n/2) + O(n). Quelle en est la solution ?

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(n3)
  4. DΘ(nlog₂ 3), soit environ n1,585

Corrigé

  1. 1. B · O(n log n)
  2. 2. B · Le tableau doit être trié
  3. 3. C · O(V + E)
  4. 4. C · Des sous-problèmes qui se chevauchent et une sous-structure optimale
  5. 5. C · O(n)
  6. 6. A · O(n²)
  7. 7. B · Au plus deux fois la taille d'une couverture par sommets minimale
  8. 8. D · Θ(nlog₂ 3), soit environ n1,585

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