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

Lequel de ces temps d'exécution est polynomial ?

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

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

  1. AEnviron log₂ n
  2. BEnviron n / 2
  3. CEnviron n
  4. DEnviron n²
3.Facile

Quelle stratégie de conception utilise le tri fusion ?

  1. ADiviser pour régner
  2. BLe choix glouton
  3. CLa programmation dynamique
  4. DLa force brute
4.Moyen

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

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

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

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

Quelle est la complexité temporelle de l'algorithme de Bellman-Ford sur un graphe à V sommets et E arêtes ?

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V³ × E)
7.Difficile

Quelle technique donne au tri rapide un temps d'exécution espéré en O(n log n) pour toute entrée ?

  1. AChoisir le pivot uniformément au hasard
  2. BN'utiliser la récursivité que sur la partie gauche
  3. CToujours choisir le premier élément
  4. DTrier l'entrée avant d'exécuter le tri rapide
8.Difficile

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

  1. AΘ(n log n)
  2. BΘ(n)
  3. CΘ(n log² n)
  4. DΘ(n²)

Corrigé

  1. 1. C · O(n³)
  2. 2. A · Environ log₂ n
  3. 3. A · Diviser pour régner
  4. 4. A · O(n²)
  5. 5. C · O(2ⁿ)
  6. 6. C · O(V × E)
  7. 7. A · Choisir le pivot uniformément au hasard
  8. 8. C · Θ(n log² n)

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