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 notation décrit une borne inférieure de croissance ?

  1. AΩ (grand Oméga)
  2. Bo (petit o)
  3. CO (grand O)
  4. DΘ (grand Thêta)
2.Facile

Que vaut log₂ 1024 ?

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

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

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

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

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

Que mesure l'analyse amortie ?

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

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

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

Quelle est la différence entre un problème indécidable et un problème intraitable ?

  1. ALes problèmes intraitables ne peuvent être résolus par aucun algorithme, tandis que les indécidables demandent seulement un temps exponentiel
  2. BLes deux signifient que le problème n'a aucun algorithme
  3. CLes problèmes indécidables sont dans NP, tandis que les problèmes intraitables sont dans P
  4. DUn problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent
8.Difficile

Qu'a établi le théorème de Cook-Levin ?

  1. ALe problème de l'arrêt est indécidable
  2. BTout problème NP peut être résolu en temps exponentiel
  3. CLe problème de satisfiabilité booléenne (SAT) est NP-complet
  4. DP est différent de NP

Corrigé

  1. 1. A · Ω (grand Oméga)
  2. 2. A · 10
  3. 3. C · O(n)
  4. 4. A · O(d(n + k))
  5. 5. D · Le coût moyen par opération sur une suite d'opérations de pire cas
  6. 6. B · O(n)
  7. 7. D · Un problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent
  8. 8. C · Le problème de satisfiabilité booléenne (SAT) est NP-complet

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