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 qu'un algorithme de force brute ?

  1. AUn algorithme qui essaie toutes les solutions candidates possibles
  2. BUn algorithme qui s'exécute sur de nombreux processeurs
  3. CUn algorithme qui utilise toujours la récursion
  4. DUn algorithme qui devine une réponse au hasard
2.Facile

Que vaut log₂ 1024 ?

  1. A10
  2. B32
  3. C512
  4. D12
3.Facile

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

  1. ATrier, chercher, renvoyer
  2. BLire, calculer, écrire
  3. CDeviner, vérifier, recommencer
  4. DDiviser, régner, combiner
4.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(V × E)
  3. CO(E log V)
  4. DO(V³ × E)
5.Moyen

La complexité temporelle de la version récursive naïve de Fibonacci (fib(n) = fib(n−1) + fib(n−2)) est :

  1. ALinéaire
  2. BExponentielle
  3. CConstante
  4. DLogarithmique
6.Moyen

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

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

Comment l'algorithme de Bellman-Ford détecte-t-il un cycle de poids négatif accessible depuis la source ?

  1. AIl exécute deux fois l'algorithme de Dijkstra et compare les deux résultats de distances
  2. BAprès V − 1 tours, il vérifie si une arête peut encore être relâchée
  3. CIl vérifie si une arête a un poids négatif
  4. DIl compte les cycles par un parcours en profondeur
8.Difficile

Quelles sont les deux choses à montrer pour prouver qu'un problème de décision X est NP-complet ?

  1. AX est dans P, et X se réduit à SAT
  2. BX est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial
  3. CX n'a pas d'algorithme polynomial, et X est décidable
  4. DX se réduit à un problème de P, et X est dans NP

Corrigé

  1. 1. A · Un algorithme qui essaie toutes les solutions candidates possibles
  2. 2. A · 10
  3. 3. D · Diviser, régner, combiner
  4. 4. B · O(V × E)
  5. 5. B · Exponentielle
  6. 6. A · O(n)
  7. 7. B · Après V − 1 tours, il vérifie si une arête peut encore être relâchée
  8. 8. B · X est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial

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