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

Que vaut log₂ 1024 ?

  1. A12
  2. B512
  3. C10
  4. D32
2.Facile

Qu'est-ce qu'un algorithme ?

  1. AUne structure de données qui stocke des nombres
  2. BTout programme informatique doté d'une interface graphique
  3. CUn langage de programmation conçu pour écrire des formules mathématiques
  4. DUne suite finie d'étapes bien définies qui résout un problème
3.Facile

Quelle est la complexité temporelle de la recherche linéaire dans un tableau non trié de n éléments (pire cas) ?

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

Quelle est la complexité temporelle de : pour i = 1 à n : pour j = 1 à i : faire un travail O(1) ?

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

Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

  1. AO(n²)
  2. BO(n)
  3. CO(log n)
  4. DO(2ⁿ)
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

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

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

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

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

Corrigé

  1. 1. C · 10
  2. 2. D · Une suite finie d'étapes bien définies qui résout un problème
  3. 3. A · O(n)
  4. 4. B · O(n²)
  5. 5. B · O(n)
  6. 6. B · O(n log n)
  7. 7. C · X est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial
  8. 8. D · Θ(n log² n)

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