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'exige la recherche dichotomique de son entrée ?

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

Un algorithme en O(n²) prend 1 seconde pour n = 1000. Combien de temps prend-il environ pour n = 2000 ?

  1. A1 seconde
  2. B8 secondes
  3. C4 secondes
  4. D2 secondes
3.Facile

La complexité spatiale mesure :

  1. ALa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  2. BLa taille physique de l'ordinateur
  3. CLe nombre de lignes de code
  4. DL'espace disque du fichier du programme une fois compilé
4.Moyen

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

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

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

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

Que mesure l'analyse amortie ?

  1. ALe coût d'un algorithme sur la meilleure entrée
  2. BLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
  3. CLe coût moyen par opération sur une suite d'opérations de pire cas
  4. DLe coût espéré sur des entrées aléatoires
7.Difficile

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

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

Que se passerait-il si quelqu'un trouvait un algorithme en temps polynomial pour un problème NP-complet ?

  1. ASeul ce problème passerait dans P
  2. BLe problème de l'arrêt deviendrait décidable
  3. CTous les algorithmes en temps exponentiel s'exécuteraient immédiatement en temps linéaire
  4. DTout problème de NP pourrait être résolu en temps polynomial, donc P = NP

Corrigé

  1. 1. D · Le tableau doit être trié
  2. 2. C · 4 secondes
  3. 3. A · La quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  4. 4. C · O(n²)
  5. 5. B · O(2ⁿ)
  6. 6. C · Le coût moyen par opération sur une suite d'opérations de pire cas
  7. 7. A · O(n log n)
  8. 8. D · Tout problème de NP pourrait être résolu en temps polynomial, donc P = NP

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